HETEROGENEOUS VEHICLE ROUTING PROBLEM WITH SIMULTANEOUS PICKUP AND DELIVERY: MATHEMATICAL FORMULATIONS AND A HEURISTIC ALGORITHM

Öz

One of the most important operational decisions in the logistics management is to determine the vehicle routes serving the customers. The Vehicle Routing Problem (VRP) can be defined as the determination of the optimal routes which meet the delivery (or pickup) demands from the depot to the customers. In the real life applications of logistics, vehicles in a fleet may differ from each other. In addition, the requirements arising from customers/goods may reveal the necessity to use different vehicles. Besides, companies do care more about the management of reverse flow of products, semi-finished and raw materials because of their economic benefits and as well as legal and environmental liabilities. In this paper, a variant of the VRP is considered with heterogeneous fleet of vehicles and simultaneous pickup and delivery. This problem is referred to Heterogeneous Vehicle Routing Problem with Simultaneous Pickup and Delivery (HVRPSPD). The HVRPSPD can be defined as determining the routes and the vehicle types on each route while minimizing the total cost. In this paper, a polynomial sized flow-based mathematical model is proposed for the HVRPSPD. Since the HVRPSPD is in the class of NP-hard problems, it is difficult to find the optimal solution in a reasonable time even for the moderate size problems. Therefore, a simple and constructive heuristic algorithm is proposed to solve the medium and large scale HVRPSPD s. This algorithm is the adaptation of very well-known Clarke-Wright Savings approach, which has originally developed for the VRP, to the HVRPSPD. The performances of the proposed mathematical model and the heuristic algorithm have been examined on the test problems. 

Anahtar Kelimeler

• Heterogeneous fleet
• simultaneous pickup and delivery
• vehicle routing problem
• mixed integer programming formulation
• heuristics
• Clarke-Wright savings algorithm

HETEROJEN EŞ-ZAMANLI TOPLA-DAĞIT ARAÇ ROTALAMA PROBLEMİ: MATEMATİKSEL MODELLER VE SEZGİSEL BİR ALGORİTMA

Öz

Lojistik yönetiminde en önemli operasyonel kararlardan birisi müşterilere hizmet verecek araç rotalarının belirlenmesidir. Araç Rotalama Problemi (ARP), bir depodan müşterilerin dağıtım (toplama) taleplerini karşılayacak en uygun rotaların belirlenmesi olarak tanımlanabilir. Gerçek hayat lojistik uygulamalarında, filoda bulunan araçlar farklı özelliklerde olabilirler. Ayrıca müşterilerden/taşınanlardan kaynaklı gereklilikler de farklı özellikte araç kullanımı zorunluluğunu ortaya çıkarabilir. Bunun yanısıra firmalar, mamul, yarı mamul ve hammaddelerin tersine akışının yönetimini de hem ekonomik getirisi hem de yasal ve çevresel yükümlülüklerinden dolayı daha fazla önemsemektedirler. Bu makalede, heterojen araç filosunun bulunduğu ve müşterilerin dağıtım ve toplama taleplerinin eşzamanlı gerçekleştiği durumların birlikte dikkate alındığı bir ARP türü üzerinde çalışılmıştır. Bu problem Heterojen Eşzamanlı Topla-Dağıt Araç Rotalama Problemi (HETD-ARP) olarak adlandırılmıştır. HETD-ARP, toplam maliyeti enküçükleyen araç rotalarının ve herbir rotada kullanılan araç tipinin belirlenmesi olarak tanımlanabilir. Problem için polinom sayıda kısıta sahip akış tabanlı bir matematiksel model önerilmiştir. HETD-ARP, NP-zor problemler sınıfında olduğundan dolayı makul sürelerde orta boyutlu problemlere bile en iyi çözümü bulmak zordur. Bu nedenle bu makalede orta ve büyük boyutlu HETD-ARP’nin çözümü için basit bir kurucu sezgisel algoritma önerilmiştir. Bu algoritma, kaynaklarda ARP için önerilen Clarke-Wright Tasarruf (CWT) algoritmasının HETD-ARP için uyarlanmış halidir. Önerilen matematiksel modelin ve sezgisel algoritmanın etkinliği test problemleri üzerinde incelenmiştir.

Anahtar Kelimeler

