Approaches for the Vehicle Routing Problem with Simultaneous Deliveries and Pickups

同時送收貨之車輛途程問題的演算法

陳正芳(Jeng-Fung Chen)

《工業工程學刊》 23卷2期 (2006/03) Pp. 141-150

https://doi.org/10.29977/JCIIE.200603.0005

摘要

回程取貨的車輛途程問題乃是在處理對不同顧客點的送貨或取貨。但在很多實務的情況中，同一顧客點可能會同時有送貨和取貨的需求。本研究對同時送收貨的車輛途程問題提出一個插入法為基的求解程序，並發展結合模擬退火法和禁忌名單的混合演算法來改善插入法所獲得的解。我們以文獻的問題對發展的平行插入法及混合演算法進行測試。測試結果顯示，我門的平行插入法優於文獻的插入法程序，混合演算法可有效地縮小平行插入法所獲得的解和最佳解的差距、可獲得優於文獻之萬用啓發式解法所求的解，且能很有效率地求得測試之小問題的最佳解。

關鍵字

模擬退火法 ； 禁忌名單 ； 車輛途程

並列摘要

The vehicle routing problem with backhauls deals with the delivery and pickup of goods at different customer locations. In many practical situations, however, the same customer may require both a delivery of goods from the central depot and a pickup of recycled/outdated items. In this paper, a parallel-insertion procedure is presented to obtain a quick solution for the vehicle routing problem with deliveries and pickups. A hybrid heuristic based on the simulated annealing method, tabu lists, and route improvement procedures is also proposed to improve the obtained solution. Computational characteristics of the proposed insertion-based procedure and the hybrid heuristic are evaluated through computational experiments. Computational experiments show that the parallel-insertion procedure obtains better solutions than those found in the open literature. Computational results also indicate that the proposed hybrid heuristic is able to reduce the gap between the obtained initial solution and optimal solution effectively and outperforms a metaheuristic tested in terms of solution quality, and is capable of obtaining optimal solutions very efficiently for small-scaled problems.

並列關鍵字

simulated annealing ； tabu list ； vehicle routing problem

參考文獻

Anily, S.,A. Federgruen(1990).A class of Euclidean routing problems with general route costs functions.Management Science.36,92-114.

Anily, S.(1996).The vehicle-routing problem with delivery and backhaul options.Naval Research Logistics.43,415-434.

Casco, D. O.,B. L. Golden,E. A. Wasil,L. Golden,A. Assad(1988).Vehicle routing with backhauls: models, algorithms, and case studies.Vehicle Routing, Methods and Studies.127-147.

Chen, J.-F.,T.-H. Wu(2005).Vehicle routing problem with simultaneous deliveries and pickups.To appear in Journal of the Operational Research Society.

Christofides, N.,A. Mingozzi,P. Toth,N. Christofides,A. Mingozzi,P. Toth,C. Sandi(1979).The vehicle routing problem.Combinatorial Optimization.315-338.