Eş zamanlı topla dağıt araç rotalama problemi için yeni bir çözüm önerisi

Abstract

 Eş zamanlı topla dağıt araç rotalama problemi; müşterilerin dağıtım ve toplama taleplerinin eş zamanlı olarak karşılandığı bir araç rotalama problemidir. Bu tez kapsamında bir ana depo üzerinden 76 müşteriye hizmet sağlayacak bir firmanın araç rotalama problemi ele alınmıştır. Minimum sayıda araç kullanımı ile gidilen mesafeyi en küçükleyecek araç rotalarının oluşturulması hedeflenmiştir. Problem çözümü için literatürde yer alan karışık tamsayılı matematiksel model kullanılmıştır ve sezgisel bir algoritma geliştirilmiştir. Farklı büyüklükteki veri setlerine algoritma uygulanmış elde edilen çözümler regresyon analizi ile değerlendirilmiştir.

Keywords

• eş zamanlı topla dağıt araç rotalama problemi,en kısa yol yöntemi,regresyon analizi

A solution approach for vehicle routing problem with simultaneous pickup and delivery

Abstract

Simultaneously pickup and delivery problem is a vehicle routing problem that pickup and delivery

demands of customers in each route are met simultaneously. The vehicle routing problem of a company

provides delivery service to 76 customers from a depot is solved. The main objective is to create vehicle

routes which minimize the distance travelled using the minimum number of vehicles. A MILP and a new

heuristic algorithm are proposed to solve the problem. The algorithm was applied different data sets and

results are evaluated with regression analysis.

Keywords

• vehicle routing problem with simultaneous pick-up and delivery,the shortest path algorithm,regression analysis

References

1. Ü. Şengül, «Tersine lojistik kavramı ve tersine lojistik ağ tasarımı,» Atatürk Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi , no. 10, 2011.
2. F. P. Goksal, İ. Karaoglan ve F. Altıparmak, «A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pick up and delivery,» Computer Industrial Engineering, no. 65, pp. 39-53, 2013.
3. H. Min, «The multiple vehicle routing problem with simultaneous delivery and Pick up points,» Transportation Reseach, pp. 377-386, 1989.
4. J. Dethloff, «Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up,» OR Spektrum, vol. 23, no. 1, pp. 79-96, 2001.
5. J. Crispim ve J. Brandao, «Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems With backhauls,» Journal of the Operational Research Society, vol. 56, pp. 1296-1302, 2005.
6. G. Nagy ve S. Salhi, «Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries,» European Journal of Operational Research, no. 162, pp. 126-141, 2005.
7. F. A. T. Montane ve R. D. Galvao, «A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service,» Computer Operations Research, no. 33, pp. 595-619, 2006.
8. S. Ropke ve D. Pisinger, « A unified heuristic for a large class of vehicle routing problems with backhauls,» European Journal of Operational Research, vol. 171, pp. 750-775, 2006.