• Heterojen filo
• eşzamanlı topla-dağıt
• araç rotalama problemi
• karma tamsayılı matematiksel modelleme
• sezgiseller
• Clarke-Wright tasarruf algoritması

Kaynakça

1. Dantzig, G.B., Ramser, J.H., “The truck dispatching problem”, Management Science, Cilt 6, No 1, 80–91, 1959.
2. Haimovich, M., Rinnooy Kan, A.H.G., Stougie, L., “Analysis of heuristic routing problems”, Vehicle Routing: Methods and Studies, Editor: Golden B. et al., North Holland, Amsterdam, 47–61, 1988.
3. Paschos, V.Th., “An overview on polynomial approximation of NP-hard problems”, Yugoslav Journal of Operations Research, Cilt 19, No 1, 3-40, 2009.
4. Hoff, A., Andersson, H., Christiansen, M., Hasle, G., Løkketangen, A., “Industrial aspects and literature survey: Fleet composition and routing”, Computers and Operations Research, Cilt 37, 2041-2061, 2010.
5. Toth, P., Vigo, D., The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics, Philadelphia, PA, A.B.D, 2002.
6. Golden, B., Assad, A., Levy, L., Gheysens, F., “The fleet size and mix vehicle routing problem”, Computers and Operations Research, Cilt 11, 49-66, 1984.
7. Gheysens. F., Golden. B., Assad. A., “A new heuristic for determining fleet size and composition”, Mathematical Programming Study, Cilt 26, 233-6, 1986.
8. Salhi, S., Rand, G.K., “Incorporating vehicle routing into the vehicle fleet composition problem”, European Journal of Operational Research, Cilt 66, 313-30, 1993.

