具載貨量限制取卸貨途程問題的啟發式演算法

Heuristic Algorithms for Capacity constrained Pickup and Delivery Vehicle Routing Problems

黃馨怡(Hsin-Yi Huang)

指導教授 ： 楊烽正

國立臺灣大學/工學院/工業工程學研究所/碩士(2006年)

https://doi.org/10.6342/NTU.2006.03185

摘要

隨著都會區點對點郵件遞送需求的遞增，具載貨量限制取卸貨途程的應用問題日益重要。本研究針對該問題提出數種有效的啟發式求解演算法，在短時間求得可以接受的較佳解。具載貨量限制的取卸貨途程問題較車輛途程問題多了一對一先取後卸和車輛載貨量的限制。求解目標是車行途程最短化。本研究提出五種啟發式解建構法和四種解改進法。解建構方法，係以逐步添加取、卸貨點的方式，在不違反限制條件下選取和插入建構中的途程。各種方法的差異，在選擇時是否有考量取或卸的屬性，在插入時則都須進行限制條件的驗證。改善法則仿車輛途程的局部修改法，在不違反限制的情況下進行解品質改善。據此，求解模式可分為先建構後改進二階段模式和建構與改進同步的單階段模式。前者是使用解建構法完成一可行車行途程再使用解改進法改善解品質。單階段的求解模式則是在解建構過程中，每加入一運貨點便進行已完成的局部路線改進。此外，具載貨量限制的取卸貨途程問題目前並無公用的標竿問題，本研究在不改變最佳途程的前提下，轉換TSP-LIB內已知最佳解的旅行推銷員問題成為具載貨量限制的取卸貨途程問題，以測試演算效率。結果顯示本研究所提的演算法可在短時間內，找到可以接受的較佳解。

關鍵字

旅行推銷員問題 ； 一對一取卸貨途程問題

並列摘要

Due to the increasing of point-to-point parcel deliveries in metropolitan area, capacity constrained pickup and delivery vehicle routing problems become popular. This paper presents several algorithms and methods for constructing and improving solutions. Compared with traditional Vehicle Routing Problem, this problem has introduced a one-follow-one precedence constraint on the routing sequence and a vehicle capacity constraint along the routing. Customers are partitioned into a pickup and delivery ones and paired with a pickup and a delivery customer. A vehicle having a limited parcel capacity starts from a depot and visits each customer exactly once with each pickup customer visited before the delivery target customer. The objective is to minimize the route length. This research proposes five route constructing algorithms and four improving methods. In addition, two computation modes are presented to solve this problem using these algorithms and methods: 1) two-stage mode, constructing a route then improving it, and 2) single-stage mode, constructing and improving the route step by step. Benchmarks of TSP-LIB are adopted and converted into capacity constrained pickup and delivery vehicle routing problems without changing the optimum routing solutions. The proposed constructing algorithms and improving methods are crossly combined to establish various computation cases to solve the numerical problems. Results are compared for those proposed algorithms and methods and conclusions are addressed.

並列關鍵字

Vehicle Routing Problem ； VRP ； TSP ； Pickup and delivery Vehicle Routing Problem ； PDVRP

參考文獻

2.許競嘉，2003，宅配業貨物配送路線規劃問題之研究，國立成功大學交通管理科學研究所碩士論文

3.Nagy, G. and Salhi, S., “Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries,” European Journal of Operation Research, Vol. 162, pp.126-141, 2005.

4.Hernández-Pérez, H. and Salazar-González, J., “A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery,” Discrete Applied Mathematics, Vol. 145, pp.126-139, 2004.

5.Bruun, A., Worsoe, U., and Pagh, M.H., “Traveling salesman with pickup and delivery”, technical report, 2003.

6.Renaud, J., Boctor, F. F. and Laporte, G., “Perturbation heuristics for the pickup and delivery traveling salesman problem,” Computers and Operations Research, Vol.29, pp.1129-1141, 2002.