Đề tài Bài toán tìm đường cho xe tải và drone giao hàng

Bài toán tìm đường cho xe tải và drone giao hàng Sử dụng 2 Phương pháp tính toán tiến hoá: Genetic algorithm & Multifactorial evolution algorithm Nguyễn Huy Hoàng - 20173132 Nội dung Giới thiệu Phát biểu bài toán Phương pháp giải quyết Kết quả Kết luận Nội dung Giới thiệu Phát biểu bài toán Phương pháp Kết quả Kết luận Giới thiệu (Nguồn: Workhorse) Giới thiệu Vấn đề lập lịch / tìm đường? Bài toán đặt ra? Khách hàng tập trung thành các cụm Các cụm cách xa nhau Kho hàng ? Nội dung Giới thiệu Phát biểu bài toán Phương pháp giải quyết Kết quả Kết luận Phát biểu bài toán Có một kho hàng, một xe tải và một drone T ập gồm C khách hàng, được chia vào k vùng (cụm) G iữa cụm i và cụm j có một hoặc nhiều đường đi , cũng có thể không có đường đi nào C ác khách hàng trong một cụm là liên thông với nhau M ỗi khách hàng chỉ được giao một lần bằng drone hoặc xe tải M ục tiêu là tìm ra cách đi sao cho tổng thời gian giao hàng là nhỏ nhất Phát biểu bài toán Chỉ xe tải mới đi được từ cụm này sang cụm khác K hi ở trong vùng, trong quá trình drone đi giao hàng, xe tải được phép giao hàng cho các khách hàng khác, drone phải quay về đúng vị trí mới của xe tải để lấy hàng giao cho khách hàng tiếp theo T rước khi xe tải rời khỏi một vùng thì drone phải quay lại xe tải Coi thời gian lấy hàng (giao hàng) bằng 0 Vận tốc drone = p * vận tốc xe tải (p > 1) Tại điểm hẹn, drone đến trước thì drone phải chờ, xe tải đến trước thì xe tải phải chờ. Minh hoạ Khách hàng Kho hàng Minh hoạ Minh hoạ Minh hoạ Minh hoạ 2 1 3 4 0 Drone route Truck route Minh hoạ Nội dung Giới thiệu Phát biểu bài toán Phương pháp giải quyết Kết quả Kết luận Phương pháp Chia bài toán làm hai mức Mức trên: Tìm đường cho xe tải đi giữa các cụm Mức dưới: Tìm đường cho xe tải và drone đi trong mỗi cụm Thuật toán sử dụng: Mức trên: Genetic Algorithm (GA) Mức dưới: Multifactorial Evolution Algorithm (MFEA) Mức trên Mức trên: Tìm đường cho xe tải đi giữa các cụm Genetic Algorithm (GA) 4 2 5 1 3 0 9 7 8 6 10 11 12 13 14 15 Mức trên - GA Mã hoá cá thể: Danh sách cạnh (0,1), (4,6), (7,10), (14,0) 4 2 5 1 3 0 9 7 8 6 10 11 12 13 14 15 Mức trên - GA Khởi tạo quần thể DFS – Tìm kiếm theo chiều sâu 4 2 5 1 3 0 9 7 8 6 10 11 12 13 14 15 Mức trên - GA Đột biến Thay đổi cạnh giữa 2 cụm (0,1), (4,6), (7,10), (14,0) (0,2), (4,6), (7,10), (14,0) 4 2 5 1 3 0 9 7 8 6 10 11 12 13 14 15 Mức trên - GA Lai ghép Cá thể con được tìm bằng cách duyệt DFS trên tập cạnh của P1 P2 P1: (0,1), (4,6), (7,10), (14,0) P2: (0,2), (2,6), (7,13), (14,0) P1 P2: (0,1), (0,2), (4,6), (2,6), (7,10), (7,13), (14,0) child: (0,1), (2,6), (7,10), (14,0) 4 2 5 1 3 0 9 7 8 6 10 11 12 13 14 15 Mức trên - GA Chọn lọc Chọn những cá thể có chi phí nhỏ nhất cho thế hệ tiếp theo (chi phí tính được sau khi giải xong mức dưới) 4 2 5 1 3 0 9 7 8 6 10 11 12 13 14 15 Mức dưới - MFEA Mức dưới: Tìm đường cho xe tải và drone đi trong mỗi cụm Multifactorial Evolution Algorithm (MFEA) Mức dưới - MFEA Ý tưởng Cần tìm đường đi cho truck và drone trong mỗi cụm, khi đã biết điểm đầu và điểm cuối Mỗi cụm tương ứng với một task Có k cụm => Giải k task song song bằng MFEA 2 1 3 4 0 start end Mức dưới - MFEA Mã hoá, giải mã 10 2 12 1 9 13 0 7 4 6 3 11 5 14 8 10 2 12 1 13 0 4 6 11 5 3 9 7 14 8 Đoạn gen Hành trình truck-drone tương ứng Mức dưới - MFEA Gen chung cho tất cả các task Độ dài bằng số nút trong cụm lớn nhất 10 2 12 1 9 13 0 7 4 6 3 11 5 14 8 Mức dưới - MFEA Giải mã gen chung thành k gen riêng cho k task Ví dụ giải mã gen chung length=15 cho task i có số khách hàng là 10 10 2 12 1 9 13 0 7 4 6 3 11 5 14 8 10 2 12 1 9 13 0 7 4 6 3 11 5 14 8 Đánh số các nút trong cụm i từ 0 đến 9. Nút bắt đầu = 0 Nút kết thúc = 9 Mức dưới - MFEA Giải mã gen chung thành k gen riêng cho k task Ví dụ giải mã gen chung length=15 cho task có số khách hàng là 10 10 2 12 1 9 13 0 7 4 6 3 11 5 14 8 10 2 12 1 9 13 0 7 4 6 3 11 5 14 8 2 1 9 0 7 4 6 3 5 8 2 1 9 0 7 4 6 3 5 8 0 1 8 2 7 4 6 3 5 9 Mức dưới - MFEA Giải mã gen chung thành k gen riêng cho k task Ví dụ giải mã gen chung length=15 cho task có số khách hàng là 10 10 2 12 1 9 13 0 7 4 6 3 11 5 14 8 Mức dưới - MFEA Giải mã gen chung thành k gen riêng cho k task Ví dụ giải mã gen chung length=15 cho task có số khách hàng là 10 10 2 12 1 9 13 0 7 4 6 3 11 5 14 8 0 1 8 2 7 4 6 3 5 9 0 1 8 2 7 4 6 3 5 9 Mức dưới - MFEA Khởi tạo quần thể Sinh ngẫu nhiên dãy hoán vị của 0,1,..N-1 với N là độ dài gen Sinh ngẫu nhiên dãy màu sắc dài N phần tử sao cho hợp lệ Ô màu xanh phải ở giữa 2 ô màu đỏ Ô màu đỏ (ngoại trừ ô đầu và cuối) phải ở giữa 2 ô màu xanh, hoặc ở giữa 1 ô màu xanh và 1 ô màu đỏ Kết hợp lại => được 1 cá thể 10 2 12 1 9 13 0 7 4 6 3 11 5 14 8 Mức dưới - MFEA Lai ghép Chỉ thay đổi phần số Partially mapped crossover P1 P2 Child 1 0 2 6 1 5 4 3 6 0 5 2 1 3 4 0 6 5 2 1 4 3 Child 1 2 0 6 1 5 3 4 Mức dưới - MFEA Đột biến Đột biến phần số Đổi chỗ 2 số Lật ngược một đoạn Trượt một đoạn Đột biến phần màu Di chuyển 1 ô màu xanh (đỏ) sang trái (phải) Thêm hoặc xoá 1 ô màu xanh (đỏ) Thêm đồng thời xanh và đỏ Xoá đồng thời xanh và đỏ Mức dưới - MFEA Chọn lọc Chọn những cá thể có độ đo fitness cao nhất Nội dung Giới thiệu Phát biểu bài toán Phương pháp giải quyết Kết quả Kết luận Input Biểu đồ hội tụ MFEA trong một lần chạy ví dụ Biểu đồ hội tụ GA Kết quả tìm được Biểu đồ hội tụ GA Kết quả tìm được Nội dung Giới thiệu Phát biểu bài toán Phương pháp giải quyết Kết quả Kết luận Kết luận - Trực quan có thể thấy kết quả chưa tối ưu - Thuật toán cần cải thiện Tối ưu thời gian chạy Thêm các toán tử đột biến / lai ghép khác Tìm cách mã hoá khác Thay đổi phương pháp khác Thank you for attention