Approaches for the Vehicle Routing Problem with Simultaneous Deliveries and Pickups

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

10.29977/JCIIE.200603.0005

陳正芳(Jeng-Fung Chen)

模擬退火法 ； 禁忌名單 ； 車輛途程 ； simulated annealing ； tabu list ； vehicle routing problem

工業工程學刊

23卷2期（2006 / 03 / 01）

141 - 150

英文

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

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.

1. Anily, S.(1996).The vehicle-routing problem with delivery and backhaul options.Naval Research Logistics,43,415-434.
2. Anily, S.,A. Federgruen(1990).A class of Euclidean routing problems with general route costs functions.Management Science,36,92-114.
3. 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.
4. Chen, J.-F.,T.-H. Wu(2005).Vehicle routing problem with simultaneous deliveries and pickups.To appear in Journal of the Operational Research Society
5. Christofides, N.,A. Mingozzi,P. Toth,N. Christofides,A. Mingozzi,P. Toth,C. Sandi(1979).The vehicle routing problem.Combinatorial Optimization,315-338.
6. Crispim, J.,J. Brandão(2005).Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls.Journal of the Operational Research Society,1-7.
7. Deif, I.,L. Bodin(1984).Extension of the Clark and Wright algorithm for solving the vehicle routing problem with backhauling.Proceedings of the Conference on Computer Software Uses in Transportation and Logistics Management,75-96.
8. Dethloff, J.(2002).Relation between vehicle routing problems: an insertion heuristic for the vehicle routing problem with simultaneous delivery and pick-up applied to the vehicle routing problem with backhauls.Journal of the Operational Research Society,53,115-118.
9. Dethloff, J.(2001).Vehicle routing and reverse logistics|the vehicle routing problem with simultaneous delivery and pickup.OR Spektrum,23,79-96.
10. Duhamel, C.,J.-Y. Potvin,J.-M. Rousseau(1997).A tabu search heuristic for the vehicle routing problem with backhauls and time windows.Transportation Science,31,49-59.
11. Glover, F.(1989).Tabu search-part I.ORSA Journal on Computing,1,190-206.
12. Goetschalckx, M.,C. Jacobs-Blecha(1989).The Vehicle routing problem with backhauls.European Journal of Operational Research,42,39-51.
13. Golden, B.,E. Baker,J. Alfaro,J. Schaffer(1985).The vehicle routing problem with backhauling: two approaches.Proceedings of the Twenty-First Annual Meeting of S.E.TIMS,90-92.
14. Homberger, J.,H. Gehring(1999).Two evolutional metaheuristics for the vehicle routing problem with time windows.INFOR Journal,37,297-318.
15. Kirkpatrick, S.,C. Gelatt,M. Vecchi(1983).Optimization by simulated annealing.Science,220,671-680.
16. Kontoravdis, G.,J. Bard(1992).Improved heuristics for the vehicle routing problem with time windows.Working Paper
17. Lin, S.(1965).Computer solutions of the TSP.Bell System Technical Journal,44
18. Metropolis, N.,A. Rosenbluth,A. Teller(1953).Equation of state calculations by fast computing machines.The Journal of Chemical Physics,21,1087-1092.
19. Min, H.(1989).The multiple vehicle routing problem with simultaneous delivery and pick-up Points.Transportation Research,23A
20. Mingozzi, A.,S. Giorgi,R. Baldacci(1999).Exact method for the vehicle routing problem with backhauls.Transportation Science,33
21. Or, I.(1976).Traveling salesman-type combinational problems and their relation to the logistics of blood banking.Disertation
22. Osman, I. H.,N. Christofides(1994).Capacitated clustering problem by hybrid simulated annealing and tabu search.International Transactions in Operational Research,41
23. Potvin, J. Y.,G. Duhamel,F. Guertin(1996).A genetic algorithm for vehicle routing with backhauling.Applied Intelligence,6
24. Potvin, J. Y.,T. Kervahut,B. L. Garcia,J. M. Rousseau(1992).A tabu search heuristic for the vehicle routing problem with time windows.Technical Report CRT-855
25. Salhi, S.,G. Nagy(1999).A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling.Journal of the Operational Research Society,50
26. Thangiah, S. R.,J. Y. Potivn,T. Sun(1996).Heuristic approaches to vehicle routing with backhauls and time windows.Computers & Operations Research,23
27. Toth, P.,D. Vigo(1996).A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls.European Journal of Operational Research,113
28. Toth, P.,D. Vigo(1997).An exact algorithm for the vehicle routing problems with backhauls.Transportation Science,113
29. Yano, C.,T. Chan, L. Richter,T. Cutler,K. Murty,D. McGettigan(1987).Vehicle routing at quality stores.Interfaces,17,52-63.

1. (2013).A hybrid heuristic method for the fleet size and mix vehicle routing problem.工業工程學刊,30(3),181-189.
2. (2020).Designing a multi-objective model for a hazardous waste routing problem considering flexibility of routes and social effects.工業工程學刊,37(1),33-45.
3. (2022).Logistics distribution scheduling model of supply chain based on genetic algorithm.工業工程學刊,39(2),83-88.