Luận văn Một thuật toán tối ưu đàn kiến giải bài toán điều phối xe

Nội dung tài liệu: Luận văn Một thuật toán tối ưu đàn kiến giải bài toán điều phối xe

1. ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ    TRẦN LAN PHƯƠNG MỘT THUẬT TOÁN TỐI ƯU ĐÀN KIẾN GIẢI BÀI TOÁN ĐIỀU PHỐI XE LUẬN VĂN THẠC SĨ Ngành: Kỹ thuật phần mềm Hà Nội, năm 2019
2. ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ    TRẦN LAN PHƯƠNG MỘT THUẬT TOÁN TỐI ƯU ĐÀN KIẾN GIẢI BÀI TOÁN ĐIỀU PHỐI XE Ngành : Kỹ thuật phần mềm Chuyên ngành : Kỹ thuật phần mềm Mã số : 8480103.01 LUẬN VĂN THẠC SĨ Ngành: Kỹ thuật phần mềm Người hướng dẫn khoa học: PGS. TS Hoàng Xuân Huấn Hà Nội, năm 2019
3. LỜI CAM ĐOAN Tôi xin cam đoan rằng luận văn này của tự cá nhân tôi tìm hiểu, nghiên cứu dưới sự hướng dẫn giúp đỡ của PGS.TS Hoàng Xuân Huấn. Trong toàn bộ nội dung của luận văn, những điều đã được trình bày hoặc là của chính cá nhân tôi hoặc là được tổng hợp từ nhiều nguồn tài liệu. Các tài liệu tham khảo được trích dẫn và chú thích đầy đủ. Các số liệu được trích dẫn trong luận văn này là trung thực. Kết quả nghiên cứu này không trùng với bất cứ công trình nào đã được công bố trước đây. Tôi xin hoàn toàn chịu trách nhiệm với lời cam đoan của mình. TÁC GIẢ LUẬN VĂN Trần Lan Phương
4. LỜI CẢM ƠN Luận văn “Một thuật toán tối ưu đàn kiến giải bài toán điều phối xe” được hoàn thành với sự giúp đỡ tận tình của các thầy giáo, cô giáo trường Đại học công nghệ - Đại học Quốc gia Hà Nội, các đồng nghiệp, gia đình và sự nỗ lực của bản thân trong suốt quá trình học tập và thực hiện luận văn. Trước tiên, em xin chân thành cảm ơn tới Ban giám hiệu nhà trường, phòng Đào tạo Đại học và Sau đại học, khoa Công nghệ thông tin và các thầy giáo, cô giáo trong trường đã tận tình truyền đạt kiến thức, giúp đỡ em trong suốt quá trình học tập chương trình cao học tại trường. Đặc biệt em xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo PGS.TS Hoàng Xuân Huấn, Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội đã tận tình chỉ dẫn, giúp đỡ và cung cấp cho em những kiến thức, tài liệu cần thiết để hoàn thành luận văn này. Cuối cùng, em xin gửi lời cảm ơn tới gia đình, bạn bè đồng nghiệp và người thân đã tin tưởng, giúp đỡ, động viên, khích lệ em trong suốt quá trình làm luận văn tốt nghiệp. Do thời gian và kiến thức có hạn chắc chắn luận văn cũng không thể tránh khỏi những thiếu sót, hạn chế. Kính mong nhận được sự chỉ bảo và góp ý của quý Thầy, Cô. Em xin chân thành cảm ơn! Hà Nội, tháng 06 năm 2019 Học viên Trần Lan Phương
5. MỤC LỤC MỞ ĐẦU .......................................................................................................................... 1 CHƯƠNG 1: GIỚI THIỆU BÀI TOÁN ĐỊNH TUYẾN XE............................................. 3 1.1. Phát biểu bài toán định tuyến xe .......................................................................... 3 1.2. Các biến thể quan trọng của bài toán định tuyến xe.............................................. 5 1.2.1. Dựa vào cấu trúc đường đi .............................................................................. 5 1.2.2. Dựa vào yêu cầu vận chuyển ........................................................................... 5 1.2.3. Dựa vào ràng buộc nội tuyến .......................................................................... 6 1.2.3.1. Ràng buộc về lượng hàng hóa .................................................................. 6 1.2.3.2. Ràng buộc về độ dài lộ trình .................................................................... 7 1.2.3.3. Ràng buộc về việc tái sử dụng xe ............................................................. 7 1.2.3.4. Ràng buộc về thời gian cho mỗi lộ trình .................................................. 7 1.2.4. Dựa vào đặc điểm đội xe ................................................................................. 8 1.2.5. Dựa vào ràng buộc liên tuyến .......................................................................... 9 1.2.6. Dựa vào hàm mục tiêu .................................................................................. 10 1.3. Các hướng tiếp cận và ứng dụng của bài toán định tuyến xe .............................. 10 1.4. Kết luận chương ................................................................................................ 12 CHƯƠNG 2: THUẬT TOÁN TỐI ƯU ĐÀN KIẾN ....................................................... 13 2.1. Giới thiệu về thuật toán...................................................................................... 13 2.2. Từ kiến tự nhiên đến kiến nhân tạo .................................................................... 13 2.2.1. Đàn kiến tự nhiên .......................................................................................... 14 2.2.2. Đàn kiến nhân tạo ......................................................................................... 15 2.3. Trình bày giải thuật............................................................................................ 15 2.3.1. Đồ thị cấu trúc .............................................................................................. 16 2.3.2. Trình bày về thuật toán ACO cơ bản ............................................................. 18 2.3.3. Quy tắc cập nhật vết mùi ............................................................................... 19 2.3.3.1. Thuật toán AS .................................................................................... 19 2.3.3.2. Thuật toán ACS.................................................................................. 22 2.3.3.3. Thuật toán Max-Min .......................................................................... 23 2.3.3.4. Thuật toán Min- Max trơn .................................................................. 25 2.4. Một số vấn đề liên quan khi áp dụng ACO......................................................... 26
6. 2.4.1. Đặc tính hội tụ .............................................................................................. 26 2.4.2. Thực hiện song song ..................................................................................... 26 2.4.3. ACO kết hợp với tìm kiếm cục bộ ................................................................. 27 2.4.4. Thông tin heuristic ........................................................................................ 27 2.4.5. Số lượng kiến ................................................................................................ 28 2.4.6. Tham số bay hơi ........................................................................................... 28 2.5. Kết luận chương. ............................................................................................... 28 CHƯƠNG 3: ỨNG DỤNG THUẬT TOÁN TỐI ƯU ĐÀN KIẾN GIẢI BÀI TOÁN MPDPTW ....................................................................................................................... 29 3.1. Phát biểu bài toán .............................................................................................. 29 3.1.1. Giới thiệu bài toán ........................................................................................ 29 3.1.2. Xây dựng mô hình toán học .......................................................................... 30 3.2. Một số phương pháp giải quyết bài toán MPDPTW ........................................... 32 3.3. Thuật toán ACO giải quyết bài toán MPDPTW ................................................. 33 3.3.1. Đồ thị cấu trúc .............................................................................................. 33 3.3.2. Xây dựng giải pháp ....................................................................................... 34 3.3.3. Quy tắc cập nhật mùi .................................................................................... 36 3.3.4. Thủ tục tìm kiếm cục bộ ............................................................................... 36 3.4. Kết luận chương ................................................................................................ 38 CHƯƠNG 4: CÀI ĐẶT VÀ ĐÁNH GIÁ THỰC NGHIỆM ........................................... 39 4.1. Cài đặt chương trình .......................................................................................... 39 4.2. Mô tả dữ liệu thực nghiệm ................................................................................. 41 4.3. Hiệu năng lời giải mô hình toán học .................................................................. 42 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ....................................................................... 50 TÀI LIỆU THAM KHẢO .............................................................................................. 51 PHỤ LỤC ....................................................................................................................... 54
7. DANH MỤC THUẬT NGỮ VIẾT TẮT STT Từ viết tắt Từ đầy đủ Ý nghĩa 1 ACO Ant Colony Optimization Tối ưu đàn kiến 2 ACS Ant Colony System Hệ đàn kiến 3 AS Ant System Hệ kiến 4 CG Column Generation Kỹ thuật sinh cột 5 CVRP Capacitated Vehicle Routing Bài toán định tuyến xe hạn Problem chế về sức chứa 6 DVRP Distance Vehicle Routing Bài toán định tuyến xe hạn Problem chế về khoảng cách 7 GA Genetic Algorithm Giải thuật di truyền 8 MMAS Max – Min Ant System Hệ kiến Max – Min 9 MPDPTW Multi – Pickup and Delivery Bài toán định tuyến xe đa Problem with TimeWindows điểm đón và giao hàng với thời gian cửa sổ 10 PDP Pickup and Delivery Problem Bài toán giao và nhận hàng 11 SA Simulated Annealing Giải thuật luyện kim 12 SMMAS Smooth – Max Min Ant System Hệ kiến Max – Min trơn 13 SOP Sequential Ordering Problem Bài toán đặt hàng tuần tự 14 TSP Travelling Salesman Problem Bài toán Người bán hàng 15 TƯTH Tối ưu hóa tổ hợp Tối ưu hóa tổ hợp 16 VRP Vehicle Routing Problem Bài toán định tuyến xe
8. DANH MỤC HÌNH VẼ Hình 1. 1 Ví dụ cho bài toán Người bán hàng– TSP. ......................................................... 3 Hình 1. 2 Mô phỏng bài toán VRP. ................................................................................... 4 Hình 1. 3 Mô phỏng bài toán CVRP. ................................................................................. 6 Hình 2. 1 Ví dụ về hoạt động của đàn kiến trong thực tế. ................................................ 14 Hình 2. 2 Ví dụ về hoạt động của đàn kiến nhân tạo. ...................................................... 15 Hình 2. 3 Đồ thị cấu trúc tổng quát cho bài toán cực trị hàm ( 1, 푛)...................... 17 Hình 2. 4 Đặc tả thuật toán ACO. ................................................................................... 19 Hình 3. 1 Minh họa các yêu cầu R1 và R6 thuộc tuyến đường của xe k. .......................... 30 Hình 3. 2 Đồ thị cấu trúc cho bài toán MPDPTW. .......................................................... 33 Hình 3. 3 Mô tả thuật toán T1 ......................................................................................... 36 Hình 3. 4 Mô tả thuật toán T2 ......................................................................................... 37 Hình 3. 5 Mô tả quá trình tìm kiếm cục bộ ...................................................................... 37 Hình 4. 1 Các bộ dữ liệu thử nghiệm............................................................................... 42 Hình 4. 2 Mô tả dữ liệu đầu vào. ..................................................................................... 43 Hình 4. 3 Mô tả kết quả chương trình. ........................................................................... 44 Hình 4. 4 Mở chương trình ............................................................................................. 54 Hình 4. 5 Chạy chương trình .......................................................................................... 55
9. DANH MỤC BẢNG BIỂU Bảng 1. 1 Các biến thể của bài toán VRP phân chia theo đặc điểm đội xe. ....................... 8 Bảng 4. 1 Kết quả thực nghiệm của ACO sử dụng SMMAS. ............................................ 45 Bảng 4. 2 Bảng so sánh ACO và CPLEX. ....................................................................... 46 Bảng 4. 3 So sánh kết quả tốt nhất của SMMAS và MMAS có cùng vòng lặp. ................. 48 Bảng 4. 4 So sánh kết quả tốt nhất của SMMAS và MMAS có cùng thời gian chạy. ........ 49
10. 1 MỞ ĐẦU 1. Lý do chọn đề tài Trong những năm gần đây, công nghệ thông tin giữ vai trò quan trọng trong hầu hết các lĩnh vực của đời sống, xã hội. Đặc biệt, mỗi ngày có một lượng lớn chi phí được sử dụng cho quá trình vận chuyển hàng hóa, du lịch trong các bài toán vận tải. Việc đưa ra lịch trình di chuyển của phương tiện vận tải một cách hợp lý giúp giảm chi phí được sử dụng cho nhiên liệu, thiết bị, phí bảo trì xe và tiền lương của lái xe là vô cùng quan trọng. Do đó, việc nghiên cứu các cách thức để đưa ra kế hoạch định tuyến tối ưu bằng chương trình máy tính rất có giá trị. Bài toán định tuyến xe (Vehicle Routing Problem - VRP) là bài toán đã được nghiên cứu trong suốt hơn 50 năm qua của Vận Trù Học với nhiều ứng dụng trong thực tế, đặc biệt là trong lĩnh vực giao thông vận tải và hậu cần,... Bài toán có liên quan đến việc thiết lập hành trình cho các phương tiện từ kho đi giao hàng tới các thành phố và quay trở lại kho ban đầu mà không vượt quá năng lực hạn chế của mỗi xe với tổng chi phí tối thiểu. Bài toán này đã được chứng minh thuộc lớp các bài toán NP-khó[8], có rất nhiều giải thuật khác nhau đã được đề xuất để tìm lời giải tối ưu cho bài toán này như: thuật toán di truyền, kỹ thuật nhánh cận, thuật toán sinh cột, Tuy nhiên các giải thuật trên đều tốn nhiều chi phí về thời gian hoặc không gian lớn. Thuật toán tối ưu hóa đàn kiến được đề xuất bởi Dorigo từ năm 1991 đến nay đã có nhiều cải tiến về quy tắc cập nhật vết mùi làm cho thuật toán trở nên hiệu quả hơn. Do vậy, tôi đã lựa chọn đề tài “Một thuật toán tối ưu đàn kiến giải quyết bài toán điều phối xe” để nghiên cứu. 2. Lịch sử vấn đề nghiên cứu Bài toán định tuyến xe (Vehicle Routing Problem-VRP) được nghiên cứu trên nhiều ràng buộc khác nhau và có rất nhiều giải thuật được đề xuất cho bài toán này. Trong đó bài toán định tuyến xe đa điểm đón và giao hàng với thời gian cửa sổ (Multi Pickup and Delivery Problem with TimeWindows-MPDPTW) là một biến thể của bài toán VRP đã được nghiên cứu trong nhiều ứng dụng thực tế như giao hàng thực phẩm, xe đưa đón học sinh tới trường, Bài toán thuộc lớp các bài toán NP-Khó được đề xuất bởi Nacache và các cộng sự vào năm 2018 [4] trên tạp chí Vận Trù Học và họ giải quyết bài toán một cách chính xác nhờ áp dụng kỹ thuật nhánh cận và phát triển một kỹ thuật tìm kiếm heuristic là A hybird Adaptive Large Neighborhood Search (ALNS) để cải thiện lời giải. Tuy nhiên các giải thuật trên đều tốn chi phí về thời gian hoặc không gian lớn, không khả thi để đưa ra lời giải tối ưu cho bài toán định tuyến có kích thước lớn.