tailieunhanh - 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. | 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 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 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 TIN 2007 - 2009 NGƯỜI HƯỚNG DẪN KHOA HỌC TS. NGUYỄN ĐỨC NGHĨA Hà nội Hà Nội Năm 2009 2009 2 Lời cảm ơn Trước tiên em xin gửi lời cảm ơn chân thành đến Thầy PGS. TS. Nguyễn Đức Nghĩ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ảng tri 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úng em 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ều kiện để con có được như ngày hôm nay. Xin cảm ơn em người vợ luôn lo lắng chia sẻ 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ục Lời cảm ơn . 2 Mục lục . 3 Chương 1 Giới thiệu . 9 Đặt vấn đề . 9 Giới thiệu về VRP . 10 Các tiêu chuẩn phân loại bài toán VRP . 12 Một số dạng chính của bài toán VRP . 13 VRP với hạn chế khả năng chở hàng hóa .13 VRP với hạn chế thời gian .14 VRP với nhiều kho hàng hóa .15 VRP định kỳ .16 VRP mở .17 VRP tách phân phối .17 VRP với khả năng chuyên chở về .17 VRP với khả năng nhặt và phân phối .18 Tối ưu tổ hợp . 19 Chương 2 Bài toán VRP với hạn chế thời gian . 20 Định nghĩa . 20 Mô hình toán học . 20 Các cấu trúc vùng lân cận. 23 Các phương pháp chính tiếp cận giải bài toán . 26 Các phương pháp chính Dựa trên