9. J. Chen, « Approaches for the vehicle routing problem with simultaneous deliveries and pick-ups,» Journal of the Chinese Institude of Industrial Engineers, vol. 23, no. 2, pp. 141-150, 2006.
10. N. Bianchessi ve G. Righini, «euristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery,» Computers Operations Research, no. 34, pp. 578-594, 2007.
11. S. N. Parrag, K. F. Doerner ve R. F. Hartl, « A survey on pick up and delivery problems part I: transportation between pickup and delivery locations,» vol. 58, no. 1, pp. 21-51, 2008a.
12. S. N. Parrag, K. F. Doerner ve R. F. Hartl, « A survey on pickup and delivery problems part II: transportation between pickup and delivery locations,» Journal fur Betriebswirtschaft, vol. 58, no. 1, pp. 81-117, 2008b.
13. C. Erbao, L. Minygyong ve N. Kai, « A differential evolution and genetic algorithm for vehicle routing problem with simultaneous pickup and delivery and time windows,» Proceedings of the 17th World Congress the International Federation of Automatic Control, Korea, 2008. J. Ai ve V. Kachitvichyanukul, «A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery,» Computers & Operations Research, cilt 36, no. 5, pp. 1693-1702, 2009.
14. M. G. Karlaftis, K. Kepaptsoglou ve E. Sambracos, « Containership routing with time deadlines and simultaneous deliveries and pick-ups,» Transportation Research Part E, no. 45, pp. 210-221, 2009.
15. E. E. Zachariadis, C. D. Tarantilis ve C. T. Kiranoudis, « A Hybrid Metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service,» Expert System With Applications, no. 36, pp. 1070-1081, 2009.
16. Y. Gajpal ve P. Abad, « An ant colony system for vehicle routing problem with simultaneous delivery and pick-up,» Computers Operations Research, cilt 36, pp. 3215-3223, 2009.
17. L. Mingyong ve C. Erbao, « An improved differential evolution algorithm for vehicle routing problem with simultaneous pick-ups and deliveries and time windows,» Engineering Applications of Artificial İntelligence, no. 23, pp. 188-195, 2010.
18. E. Zachariadis, C. D. Tarantilis ve C. T. Kiranoudis, «An Adaptive Memory Methodology For The Vehicle Routing Problem With Simultaneous Pick-ups And Deliveries,» European Journal of Operational Research, no. 202, pp. 401-411, 2010.
19. A. Subramanian, L. M. Drummond, C. Bentes, L. S. Ochi ve R. Farias, « A parallel heuristic for the vehicle routing problem with simultaneous pick-up and delivery,» Computers Operations Research, no. 37, pp. 1899-1911, 2010.
20. B. Çatay, « A new saving-based ant algorithm for the vehicle routing problem,» Expert Systems with Applications, no. 37, pp. 6809-6817, 2010. S. Çetin ve C. Gencer, « Kesin zaman pencereli eş zamanlı dağıtım toplamalı araç rotalama problemi,» Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, cilt 25, no. 3, pp. 579-585, 2010.
21. J. Fan, «The vehicle routing problem with simultaneous pick-up and delivery Based on customer satisfaction,» Advanced in Control Engineering and Information Science, no. 15, pp. 5284-5289, 2011.
22. A. Subramanian, E. Uchoa, A. A. Pessoa ve L. S. Ochi, « Branch and cut with lazy separation for the vehicle routing problem with simultaneous pick-up and delivery,» Operations Research Letters, no. 39, pp. 338-341, 2011.
23. E. E. Zachariadis ve C. T. Kiranoudis, « A local search metaheuristic algorithm for the vehicle routing problem with simultaneous pick-ups and deliveries,» Expert Systems with Applications, no. 38, pp. 2717-2726, 2011. S. Tasan ve M. Gen, «A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries,» Computer Industrial Engineering, no. 62, pp. 755-761, 2012.
24. T. Zhang, W. A. Chaovalitwongse ve Y. Zhang, «Scatter search for the stochastic travel time vehicle routing problem with simultaneous pick-ups and deliveries,» Computer Operations Research, vol. 39, pp. 2277-2290, 2012.
25. H. F. Wang ve Y. Y. Chen, « A genetic algorithm for the simultaneous delivery and pick-up problems with time windows,» Computer Industrial Engineering, no. 62, pp. 84-95, 2012.
26. R. C. Cruz, T. C. Silva, M. J. Souza, V. N. Coelho, M. T. Mine ve A. X. Martins, «Genvns-Ts-Cl-Pr: A heuristic approach for solving the vehicle routing problem with simultaneous pick-up and delivery,» Electronic Notes in Discrete Mathematics, no. 39, pp. 217-224, 2012.
27. R. Liu, X. Xie, V. Augusto ve C. Rodriguez, « Heuristic approaches for a special simultaneous pick-up and delivery problem with time windows in home health aare industry,» European Journal of Operational Research, no. 230, pp. 475-486, 2013.
28. H. O. Günther, O. Kulak, C. B. Kalayci ve O. Polat, « A perturbation based variable neighborhood search heuristic for solving the vehicle routing problem with simultaneous pickup and delivery,» European Journal of Operational Research, no. 242, pp. 369-382, 2015.
29. C. Wang, D. Mu, F. Zhao ve J. W. Sutherland, « A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup–delivery and time windows,» Computers Industrial Engineering, no. 83, pp. 111-122, 2015.
30. M. Avci ve S. Topaloglu, « A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery,» Expert Systems With Applications, no. 53, pp. 160-171, 2016.
31. C. B. Kalayci ve C. Kaya, «An ant colony system empowered variable neighborhood search algorithm for the vehicle routing problem with simultaneous pick-up and delivery,» Expert Systems With Applications, no. 66, pp. 163-175, 2016.
32. İ. Karaoğlan, Dağıtım ağları tasarımında yer seçimleri ve eş zamanlı topla dağıt araç rotalama problemleri, Gazi Üniversitesi, Fen Bilimleri Enstitüsü, Endüstri Mühendisliği Bölümü, Doktora Tezi. Ankara, 2009.
33. G. Dinç Yalçın, Önce dağıt sonra topla araç rotalama problemi için bulanık ortamda çok amaçlı yaklaşım ve uygulama, Anadolu Üniversitesi, Fen Bilimleri Enstitüsü, Endüstri Mühendisliği Bölümü, Yüksek Lisans Tezi, 2012.
34. G. Mosheiov, «Vehicle routing with pick-up and delivery tour partitioning heuristics,» Computers İndustrial Engineering, vol. 34, no. 3, pp. 669-684, 1998.