Luận văn Thạc sĩ Kỹ thuật phần mềm: Một thuật toán tối ưu đàn kiến giải bài toán điều phối xe

Mục tiêu của luận văn này là đưa ra một giải pháp để giải quyết bài toán với kích thước lớn và dễ dàng cho việc cài đặt thực nghiệm. Cụ thể, chúng tôi áp dụng một thuật toán tối ưu đàn kiến (ACO) với quy tắc cập nhật mùi Max-Min trơn (SMMAS) có tìm kiếm địa phương để đưa ra lời giải cho bài toán định tuyến xe đa điểm đón và giao hàng với thời gian cửa sổ (MPDPTW).
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Kỹ thuật phần mềm: Một thuật toán tối ưu đàn kiến giải bài toán điều phối xe ĐẠ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 ĐẠ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 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ềunguồ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 đượctrí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 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ànhvớ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ốcgia 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ọctậ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 caohọ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 ìn h 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ốtnghiệ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ỏinhữ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 MỤC LỤCMỞ ĐẦU .......................................................................................................................... 1CHƯƠ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 ............................. ...