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) VOI HAN CHE THỜI GIAN LUẬN VĂN THẠC SĨ KHOA HỌC HaNgi Năm 2009 BỘ GIÁO DỤC VÀ DÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỌI NVILL “HA NHIATĐN Nguyễn Việt Hân THUẬT TOÁN DI TRUYÊN SONG SƠNG GIẢI BÀI TOAN VRP (VEHICLE ROUTING PROBLEM) VOT HẠN CHẾ THỜI GIAN LUẬN VĂN THẠC SĨ KHOA HỌC CIIUYEN NGANII: CONG NGIIE TIONG TIN 600 - ¿006 NGUOIIIVONG DAN KIIOA II9C: TS. NGUYEN DUC NGHIA Hà nội Ha Nội — Năm 2009 2009 ie 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 PGQS. Nguyễn Đức ẬNghữa dã định hướng nghiên cứu và góp ý cho cm dễ có được luận văn hoàn chỉnh. Em xin cam on Quy Thay cô trong Khoa, với lòng nhiệt huyết, dã vụn đắp nền tảng, tri thức vững chắc cho các thế hệ học viễn.
Dây sẽ là bả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 răng và tạo mọi điều kiện đễ cơn 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 ‡chó khăn, thử thách. Sau cùng, không thê thiểu lời cảm ơn đến các anh chi déng nghiệp đã trao đổi, khích lệ và đành thời gian nhiều hơn cho tôi để hoãn thành tốt luận vẫn. Mục lục 2 3 Chương1: Giớithiệu.
9 11 Dat van dé 9 1.2 Gidi tnéuvé VRP 10 1.3 Cac tigu chudn phan logi bai toan VRP 12 1.4 Một số đạng chỉnh của bai toan VRP. VRP với hạn chế khả năng chổ hàng hỏa 13 1.2 VRP với hạn chế thời gian 1⁄43 VRPvdinhiễu kho hàng hóa.6 — VRP tach phan phdi 17 1.7 VRP với khả nẵng chuyên chớ vẻ 17 148 VRP với khả năng nhặt và phản phối 18 1.5 Tôi rulỗ hợp - 19 Chương2: Bài toán VRP với hạn chế thừi gian lì.3 Các cầu trúc vùng lần cận. Các phương pháp chính tiếp cận giải 26 2.41 Cáephương pháp chính xác.11 Dựa trên quy hoạch động.` 2412 Dựa trên phát sinh cột - - - 26 2.3 Dựa trên phần rã Lagrange - 6 BALA Diya trên K-TT@6. Mục lục 2 3 Chương1: Giớithiệu.
9 11 Dat van dé 9 1.2 Gidi tnéuvé VRP 10 1.3 Cac tigu chudn phan logi bai toan VRP 12 1.4 Một số đạng chỉnh của bai toan VRP. VRP với hạn chế khả năng chổ hàng hỏa 13 1.2 VRP với hạn chế thời gian 1⁄43 VRPvdinhiễu kho hàng hóa.6 — VRP tach phan phdi 17 1.7 VRP với khả nẵng chuyên chớ vẻ 17 148 VRP với khả năng nhặt và phản phối 18 1.5 Tôi rulỗ hợp - 19 Chương2: Bài toán VRP với hạn chế thừi gian lì.3 Các cầu trúc vùng lần cận. Các phương pháp chính tiếp cận giải 26 2.41 Cáephương pháp chính xác.11 Dựa trên quy hoạch động.` 2412 Dựa trên phát sinh cột - - - 26 2.3 Dựa trên phần rã Lagrange - 6 BALA Diya trên K-TT@6. Danh sách các bảng Bảng 5I Bang so sánh kết quả tung bình lừ các kết quả tốt nhất giữa các phương pháp và kết quả tốt nhất dược biết.
liảng 52 ang chỉ tiết so sánh thời gian trung binh khi thực thi tuân tự so với thời gian trung bình khi thực thi song song ứng với số tiễn trinh kháo nhau và theo từng tip tin mu.3 Bang téng hgp so sanh thdi gian trong binh thực thi tuần tự và song song trong mỗi nhóm dữ liệu. 74 lăng 54 — Bảng Speedup trung bình của chương trình thực thì song song tính theo từng nhóm mẫu. 74 Mục lục 2 3 Chương1: Giớithiệu. 9 11 Dat van dé 9 1.2 Gidi tnéuvé VRP 10 1.3 Cac tigu chudn phan logi bai toan VRP 12 1.4 Một số đạng chỉnh của bai toan VRP.
VRP với hạn chế khả năng chổ hàng hỏa 13 1.2 VRP với hạn chế thời gian 1⁄43 VRPvdinhiễu kho hàng hóa.6 — VRP tach phan phdi 17 1.7 VRP với khả nẵng chuyên chớ vẻ 17 148 VRP với khả năng nhặt và phản phối 18 1.5 Tôi rulỗ hợp - 19 Chương2: Bài toán VRP với hạn chế thừi gian lì.3 Các cầu trúc vùng lần cận. Các phương pháp chính tiếp cận giải 26 2.41 Cáephương pháp chính xác.11 Dựa trên quy hoạch động.` 2412 Dựa trên phát sinh cột - - - 26 2.3 Dựa trên phần rã Lagrange - 6 BALA Diya trên K-TT@6. Mục lục 2 3 Chương1: Giớithiệu. 9 11 Dat van dé 9 1.2 Gidi tnéuvé VRP 10 1.3 Cac tigu chudn phan logi bai toan VRP 12 1.4 Một số đạng chỉnh của bai toan VRP.
VRP với hạn chế khả năng chổ hàng hỏa 13 1.2 VRP với hạn chế thời gian 1⁄43 VRPvdinhiễu kho hàng hóa.6 — VRP tach phan phdi 17 1.7 VRP với khả nẵng chuyên chớ vẻ 17 148 VRP với khả năng nhặt và phản phối 18 1.5 Tôi rulỗ hợp - 19 Chương2: Bài toán VRP với hạn chế thừi gian lì.3 Các cầu trúc vùng lần cận. Các phương pháp chính tiếp cận giải 26 2.41 Cáephương pháp chính xác.11 Dựa trên quy hoạch động.` 2412 Dựa trên phát sinh cột - - - 26 2.3 Dựa trên phần rã Lagrange - 6 BALA Diya trên K-TT@6. Chương1: Giới thiệu 1.1 Đặt van dé VRP la bai toản xác định các lộ trinh tối ưu cho dội xe vận chuyển nhằm phục vụ các khách hàng ở các vị trí khác nhau. Dây là bài toán có nhiều ứng đựng trong thực tế từ khâu cung cắp nguyên liệu thô đến khâu phân phối thành phẩm trong các nhà may san xuất, các công ty địch vụ vận chuyển như bưu phẩm, hanh khách,.
Rỡ ràng, chỉ phi vận chuyền sẽ giảm nêu cáo xe di chuyễn theo các lộ trình tôi trị, tí da giúp giảm giả thành hàng hóa. Trong thời đại kinh tế xã hội ngày cảng phải. triển, các yêu cầu của khách hang ngảy cảng khắt khe hơn. Liêu biểu như yêu cầu phái được đáp ứng trong một khoảng thời gian xác định: các công ty hoạt động theo một thời gian biểu chinh xác,.
Chính vì vậy, vẫn để lập lộ trình VRP với han chế gian (viết tắt là VRPTW) ngày cảng được quan tâm hơn. Luận văn đặt nghiên cứu trên bài toán VRPTW phủ hợp với xu thê phát triển. Hơn thể, VRP là một dạng bài toán NP-khó, do đó, VRPTW cũng thuộc KT-khó. Mục tiêu của VRPTW là tối thiểu số xe vận clruyễn va tổng khoảng cách di chuyển khi phục vụ các khách hàng mà không vì phạm các ràng buộc về khả năng chuyên.
chờ của các xe và cáo cửa số thời gian đáp ứng. Để tìm lời giải khả thí cho bài toàn, nhiễu thuật toán dã dược nghiên cứu và ứng dụng như các thuật toản đựa trên quy hoạch động, các thuật toán đựa trên sự nới lỏng Laprange, các thuật toán dựa trên heunctic,. Trong dé, cde thual loan heuristic duge quan lâm nhiều nhài. tiếp cận giải thuật di truyền giải quyết bài toàn VRPTW, Đây là giải thuật dựa trên heuristic duce img dung rộng rãi trong nhiều bài toán tồi tru thực tế thuộc nhiều lĩnh vực khác nhau.
Các thuật toán đựa trên heuristic thường cho các lời giãi có tỉnh khả thủ cao, gần với lời giải tối ưu của bải toán. Tuy nhiên, giải thuật phải lặp qua nhiều vòng lập với nhiều tỉnh toán đôi hỏi nhiéu năng lực tính toán của máy tính Tiêu biếu như thuật toán dị truyền phải lắp qua nhiều thể hệ, các thao tác tỉnh toán thực hiện trên từng, Danh sách các từ viết tắt GA Genetic Algorithm PGA Parallel Genetic Algorithm MIMD Multiple Instruction Multiple Data VRP Vehicle Routing Problem VRETW Vehicle Routing Problem with Time Window PFIH, Push-Forward Insertion Heuristic LSD d-Interchange Local Search Descent. TSP Travelling Salesman Problem ACS Ant Colony System ACO Ant Colony Optimization MACS- Multiple Ant Colony System for Vebicle Routing Problems with VRPIW ‘Time Windows PMX Partially Mapped Crossaver 242 — Cáo phương pháp heurisie 37 244. Heuristic xây đựng lồ trình.
- - 28 2423 Heuristic ofi thiện 16 trình - 29 Chuong 3: Thuật toản di truyền song song.1 Giới thiệu về thuật toán đi tuyẻn. Cáo phép Loàn chính của thuật toán đi truyền - 36 321 Phépchọn. Các mô hình song song.2 Song song dang chil t .3 Song song dang da quản thẻ con cỏ di trủ. Song song dang quần thể con chồng lập, không di trú.5 Thuật loàn đi ruyển song sơng khối lớn - - 45 3.6 Song song dang các nhỏm cá thể động,.7 Thwat toan song song trang thái ổn định.8 ThmẬLIoán song sung hôn lạp.9 Cáo phương pháplai.
Chương 4: Thuật toán di truyền song song giải b: gian + 4.1 leuristie xây dựng lộtrình.2 Thuật toán di truyền giải bài toán VRPTW.21 Biểu diễn nhiều sắc the.2 Tao quam thd ban dato cceescsesssssssesseesssnsssnsssssseesseeeeesseessutenieeee 53 42.3 Đánh giá tinh thích nghỉ - - 34 424 Các thao tác ditruyến.cccec TH re 35 42. - - - 36 242 — Cáo phương pháp heurisie 37 244. Heuristic xây đựng lồ trình. - - 28 2423 Heuristic ofi thiện 16 trình - 29 Chuong 3: Thuật toản di truyền song song.1 Giới thiệu về thuật toán đi tuyẻn.
Cáo phép Loàn chính của thuật toán đi truyền - 36 321 Phépchọn. Các mô hình song song.2 Song song dang chil t .3 Song song dang da quản thẻ con cỏ di trủ. Song song dang quần thể con chồng lập, không di trú.5 Thuật loàn đi ruyển song sơng khối lớn - - 45 3.6 Song song dang các nhỏm cá thể động,.7 Thwat toan song song trang thái ổn định.8 ThmẬLIoán song sung hôn lạp.9 Cáo phương pháplai. Chương 4: Thuật toán di truyền song song giải b: gian + 4.1 leuristie xây dựng lộtrình.2 Thuật toán di truyền giải bài toán VRPTW.21 Biểu diễn nhiều sắc the.2 Tao quam thd ban dato cceescsesssssssesseesssnsssnsssssseesseeeeesseessutenieeee 53 42.3 Đánh giá tinh thích nghỉ - - 34 424 Các thao tác ditruyến.cccec TH re 35 42.
- - - 36 Chương1: Giới thiệu 1.1 Đặt van dé VRP la bai toản xác định các lộ trinh tối ưu cho dội xe vận chuyển nhằm phục vụ các khách hàng ở các vị trí khác nhau. Dây là bài toán có nhiều ứng đựng trong thực tế từ khâu cung cắp nguyên liệu thô đến khâu phân phối thành phẩm trong các nhà may san xuất, các công ty địch vụ vận chuyển như bưu phẩm, hanh khách,. Rỡ ràng, chỉ phi vận chuyền sẽ giảm nêu cáo xe di chuyễn theo các lộ trình tôi trị, tí da giúp giảm giả thành hàng hóa. Trong thời đại kinh tế xã hội ngày cảng phải.
triển, các yêu cầu của khách hang ngảy cảng khắt khe hơn. Liêu biểu như yêu cầu phái được đáp ứng trong một khoảng thời gian xác định: các công ty hoạt động theo một thời gian biểu chinh xác,. Chính vì vậy, vẫn để lập lộ trình VRP với han chế gian (viết tắt là VRPTW) ngày cảng được quan tâm hơn.