Chương 1. Trinh bảy một cách lổng quan về VRP trong dò để cập tới định nghĩa, các đặc điểm,các dạng vá mồ hình toán học của VRP. Cương 2: Tập trung nghiên cứu ding bai loón VRPTW. Trong chương này trình bảy khải niệm chưng, mô hình toán học và một số cách tiếp cận hiện có để giải VRPTW.
Chương 3: Trình bày vẻ giải thuật bầy kiên, từ nên táng sinli học tới áp dựng vào kiến nhần tạo. Chương này gững trình bảy cỗ giải thuật bây kiến đầu. tiến cho tới các giái thuật chính, có hiệu quả cao như Hệ thông bẩy kiển, Hệ thống kiến Max — Min, tối ru hóa bẩy kiến. Chương 4: Từ kiến thức nên táng ở chương hai và chương ba, chương, nảy trình bảy việc áp dụng giải thuật bảy kiến ACS đề giải VRPTW nói chung và để xuất giải thuật MACB để giải bài toán VRPMTW.
Đây có thể nói là phân nội dung chính của luận văn. Chương 5: Trinh bay các kết quả thứ nghiệm khi cài đặt giải thuật MACS - VRPMTW và chạy chương trình với các bộ đữ liệu, từ đỏ đưa ra kết luận và so sánh kết quả của phương pháp với phương pháp khác. DANH SÁCH CÁC HÌNH Hình 1.1: Các lớp bài toán VRE.2: Vi du cáo luồng đường đi trên một lộ trình (C Hình 2. Téi ưu cục bộ.4: Mét trưởng hợp ma FB la tét hon GB Hinh 3.1: Thi nghiém cầu đôi Tinh 3.2:Dé thi twong mg với mô hình thí nghiệm ở hính 3 1.
Kién tric cia MACS — VRPTW. Các nhà nghiên cừu đã đề xuất rất nhiêu cách tiếp cận từ cách tiếp cận xueo tới tối ưu hóa cho VRPTW, trong đó các tiếp cận ruẹo là thành công hon cả ví dụ như mẹo láng giểng gân nhất, mô phỏng tôi luyện (SA), tìm kiếm Tabu (TS), giai thudl. SA được đưa ra đầu tiên bởi Kirkpatrick [7], tim kiếm không gian lời giải bằng cách mô phỏng quá trình tỏi luyện khn loại. SA thưc hiển nhảy tới các vùng trong không gian tim kiếm ban đâu.
Bước nhảy được giảm đản theo. thời gian hoặc khu nhiệt dộ giảm xuống. Cuối củng, quá trình sẽ trở thành tìm kiếm cục bộ. Osman [8] ứng dựng SA đế giải VRP băng cách đi chuyển mệt khách hàng từ một bánh trình tới hành trình kháe hoặc hoán chuyên ben khách hàng từ hai lộ trình với nhau.
Nói chưng, SA là giải thuật đơn giản, nhanh để äi VRPTW với kết quả gần tôi ưu nhưng trong trường, hợp riểu tối ưu lổng. thể là rất xa so với lời giải ban đầu thì có thể SA không đủ năng lượng để đi xa nbz vay T8 [6] là một chiến lược tìm kiếm dựa trên bộ nhớ, chọn lời giái tốt nhất tuà không vì phạm cáo giới lạn tảo đỏ để ngăm chặn chủ trình. Thông thường các giới hạn này được lưu trữ trong một cấu trúc hàng đợi goi Ja Tabu lạt. Cáo giới bạn này ngắn chắn một đì chuyển đã được thực hiện rong L lần lặp cuối cùng và lời giái đưa ra trong trường hợp này cũng, bị loại bó.
TS dừng sau một số lầu lặp cô định. Gerdreen, Hertz va Laporte dai ing dung TS cing với mẹo láng giéng gan nhất để đi chuyển một khách hang từ 16 tinh nay sang lộ trình khác. GA được phát triển bới Holland [9] xây dựng lời giới VRPTW theo dạng lá các bịt xâu hoặc nhiễm sắc thế. Phương pháp bắt đầu một đân cư oó nhiễm sắc thể ngẫu nhiên, chọn lựa các nhiễm sắc thể phú hợp hơn đẻ thực hiện lai tạo và trao đối chéo, đưa ra các thế hệ cem khác thể hệ cha nhưng kế thừa gen từ cha mẹ.
Quá trình này được tiếp tục clìo tới khi đạt tới một số lượng cỗ định các thế hệ hoặc đân cư đã đủ Gambardell di dua ra giải thuật MACS VRPTW vao năm 1999 [5], giải thuật này được xây đựng dựa trên nên tăng là hệ thông bầy kiến (ACS), hay tổng quát hơn lá ACO, một cách tiếp cận mẹo mới bắt nguồn từ hành vỉ của các chú kiến trong thực tế. Ý tưỡng của ACO là có một số lượng lớn. các chú kiếu nhân tạo hoạt động phối hợp với nhau để xây dựng một lời giải Kiến trong thực tế phổi hợp với nhau trong quả trình tìm thức ăn bằng cach để lại một lượng mùi trên đường đi để cho sác chủ kiến khác theo sau. Đề tối thiểu hóa số xe và thời gian đi cho VRPTW, giải thuật nảy gán mỗi mục tiêu cho một bây kiến vả hai bẩy kiến nảy trao ai thông tin thông qua việc cập nhit vét mui.
Cho dén nay, MACS “VRPTW duge coi là đú sức cạnh tranh với các phương pháp tốt nhất để giải VRPTW vẻ cả chất lượng lời giải và thời gian tính toàn. Từ các ứng dụng thực tế của VRPTW ta thấy có thể một khách hàng sẽ gố nhu cầu được phục vụ nhiều lần với nhiều khoảng thời gian kháe nhau, đơn vị chú quản có nhiều xe khác nhau. từ đỏ ta có biến thể cúa VRPTW là VRPMTW (VRP with Multiple Time Windows). Thue chất đây cũng chỉnh lá bai toán VRPTW nhưng có thêm một sỏ rẻng buôc như thêm nhiều khung thời gian cho một khách hàng (khách hàng muốn được phục vụ nhiều lân), có nhiều loại xe phục vu[H].
Cho tới nay chưa cá nhiều nghiên cứu, giải pháp cha VRTMTW mặc dũ tạ có thể lối các trợo cho VRPTW để giải bài loán này, Như đã nói ở trên, MACS— VRPTW lá một mẹo có thể nói là rất tốt đề giải VRPTW vì vậy Iuận vẫn này tập trung vào việc nghiên cửu, ép dụng MAOS vào VRPMTW Luận văn gồm năm chương, với các nội dưng sau: Chương 1. Trinh bảy một cách lổng quan về VRP trong dò để cập tới định nghĩa, các đặc điểm,các dạng vá mồ hình toán học của VRP. Cương 2: Tập trung nghiên cứu ding bai loón VRPTW. Trong chương này trình bảy khải niệm chưng, mô hình toán học và một số cách tiếp cận hiện có để giải VRPTW.
Chương 3: Trình bày vẻ giải thuật bầy kiên, từ nên táng sinli học tới áp dựng vào kiến nhần tạo. Chương này gững trình bảy cỗ giải thuật bây kiến đầu. tiến cho tới các giái thuật chính, có hiệu quả cao như Hệ thông bẩy kiển, Hệ thống kiến Max — Min, tối ru hóa bẩy kiến. Chương 4: Từ kiến thức nên táng ở chương hai và chương ba, chương, nảy trình bảy việc áp dụng giải thuật bảy kiến ACS đề giải VRPTW nói chung và để xuất giải thuật MACB để giải bài toán VRPMTW.
Đây có thể nói là phân nội dung chính của luận văn. Chương 5: Trinh bay các kết quả thứ nghiệm khi cài đặt giải thuật MACS - VRPMTW và chạy chương trình với các bộ đữ liệu, từ đỏ đưa ra kết luận và so sánh kết quả của phương pháp với phương pháp khác. LỜI NÓI BẦU 'Trong, các thập ký gắn đây, chúng ta đã thấy rất nhiều ứng dụng tối ưu. hóa dựa tiên các kỹ thuật lập trùnh toán học và các nghiên cứu cho bái toán quản lý việc phân phổi hàng hớa vả các dịch vụ trong các hệ thỏng phân tán.
Môt số lượng lớn các ứng dụng trong thực tế trên thể giỏi đã chỉ ra rằng việc sử dụng các thủ tục được máy tính hóa cho quá trinh phản phỏi hảng hỏa tiết kiệm được từ 5% tới 20% tổng chỉ phí vận chuyển. Từ đỏ, 48 thay ring vide tiết kiệm nảy trên hệ thông kinh té toản câu là rất ý nghĩa. Thực vậy, quá trình. vận chuyển liên quan tới tắt cả các giai đoạn sản xuất và phân phối và chiếm từ 10% toi 20% chi phi sin xuat hang hoa.
Sự thành công của việc sử dụng các kỷ thuật nghiên cứu vào hoạt động thực tiễn là do sự phát tiển của các hệ thống máy tính lừ cả phần miêm lẫn phần cũng và củng do việc tăng cường tích hợp các hệ thông thông tin vào các quy trình sản xuải. và thương Tnại. Một yếu tổ khác không kém phần quan trọng là sự phát triển của các công eu mô hình hỏa mang tinh giải thuật đã được cải đất trong các năm gần đầy. Thục vậy, các mô hình đã phán ảnh được tất cả các đặc điểm của bải toán phân tán nảy sinh trong các ứng dụng thực tế và các thuật toán tương tìng với bài toán đỏ, cách cài đặt trên máy tính đề tìm được một giải pháp tốt với thời gian tỉnh toán chấp nhận được.
Vi vậy báo cáo này xin trình bày về bài toán liền quan tới việc phân. phối hàng hóa giữa các kho hàng và khách hàng, được gọi là bài toán lô trình. VRP được Dantzig và Ramser [1] đưa ra vào năm 1959 với bài loán bạn đầu lá viêo phân phố gạs tới cóc tam báu lễ và lui ông cửng đã đề xuất được mỏ hình toán học, giải thuật đầu tiên cho bài toán. Ké tir dé cho tdi nay, VRP di dược vất nhiều nhà nghiên cứu quan tm, mở rộng, đưa ra các giải pháp, ứng dụng váo thực tế.
VIKP có rất nhiều biến thé whu CVRP, VRPTW, VRPB, VRPPD, trong đỏ VRPTW bài toan quan trọng, xuất hiện trong rất nhiều hệ thông phân tán. V'RPTW có thẻ được mô tả như là bài toán tỉnh toán gác lộ trình có chủ pú nhỏ nhất từ kho hàng tới một tập các khách hàng, cáo lộ trình phái thóa mãn mỗi khách hàng chỉ được thăm một lên bởi chỉ một xe hàng trong một khoảng thời gian nhất định, tất cỗ. whe lộ trình phải bất dâu từ kho hàng và kết thúc cũng tại kho bàng, tổng các yêu cảu của khách hàng không vượt quá dung lượng xe. VRPTW có nhiều mục tiểu ví dụ như tôi thiểu hỏa số lượng xe sử dụng, tổng, thời gian di và phục vụ là íL nhật, Một số ứng dụng của VRPTW trong thực lễ như với các bài loán: cung cấp địch vụ ngân hàng, phân phát thư, thu thập các sản pham do khach hàng trả lại, các địch vụ của nhà hàng ăn uống.
MỤC LỤC LOI NOI DAU. CAC TU VINT TAT. DANH SACH CAC HINH DANIT SACILCAC BANG. Chuong 1— TONG QUAN VAL VRP 1.
VRP với hạn chế về thời gia 1. VRP nhập xuất bảng kết hợp. VRP nhập xuất hàng đẳng thời (VREPD) 1. Cae m6 hinh eg bán cho VRE.
Mô hình luồng phương tiện. Mô hình luỗng hàng hóa 1. Mô bình phân hoạch tập. Chương 2 VRP VỚI HẠN CHẾ THỜI GIAN 2.
Giới thiệu chung, 2. Mô hình toán học. Các biển thẻ của VRPTW. Các phương pháp giải VRPTW 2.
Thuật toán giải đứng 2. Thuật toán mẹo cỗ điền a) Xây dụng lộ trình. b) Cai Gén 13 tinh 34. Thuật toán mẹo kết hợp.
Thuật toán siêu mieo a) Lời giải ban đầu. "— bì Tìm kiểm cục bộ với À.— Irlerolunge e) Mồ phóng tôi luyện. d) Tim kiểm Tabu.