Thuật toán tối ưu thời gian cho mô hình cộng tác giữa xe tải và nhiều Drones

THUẬT TOÁN TỐI ƯU THỜI GIAN CHO MÔ HÌNH CỘNG TÁC GIỮA XE TẢI VÀ NHIỀU DRONES Student: Phạm Duy Anh – 20183481 Nguyễn Hữu Kiệt – 20183571 GVHD: Huỳnh Thị Thanh Bình Sử dụng giải thuật MFEA với mã hóa số thực Min Lin, Jun-Yan Lyu, Jia-Jing Gao, and Ling-Yu Li Tạp chí Hindawa 2020 Nội dung Tổng quan bài toán Đặt vấn đề Phương pháp giải quyết Kết quả thực nghiệm Các kết luận 2 3 Tổng quan Tổng quan Hệ thống phân phối cộng tác gồm nhiều drone và 1 xe tải, ở đó xe tải phân phối hàng hóa tới cho một nhóm các khách hàng theo một đường đi khép kín với sự trợ giúp của một số drones. Mỗi chuyến hành trình của xe tải xuất phát từ một trung tâm phân phối, cung ứng hàng hóa cho các khách hàng và trở lại sau khi đã hoàn thành tất cả nhiệm vụ. 4 5 Các nghiên cứu liên quan Murray và Raj đề xuất phương pháp mới cho bài toán “flying sidekick traveling salesman problem”, ở đó một xe tải làm việc với nhiều thiết bị không người lái (drones, or UAVs) để vận chuyển hàng hóa. Các tác giả mô tả bài toán như một chương trình tuyến tính hỗn hợp nguyên (MILP) và đề xuất giải pháp heuristic sử dụng ba chuỗi bài toán con. Thực nghiệm cho thấy hiệu quả giải quyết các mô hình thực tế trong thời gian hợp lý. [1] C. C. Murray and R. Raj, “The multiple flying sidekicks traveling salesman problem: parcel delivery with multiple drones,”  Transportation Research Part C: Emerging Technologies , vol. 110, pp. 368–398, 2020. 6 Mô hình này chỉ ra sự hạn chế của xe tải trong mạng lưới đường phố, trong khi các drones có sẵn để giao hàng (nhưng hạn chế về sức chứa và phạm vi bay), mục tiêu giảm thiểu thời gian phân phối. Không giống nhiều bài báo khác, mô hình không chỉ cho phép một drone mang nhiều gói hàng không đồng nhất mà khối lượng này có ảnh hưởng đến năng lượng tiêu thụ của nó. Các tác giả kết hợp công nghệ sắp topo và đề xuất một số thuật toán phân phối nhiệm vụ. Các thí nghiệm tính toán và phân tích độ nhạy cùng được thực hiện bằng cách sử dụng các thông số vật lý cho drones. Các nghiên cứu liên quan S. Poikonen and B. Golden, “Multi-visit drone routing problem,” Computers & Operations Research, vol. 113, Article ID 104802, 2020 [2] 7 Các nghiên cứu liên quan [3] Q. M. Ha, Y. Deville, Q. D. Pham, and M. H. Ha, “A hybrid genetic algorithm for the traveling salesman problem with drone,” Journal of Heuristics, vol. 26, no. 2, pp. 219–247, 2019 Bài báo này giải quyết vấn đề Người bán hàng đi du lịch với Drone (TSP-D) và đề xuất thuật toán lai giữa giải thuật di truyền với quản lý dân số động và kiểm soát đa dạng thích ứng dựa trên thuật toán phân tách. Đặt vấn đề Hệ thống cộng tác giữa xe tải và các drone được thể hiện trên mạng lưới đường giao thông đô thị. Mạng lưới này được thể hiện bởi đồ thị G = (V, E) , ở đó V là tập các nút giao thông đường bộ và E là tập hợp các đoạn đường. Tập hợp V gồm n + 1 số nguyên là 0, 1, 2, , n – 1, n trong đó số 0 đại diện cho trung tâm phân phối. Tọa độ của nút giao u được ký hiệu: Một đường đi từ nút giao u tới nút giao v được cho bởi: 8 9 10 11 Các biến quyết định biến nhị phân kiểm tra xem có tồn tại đường đi (u,v) trong chu trình biến nhị phân bằng 1 nếu Khách hàng được Drone k phục vụ , lần lượt là điểm cất cánh và hạ cánh của Drone phục vụ cho Khách hàng 12 là quãng đường xe tải đi từ trung tâm phân phối tới điểm cất cánh là quãng đường xe tải đi từ trung tâm phân phối tới điểm hạ cánh Quãng đường drone đi để vận chuyển hàng đến khách hàng là biến nhị phân biểu diễn điểm cất cánh có thuộc cạnh hay không là số thực biểu diễn tỉ lệ giữa khoảng cách và khoảng cách là biến nhị phân biểu diễn điểm hạ cánh có thuộc cạnh hay không là số thực biểu diễn tỉ lệ giữa khoảng cách và khoảng cách 13 Các giả thiết Chỉ có 1 xe tải và được trang bị một số lượng drones cố định Mỗi điểm phục vụ khách hàng chỉ được phục vụ bởi một drone Tất cả drone đều có cùng tốc độ Mỗi drone chỉ có thể vận chuyển một món hàng trong mỗi lần Xe tải không thể giao hàng Drones có thể hạ cạnh hay cất cánh mà không phục thuộc vào trạng thái của xe tải Số lượng drones là cố định và tải trọng của xe tải là tổng của kiện hàng trên các drone, có nghĩa là khối lượng drones coi như không đáng kể 14 Hàm mục tiêu Mô hình toán học 15 16 Hybrid Genetic Algorithm Mức trên (GA): Xác định chu trình tốt nhất Mức dưới: Với mỗi chu trình tìm được, xác định điểm cất cánh và hạ cánh tốt nhất cho mỗi drone Giải thuật 17 Mức trên 1. Mã hóa và giải mã: mã hóa nhị phân 3. Khởi tạo quần thể: Mỗi gene được tạo ngẫu nhiên trong phạm vi cho trước, cho tới khi đạt được đủ số lượng cá thể thì dừng lại 2. Tính độ thích nghi: tính dựa vào mức dưới 4. Chọn lọc cá thể ưu thế: Sao chép một lượng cá thể nhất định vào thể hệ kế tiếp dựa vào bánh xe roulette. Việc chọn những cá thể tốt nhất tùy thuộc vào xác suất nhất định. 5. Lai ghép: chọn 2 cha mẹ ngẫu nhiên từ thế hệ trước, chọn một điểm cắt ngẫu nhiên và trao đổi chéo 6. Đột biến: chọn ngẫu nhiên các điểm đột biến trên NST, và tạo ngẫu nhiên một giá trị mới cho các gene tại các điểm đột biến này 7. Tái sinh: sản xuất các cá thể trong quần thể mới theo ba hướng: (1) lai ghép; (2) đột biến; (3) chọn 10% cá thể tốt nhất từ quần thể ban đầu 8. Điều kiện dừng: Nếu số lượng thế hệ đạt tới mức tối đa được chỉ định, dừng thuật toán và đưa ra lời giải tối ưu, nếu không quay lại Bước 4 và thực hiện các thao tác ở trên 18 Mức dưới 2. Xác định cho mỗi drone: Xác định trước điểm hạ cánh để drone và xe tải sẽ gặp nhau vào cùng thời điểm 1. Xác định thứ tự các điểm khách hàng cần giao: với mỗi điểm khách hàng , xác định trên chu trình mà gần nhất. Nếu sớm hơn thì điểm khách hàng được xếp trước Giả sử rằng đối xứng nhau qua đường nối , ta có thể xấp xỉ công thức trên (hai đường trên coi như vuông góc) : 19 Mức dưới 3. Tính toán : với mỗi drone k, chọn điểm khách hàng chưa được duyệt theo thứ tự đã sắp xếp. Xét nếu khách hàng thứ được drone phục vụ. Nếu điểm ở trước thì đặt và chuyển sang duyệt điểm khách hàng thứ 20 Giải thuật đề xuất Heuristic Multi-Factorial Evolutionary Algorithm with Real Number Encoding Mức trên (MFEA): Mã hóa các cá thể dưới dạng số thực để tìm danh sách cạnh cho chu trình của xe tải Mức dưới: Tính factorial_cost thông qua thuật toán heuristic. Dựa vào chu trình của xe tải, tương ứng với mỗi điểm khách hàng, tìm kiếm điểm cất cánh và hạ cánh cho drone sao cho hiệu thời gian là không quá lớn. 22 Mức trên 1. Mã hóa và giải mã: mã hóa số thực 0.12 0.31 0.90 0.17 0.01 0.57 0.68 0.86 0.77 Mỗi cá thể được mã hóa dưới dạng một chuỗi số thực với chiều dài đúng bằng số lượng đỉnh của đồ thị Giá trị của mỗi NST tương ứng với thứ tự cạnh kế tiếp, bắt đầu từ đỉnh 0 (tương ứng với trung tâm phân phối) 23 Mức trên 1. Mã hóa và giải mã: mã hóa số thực 0.12 0.31 0.90 0.17 0.01 0.57 0.68 0.86 0.77 Mỗi cá thể được mã hóa dưới dạng một chuỗi số thực với chiều dài đúng bằng số lượng đỉnh của đồ thị Giá trị của mỗi NST tương ứng với thứ tự cạnh kế tiếp, bắt đầu từ đỉnh 0 (tương ứng với trung tâm phân phối) 0 1 2 3 0 8 12 13 17 0.12 * 4 = 0.48 => 0 24 Mức trên 1. Mã hóa và giải mã: mã hóa số thực 0.12 0.31 0.90 0.17 0.01 0.57 0.68 0.86 0.77 Mỗi cá thể được mã hóa dưới dạng một chuỗi số thực với chiều dài đúng bằng số lượng đỉnh của đồ thị Giá trị của mỗi NST tương ứng với thứ tự cạnh kế tiếp, bắt đầu từ đỉnh 0 (tương ứng với trung tâm phân phối) 0 1 2 3 8 3 7 9 0.34 * 3 = 1.02 => 1 25 Mức trên 1. Mã hóa và giải mã: mã hóa số thực 0.12 0.31 0.90 0.17 0.01 0.57 0.68 0.86 0.77 Mỗi cá thể được mã hóa dưới dạng một chuỗi số thực với chiều dài đúng bằng số lượng đỉnh của đồ thị Giá trị của mỗi NST tương ứng với thứ tự cạnh kế tiếp, bắt đầu từ đỉnh 0 (tương ứng với trung tâm phân phối) 0 1 2 3 7 2 6 12 0.90 * 3 = 2.7 => 2 26 Mức trên 1. Mã hóa và giải mã: mã hóa số thực 0.12 0.31 0.90 0.17 0.01 0.57 0.68 0.86 0.77 Mỗi cá thể được mã hóa dưới dạng một chuỗi số thực với chiều dài đúng bằng số lượng đỉnh của đồ thị Giá trị của mỗi NST tương ứng với thứ tự cạnh kế tiếp, bắt đầu từ đỉnh 0 (tương ứng với trung tâm phân phối) 0 1 2 3 12 0 16 11 0.17 * 3 = 0.51 => 0 Mức trên 27 Mức dưới 2. Xác định cho mỗi drone: Xác định trước điểm hạ cánh để drone và xe tải xe gặp nhau vào cùng thời điểm 1. Xác định thứ tự các điểm khách hàng cần giao: với mỗi điểm khách hàng , xác định trên chu trình mà gần nhất. Nếu sớm hơn thì điểm khách hàng được xếp trước Giả sử rằng đối xứng nhau qua đường nối , ta có thể xấp xỉ công thức trên (hai đường trên coi như vuông góc) : 28 29 u v w Từ đó xác định và là giao điểm của các đường thẳng tạo với một góc và các cạnh thuộc chu trình Mức dưới Mức dưới 3. Tính toán : với mỗi drone k, chọn điểm khách hàng chưa được duyệt theo thứ tự đã sắp xếp. Xét nếu khách hàng thứ được drone phục vụ. Nếu điểm ở trước thì đặt và chuyển sang duyệt điểm khách hàng thứ 30 31 Kết quả Tập dữ liệu tự sinh gồm 3 loại đồ thị: 100, 400, 900 đỉnh và số lượng khách hàng lần lượt là 20, 60, 100. 32 33 34 35 Kết luận Giải thuật đề xuất sử dụng MFEA với mã hóa số thực đã khắc phục được một số nhược điểm của giải thuật trong bài báo: Với mã hóa số thực này thì số cá thể không hợp lệ được loại bỏ rất nhiều so với mã hóa nhị phân; Mức trên sử dụng MFEA tăng hiệu quả đáng kể trong việc tìm kiếm một chu trình phù hợp cho xe tải do có quá trình trao đổi tri thức giữa các tác vụ. Một số nghiên cứu trong tương lai được chỉ ra: Bổ sung các ràng buộc khác trong thực tế, chẳng hạn như hàng hóa phải được giao trong thời gian khách hàng chỉ định Thêm những điều kiện không chắc chắn trong việc lập kế hoạch, bao gồm điều kiện đường đô thị, mức độ ảnh hương do hỏng xe, tai nạn giao thông, drones gặp sự cố, nhu cầu khách hàng bị thay đổi Xem xét các thuật giải tốt hơn Kết hợp mô phỏng với thuật giải tối ưu nhằm xây dựng mô hình tối ưu hóa mô phỏng để giải quyết đồng thời nhiều bài toán phân phối. 36