Luận văn Thạc sĩ Khoa học: Thuật toán di truyền song song giải bài toán VRP (Vehicle Routing Problem) với hạn chế thời gian

Đề tài "Thuật toán di truyền song song giải bài toán VRP (Vehicle Routing Problem) với hạn chế thời gian" tập trung giải quyết bài toán lập lộ trình xe vận chuyển với hạn chế thời gian – VRPTW, được ứng dụng nhiều trong dịch vụ vận chuyển. Mục tiêu bài toán là tối thiểu số xe vận chuyển và tổng khoảng cách di chuyển khi phục vụ các khách hàng mà không vi phạm các ràng buộc về khả năng chuyên chở của các xe và các cửa sổ thời gian đáp ứng.
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Khoa học: Thuật toán di truyền song song giải bài toán VRP (Vehicle Routing Problem) với hạn chế thời gian BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI --------   -------- Nguyễn Việt HânTHUẬT TOÁN DI TRUYỀN SONG SONG GIẢI BÀI TOÁN VRP (VEHICLE ROUTING PROBLEM) VỚI HẠN CHẾ THỜI GIAN LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội – Năm 2009 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI --------------------------------------- NGUYỄN VIỆT HÂN Nguyễn Việt Hân THUẬT TOÁN DI TRUYỀN SONG SONG GIẢI BÀI TOÁN VRP (VEHICLE ROUTING PROBLEM) VỚI HẠN CHẾ THỜI GIAN LUẬN VĂN THẠC SĨ KHOA HỌC CHUYÊN NGÀNH: CÔNG NGHỆ THÔNG TIN2007 - 2009 NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. NGUYỄN ĐỨC NGHĨAHà nội Hà Nội – Năm 2009 2009 2Lời cảm ơnTrước tiên, em xin gửi lời cảm ơn chân thành đến Thầy PGS. TS. Nguyễn ĐứcNghĩa đã định hướng nghiên cứu và góp ý cho em để có được luận văn hoàn chỉnh.Em xin cảm ơn Quý Thầy cô trong Khoa, với lòng nhiệt huyết, đã vun đắp nền tảngtri thức vững chắc cho các thế hệ học viên. Đây sẽ là hành trang vô giá cho chúngem trên con đường nghiên cứu khoa học.Nhân đây, con xin gửi lời biết ơn đến cha mẹ đã vất vả nuôi nấng và tạo mọi điềukiện để con có được như ngày hôm nay. Xin cảm ơn em, người vợ luôn lo lắng, chiasẻ và động viên anh vượt qua những khó khăn, thử thách.Sau cùng, không thể thiếu lời cảm ơn đến các anh chị đồng nghiệp đã trao đổi,khích lệ và dành thời gian nhiều hơn cho tôi để hoàn thành tốt luận văn. 3 Mục lụcLời cảm ơn ................................................................................................................. 2Mục lục ....................................................................................................................... 3Chương 1: Giới thiệu ............................................................................................. 9 1.1 Đặt vấn đề ..................................................................................................... 9 1.2 Giới thiệu về VRP ...................................................................................... 10 1.3 Các tiêu chuẩn phân loại bài toán VRP ...................................................... 12 1.4 Một số dạng chính của bài toán VRP ......................................................... 13 1.4.1 VRP với hạn chế khả năng chở hàng hóa ...........................................13 1.4.2 VRP với hạn chế thời gian ..................................................................14 1.4.3 VRP với nhiều kho hàng hóa ..............................................................15 1.4.4 VRP định kỳ ........................................................................................16 1.4.5 VRP mở ...............................................................................................17 1.4.6 VRP tách phân phối ............................................................................17 1.4.7 VRP với khả năng chuyên chở về .......................................................17 1.4.8 VRP với khả năng nhặt và phân phối .................................................18 1.5 Tối ưu tổ hợp .............................................................................................. 19Chương 2: Bài toán VRP với hạn chế thời gian ................................................ 20 2.1 Định nghĩa .................................................................................................. 20 2.2 Mô hình toán học ........................................................................................ 20 2.3 Các cấu trúc vùng lân cận........................................................................... 23 2.4 Các phương pháp chính tiếp cận giải bài toán ........................................... 26 2.4.1 Các phương pháp chính xác................................................................26 2.4.1.1 Dựa trên quy hoạch động ................................................................26 2.4.1.2 Dựa trên phát sinh cột .....................................................................26 2.4.1.3 Dựa trên phân rã Lagrange...................................... ...