Bölünmüş talepli eş zamanlı topla dağıt araç rotalama problemi için karşılaştırmalı matematiksel modeller

Bu çalışmada, Eş Zamanlı Topla Dağıt Araç Rotalama Problemi (ETDARP) ve Bölünmüş Dağıtımlı AraçRotalama Problemlerinin (BDARP) genelleştirilmiş bir çeşidi olan Bölünmüş Talepli Eş Zamanlı Topla Dağıt Araç Rotalama Problemi (BTETDARP) ele alınmıştır. ETDARP den farklı olarak BTETDARP'de,bir düğüme birden fazla kez ziyarete izin verilmekte ve müşteri talepleri araç kapasitesinden fazlaolabilmektedir. Yazarların bildiğine göre, BTETDARP için genel bir model ilk kez bu çalışmada elealınmıştır. Çalışmada tanımlanan BTETDARP için 2 matematiksel model sunulmuştur. Literatürdentüretilen test problemleri üzerindeki deneysel çalışmalar sunulmuş ve modellerin performansı ve etkinlikleri karşılaştırılmıştır. Önerilen ikinci modelin tüm performans kriterleri açısından daha iyi performanssergilediği görülmüştür. Orta ve büyük boyutlu problemlerin çözümü için önerilerde bulunulmuştur.

Comparative mathematical models for split delivery simultaneous pickup and delivery vehicle routing problem

In this study, Split Delivery Simultaneous Pickup and Delivery Vehicle Routing Problem (SDSPDVRP) is considered which is a generalized version of the Simultaneous Pickup And Delivery Vehicle RoutingProblem (SPDVRP) and Split Delivery Vehicle Routing Problem (SDVRP). Unlike the SPDVRP, in theSDSPDVRP, each customer can be visited more than once, and the demand of each customer can be greaterthan the capacity of the vehicles. According to the authors' knowledge, a general model for the SDSPDVRPare presented in literature for the first time in this study. In the study, two mathematical models presented for the defined BTETDARP. Computational results on a set of instances, generated from literature, arepresented and the performance of the models compared and evaluated. Proposals have been made for thesolution of medium and large scale problems. All performance criteria for the proposed second model hasbeen shown to outperform.

PDF

___

