Thuật Toán Bầy Kiến Giải Bài Toán VRP Cehicle Routing Problem Với ...

Có thể bạn quan tâm

Tải bản đầy đủ (.pdf) (108 trang)

Trang chủ

Thạc sĩ - Cao học

Công nghệ thông tin

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ạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.48 MB, 108 trang )

..bộ giáo dục v đo tạotrờng đại học bách khoa h nội--------------------------------------NGUYN TH HNGUYN TH HCÔNG NGHệ THÔNG TINTHUT TON BẦY KIẾN GIẢI BÀI TOÁN VRP(VEHICLE ROUTING PROBLEM) VỚI HẠN CHTHI GIANluận văn thạc Sỹ khoa học2007-2009H nội2009H Nội Năm 2009 bộ giáo dục v đo tạotrờ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 (VEHICLEROUTING PROBLEM) VI HN CH THI GIANChuyên ngnh :công nghệ thông tinluận văn thạc sĩ KHOA HọCngời hớng dẫn khoa học:PGS.TS. NGUYN C NGHAH Nội - Năm 2009 Trang 1Lời cam đoanTô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ếtqủ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ơngtrình nào khác.Nguyễn Thị Hà Trang 2Mục lụcLời cam đoan ...............................................................................................................1Mục lục........................................................................................................................2Danh mục thuật ngữ và từ viết tắt ...............................................................................5Danh mục hình ảnh .....................................................................................................7Danh mục bảng ...........................................................................................................8Mở đầu ........................................................................................................................9Chương 1 - BÀI TỐN LỘ TRÌNH VẬN TẢI (VRP) ........................................ 111.1. Những đặc trưng cơ bản của bài toán VRP.............................................. 111.1.1. Mạng lưới đường đi ................................................................................ 121.1.2. Các xe vận tải .......................................................................................... 131.1.3. Các khách hàng ....................................................................................... 131.1.4. Những yếu tố không xác định trong bài toán VRP ................................. 141.2. Các dạng cơ bản bài toán VRP .................................................................. 151.2.1. Bài toán VRP với hạn chế về trọng tải xe (CVRP) ................................. 161.2.2. VRP với hạn chế về thời điểm phục vụ (VRPTW) ................................. 161.2.3. VRP với nhận và chuyển hàng kết hợp (VRPPD) .................................. 171.2.4. VRP với chi phí phụ thuộc thời gian (TDVRP) ...................................... 181.2.5. VRP với yêu cầu đặt hàng chưa biết (DVRP)......................................... 191.3. Mơ hình tốn học cho bài tốn VRP ......................................................... 191.3.1. Mơ hình lưu lượng xe vận tải .................................................................. 201.3.2. Cải tiến mơ hình lưu lượng xe vận tải ..................................................... 261.4. Các phương pháp heuristic và metaheuristic giải bài toán VRP ........... 29 Trang 31.4.1. Các thuật toán heuristic cho bài toán VRP ............................................. 291.4.2. Một số thuật toán metaheuristic cho bài toán VRP................................. 341.5. Bài toán VRPTW và thuật toán Đa bầy kiến ........................................... 37Chương 2 - THUẬT TOÁN BẦY KIẾN ............................................................... 382.1. Giới thiệu thuật toán bầy kiến ................................................................... 382.1.1. Dạng bài toán cho thuật toán Bầy kiến. .................................................. 392.1.2. Đặc điểm chung của mỗi con kiến. ......................................................... 412.1.3. Cấu trúc chung của họ thuật toán Bầy kiến ............................................ 432.2. Bầy kiến cơ sở .............................................................................................. 452.3. Thuật toán Đa bầy kiến cho bài toán VRPTW ........................................ 502.3.1. Bầy kiến ACS-VEI và ACS-TIME ......................................................... 532.3.2. Lộ trình đường đi cho bài tốn VRP ....................................................... 572.3.3. Chương trình con sinh phương án ........................................................... 58Chương 3 - THỰC NGHIỆM TÍNH TỐN ......................................................... 613.1. Phân tích thiết kế chương trình ................................................................. 613.1.1. Xác định u cầu ..................................................................................... 613.1.2. Thiết kế chức năng chương trình ............................................................ 633.1.3. Các chức năng chính của chương trình ................................................... 633.1.4. Thiết kế file kết quả................................................................................. 653.2. Cài đặt chương trình ................................................................................... 703.2.1. Lớp Vertex: lưu dữ liệu về khách hàng................................................... 713.2.2. Lớp Ant: lớp trừu tượng biểu diễn các con kiến nói chung .................... 723.2.3. Lớp AntColony: lớp trừu tượng biểu diễn bầy kiến. .............................. 743.2.4. Lớp AntGraph ......................................................................................... 77 Trang 43.2.5. Lớp Ant4VRPTW ................................................................................... 783.2.6. Lớp ACS-TIME và ACS-VEI ................................................................. 803.2.7. Lớp MACS-VRPTW .............................................................................. 823.3. Kết quả thực nghiệm và đánh giá .............................................................. 833.3.1. Lựa chọn dữ liệu kiểm thử ...................................................................... 833.3.2. Lựa chọn tham số kiểm thử ..................................................................... 853.3.3. Lựa chọn điều kiện dừng......................................................................... 873.3.4. Kết quả thực nghiệm ............................................................................... 88Chương 4 - KẾT LUẬN .......................................................................................... 93Tài liệu tham khảo .....................................................................................................94Phụ lục: Kết quả thực nghiệm chi tiết .......................................................................96 Trang 5Danh mục thuật ngữ và từ viết tắtThuật ngữ tiếng anhThuật ngữ Tiếng việt và ý nghĩaExploitationKhai phá đường điExplorationThăm dị đường điglobal updatingCập nhật tồn cụclocal updatingCập nhật cục bộpheromone traitsDấu vết đặc trưnglocal searchTìm kiếm cục bộDepositLưu vếtconstruction graphĐồ thị xây dựng phương ánheuristic*Thuật toán cho phép xây dựng phương án tốtcủa bài toán trong khoảng thời gian ngắnPhương pháp heuristic được thiết kế để áp dụngmetaheuristic*cho nhiều bài toán khác nhau.Genetic Algorithms – GAThuật toán di truyềnTabu Search – TSThuật tốn tìm kiếm TabuAnt Colony Optimization – ACOThuật tốn Bầy kiến.Simulated Annealing - SAThuật tốn mơ phỏng luyện thépTraveling Salesman Problem – TSP Bài toán Người du lịchVehicle Routing Problem – VRPBài tốn lộ trình giao nhận hàng hóaCapacitated VRP – CVRPBài tốn VRP với ràng buộc trọng tải xeVRP with Pick-up and Delivery – Bài toán VRP với giao và nhận hàng kết hợpVRPPDWindows– Bài toán VRP với hạn chế thời điểm phục vụTime Dependent VRP –TDVRPBài tốn VRP với chi phí phụ thuộc thời gianDynamic VRP -DVRPBài toán VRP với yêu cầu đặt hàng chưa biếtVRPwithTimeVRPTW Trang 6Stochastic VRPBài toán VRP với thành phần chưa xác đinhAnt Colony System -ACSThuật toán bầy kiến cho bài toán TSP.MACS-VRPTWThuật toán Đa bầy kiến cho bài toán VRPTWGhi chú: Những từ đánh dấu * được giữ nguyên bản tiếng Anh do ý nghĩaq dài và khơng thể tìm thấy từ Tiếng việt tương ứng. Trang 7Danh mục hình ảnhHình 1-1: Minh họa thuật tốn trao đổi chéo ............................................................32Hình 1-2: Trường hợp riêng của trao đổi chéo .........................................................33Hình 2-1: Cấu trúc chung của các thuật tốn bầy kiến. ............................................45Hình 2-2: Lựa chọn đường đi dựa trên hai tham số ηij và τij. ....................................47Hình 2-3: Mơ hình thuật tốn Đa bầy kiến giải bài tốn VRPTW ...........................51Hình 2-4: Thuật tốn MACS-VRPTW .....................................................................52Hình 2-5: Thuật tốn cho ACS-TIME. .....................................................................54Hình 2-6: Thuật tốn cho ACS-TIME ......................................................................56Hình 2-7: Phương án cho bài tốn VRPTW .............................................................57Hình 2-8: Phương thức xây dựng phương án mới của mỗi con kiến. .......................59Hình 3-1: Cấu trúc file đầu vào .................................................................................61Hình 3-2: Mơ hình chương trình mơ phỏng .............................................................62Hình 3-3: Thiết kế chức năng chương trình ..............................................................63Hình 3-4: Cấu trúc file kết quả..................................................................................66Hình 3-5: Ví dụ file đầu ra cho các con kiến ............................................................68Hình 3-6: Cấu trúc file lưu kết quả cho Bầy kiến .....................................................70Hình 3-7: Cấu trúc lớp Ant .......................................................................................72Hình 3-8: Lớp AntColony .........................................................................................75Hình 3-9: Cấu trúc lớp AntGraph .............................................................................77Hình 3-10: Cấu trúc lớp Ant4VRPTW .....................................................................79Hình 3-11: Cài đặt hai lớp ACS-TIME và ACS-VEI ...............................................81Hình 3-12: Cấu trúc lớp MACS-VRPTW .................................................................82Hì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 ........89Hình 3-14: Đồ thị so sánh kết quả thực nghiệm với tác giả ......................................90Hình 3-15: Đồ thị so sánh kết quả với hai thuật toán CR và PB ..............................92 Trang 8Danh mục bảngBảng 3-1: Các thuộc tính của lớp Vertex ..................................................................71Bảng 3-2: Các biến tĩnh trong lớp Ant để lưu phương án tốt nhất ...........................72Bảng 3-3: Kết quả thực nghiệm tìm tham số ............................................................86Bảng 3-4: Kết quả chạy so với phương án tốt nhất hiện biết. ...................................88Bả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ả .................90Bảng 3-6: So sánh kết quả thực nghiệm với hai thuật toán CR và PB .....................91Bảng 3-7: Kết quả thực nghiệm chi tiết ....................................................................96 Trang 9Mở đầu1. 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 đóngvai trị rất quan trọng và được chun mơn hóa để tìm ra một đường đi vớichi 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à khoahọc đã tập trung nghiên cứu và xây dựng các thuật toán mới để đưa ra lờigiả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ápheuristics, metaheuristics, thuật toán bầy kiến,… để áp dụng được cho cácbài toán lớn.Ưu thế của thuật toán bầy kiến so với thuật tốn tối ưu hóa thơng thườnglà 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ấtngắn, với các thực nghiệm chứng minh trong trường hợp cho bài tố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áchtiếp cận hiện có để giải bài tốn VRPPhát triển thuật tốn, thực nghiệm tính tốn với thuật tố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 tốn bầy kiến, bàitố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 tốn VRPvới hạn chế thời gian. Từ đó phát triển thuật toán dựa trên sơ đồ thuật toánbầy kiến để bài bài toán VRP và tiến hành thực nghiệm tính tốn để đưa racá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ándự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ệmtính tố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 tố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 tốn VRP.Tìm hiểu thuật tố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 tốn.Thực nghiệm tính tố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ậttoá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ánVRP 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 11Chương 1 - BÀI TỐ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 đếnkhách hàng bằng một đồn xe vận tải. Rất nhiều vấn đề trong cuộc sống có thể quyvề bài tốn này, ví dụ như đưa thư, phân phối gas đến các đại lý, phân phối hànghó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 tốnVRP 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ụngmộ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ờigiải bài tốn cịn phải chú ý đến nhiều vấn đề ràng buộc như: trọng tải của xe, thờigian làm việc của lái xe và tối thiểu hóa chi phí vận chuyển.Bài tốn VRP có thể đưa về dạng một bài tốn quy hoạch tuyến tính, địnhnghĩ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 VRPCũng giống như những bài tố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ụctiêu của bài tốn VRP có thể rất phức tạp và đôi khi mâu thuẫn lẫn nhau. Mục tiêuchung 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 chiphí 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ượngxe. 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 12buộ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áchhàng phải chờ, khi đó, một khoản phí đền bù phải trả tùy theo hợp đồng. Trongnhữ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ữahai 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ácquyết định trong q trình tính tốn. Lời giải của bài toán được biểu diễn dựa trêntậ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ợpcủ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 ánphả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 tốn chobài tố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ácbiến. Với bài tố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áckhách hàng người đưa ra yêu cầu và nhận hàng.1.1.1. Mạng lưới đường điMạng lưới đường được biểu diễn như là một đồ thị với các kho và các kháchhàng là các đỉnh, và các cạnh biểu diễn khoảng cách (theo thời gian, khơng gianhoặ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ựatrê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 tốntì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ấtgiữ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 13khoả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 tốn VRP. Ví dụ như khi chi phí đi lại giữacá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 tốn VRP với chi phí phụ thuộc thời gian (TDVRP).1.1.2. Các xe vận tảiCá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ộccủa mơ hình bài tố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ácxe vận nói chung là khơng đồng nhất. Ngồ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ảitrọ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êucầ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ànghó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àngKhách hàng là trung tâm của bài toán VRP. Một phương án chấp nhận đượccủ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ằngviệ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ấtnhiều bài tốn VRP khác nhau. Ví dụ như khi mỗi khách hàng yêu cầu phải đượcgiao (delivery) một lượng hàng hóa hay thu gom hàng (pick-up) tại địa điểm củakhách hàng rồi vận chuyển đến nơi khác ta có bài tốn VRP với nhận và chuyểnhàng kết hợp (VRPPD). Khi tính đến koảng thời gian mà khách hàng có thể đượcphục vụ (time windows) ta có bài tốn VRP với hạn chế thời điểm phục vụ(VRPTW). Đối với bài tốn VRP có giới hạn thời điểm phục vụ, bài tốn cần nhiềuthêm rất nhiều xử lý, vì khi đó xe khơng thể đến muộn hơn thời gian cho phépnhưng nó có thể đến sớm và đợi cho đến giờ để phục vụ khách hàng. Trong trường Trang 14hợ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 tố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 tốn VRPTrong những dạng bài tố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ộcvà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 tốn dạng này được gọi là VRP khơng xác định (stochastic VRP). Nhữngyế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áchhà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ượnghàng hóa yêu cầu. Đặc biệt là trong trường hợp người lập kế hoạch kinh doanhmuố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ơngthườ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ắptớ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ướcnà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ấtnhiề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 .10F21FNgoài ra các yếu tố chưa biết có thể là thời gian vận chuyển và thời gianphụ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 trong1Xem thêm tại: M. Gendreau, G. Laporte, và R. S´eguin. Stochastic vehicle routing. EuropeanJournal of Operational Research, 88(1):3–12, 19962Xem thêm tại: L. Bianchi và các cộng sự. Metaheuristics for the vehicle routing problem withstochastic demands. Technical Report TR-12-04, IDSIA, Galleria 2, Manno, 6928, Switzerland,2004 Trang 15thự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ưởngrấ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ự ảnhhưở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óanếu chúng ta có thể giả sử là thời gian di chuyển gần như là hằng số trong nhữngkhoả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ạicá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ộcthờ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 tốn. Vấn đề này xuất hiện do sai số tính tốn khoảngcách giữa các khách hàng. Vì chi phí để tính tốn chính xác khoảng cách giữa cáckhá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ườnghợp, một mơ hình bài tố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 tốn lý thuyết. Hơn nữa thời gian di chuyển cịn phụ thuộcvà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áctuyến là khơng cố định thì việc đánh giá chính xác thời gian di chuyển sẽ trở thànhvấn đề lớn.1.2. Các dạng cơ bản bài toán VRPTrong 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ánVRP. 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ànhphầ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 161.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 tố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 tốn CVRP trở thànhbài tốn Người du lịch. Từ đó có thể thấy bài tốn CVRP là bài tốn NP-khó.Dạng cơ bản của bài tố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ụcvụ 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 tố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áchhà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ớimỗi cạnh trong A. Nếu ma trận chi phí là khơng đối xứng chúng ta có bài tốnCVRP khơng đối xứng.Bài tố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àitố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 tốn VRPTW vẫn cịn ràng buộc về trọng tải của xe chứa ngoài ravớ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 17khung 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ảnhrỗ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ậnchuyể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 tố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ụcvụ 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âmnhiề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 tốn VRPTWlà 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 chobài tốn khơng thể giữ nguyên kết quả khi đi theo thứ tự ngược lại dù chi phí đi lạicó là đối xứng hay khơng.Bài tốn VRPTW cũng là bài tốn NP-khó, thậm chí để tìm một phương ánchấ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àitốn NP-khó . Ràng buộc về thời điểm phục vụ trong bài toán VRPTW cần nhiều32Fthay đổi phức tạp trong các cách tiếp cận để giải chính xác bài tốn CVRP do đó kếtquả tính tố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ểnhà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ập3Xem 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 18trung ở 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êucầ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 tốn có thể vận chuyển hàng hóa hoặc đưa đónngười. Nếu cần vận chuyển người (ví dụ: xe bus đưa đón nhân viên) bài tốn lncó 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 tố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 q trình vận chuyển. Ví dụ như khi vận chuyển thư tín,thư ln đượ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àngln đượ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àngbuộ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 tố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 kiatrong thành phố phụ thuộc rất nhiều vào khoảng thời gian trong ngày. Đối với dạngnà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àmchi phí. Một cách tiếp cận cho bài tốn này là chia nhỏ thời gian trong ngày thành43Fcác khoảng nhỏ, thời gian (hay chi phí vận chuyển) thay đổi khi chuyển từ khoảngthờ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ể đếnnơ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 gianvậ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 tốn.4Xem 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 Trang 191.2.5. VRP với yêu cầu đặt hàng chưa biết (DVRP)Bài toán VRP với yêu cầu đặt hàng chưa biết là một mở rộng khác của bàitoán VRP chuẩn, với nhiều ràng buộc tương ứng với nhiều ứng dụng trong thực tế.Trong đó, u cầu phục vụ khơng hồn tồn được biết trước khi bắt đầu một tuyếnđương, yêu cầu này có thể xuất hiện trong q trình phân phối. Bởi vì một u cầumới có thể xuất hiện khi xe đang trong quá trình vận chuyển, quãng đường cần phảitính tốn lại ngay lập tức. Thơng thường trong thực tế sẽ có một hệ thống thơng tingiữa tài xế và trung tâm điều vận (nơi tính tốn lộ trình vận chuyển). Khi đó, trungtâm có thể thơng tin cho tài xế về nơi đến tiếp theo nhờ đó tại mỗi thời điểm tài xếcó thể biết một phần về lộ trình phải đi tiếp theo.Một ứng dụng điển hình cho bài toán này là hệ thống đưa thư, khi mà bưukiện được thu gom ở chỗ khách hàng và mang trở về trung tâm cho xử lý và chuyểnhàng. Trong q trình thu gom có thể xuất hiện u cầu mới của khách hàng, khi đólộ trình cần phải được tính tốn lại cho phù hợp.1.3. Mơ hình tốn học cho bài toán VRPĐối với họ bài toán VRP, rất nhiều mơ hình tốn học được xây dựng để phụcvụ cho việc thích kế các thuật tốn thích hợp. Trong phần này, em sẽ giới thiệu vềmơ hình tốn học cho bài tốn VRP cơ bản. Nhìn chung, có nhiều mơ hình tươngứng với các dạng khác nhau của bài tốn VRP, ở đây, em xin trình bày mơ hìnhtốn học lưu lượng xe vận tải (Vehicle flow model) được sử dụng nhiều để giảiquyết bài toán CVRP. Mặc dù thuật toán Đa bầy kiến mà em nghiên cứu khơng sửdụng trực tiếp mơ hình tốn học này nhưng việc tìm hiểu một mơ hình cơ bản sẽgiúp hiểu rõ hơn về bài tốn VRP. Từ đó sẽ giúp ích cho việc nghiên cứu hoặc cảitiến các thuật toán sau này. Ở phần sau em sẽ trình bày mộ số kỹ thuật cải tiến cũngnhư cách kết hợp thêm các ràng buộc hoặc thay đổi hàm mục tiêu để áp dụng chocác dạng bài toán khác. Trang 201.3.1. Mơ hình lưu lượng xe vận tảiMơ hình toán học phổ biến nhất được xây dựng cho bài tốn VRP là mơ hìnhlưu lượng xe vận tải (vehicle flow model). Trong mơ hình này, một tập các biếnnhận giá trị nguyên tương ứng với mỗi cạnh của đồ thị để biểu diễn số lần cạnh đóđược đi qua bởi một xe. Mơ hình này phù hợp cho trường hợp hàm chi phí của bàitốn là tổng của các chi phí tương ứng với mỗi cạnh. Đồng thời các ràng buộc củabài tốn có thể được biểu diễn một cách rõ ràng thông qua tập các cạnh và chi phítương ứng. Tuy nhiên, mơ hình này khơng thể giải quyết được nhiều vấn đề phứctạp trong thực tế, ví dụ như khi chi phí của một lộ trình phụ thuộc vào toàn bộ cácđỉnh được thăm hoặc thay đổi tùy thuộc vào loại xe được sử dụng cho lộ trình đó.Do đó khi có thêm ràng buộc, sẽ rất khó để sử dụnng mơ hình này vào việc thiết kếthuật toán.Để đơn giản ở đây ta quy ước mọi đồ thị được nhắc đến như là G(V, A) hayG(V, E) nếu khơng nói rõ đều là đồ thị đầy đủ.Đầu tiên mơ hình lưu lượng xe vận tải được xây dựng cho bài tốn CVRPkhơng đối xứng. Mơ hình này có dạng hai chỉ số (mỗi biến x được đặc trưng bởi cặpchỉ số i, j) tức là sử dụng O(n2) biến nhị phân x để chỉ ra nếu một xe đi qua mộtcạnh trên phương án tối ưu. Nói cách khác, biến xij bằng 1 nếu cạnh (i, j) ∈ A nằmtrong phương án tối ưu, và giá trị 0 nếu ngược lại.G = (V, A) là một đồ thị đầy đủ, V = {0... n} là tập các đỉnh (các đỉnh i = 1...n biểu diễn các khách hàng còn đỉnh 0 để chỉ kho chứa) và A là tập các cạnh (đườngnối tất cả các khách hàng và kho chứa).Một giá trị không âm cij tương ứng với mỗi cạnh (i, j) ∈ A biểu diễn chi phíphải trả khi đi từ đỉnh i đến đỉnh j. Nói chung, cạnh vịng (i, i) là khơng được phépxuất hiện trong phương án nên cij = +∞ với mọi i ∈ V. Trang 21Mỗi khách hàng thứ i (i = 1… n) tương ứng với một số không âm di biểudiễn số hàng hóa được yêu cầu, với kho chứa có d0 = 0. Với mỗi tập đỉnh S ⊆ V tacó d(S) =biểu diễn tổng yêu cầu của tập S đó.Ở kho chứ có một tập K xe vận tải, mỗi xe có trọng tải C. Để đảm bảo khảnăng thực hiện của bài toán, ta giả sử di ≤ C với mỗi i = 1… n. Mỗi xe chỉ thực hiệnnhiều nhất một lộ trình, và ta giả sử là K là không nhỏ hơn Kmin là số lượng xe nhỏnhất cần thiết để phục vụ tất cả mọi khách hàng.Với mỗi tập S ⊆ V \ {0}, ta có r(S) là số lượng nhỏ nhất xe cần để phục vụtất cả mọi khách hàng trong tập S. Ta có r(V \ {0}) = Kmin. Thông thường, r(S)được thay bằng giá trị cận dưới:Mơ hình VRP1:(1.1)Thỏa mãn:(1.2)(1.3)(1.4)(1.5)(1.6)(1.7) Trang 22Ràng buộc (1.2) và (1.3) là ràng buộc về bậc của một đỉnh, nghĩa là mỗi đỉnhchỉ có một đường đi vào và một đường đi ra (hay mỗi khách hàng chỉ được phục vụmột lần). Tương tự, ràng buộc (1.4) và (1.5) thể hiện bậc của đỉnh tương ứng vớikho chứa.Ràng buộc (1.6) thể hiện sự liên kết trong phương án tối ưu và ràng buộc vềtrọng tải của xe. Ràng buộc này quy định với mỗi nhát cắt (V \ S, S) tương ứng vớimột tập khách hàng S bất kỳ thì tập S được đi qua bởi khơng ít hơn r(S) cạnh ( vớir(S) là số lượng xe vận tải nhỏ nhất cần thiết để phục vụ tập S).Mơ hình trên có thể thay đổi để áp dụng cho bài tốn đối xứng SCVRP. Khiđó lộ trình là khơng có hướng, tức là với mỗi cạnh (i, j) ∈ A, i, j ≠ 0, chỉ một tronghai biến xij hoặc xji được sử dụng (ta chọn xij với i < j). Khi đó có thể có lộ trình chomột xe mà chỉ phục vụ một khách hàng, tức là sẽ có cạnh (0, i) hoặc (j, 0) được đihai lần, do đó x0j và xi0 có thể nhận giá trị 0, 1, 2.Mơ hình VRP2:(1.8)Thỏa mãn:(1.9)(1.10)(1.11)(1.12)(1.13) Trang 23Mơ hình hai chỉ số này có thể được chuyển về dạng một chỉ số (ij thay bằngcạnh e ∈ E) ta có mơ hình tương đương sau (trong đó δ(i) là tập cách đỉnh kề vớiđỉnh i).Mơ hình VRP3:(1.14)Thỏa mãn:(1.15)(1.16)(1.17)(1.18)(1.19)Mơ hình lưu lượng xe vận tải được sử dụng rộng rãi cho dạng cơ bản SCVRPvà ACVRP của bải toán VRP. Tuy nhiên đối với những dạng phức tạp hơn của bàitốn, mơ hình này có một vài điểm khơng thích hợp. Thứ nhất là nó chỉ có thể sửdụng khi chi phí của cả phương án là tổng của chi phí trên từng cạnh đã đi qua.Ngồi ra mơ hình này cũng khơng cho biết xe nào xe đi qua một cạnh xác định. Dođó nó khơng phù hợp nếu chi phí phụ thuộc vào loại xe được sử dụng.Để tăng thêm tính ứng dụng cho mơ hình này, ta có thể biến đổi mơ hình đểchỉ ra loại xe đi trên từng cạnh (quãng đường giữa hai khách hàng). Khi đó có thểthêm nhiều ràng buộc tương ứng với các bài tốn thực tế. Một mơ hình như vậyđược gọi là mơ hình lưu lượng xe vận tải ba chỉ số. Mơ hình này sửa dụng O(n2K)biến nhị phân x: biến xijk biểu diễn số lần cạnh (i, j) ∈ A được đi qua bởi xe thứ k (k= 1… K) trong phương án tối ưu. Ngồi ra cịn có O(nK) biến nhị phân y: biến yik (i

Tài liệu liên quan

luận văn: THUẬT TOÁN PHỎNG BẦY KIẾN GIẢI BÀI TOÁN K-MEDIAN doc
- 87
- 876
- 1
Luận văn: Thuật toán phỏng bầy kiến giải bài toán K-Median pdf
- 87
- 597
- 0
bai:on tap cac phep tinh voi so do thoi gian
- 11
- 1
- 0
Tiểu luận môn Thuật Toán và Phương Pháp Giải Quyết Vấn Đề THUẬT TOÁN TỐI ƯU BẦY KIẾN TRONG BÀI TOÁN NGƯỜI DU LỊCH
- 30
- 730
- 2
Thuật toán phỏng bầy kiến giải bài toán k median
- 87
- 188
- 0
Giải thuật bầy kiến giải bài toán VRP với hạn chế thời gian (VRPMTW)
- 88
- 589
- 14
Thuật toán trình bày kiến giải bài toán cây khung chi phí lộ trình nhỏ nhất
- 65
- 253
- 0
Một thuật toán tối ưu đàn kiến giải bài toán điều phối xe
- 66
- 87
- 0
Luận văn thạc sĩ kỹ thuật phần mềm: Một thuật toán tối ưu đàn kiến giải bài toán điều phối xe
- 66
- 61
- 0
Một thuật toán tối ưu đàn kiến giải bài toán điều phối xe
- 66
- 33
- 0