Araç Rotalama Problemleri ve Çözüm Yöntemleri

Year 2015, Volume: 3 Issue: 2, 77 - 107, 09.05.2016

Timur Keskintürk , Nihan Topuk , Okan Özyeşil

Abstract

Bu çalışma araç rotalama problemleri (ARP)  için güncel durum analizi ve literatür taraması sunmaktadır. Çalışmada 1957 ve 2015 yılları arasında yayımlanan, kapasite ve mesafe kısıtlı,zaman pencereli, ayrık teslimatlı, geri toplamalı, periyodik teslimatlı, ve topla ve dağıt olarak kategorize edilen araç rotalama problemleri çeşitleri ve problem türlerine göre çözüm yöntemleri ele alınmıştır. Çözüm yöntemleri kesin, klasik sezgisel ve metasezgiseller olarak üç grupta ele alınmıştır. Aynı zamanda bu çalışmada ARP, farklı parametre ve değişkenlere göre  kategorize edilerek incelenmiştir. Çalışmanın sonunda problemle ilgili olarak bir uygulama ele alınmıştır.

Keywords

-

References

• Altıparmak, F., Dengiz, B., Kara, İ., Karaoğlan İ. (2008). Eş zamanlı topla-dağıt araç rotalama problemi için yeni matematiksel formülasyonlar. sayfa no. 130.YA/EM 2008-Yöneylem Araştırması ve Endüstri Mühendisliği XXVIII. Ulusal Kongresi Bildiri Özetleri Kitabı, Galatasaray Üniversitesi, İstanbul, 30 Haziran - 2 Temmuz
• Araque, J.R., Kudva, G., Morin, T.L., Pekny, J.F., (1994). A branch-and-cut algorithm for vehicle routing problems. Annals of Operations Research 50, 37-59.
• Atmaca, E., (2012). Bir Kargo Şirketinde Araç Rotalama Problemi ve Uygulaması. Türk Bilim Araştırma Vakfı Dergisi, Cilt:5, Sayı:2, Sayfa: 12-27
• Avcı,M.,Topaloğlu, Ş., (2015). An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries,Computers & Industrial Engineering, 83, 15–29
• Balas, E., Toth, P., (1983). Branch and bound methods for the traveling salesman problem. Management Science Research Report No. MSRR 488.
• Başkaya Z., Avcı Öztürk, B.,(2005). Tamsayılı programlamada dal kesme yöntemi ve bir ekmek fabrikasında oluşturulan araç rotalama problemine uygulanması. Uludağ Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi Cilt XXIV, Sayı 1, s. 101-114.
• Bellmore, M., Nemhauser G.L., (1966). The Travelling Salesman Problem: A Survey.Operations Research, Vol. 16, No. 3 , pp. 538-558.
• Bozyer, Z., Alkan, A., Fığlalı, A., (2014). Kapasite Kısıtlı Araç Rotalama Probleminin Çözümü için Önce Grupla Sonra Rotala Merkezli Sezgisel Algoritma Önerisi. Bilişim Teknolojileri Dergisi, Cilt: 7, Sayı: 2
• Chauhan, C., Gupta, R., Pathak, K., (2012). Survey of Methods of Solving TSP along with its Implementation using Dynamic Programming Approach. International Journal of Computer Applications (0975–8887) Volume 52– No.4.
• Christofides, N., Mingozzi, A., Toth, P., (1979) The Vehicle Routing Problem In Combinatorial Optimization. Wiley Chichester.
• Clarke, G., Wright, J.W., (1964). Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research, Vol. 12, pp. 568-581
• Cordeau, J.F., Gendreau, M., Laporte, G., Potvin, J.Y., Semet, F., (2002). A Guide to Vehicle Routing Heuristics. The Journal of the Operational Research Society, Vol. 53, No. 5 pp. 512-522.
• Croes, G.A., (1958). A Method for Solving Traveling-Salesman Problems. Operations Research, Vol. 6, pp. 791-812.
• Çevik, K.K., Koçer, H.E., (2013). Parçacık Sürü Optimizasyonu ile Yapay Sinir Ağları Eğitimine Dayalı Bir Esnek Hesaplama Uygulaması. Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 17 (2), 39-45.
• Dantzig, G.B., Ramser J.B., (1959) The Truck Dispatching Problem. Management Sci. 6, 80-91
• Dantzig,G.B., Fulkerson, R.,Johnson,J.,(1957). Solution of a Large ScaleTravelling Salesman Problem, J.Opns.Res.Soc.4, 266-277
• Demiral, M. F. 2008. “Servis Araçlarının Rotalanmasında Optimizasyon ve Bir Uygulama,” Yüksek Lisans Tezi, Süleyman Demirel Üniversitesi, Sosyal Bilimler Enstitüsü, Isparta.
• Demircioğlu, M., (2009). Araç Rotalama Probleminin Sezgisel Bir Yaklaşım İle Çözümlenmesi Üzerine Bir Uygulama. Çukurova Üniversitesi Sosyal Bilimler Enstitüsü İşletme Anabilim Dalı, Doktora Tezi.
• Dorigo, M., Maniezzo, V., Colorni, A., (1991). Positive Feedback as a Search Strategy. Technical Report N. 91-016, Politecnico di Milano.
• Duhamel, C., Potvin, J.-Y., & Rousseau, J.-M. (1997). A tabu search heuristic for the vehicle routing problem with backhauls and time windows. Transportation Science, 31(1), 49–59.
• Düzakın, E., Demircioğlu, M., (2009). Araç Rotalama Problemleri ve Çözüm Yöntemleri. Çukurova Üniversitesi İİBF Dergisi Cilt:13. Sayı:1, ss.68-87.
• Erol, V., (2006). Araç Rotalama Problemleri İçin Popülasyon ve Komşuluk Tabanlı Metasezgisel Bir Algoritmanın Tasarımı ve Uygulaması, Yıldız Teknik Üniversitesi, Sistem Mühendisliği, Yüksek Lisans Tezi, Sabancı Kütüphanesi, İstanbul.
• Eryavuz, M., Gencer, C., (2001). Araç Rotalama Problemlerine Ait Bir Uygulama.Süleyman Demirel Üniversitesi İktisadi ve İdari Bilimler Fakültesi C.6, S.1, s.139-155.
• Fisher, M.L., Jaikumar, R., (1981). A Generalized Assignment Heuristic For Vehicle Routing. Networks 11, 109-124.
• Flood, M., (1955). The Travelling-Salesman Problem, J.Opns.Res.Soc.4, 61-75
• García-Nájera,A., Bullinaria John. A. , Gutiérrez-Andrade, Miguel A., (2015). An evolutionary approach for multi-objective vehicle routing problems with backhauls", Computers & Industrial Engineering 81 90–108.
• Gaskell, T.J., (1967). Basis For Vehicle Fleet Scheduling. Opl. Res. Q. , 281.
• Genreau, M., Potvin, J.Y., Braysy, O., Hasle, G., Lokketangen, A., (2007). Metaheuristics for the vehicle routing problem and its extensions: a categorized bibliography. CIRRELT-2007-27.
• Gillett, B.E., Miller, L.R., (1971). A Heuristic Algorithm For the Vehicle Dispatch Problem. Operation Research, vol. 22: 340-349
• Glover, F., Laguna, M., (1989). Tabu Search-Part I. ORSA Journal on Computing,1 (3): 190-206.
• Holland, J.H., (1975). Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor, MI.
• Irnich, S. (2008). Solution of real-world postman problems. European Journal of Operational,vol. 190, No. 1, October 2008, 52-67, ISSN: 0377-2217
• Karaboğa, D., (2005). An Idea Based on Honey Bee Swarm For Numerical Optimization. Technical Report, TR-06, Erciyes University, Engineering Faculty, Computer Engineering Faculty.
• Kennedy, J., Eberhart, C., (1995). Particle Swarm Optimization. Proc. of IEEE International Conference on Neural Network, Piscataway, NJ. s. 1942-1948.
• Kirkpatrick, S., Gelatt C.D. Jr., Vecci, (1983). Optimization by simulated annealing. M.P. Science, 220, (4598): 671–680.
• Kumar, S.N., (2012). Panneerselvam, R., A Survey on the Vehicle Routing Problem and Its Variants. Intelligent Information Management, 4, 66-74.
• Langevin, A. & Soumis, F. (1989). Design of multiple-vehicle delivery tours satisfying timeconstraints. Transportation Research Part B, Vol. 23, No. 2, April 1989, 123-138, ISSN:0191-2615
• Laporte, G., (1992). The Vehicle Routing Problem: An overview of exact and approximate algorithms. European Journal of Operational Research 59, 345-358.
• Li, Jian., . Pardalos, Panos M ., Sun, Hao., Pei,Jun., Zhang,Yong., (2015). "Iterated local search embedded adaptive neighborhood selection approach for the multi-depot vehicle routing problem with simultaneous deliveries and pickups, Expert Systems with Applications vol. 42, pp. 3551–3561
• Lysgaard J., (1997). Clarke & Wright's Savings Algorithm. Department of Management Science and Logistics, The Aarhus School of Business, Fuglesangs Allé 4, DK-8210 Aarhus V, September
• M. E.McNabb, J. D.Weir,R. R.Hill,S.N.Hall, (2015). Testing local search move operators on the vehicle routing problem with split deliveries and time windows”, Computers &OperationsResearch, vol. 56, pp. 93–109.
• Mitrovic-Minic, S. & Laporte, G. (2006). The pickup and delivery problem with time
• N. Norouzi, M. Sadegh-Amalnick, M. Alinaghiyan, (2015). Evaluating of the particle swarm optimizationin a periodic vehicle routing problem, Measurement, vol. 62, pp. 162–169.
• Nilsson, C., (2003). Heuristics for the Traveling Salesman Problem. Linköping University.
• Nurcahyo, G.W., Alias, R.A., Shamsuddın, S.M., Sap., M.N.M., (2002), Sweep Algorithm in Vehicle Routing Problem For Public Transport. Jurnal Antarabangsa (Teknologi Maklumat) 2(2002): 51-64.
• Orhan, B.,Kapanoğlu, Muzaffer. ve Karakoç, T. Hikmet,(2010). Havayolu Operasyonlarında Planlama ve Çizelgeleme Planning and Scheduling of Airline Operations, Yüksek Lisans Tezi, Eskişehir Osmangazi Üniversitesi, Müh.-Mim. Fakültesi, Endüstri Mühendisliği Bölümü
• Oropeza, A., Cruz-Chávez, M., Cruz-Rosal Martín H. es, P. Bernal, J .C.Abarca , (2012) Unsupervised Clustering Method for the Capacited Vehicle Routing Problem,Ninth Electronics, Robotics and Automotive Mechanics Conference, Mexico
• Öztürk,N.,Küçükoğlu,İ.,(2013). A differential evolution approach for the vehicle routing problem with backhauls and time windows,Journal of Advanced Transportation published online in Wiley Online Library DOI: 10.1002/atr.1237
• Pan, L., (2015). Cutting Plane Method. The Chinese University of Hong Kong,Operations Research and Logistics Jan. 20.
• Rand, G.K., (2009). The life and times of the Savings Method for Vehicle Routing Problems. Orion Volume 25 (2), pp. 125–145.
• Renaud, J., Boctor, F.F., Laporte, G., (1996). An Improved Petal Heuristic for the Vehicle Routing Problem. Journal of Operational Research Society, c. 47, sf. 329-336.
• Ropke, S., (2005). Heuristic and exact algorithms for vehicle routing problems.
• Solomon, M.M., (1987). Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. Operations Research, Vol. 35, No. 2., pp. 254-265.
• Sombuntham, P.,& Kachitvichyanukul, V. (2010). Multi-depot vehicle routing problem with pickup and delivery requests. IAENG Transactions on EngineeringTechnologies, 5, 71–85
• Szeto, W., Wu, Y., Ho, S.C., (2011). An artificial bee colony algorithm for the capacitated vehicle routing problem. European Journal of Operational Research, 215, 126–135.
• Şahin, Y., Eroğlu, A., (2014). Kapasite Kısıtlı Araç Rotalama Problemi İçin Metasezgisel Yöntemler: Bilimsel Yazın Taraması.Süleyman Demirel Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi C.19, S.4, s.337-355.
• Toth, P., Vigo, D., (2002). The Vehicle Routing Problem.
• windows and transshipment. Inform, vol. 44, no. 217-227, ISSN:0315-5986
• www.google.com/maps
• www.tuik.gov.tr
• Yellow, P., (1970). A Computational Modification To The Savings Method Of Vehicle Scheduling. Operational Research Quarterly, Vol. 21, 281.