.png)
Phương pháp tối ưu đàn kiến giải bài toán định tuyến xe (Nguyễn Vũ Hoàng Vương)
.png)
Bài toán VRP cũng có nhiều ý nghĩa trong khoa học, bài toán đã được chứng minh là NP-khó. Do đó những thuật toán chính xác dùng để giải chúng chỉ có thể giải được bài toán với kích thước nhỏ. Để giải được bài toán với kích thước lớn, đã có nhiều công tr ình nghiên cứu áp dụng các phương pháp metaheur istic cho bài toán VRP, ví dụ như dùng giải thuật di tr uyền (GA – genetic algor ithm), tìm kiếm Tabu (Tabu search), thuật toán luyện kim (Simulated annealing). Một số thuật toán metaheur istic tốt nhất hiện nay có thể cho lời giải với độ tốt kém 0.5% đến 1% so với lời giải tối ưu cho các bài toán lên tới hàng trăm điểm giao hàng
NỘI DUNG:
Bài toán VRP và các biến thể 1
1.1 Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Bài toán VRP và các khái niệm liên quan . . . . . . . . . . . . . . . . 3
1.3 Bài toán CVRP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Các biến thể của CVRP . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4.1 Thay đổi cấu tr úc tuyến xe . . . . . . . . . . . . . . . . . . . . 7
1.4.2 Thay đổi hàm mục tiêu . . . . . . . . . . . . . . . . . . . . . . 8
1.4.3 Thêm các ràng buộc cho các tuyến xe . . . . . . . . . . . . . . 9
2 Các công trình nghiên cứu liên quan 10
2.1 Thuật toán chính xác . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Heur istic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.1 Heur istic xây dựng . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.2 Heur istic cải thiện . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Metaheur istic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.1 Tìm kiếm Tabu . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.2 Thuật toán luyện kim . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.3 Giải thuật di tr uyền . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.4 Tối ưu hóa đàn kiến . . . . . . . . . . . . . . . . . . . . . . . . 17
3 Phương pháp ACO đề xuất 18
3.1 Tối ưu hóa đàn kiến . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.1.1 Từ kiến tự nhiên đến kiến nhân tạo . . . . . . . . . . . . . . . . 18
3.1.2 Thuật toán ACO . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.3 Tóm tắt thuật toán ACO . . . . . . . . . . . . . . . . . . . . . 21
3.2 Áp dụng ACO cho bài toán CVRP . . . . . . . . . . . . . . . . . . . . 22
vi
Nội dung vii
3.2.1 Bước 1: Khởi tạo ma trận heur istic và vết mùi . . . . . . . . . . 23
3.2.2 Bước 2: Kiến tạo lời giải . . . . . . . . . . . . . . . . . . . . . 23
3.2.3 Bước 3: Cập nhật vết mùi . . . . . . . . . . . . . . . . . . . . . 24
4 Kết quả thực nghiệm và kết luận 25
4.1 Dữ liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.2 Thiết lập tham số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.3 Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.3.1 Phân tích kết quả . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.3.2 So sánh thời gian chạy . . . . . . . . . . . . . . . . . . . . . . 31
4.4 Kết luận . .
Bài toán VRP cũng có nhiều ý nghĩa trong khoa học, bài toán đã được chứng minh là NP-khó. Do đó những thuật toán chính xác dùng để giải chúng chỉ có thể giải được bài toán với kích thước nhỏ. Để giải được bài toán với kích thước lớn, đã có nhiều công tr ình nghiên cứu áp dụng các phương pháp metaheur istic cho bài toán VRP, ví dụ như dùng giải thuật di tr uyền (GA – genetic algor ithm), tìm kiếm Tabu (Tabu search), thuật toán luyện kim (Simulated annealing). Một số thuật toán metaheur istic tốt nhất hiện nay có thể cho lời giải với độ tốt kém 0.5% đến 1% so với lời giải tối ưu cho các bài toán lên tới hàng trăm điểm giao hàng
NỘI DUNG:
Bài toán VRP và các biến thể 1
1.1 Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Bài toán VRP và các khái niệm liên quan . . . . . . . . . . . . . . . . 3
1.3 Bài toán CVRP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Các biến thể của CVRP . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4.1 Thay đổi cấu tr úc tuyến xe . . . . . . . . . . . . . . . . . . . . 7
1.4.2 Thay đổi hàm mục tiêu . . . . . . . . . . . . . . . . . . . . . . 8
1.4.3 Thêm các ràng buộc cho các tuyến xe . . . . . . . . . . . . . . 9
2 Các công trình nghiên cứu liên quan 10
2.1 Thuật toán chính xác . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Heur istic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.1 Heur istic xây dựng . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.2 Heur istic cải thiện . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Metaheur istic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.1 Tìm kiếm Tabu . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.2 Thuật toán luyện kim . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.3 Giải thuật di tr uyền . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.4 Tối ưu hóa đàn kiến . . . . . . . . . . . . . . . . . . . . . . . . 17
3 Phương pháp ACO đề xuất 18
3.1 Tối ưu hóa đàn kiến . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.1.1 Từ kiến tự nhiên đến kiến nhân tạo . . . . . . . . . . . . . . . . 18
3.1.2 Thuật toán ACO . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.3 Tóm tắt thuật toán ACO . . . . . . . . . . . . . . . . . . . . . 21
3.2 Áp dụng ACO cho bài toán CVRP . . . . . . . . . . . . . . . . . . . . 22
vi
Nội dung vii
3.2.1 Bước 1: Khởi tạo ma trận heur istic và vết mùi . . . . . . . . . . 23
3.2.2 Bước 2: Kiến tạo lời giải . . . . . . . . . . . . . . . . . . . . . 23
3.2.3 Bước 3: Cập nhật vết mùi . . . . . . . . . . . . . . . . . . . . . 24
4 Kết quả thực nghiệm và kết luận 25
4.1 Dữ liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.2 Thiết lập tham số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.3 Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.3.1 Phân tích kết quả . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.3.2 So sánh thời gian chạy . . . . . . . . . . . . . . . . . . . . . . 31
4.4 Kết luận . .
%20(1).png "Hướng dẫn download ti liệu")
.png "Hướng dẫn download ti liệu")
.png)
%20(1).png "Gói VIP Member EBOOKBKMT - Hỗ trợ tài liệu nhanh nhất, không giới hạn (Update 2024)")
.png "BÀI THUYẾT TRÌNH HỘI THI BÍ THƯ CHI BỘ GIỎI (FULL)")
Không có nhận xét nào: