Xemtailieu Tải về Thuật toán bầy kiến giải bài toán vrp (cehicle 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 THỊ HÀ NGUYỄN THỊ HÀ C¤NG NGHÖ TH¤NG TIN THUẬT TOÁN BẦY KIẾN 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 2007-2009 Hμ néi 2009 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 THỊ HÀ THUẬT TOÁN BẦY KIẾN GIẢI BÀI TOÁN VRP (VEHICLE ROUTING PROBLEM) VỚI HẠN CHẾ THỜI GIAN Chuyªn ngμnh : c«ng nghÖ th«ng tin luËn v¨n th¹c sÜ KHOA HäC ng−êi h−íng dÉn khoa häc: PGS.TS. NGUYỄN ĐỨC NGHĨA Hμ Néi - N¨m 2009 Trang 1 Lời cam đoan Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết qủa nêu trong luận văn là trung thực và chưa từng được ai công bố trong bất kì công trình nào khác. Nguyễn Thị Hà Trang 2 Mục lục Lời cam đoan ...............................................................................................................1 Mục lục........................................................................................................................2 Danh mục thuật ngữ và từ viết tắt ...............................................................................5 Danh mục hình ảnh .....................................................................................................7 Danh mục bảng ...........................................................................................................8 Mở đầu ........................................................................................................................9 Chương 1 - BÀI TOÁN LỘ TRÌNH VẬN TẢI (VRP) ........................................ 11 1.1. Những đặc trưng cơ bản của bài toán VRP.............................................. 11 1.1.1. Mạng lưới đường đi ................................................................................ 12 1.1.2. Các xe vận tải .......................................................................................... 13 1.1.3. Các khách hàng ....................................................................................... 13 1.1.4. Những yếu tố không xác định trong bài toán VRP ................................. 14 1.2. Các dạng cơ bản bài toán VRP .................................................................. 15 1.2.1. Bài toán VRP với hạn chế về trọng tải xe (CVRP) ................................. 16 1.2.2. VRP với hạn chế về thời điểm phục vụ (VRPTW) ................................. 16 1.2.3. VRP với nhận và chuyển hàng kết hợp (VRPPD) .................................. 17 1.2.4. VRP với chi phí phụ thuộc thời gian (TDVRP) ...................................... 18 1.2.5. VRP với yêu cầu đặt hàng chưa biết (DVRP)......................................... 19 1.3. Mô hình toán học cho bài toán VRP ......................................................... 19 1.3.1. Mô hình lưu lượng xe vận tải .................................................................. 20 1.3.2. Cải tiến mô hình lưu lượng xe vận tải ..................................................... 26 1.4. Các phương pháp heuristic và metaheuristic giải bài toán VRP ........... 29 Trang 3 1.4.1. Các thuật toán heuristic cho bài toán VRP ............................................. 29 1.4.2. Một số thuật toán metaheuristic cho bài toán VRP................................. 34 1.5. Bài toán VRPTW và thuật toán Đa bầy kiến ........................................... 37 Chương 2 - THUẬT TOÁN BẦY KIẾN ............................................................... 38 2.1. Giới thiệu thuật toán bầy kiến ................................................................... 38 2.1.1. Dạng bài toán cho thuật toán Bầy kiến. .................................................. 39 2.1.2. Đặc điểm chung của mỗi con kiến. ......................................................... 41 2.1.3. Cấu trúc chung của họ thuật toán Bầy kiến ............................................ 43 2.2. Bầy kiến cơ sở .............................................................................................. 45 2.3. Thuật toán Đa bầy kiến cho bài toán VRPTW ........................................ 50 2.3.1. Bầy kiến ACS-VEI và ACS-TIME ......................................................... 53 2.3.2. Lộ trình đường đi cho bài toán VRP ....................................................... 57 2.3.3. Chương trình con sinh phương án ........................................................... 58 Chương 3 - THỰC NGHIỆM TÍNH TOÁN ......................................................... 61 3.1. Phân tích thiết kế chương trình ................................................................. 61 3.1.1. Xác định yêu cầu ..................................................................................... 61 3.1.2. Thiết kế chức năng chương trình ............................................................ 63 3.1.3. Các chức năng chính của chương trình ................................................... 63 3.1.4. Thiết kế file kết quả................................................................................. 65 3.2. Cài đặt chương trình ................................................................................... 70 3.2.1. Lớp Vertex: lưu dữ liệu về khách hàng................................................... 71 3.2.2. Lớp Ant: lớp trừu tượng biểu diễn các con kiến nói chung .................... 72 3.2.3. Lớp AntColony: lớp trừu tượng biểu diễn bầy kiến. .............................. 74 3.2.4. Lớp AntGraph ......................................................................................... 77 Trang 4 3.2.5. Lớp Ant4VRPTW ................................................................................... 78 3.2.6. Lớp ACS-TIME và ACS-VEI ................................................................. 80 3.2.7. Lớp MACS-VRPTW .............................................................................. 82 3.3. Kết quả thực nghiệm và đánh giá .............................................................. 83 3.3.1. Lựa chọn dữ liệu kiểm thử ...................................................................... 83 3.3.2. Lựa chọn tham số kiểm thử ..................................................................... 85 3.3.3. Lựa chọn điều kiện dừng......................................................................... 87 3.3.4. Kết quả thực nghiệm ............................................................................... 88 Chương 4 - KẾT LUẬN .......................................................................................... 93 Tài liệu tham khảo .....................................................................................................94 Phụ lục: Kết quả thực nghiệm chi tiết .......................................................................96 Trang 5 Danh mục thuật ngữ và từ viết tắt Thuật ngữ tiếng anh Thuật ngữ Tiếng việt và ý nghĩa Exploitation Khai phá đường đi Exploration Thăm dò đường đi global updating Cập nhật toàn cục local updating Cập nhật cục bộ pheromone traits Dấu vết đặc trưng local search Tìm kiếm cục bộ Deposit Lưu vết construction graph Đồ thị xây dựng phương án heuristic* Thuật toán cho phép xây dựng phương án tốt của bài toán trong khoảng thời gian ngắn Phương pháp heuristic được thiết kế để áp dụng metaheuristic* cho nhiều bài toán khác nhau. Genetic Algorithms – GA Thuật toán di truyền Tabu Search – TS Thuật toán tìm kiếm Tabu Ant Colony Optimization – ACO Thuật toán Bầy kiến. Simulated Annealing - SA Thuật toán mô phỏng luyện thép Traveling Salesman Problem – TSP Bài toán Người du lịch Vehicle Routing Problem – VRP Bài toán lộ trình giao nhận hàng hóa Capacitated VRP – CVRP Bài toán VRP với ràng buộc trọng tải xe VRP with Pick-up and Delivery – Bài toán VRP với giao và nhận hàng kết hợp VRPPD Windows – Bài toán VRP với hạn chế thời điểm phục vụ Time Dependent VRP –TDVRP Bài toán VRP với chi phí phụ thuộc thời gian Dynamic VRP -DVRP Bài toán VRP với yêu cầu đặt hàng chưa biết VRP with Time VRPTW Trang 6 Stochastic VRP Bài toán VRP với thành phần chưa xác đinh Ant Colony System -ACS Thuật toán bầy kiến cho bài toán TSP. MACS-VRPTW Thuật toán Đa bầy kiến cho bài toán VRPTW Ghi chú: Những từ đánh dấu * được giữ nguyên bản tiếng Anh do ý nghĩa quá dài và không thể tìm thấy từ Tiếng việt tương ứng. Trang 7 Danh mục hình ảnh Hình 1-1: Minh họa thuật toán trao đổi chéo ............................................................32 Hình 1-2: Trường hợp riêng của trao đổi chéo .........................................................33 Hình 2-1: Cấu trúc chung của các thuật toán bầy kiến. ............................................45 Hình 2-2: Lựa chọn đường đi dựa trên hai tham số ηij và τij. ....................................47 Hình 2-3: Mô hình thuật toán Đa bầy kiến giải bài toán VRPTW ...........................51 Hình 2-4: Thuật toán MACS-VRPTW .....................................................................52 Hình 2-5: Thuật toán cho ACS-TIME. .....................................................................54 Hình 2-6: Thuật toán cho ACS-TIME ......................................................................56 Hình 2-7: Phương án cho bài toán VRPTW .............................................................57 Hình 2-8: Phương thức xây dựng phương án mới của mỗi con kiến. .......................59 Hình 3-1: Cấu trúc file đầu vào .................................................................................61 Hình 3-2: Mô hình chương trình mô phỏng .............................................................62 Hình 3-3: Thiết kế chức năng chương trình ..............................................................63 Hình 3-4: Cấu trúc file kết quả..................................................................................66 Hình 3-5: Ví dụ file đầu ra cho các con kiến ............................................................68 Hình 3-6: Cấu trúc file lưu kết quả cho Bầy kiến .....................................................70 Hình 3-7: Cấu trúc lớp Ant .......................................................................................72 Hình 3-8: Lớp AntColony .........................................................................................75 Hình 3-9: Cấu trúc lớp AntGraph .............................................................................77 Hình 3-10: Cấu trúc lớp Ant4VRPTW .....................................................................79 Hình 3-11: Cài đặt hai lớp ACS-TIME và ACS-VEI ...............................................81 Hình 3-12: Cấu trúc lớp MACS-VRPTW .................................................................82 Hình 3-13: Đồ thị so sánh kết quả thực nghiệm với kết quả tốt nhất hiện biết ........89 Hình 3-14: Đồ thị so sánh kết quả thực nghiệm với tác giả ......................................90 Hình 3-15: Đồ thị so sánh kết quả với hai thuật toán CR và PB ..............................92 Trang 8 Danh mục bảng Bảng 3-1: Các thuộc tính của lớp Vertex ..................................................................71 Bảng 3-2: Các biến tĩnh trong lớp Ant để lưu phương án tốt nhất ...........................72 Bảng 3-3: Kết quả thực nghiệm tìm tham số ............................................................86 Bảng 3-4: Kết quả chạy so với phương án tốt nhất hiện biết. ...................................88 Bảng 3-5: So sánh kết quả thực nghiệm tốt nhất với kết quả của tác giả .................90 Bảng 3-6: So sánh kết quả thực nghiệm với hai thuật toán CR và PB .....................91 Bảng 3-7: Kết quả thực nghiệm chi tiết ....................................................................96 Trang 9 Mở đầu 1. Tính cấp thiết của đề tài Trong họat động kinh doanh thương mại việc phân phối hàng hóa đóng vai trò rất quan trọng và được chuyên môn hóa để tìm ra một đường đi với chi phí hiệu quả nhất để phân phối hàng hóa trong cùng hệ thống mạng cung ứng.. Cùng với sự phát triển của máy tính và khoa học kỹ thuật, các nhà khoa học đã tập trung nghiên cứu và xây dựng các thuật toán mới để đưa ra lời giải cho những bài toán tối ưu với một chi phí nhất định như là: phương pháp heuristics, metaheuristics, thuật toán bầy kiến,… để áp dụng được cho các bài toán lớn. Ưu thế của thuật toán bầy kiến so với thuật toán tối ưu hóa thông thường là khả năng sinh ra một phương án tối ưu cục bộ tốt trong một thời gian rất ngắn, với các thực nghiệm chứng minh trong trường hợp cho bài toán TSP, VRP. 2. Mục đích ( các kết quả cần đạt được) Hiểu bài toán VRP với hạn chế thời gian, thuật toán bầy kiến và các cách tiếp cận hiện có để giải bài toán VRP Phát triển thuật toán, thực nghiệm tính toán với thuật toán và đánh giá được hiệu quả đạt được. 3. Ý nghĩa thực tiễn Cơ sở khoa học: đề tài tiếp cận các lý thuyết về thuật toán bầy kiến, bài toán lộ trình vận tải (VRP) và các cách tiếp cận hiện có để giải bài toán VRP với hạn chế thời gian. Từ đó phát triển thuật toán dựa trên sơ đồ thuật toán bầy kiến để bài bài toán VRP và tiến hành thực nghiệm tính toán để đưa ra các đánh giá về hiệu quả của thuật toán. Trang 10 Ý nghĩa thực tiễn: kết quả hướng đến của đề tài là phát triển thuật toán dựa trên sơ đồ thuật toán bầy kiến giải bài toán VRP, trên cơ sở thực nghiệm tính toán và đánh giá hiệu quả của thuật toán đưa ra đề xuất ứng dụng. 4. Các vấn đề cần giải quyết Tìm hiểu bài toán VRP với hạn chế thời gian. Tìm hiểu các cách tiếp cận hiện có để giải bài toán VRP. Tìm hiểu thuật toán bầy kiến. Phát triển thuật toán dựa trên sơ đồ thuật toán bầy kiến để giải bài toán. Thực nghiệm tính toán với thuật toán đã đề xuất để đánh giá kết quả đạt được. 5. Kết quả Cơ sở lý thuyết về: các dạng của bài toán VRP, thuật toán bày kiến, thuật toán đa bầy kiến, các cách tiếp cận để giải bài toán đã đề xuất. Xây dựng được phân mềm ứng dụng thuật toán đa bầy kiến cho bài toán VRP với hạn chế thời gian và thực nghiệm trên các bộ dữ liệu đề xuất (Solomon). 6. Cấu trúc của luận văn Luận văn gồm 4 chương, 102 trang, 15 hình, 7 bảng. Trang 11 Chương 1 - BÀI TOÁN LỘ TRÌNH VẬN TẢI (VRP) Bài toán VPR là bài toán về việc vận chuyển hàng hóa từ kho chứa hàng đến khách hàng bằng một đoàn xe vận tải. Rất nhiều vấn đề trong cuộc sống có thể quy về bài toán này, ví dụ như đưa thư, phân phối gas đến các đại lý, phân phối hàng hóa đến các siêu thị, xe buýt đưa đón nhân viên… Nói chung, giải quyết bài toán VRP tức là phải tìm ra tuyến đường tốt nhất để phục vụ tất cả khách hàng sử dụng một đoàn xe nhất định. Ngoài việc đảm bảo tất cả mọi khách hàng được phục vụ, lời giải bài toán còn phải chú ý đến nhiều vấn đề ràng buộc như: trọng tải của xe, thời gian làm việc của lái xe và tối thiểu hóa chi phí vận chuyển. Bài toán VRP có thể đưa về dạng một bài toán quy hoạch tuyến tính, định nghĩa bằng một hàm mục tiêu và một tập các ràng buộc. 1.1. Những đặc trưng cơ bản của bài toán VRP Cũng giống như những bài toán quy hoạch tuyến tính những đặc trưng cơ bản của bài toán VRP là hàm mục tiêu, các ràng buộc và các phương án. Mục tiêu của bài toán là tìm ra lời giải thích hợp nhất. Trong thực tế, mục tiêu của bài toán VRP có thể rất phức tạp và đôi khi mâu thuẫn lẫn nhau. Mục tiêu chung nhất là tối thiểu hóa chi phí vận chuyển. Mục tiêu này được biểu diễn như là một hàm của khoảng cách hay thời gian vận chuyển, chi phí này phụ thuộc vào chi phí cho việc vận hành xe và cho tài xế do đó nói chung cần phải tối thiểu số lượng xe. Một số mục tiêu khác có thể tính đến như là hiệu quả của xe, tính bằng tỷ lệ sử dụng của trọng tải xe (tỷ lệ càng cao thì hiệu quả sử dụng xe càng cao). Bên cạnh đó, cũng có thể có những hàm mục tiêu phức tạp hơn liên quan đến những ràng Trang 12 buộc mà nếu vi phạm phải trả một cái giá nào đó, ví dụ như xe đến chậm làm khách hàng phải chờ, khi đó, một khoản phí đền bù phải trả tùy theo hợp đồng. Trong những bài toán thực tế, có thể phải tính đến chi phí phụ thuộc vào loại đường đi: ví dụ như đi trong thành phố tốn thời gian và chi phí hơn so với đường cao tốc. Hàm mục tiêu là một hàm số bao gồm những biến tự do (biến quyết định), được quyết định bởi người lập kế hoạch: ví dụ như biến biểu diễn đoạn đường giữa hai khách hàng có trong lộ trình hay không, và biến phụ thuộc là kết quả của các quyết định trong quá trình tính toán. Lời giải của bài toán được biểu diễn dựa trên tập các biến quyết định cho đánh giá tốt nhất của hàm mục tiêu. Trong trường hợp của bài toán VRP, quyết định được đưa ra là thứ tự đưa hàng tới khách hàng, tức là tập các tuyến đường. Một tuyến đường bắt đầu từ kho chứa hàng và là một dãy có thứ tự của ghé thăm các khác hàng và thực hiện yêu cầu của họ. Một phương án phải thỏa mãn tính khả thi tức là không vi phạm các ràng buộc như ràng buộc về số lượng hàng không được vượt quá trọng tải xe. Để tìm giá trị của các biến quyết định, chúng ta cần một mô hình tín toán cho bài toán. Mô hình này được xây dựng dựa trên các ràng buộc biểu diễn mối quan hệ giữa các biến tự do và biến phụ thuộc và tập hợp các giá trị có thể nhận của các biến. Với bài toán VRP, mô hình này gồm có các thành phần chính như: hệ thống đường mô tả sự liên kết giữa các khách hàng và các kho chứa; tập xe vận tải và các khách hàng người đưa ra yêu cầu và nhận hàng. 1.1.1. Mạng lưới đường đi Mạng lưới đường được biểu diễn như là một đồ thị với các kho và các khách hàng là các đỉnh, và các cạnh biểu diễn khoảng cách (theo thời gian, không gian hoặc cả hai) giữa các đỉnh. Mô hình mạng lưới đường đi này có thể xây dựng dựa trên một bản đồ thực tế của khu vực chứa các kho và khách hàng. Một thuật toán tìm đường đi ngắn nhất có thể được sử dụng để tìm tất cả các đường đi ngắn nhất giữa các cặp đỉnh (theo thời gian hoặc không gian), dựa trên đó xây dựng ma trận Trang 13 khoảng cách. Tùy theo cách xây dựng khoảng cách giữa các đỉnh chúng ta có thể phát triển nhiều dạng khác nhau của bài toán VRP. Ví dụ như khi chi phí đi lại giữa các đỉnh thay đổi theo thời gian (đặc điểm phổ biến trong các thành phố như Hà Nội) ta có dạng bài toán VRP với chi phí phụ thuộc thời gian (TDVRP). 1.1.2. Các xe vận tải Các xe vận tải và các đặc tính của chúng được thể hiện trong các ràng buộc của mô hình bài toán. Đội xe này có thể là đồng nhất nếu tất cả xe là giống nhau về tính chất. Tuy nhiên trên thực tế hầu hết đặc tính của các xe là khác nhau do đó các xe vận nói chung là không đồng nhất. Ngoài các đặc tính quan trọng về trọng tải, giá vận chuyển, các đặc tính về máy móc như: chiều cao, khối lượng, chiều rộng, số trục… đều có thể được tính đến như là các ràng buộc cho xe. Ví dụ như xe tải có tải trọng lớn không thể đi vào thành phố vào giờ cao điểm. Ngoài ra cũng có thể có những phụ kiện trên xe dùng để tháo dỡ hàng cho những loại hàng đặc biệt theo yêu cầu của khách hàng. Tải trọng của xe có thể được biểu diễn theo tùy theo loại hàng hóa được vận chuyển (ví dụ như lít với xăng dầu, kilogram hoặc mét khối). 1.1.3. Các khách hàng Khách hàng là trung tâm của bài toán VRP. Một phương án chấp nhận được của bất kỳ dạng nào bài toán đều phải phục vụ được tất cả các khách hàng. Bằng việc khai thác các đặc điểm khác nhau của mỗi khách hàng ta có thể xây dựng rất nhiều bài toán VRP khác nhau. Ví dụ như khi mỗi khách hàng yêu cầu phải được giao (delivery) một lượng hàng hóa hay thu gom hàng (pick-up) tại địa điểm của khách hàng rồi vận chuyển đến nơi khác ta có bài toán VRP với nhận và chuyển hàng kết hợp (VRPPD). Khi tính đến koảng thời gian mà khách hàng có thể được phục vụ (time windows) ta có bài toán VRP với hạn chế thời điểm phục vụ (VRPTW). Đối với bài toán VRP có giới hạn thời điểm phục vụ, bài toán cần nhiều thêm rất nhiều xử lý, vì khi đó xe không thể đến muộn hơn thời gian cho phép nhưng nó có thể đến sớm và đợi cho đến giờ để phục vụ khách hàng. Trong trường Trang 14 hợp này, một khoản phí phạt có thể được tính đến khi xe đến chậm hơn giờ quy định. Khi đó hàm mục tiêu phải thay đổi để tính đến khoản tiền phạt này. Ngoài ra, đối với mỗi khách hàng còn cần phải tính đến thời gian bốc dỡ hoặc xếp hàng hóa, thời gian này phụ thuộc vào loại hàng hóa, số lượng khi đặt hàng và người bốc dỡ. Thời gian phụ vụ này được dùng để tính toán thời gian mà mỗi xe cần trước khi đi đến chỗ khách hàng kế tiếp. 1.1.4. Những yếu tố không xác định trong bài toán VRP Trong những dạng bài toán VRP trình bày ở trên, ta chưa nhắc đến vai trò của những yếu tố chưa xác định. Trong nhiều trường hợp hàm mục tiêu phụ thuộc vào nhiều yếu tố chưa xác định, khi đó hàm mục tiêu sẽ có tính biến thiên rất lớn. Lớp bài toán dạng này được gọi là VRP không xác định (stochastic VRP). Những yếu tố chưa biết có thể là có khách hàng hoặc không, khối lượng hàng hóa khách hàng yêu cầu hay thời gian di chuyển và thời gian phục vụ. Trong thực tế, các yếu tố chưa xác định thường là khách hàng hoặc lượng hàng hóa yêu cầu. Đặc biệt là trong trường hợp người lập kế hoạch kinh doanh muốn lập kế hoạch cho khoảng thời gian xa hơn so với dữ liệu hiện có. Thông thường, một công ty thường muốn lập kế hoạch vận chuyển trong một vài tháng sắp tới nhằm xây dựng chiến lược kinh doanh phù hợp. Các tuyến đường được lập trước này sẽ được sử dụng vào thực tế khi các yêu cầu của khách hàng xuất hiện. Vì tính ứng dụng thực tiễn cao như vậy nên lớp bày toán dạng này được nghiên cứu rất nhiều trong thời gian gần đây. Ví dụ như những nghiên cứu của M. Gendreau, G. Laporte, và R. S´eguin và của Bianchi . 1 0F 2 1F Ngoài ra các yếu tố chưa biết có thể là thời gian vận chuyển và thời gian phục vụ. Những yế tố này, đặc biệt là thời gian vận chuyển, thường xuất hiện trong 1 Xem thêm tại: M. Gendreau, G. Laporte, và R. S´eguin. Stochastic vehicle routing. European Journal of Operational Research, 88(1):3–12, 1996 2 Xem thêm tại: L. Bianchi và các cộng sự. Metaheuristics for the vehicle routing problem with stochastic demands. Technical Report TR-12-04, IDSIA, Galleria 2, Manno, 6928, Switzerland, 2004 Trang 15 thực tế tại các thành phố lớn và có mật độ giao thông cao như Hà Nội và TP. Hồ Chí Minh. Trên thực tế, sự biến đổi của thời gian vận chuyển này có thể ảnh hưởng rất lớn đến kết quả của các phương án đã được xây dựng cho bài toán. Sự ảnh hưởng của việc thời gian vận chuyển chưa xác định có thể được làm đơn giản hóa nếu chúng ta có thể giả sử là thời gian di chuyển gần như là hằng số trong những khoảng thời gian trong ngày. Điều này là hoàn toàn hợp lý do mật độ giao thông tại các thành phố thường rất cao ở giờ cao nhưng lại bình thường ở những khung giờ khác. Bài toán tiêu biểu cho những bài toán dạng này, VRP với chi phí phụ thuộc thời gian (TDVRP) sẽ được giới thiệu ở phần 1.2.4. Cuối cùng, trong nhiều trường hợp, yếu tố chưa xác định cần phải tính đến là do sai số trong mô hình bài toán. Vấn đề này xuất hiện do sai số tính toán khoảng cách giữa các khách hàng. Vì chi phí để tính toán chính xác khoảng cách giữa các khách thường là rất cao đối với một lượng khách hàng lớn, nên trong nhiều trường hợp, một mô hình bài toán được xây dựng dựa trên khoảng cách xấp xỉ giữa các đỉnh. Do đó khi áp dụng vào thực tế, thời gian vận chuyển có thể lớn hơn hoặc nhỏ hơn so với thời gian tính toán lý thuyết. Hơn nữa thời gian di chuyển còn phụ thuộc vào tài xế. Khi tuyến đường vận chuyển là cố định, tài xế sẽ “thạo đường” hơn và thời gian di chuyển nhanh hơn. Còn khi các khách hàng thay đổi nhiều dẫn đến các tuyến là không cố định thì việc đánh giá chính xác thời gian di chuyển sẽ trở thành vấn đề lớn. 1.2. Các dạng cơ bản bài toán VRP Trong phần này, em sẽ giới thiệu qua về một số dạng cơ bản của bài toán VRP. Những bài toán này được sinh ra bằng việc thêm các đặc trưng vào các thành phần cơ bản như mô hình đường đi, loại xe vận tải, và các khách hàng. Trang 16 1.2.1. Bài toán VRP với hạn chế về trọng tải xe (CVRP) Đây là dạng cơ bản nhất của bài toán VRP trong đó chỉ tính đến giới hạn về trọng tải của mỗi xe. Chú ý là nếu không có ràng buộc này, và giới hạn rằng tất cả mọi khách hàng phải được phục vụ trên một tuyến đường, bài toán CVRP trở thành bài toán Người du lịch. Từ đó có thể thấy bài toán CVRP là bài toán NP-khó. Dạng cơ bản của bài toán CVRP có các đặc điểm sau: Yêu cầu của khách hàng được biết trước Việc phân phối không bị chia nhỏ, tức là một khách hàng chỉ được phục vụ bởi tối đa một xe. Đội xe là đồng nhất và chỉ có duy nhất một kho chứa hàng. Mục tiêu là tối thiểu chi phí vận chuyển, thường được biểu diễn bằng quãng đường cần phải đi để phục vụ tất cả các khách hàng. Bài toán có thể được biểu diễn như là một bài toán đồ thị với G = (V,A) là một đồ thị đầy đủ, V = {0, ..., n} là tập các đỉnh (đỉnh i = 1,...,n biểu diễn khách hàng, đỉnh 0 là kho chứa) và A là tập các cạnh (đường nối tất cả các khách hàng và kho chứa). Số không âm di gắn với mỗi đỉnh biểu diễn số lượng hàng hóa yêu cầu, cùng với ma trận chi phí cij (biểu diễn khoảng cách hoặc thời gian) tương ứng với mỗi cạnh trong A. Nếu ma trận chi phí là không đối xứng chúng ta có bài toán CVRP không đối xứng. Bài toán CVRP là dạng được nghiên cứu nhiều nhất của bài toán VRP. Những nghiên cứu này sau đó thường được mở rộng để áp dụng cho các dạng bài toán khác có nhiều ý nghĩa thực tiễn hơn. 1.2.2. VRP với hạn chế về thời điểm phục vụ (VRPTW) Trong bài toán VRPTW vẫn còn ràng buộc về trọng tải của xe chứa ngoài ra với khách hàng thứ i có tương ứng với một khoảng thời gian [ai, bi], được gọi là Trang 17 khung thời gian phục vụ, và khoảng thời gian si là thời gian cần thiết để phục vụ. Dạng này của bài toán thường thấy trong thực tế khi khách hàng khó mà có thể rảnh rỗi trong mọi lúc để chờ được phục vụ. Khung thời gian có thể có đơn vị là phút, giờ hay ngày, tuy nhiên nó thường tương ứng với thời gian lập kế hoạch vận chuyển. Ví dụ như khi ta cần lập kế hoạch cho 5 ngày tới thì với khung thời gian là vài giờ, việc tính toán sẽ dễ hơn nhiều so với khi khung thời gian là vài phút. Hạn chế về thời điểm phục vụ này có thể ở dạng mềm tức là thời điểm phục vụ nếu bị vi phạm sẽ phải chịu một chi phí phạt nào đó, hoặc ở đạng cứng tức là không cho phép xe vận tải đến sau khung thời gian tương ứng và xe đến sớm phải đợi cho đến khi khách hàng sẵn sàng. Trên thực tế, dạng thứ hai được quan tâm nhiền hơn và đã có rất nhiều nghiên cứu trong vài thập kỷ gần đây. Do đó khi nhắc đến VRPTW, ta ngầm hiểu ràng buộc về thời điểm phục là không thể vi phạm. Một điểm nữa cần chú ý là với hạn chế khung thời gian phục vụ, ta đã đã ngầm định một thứ tự các khách hàng cần được phục vụ. Khi đó, bài toán VRPTW là không đối xứng dù ma trận giá có đối xứng hay không. Tức là một lộ trình cho bài toán không thể giữ nguyên kết quả khi đi theo thứ tự ngược lại dù chi phí đi lại có là đối xứng hay không. Bài toán VRPTW cũng là bài toán NP-khó, thậm chí để tìm một phương án chấp nhận được của bài toán với số lượng xe vận tải xác định cũng đã là một bài toán NP-khó . Ràng buộc về thời điểm phục vụ trong bài toán VRPTW cần nhiều 3 2F thay đổi phức tạp trong các cách tiếp cận để giải chính xác bài toán CVRP do đó kết quả tính toán thường tồi hơn nhiều. 1.2.3. VRP với nhận và chuyển hàng kết hợp (VRPPD) Trong dạng này, đội xe phải phục vụ một tập các yêu cầu về vận chuyển hàng hóa từ nơi này đến nơi khác. Trong đó, hàng hóa không nhất thiết phải tập 3 Xem chi tiết tại: M.W.P. Savelsbergh. Local search in routing problems with time windows. Annals of Operations Research, 4:285–305, 1985. Trang 18 trung ở kho chứa mà có thể phân bố ở tại các nút của mạng lưới đường đi. Một yêu cầu vận chuyển ở dạng này của bài toán là lấy hàng từ điểm nguồn và vận chuyển đến điểm đích. Với dạng này của bài toán có thể vận chuyển hàng hóa hoặc đưa đón người. Nếu cần vận chuyển người (ví dụ: xe bus đưa đón nhân viên) bài toán luôn có gắn với khung thời gian giới hạn phục vụ ở cả điểm nhận hàng và giao hàng, đồng thời phải có ràng buộc thể hiện sự không hài lòng của khách hàng khi phải chờ quá lâu ở điểm nhận hàng và ràng buộc thể hiện giới hạn về thời gian vận chuyển. Nếu vận chuyển hàng hóa, bài toán có thể đơn giản hơn so với vận chuyển người, tùy thuộc vào đặc tính của quá trình vận chuyển. Ví dụ như khi vận chuyển thư tín, thư luôn được vận chuyển đi từ bưu điện và mọi thư thu gom tại các hòm thư đều đưa về bưu điện. Hơn nữa, trong nhiều trường hợp có thể giả sử là việc giao hàng luôn được thực hiện trước khi nhận hàng, khi đó sẽ làm giảm sự ảnh hưởng của ràng buộc về trọng tải của xe. 1.2.4. VRP với chi phí phụ thuộc thời gian (TDVRP) Đây là một dạng mở rộng của dạng VRPTW trong môi trường thành phố. Trong bài toán TDVRP, chi phí trên mỗi cạnh của đồ thị thay đổi theo thời gian. Ràng buộc này thường thấy trong thực tế khi việc đi lại từ điểm này đến điểm kia trong thành phố phụ thuộc rất nhiều vào khoảng thời gian trong ngày. Đối với dạng này của bài toán cần phải chú ý đến việc xác định sự phụ thuộc thời gian của hàm chi phí. Một cách tiếp cận cho bài toán này là chia nhỏ thời gian trong ngày thành 4 3F các khoảng nhỏ, thời gian (hay chi phí vận chuyển) thay đổi khi chuyển từ khoảng thời gian này sang khoảng thời gian khác. Tuy nhiên cách tiếp cận này có thể dẫn đến trường hợp trái với cảm nhận thông thường, đó là khi một xe đi sau có thể đến nơi trước một xe đi trước đó dù 2 xe đi cùng một tuyến đường. Do đó hàm thời gian vận chuyển phải được xây dựng một cách cẩn thận trước khi bắt đầu tính toán. 4 Xem thêm: S. Ichoua, M. Gendreau, và J.-Y. Potvin. Vehicle dispatching with time-dependent travel times. European Journal of Operational Research, 144(2):379–396, 2003 Tải về bản full