9. Taillard, E.D., “A heuristic column generation method for the heterogeneous fleet VRP”, RAIRO - Operations Research, Cilt 33, No 1, 1-14, 1999.
10. Tarantilis, C.D., Kiranoudis, C.T., Vassiliadis, V.S., “A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem”, European Journal of Operational Research, Cilt 152, 148-58, 2004.
11. Baldacci, R., Toth, P., Vigo, D., “Exact algorithms for routing problems under vehicle capacity constraints”, Annals of Operations Research, Cilt 175, No 1, 213-245, 2010.
12. Parragh, S.N., Doerner, K.F., Hartl, R.F., “A survey on pickup and delivery problems Part I: Transportation between customers and depot”, Journal fur Betriebswirtschaft, Cilt 58, No 1, 21-51, 2008.
13. Parragh, S.N., Doerner, K.F., Hartl, R.F., “A survey on pickup and delivery problems Part II: Transportation between pickup and delivery locations”, Journal fur Betriebswirtschaft, Cilt 58, No 1, 81-117, 2008.
14. Min, H., “The multiple vehicle routing problem with simultaneous delivery and pickup points”, Transportation Research A, Cilt 23, No 5, 377-386, 1989.
15. Halse, K., Modeling and solving complex vehicle routing problems, Ph.D thesis, Technical University of Denmark, Institute of Mathematical Statistics and Operations Research, 1992.
16. Ropke, S., Pisinger., D., “A unified heuristic for a large class of vehicle routing problems with backhauls”, European Journal of Operational Research, Cilt 171, No 3, 750-775, 2006.
17. Bianchessi, N., Righini G., “Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery”, Computers and Operations Research, Cilt 34, No 2, 578-594, 2007.
18. Ai, J.T., Kachitvichyanukul, V., “A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery”, Computers and Operations Research, Cilt 36, 1693-1702, 2009.
19. Subramanian, A., Drummond, L.M.A., Bentes, C., Ochi, L.S., Farias, R., “A parallel heuristic for the Vehicle Routing Problem with Simultaneous Pickup and Delivery”, Computers and Operations Research, Cilt 37, No 11, 1899-1911, 2010.
20. Subramanian, A., Uchoa, E., Pessoa, A.A., Ochi, L.S., “Branch-and-cut with lazy separation for the vehicle routing problem with simultaneous pickup and delivery”, Operations Research Letters, Cilt 39, 338-341, 2011.
21. Karaoğlan, İ., Dağıtım Ağları Tasarımında Yer Seçimi ve Eşzamanlı Topla-Dağıt Araç Rotalama Problemi, Doktora Tezi, Gazi Üniversitesi, Fen Bilimleri Enstitüsü, 2009.
22. Goksal, F. P., Eşzamanlı Topla-Dağıt Araç Rotalama Problemi için Sezgisel Yaklaşımlar: Genetik Algoritma ve Kuş Sürüsü Eniyileme, Yüksek Lisans Tezi, Gazi Üniversitesi, Fen Bilimleri Enstitüsü, 2010.
23. Polat, O., Kalayci, C.B., Kulak, O., Günther, H. O., “A perturbation based variable neighborhood search heuristic for solving the Vehicle Routing Problem with Simultaneous Pickup and Delivery with Time Limit”, European Journal of Operational Research, Cilt 242, 369-382, 2015.
24. Montané, F.A.T., Galvão, R.D., “A tabu search algorithm for the vehicle routing problemwith simultaneous pick-up and delivery service”, Computer and Operations Research, Cilt 33, 595-619, 2006.
25. Rieck, J., Zimmermann, J., “A hybrid algorithm for vehicle routing of less-than-truckload carriers”, Metaheuristics in Service Industry, Lecture Notes in Economics and Mathematical Systems, Editor: Geiger, M.J., et al., Cilt 624, Springer-Verlag, Berlin, Heidelberg, Germany, 2009.
26. Dethloff, J., “Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up”, OR Spektrum, Cilt 23, No 1, 79-96, 2001.
27. Clarke, G., Wright, J.V., “Scheduling of vehicles from central depot to a number of delivery points”, Operations Research, Cilt 12, 568-581, 1964.
28. Çetin, S., Kesin Zaman Pencereli Eş Zamanlı Dağıtım Toplamalı Araç Rotalama Problemleri, Doktora Tezi, Gazi Üniversitesi, Fen Bilimleri Enstitüsü, 2011.
29. Çetin, S., Gencer, C., Kesin Zaman Pencereli - Eş Zamanlı Dağıtım Toplamalı Araç Rotalama Problemi: Matematiksel Model”, Journal of the Faculty of Engineering and Architecture of Gazi University, Cilt 25, No 3, 579-585, 2010.
30. Çetin, S., Gencer, C., “Heterojen araç filolu zaman pencereli eş zamanlı dağıtım-toplamalı araç rotalama problemleri: matematiksel model”, International Journal of Research and Development, Cilt 3, No 1, 19-27, 2011.
31. Ríos-Mercado, R.Z., López-Pérez, J.F., Castrillón-Escobar A., “A GRASP for a multi-depot multi-commodity pickup and delivery problem with time windows and heterogeneous fleet in the bottled beverage industry”, Lecture Notes in Computer Science, Cilt 8197, 143-157, 2013.
32. Waters, C.D.J., “Expanding the scope of linear programming solutions for vehicle scheduling problems”, Omega, Cilt 16, No 6, 577-583, 1988.
33. Kara, İ., Derya, T., “Polynomial Size Formulations for the Distance and Capacity Constrained Vehicle Routing Problem”, Numerical Analysis and Applied Mathematics, ICNAAM 2011, American Institute of Physics Conf. Proc. Cilt 1389, 1713-1718, 2011.
34. Laporte, G., Gendreau, M., Potvin, J.Y., Semet, F., “Classical and modern heuristics for the vehicle routing problem”, International Transactions in Operational Research, Cilt 7, No 4-5, 285-300, 2006.
35. Gajpal, Y., Abad, P., “Saving-based algorithms for vehicle routing problem with simultaneous pickup and delivery”, The Journal of the Operational Research Society, Cilt 61, No 10, 1498-1509, 2010.
36. Johnson, D.S., Aragon, C.R., McGeogh, L.A., and Schevon, C., “Optimization by simulated annealing: An experimental evaluation: Part 1. Graph Partitioning”, Operations Research, Cilt 37, 865-891, 1989.
37. Cordeau, J.F., Gendreau, M., Laporte, G., Potvin, J.Y., and Semet, F., “A Guide to vehicle routing heuristics”, The Journal of the Operational Research Society, Cilt 53, 512-522, 2002.
38. Nagy, G., Salhi, S., “Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries”, European Journal of Operational Research, Cilt 162, No 1, 126–141, 2005.
39. Salhi, S., Nagy, G., “A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling”, Journal of the Operational Research Society, Cilt 50, No 10, 1034-1042, 1999.