1. Dror M., Trudeau P., Savings by split delivery routing, Transportation Science, 23, 141-145,1989.
2. Dantzig, G.B. ve Ramser, J.H., The truck dispatching problem, Management Science, 6, 80-91, 1959.
3. Toth P, Vigo D., The vehicle routing problem, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, 2002.
4. Salhi S., Nagy G., A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling, Journal of the Operational Research Society, 50, 1034-1042, 1999.
5. Min H., Current J., Schilling D., The multiple depot vehicle routing problem with backhauling, Journal of Business Logistics, 13, 259-288, 1992.
6. Min H., The multiple vehicle routing problem with simultaneous delivery andpick-up points, Transportation Research, 23A, 377-386, 1989.
7. Dethloff J, Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up, OR Spektrum, 23, 79-96, 2001.
8. Casco D.O., Golden B.L., Wasil E.A., Vehicle routing with backhauls: Models, algorithms, and case studies, In:Golden, B.L., Assad, A.A. (Eds.), Vehicle Routing: Methods and Studies, Elsevier, Amsterdam, 127-147, 1988.
9. Tang F.A., Galvao R.D., A tabu search algorithm for the vehicle routing problem with simultaneous pick up and delivery service, Computers& Operations Research, 33, 595-619, 2006.
10. DellAmico M., Righini G., Salani M., A branch-andprice approach to the vehicle routing problem with simultaneous distribution and collection, Transportation Science, 40 (2), 235, 2006.
11. Ai T., Kachitvichyanukul V., A particle swarm optimization for the vehicle routing problem with simultaneous pick up and delivery, Computers& Operations Research, 36, 1693-1702, 2009.
12. Keçeci B., Altiparmak F., Kara İ., Heterogeneous vehicle routing problem with simultaneous pickup and delivery: mathematical formulations and a heuristic algorithm, Journal of the Faculty of Engineering and Architecture of Gazi University, 30 (2), 185-195, 2015.
13. Çetin S., Gencer C., Vehicle routing problems with hard time windows and simultaneous pick up and delivery: A mathematical model, Journal of the Faculty of Engineering and Architecture of Gazi University, 25 (3), 579-585, 2010.
14. Dror M., Trudeau P., Split delivery routing, Naval Res. Logistics, 37, 383-402, 1990.
15. Dror M., Loporte, G., Trudeau P., Vehicle routing with split deliveries, Discrete Applied Mathematics, 50, 239- 254,1994.
16. Gendreau M., Hertz A., Laporte G., A tabu search heuristic for the vehicle routing problem, Management Science, 40, 1276-1290, 1994.
17. Frizzell P.W., Giffin J.W., The split delivery vehicle scheduling problem with time windows and grid network distances, Computer Operation Research, 22, 655-667, 1995.
18. Archetti C., Hertz A., Speranza M.G., A Tabu Search Algorithm for the Split Delivery Vehicle Routing Problem, Transportatıon Science, 40 (1), 64-73, 2006.
19. Mitra S., An algorithm for the generalized vehicle routing problem with backhauling, Asia-Pacific Journal of Operational Research, 22, 153-169, 2005.
20. Mitra S., A parallel clustering technique for the vehicle routing problem with split deliveries and pickups, Journal of the Operational Research Society, 59, 1532- 1546, 2008.
21. Nowak M.A., Ergun O., White C.C. III, Pickup and delivery with split loads, Transportation Science, 42, 32-43, 2008.
22. Nowak M.A., Ergun O., White C.C. III, An empirical study on the benefit of split loads with the pickup and delivery problem, European Journal of Operational Research, 198, 734-740, 2009.
23. Thangiah S.R., Fergany A., Awan S., Real-time splitdelivery pickup and delivery time window problems with transfers, Central European Journal of Operations Research, 15, 329-349, 2007.
24. Khmelev A., Kochetov Y., A hyrid VND method for the split delivery vehicle routing problem, Electronic Notes in Discrete Mathematics, 47, 5-12, 2015.
25. Wang K., Vel C., Ning A., Competitive Decision Algorithm for the Split Vehicle Routing Problem with Simultaneous Pickup and Delivery and Time Windows, International Conference on Future Information Technology and Management Engineering, 2010.
26. Tang G., Ning A., Wang K., Qi X., A Practical Split Vehicle Routing Problem with Simultaneous Pickup and Delivery, Industrial Engineering and Engineering Management, IE&EM'09. 16th International Conference, 2009.
27. Nowak M., Ergun O., White C.C., An empirical study on the benefit of split loads with the pickup and delivery problem, European Journal of Operational Research 198, 734-740, 2009.
28. Wang Y., Ma X., Lao Y., Yu H., Lıu Y., A two-stage heuristic method for vehicle routing problem with split deliveries and pickups, Zhejiang Univ-200 Sci C (Comput & Electron) 15 (3), 200-210, 2014.
29. Annouch A., Bellabdaouı A., Mınkhar J.,Split delivery and pickup vehicle routing problem with twodimensional loading constraints, Information Technology and Management of Enterprises, SITA 2016- 11th International Conference on Intelligent Systems: Theories and Applications, 5090-5781, 2016.
30. Silva M.M., Subramanian A., Ochi L.S., An iterated local search heuristic for the split delivery vehicle routing problem, Computers and Operations Research, 53, 234-249, 2015.
31. Nishi, T., Izuno, T., Column generation heuristics for ship routing and scheduling problems in crude oil transportation with split deliveries, 60, 329-338, Computers and Chemical Engineering, 2014.
32. Wang Y., Ma X.L., Lao Y.T., Yu H.Y., Liu Y., A twostage heuristic method for vehicle routing problem with split deliveries and pickups, Journal of Zhejiang University: Science C, 15 (3), 200-210, 2014.
33. Suárez J.G., Anticona M.T., Solving the capacitated vehicle routing problem and the split delivery using GRASP metaheuristic, IFIP Advances in Information and Communication Technology,331 AICT, 243-249, 2010.
34. Koç Ç., Karaoğlan I., A mathematical model for the time-dependent vehicle routing problem, Journal of the Faculty of Engineering and Architecture of Gazi University, 29 (3), 549-558, 2014.
35. Hezer S., Kara Y., Solving vehicle routing problem with simultaneous delivery and pick-up using an algorithm based on bacterial foraging optimization, Journal of the Faculty of Engineering and Architecture of Gazi University 28 (2), 373-382, 2013.
36. Yin C., Bu L., Gong H., Mathematical model and algorithm of split load vehicle routing problem with simultaneous delivery and pickup, International Journal of Innovative Computing, Information and Control 9 (11), 4497-4508, 2013.
37. Tang J., Ma Y., Guan J., Yan C., A Max-Min Ant System for the split delivery weighted vehicle routing problem, Expert Systems with Applications, 40 (18), 7468-7477, 2013.
38. Koç Ç., Karaoglan I., A mathematical model for the vehicle routing problem with time windows and multiple use of vehicles, Journal of the Faculty of Engineering and Architecture of Gazi University, 27 (3), 569-576, 2012.
39. Tang J., Ma Y., Guan J., Yan C., A Max-Min Ant System for the split delivery weighted vehicle routing problem, Expert Systems with Applications, 40 (18), 7468-7477, 2013.
40. Miller C.E., Tucker A.W., Zemlin, R. A., Integer programming formulations and traveling salesman problems, Journal of the ACM, 7, 326-329, 1960.
41. Kulkarni R.V., Bhave P.R., Integer programming formulations of vehicle routing problems, European Journal of Operational Research, 20, 58-67, 1985.
42. Desrochers M., Laporte G., Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints, Operations Research Letters, 10, 27-36, 1991.
43. Kara İ., Laporte G., Bektas, T., A note on the lifted Miller-Tucker-Zemlin subtour elimination constraints for the capacitated vehicle routing problem, European Journal of Operational Research, 158, 793-795, 2004.
44. Kara İ., Two indexed polynomial size formulations for vehicle routing problems, Teknik Rapor, AnkaraTürkiye, (2008).
45. 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.
46. Christofides N., Mingozzi A., Toth P., The vehicle routing problem, In Christofides, N.,Mingozzi, A., Toth, Sandi, C., editors, Combinatorial optimization, Wiley, Chichester, UK, 315-338, 1979.