Deterministik ve Stokastik Araç Rotalama Problemleri: Matematiksel Modeller ve Çözüm Yöntemleri

Gerçek hayat problemlerine maksimum ve minimum seviyede çözüm aramak insanoğlu için vazgeçilmez olmuştur. Optimizasyon, bu problemlere optimal yaklaşımı esas alarak çözüme yönelik algoritmalar geliştirilmesini sağlamaktadır. Günümüzde, firmalar müşterilerine en az maliyetle dağıtım ağını oluşturacak merkezlerden hizmet vermeyi amaçlayan problemlerini çözmeye çalışmaktadırlar. Bu problemler içinde Araç Rotalama Problemleri (ARP) küreselleşen dünyada lojistik desteği sağlamak adına önemli bir yer tutmaktadır. Araç rotalama problemleri ile merkezi bir depodan farklı bölgelerde konumlanmış şubeler için bir araç filosu ile farklı rotalar bulmaya yönelik en az maliyetli, modeller, algoritmalar ve çözüm yöntemleri geliştirilmektedir. Zaman içinde yapılan araç rotalama çalışmaları deterministik ve stokastik yapıdaki problemlere en iyi çözümü bulmayı hedeflemektedir. Araç rotalama problemleri bilinen talepler, müşteriler, hizmet veya seyahat süreleri ile oluşturulan kısıtlarla problemi çözmeyi amaçlar. Stokastik araç rotalama problemlerinde (SARP) talepleri, müşterileri, seyahat veya hizmet sürelerini oluşturan parametreler rassal olarak bulunur ve SARP reel dünyadaki problemlere daha yakındır. Çalışmamızda ARP ve SARP problemlerinin matematiksel model yapıları belli başlıklar altında incelenmiştir. Stokastik rotalama problemleminin çözüm zorluğu amaç fonksiyonundaki hesaplanabilirliğinin deterministik rotlama problemlerinden oldukça fazla işlem gerektirmesidir. Stokastik rotalama problemleri literatürde şans kısıtlı ve yardımcı eylemli olarak modellenmiştir, bu zor ve karmaşık rassal matematiksel modeller incelenmiştir. Ardından deterministik ve stokastik araç rotalama problemleri ve son zamanlarda yapılan çalışmalardaki yeni gelişmeler incelenmiştir. Daha sonra ARP için literatürdeki kesin ve sezgisel çözüm yöntemleri incelenmiştir.

Deterministic and Stochastic Vehicle Routing Problems: Mathematical Models and SolutionMethods

It has become indispensable for human beings to seek maximum and minimum solutions to real life problems. Optimization ensures that algorithms are developed for solutions based on the optimal approach to these problems. Today, companies are trying to solve their problems that aim to serve their customers from the centers that will form the distribution network with the least cost. Among these problems, Vehicle Routing Problems (VRP) has an important place in providing logistics support in the globalizing world. With vehicle routing problems, the least costly models, algorithms and solution methods are developed to find different routes with a vehicle fleet for branches located in different regions from a central warehouse. Vehicle routing studies conducted over time aim to find the best solution to problems in deterministic and stochastic nature. Vehicle routing problems aim to solve the problem with the constraints created by known demands, customers, service or travel times. In stochastic vehicle routing problems (SVRP), the parameters that make up the demands, customers, travel or service times are found randomly and the SVRP is closer to the problems in the real world. In our study, the mathematical model structures of VRP and SVRP problems were examined under certain headings. The problem of solving the stochastic routing problem is that the computability of the objective function requires considerably more operations than deterministic routing problems. Stochastic routing problems have been modeled in the literature as chance constrained and auxiliary action, and these difficult and complex random mathematical models have been studied. Then, deterministic and stochastic vehicle routing problems and new developments in recent studies are examined. Then, the exact and intuitive solution methods for VRP in the literature are examined.

PDF

___

Ağayeva, Ç., Alpaslan, M. & Tuna, G. (2016). Stokastik programlama metotlarının mühendislik uygulamaları (1506F531), Anadolu Üniversitesi.
Ahuja, R. K., Magnanti, T. L. & Orlin J. B. (1993). Network flows: theory, algorithms, and applications, Prentice-Hall.
Alparslan, M.T. (2019). Araç rotalama problemleri için matematiksel modeller ve subgradyant temelli çözüm yaklaşımı [Yayımlanmamış doktora tezi]. Eskişehir Teknik Üniversitesi Lisansüstü Eğitim Enstitüsü.
Applegate, D. L., Bixby, R. E., Chvatal, V. & Cook, W. J. (2006). The traveling salesman problem: a computational study. Princeton University Press.
Atasagun, G. C. & Karaoğlan, İ. (2019). Zaman bağımlı eş zamanlı topla dağıt araç rotalama problemi için bir matematiksel model. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 34(4), 1743-1756. https://doi.org/10.17341/gazimmfd.571515
Atasagun, G. C. (2015). Zaman bağımlı eş zamanlı topla dağıt araç rotalama problemi [Yayımlanmamış yüksek lisan tezi] Selçuk Üniversitesi Fen Bilimleri Enstitüsü.
Atmaca, E. (2012). Bir kargo şirketinde araç rotalama problemi. Tübav Bilim Dergisi, 5(2), 12-27.
Aydoğdu, B. (2017). Dinamik eş zamanlı topla-dağıt araç rotalama problemi için matematiksel model ve sezgisel yaklaşımlar [Yayımlanmamış doktora tezi]. Gazi Üniversitesi Fen Bilimleri Enstitüsü.
Azimli, A. (2011). Matematiksel optimizasyon. Papatya Yayıncılık.
Baradaran, V., Shafaei, A. & Hosseinian, A. H. (2019). Stochastic vehicle routing problem with heterogeneous vehicles and multiple prioritized time windows: Mathematical modeling and solution approach. Computers & Industrial Engineering, 131, 187-199. https://doi.org/10.1016/j.cie.2019.03.047.
Beliën, J., De Boeck, L. & Van Ackere, J. (2014). Municipal solid waste collection and management problems: a literature review. Transportation Science, 48(1), 78-102. https://doi.org/10.1287/trsc.1120.0448.
Baykoç, Ö. F. & Isleyen, S. K. (2007). Stokastik talepli araç rotalama problemi için şans kısıtı yaklaşımı. Teknoloji, 10(1),31-39
Bramel, J. & Simchi-Levi, D. (1997). The logic of logistics: theory, algorithms, and applications for logistics management (pp. 175-240). Springer.
Clarke, G. & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations research, 12(4), 568-581. https://doi.org/10.1287/opre.12.4.568
Cordeau, J. F., Gendreau, M., Laporte, G., Potvin, J. Y. & Semet, F. (2002). A guide to vehicle routing heuristics. Journal of the Operational Research society, 53(5), 512-522. https://doi.org/10.1057/palgrave.jors.2601319
Corberán, A., Martı́ , R. & Romero, A. (2000). Heuristics for the mixed rural postman problem. Computers & Operations Research, 27(2), 183-203. https://doi.org/10.1016/S0305-0548(99)00031-3
Cömert, S. E., Yazgan, H. R. & Görgülü, N. (2019). Eş zamanlı topla dağıt araç rotalama problemi için iki aşamalı bir çözüm yöntemi önerisi. International Journal of Advances in Engineering and Pure Sciences, 31(2), 107-117. https://doi.org/10.7240/jeps.461528
Çaybaşı, G. (2019). Evde sağlık hizmetleri araç rotalama problemi için uygulama tasarımı önerisi [Yayımlanmamış yüksek lisan tezi] Gümüşhane Üniversitesi, Sosyal Bilimler.
Çebı̇, S. & Yıldırım, B. (2020). Kapasite kısıtlı araç rotalama problemi için sezgisel yöntemler: Eticaret tedarikçilerine yönelik bir uygulama. Uluslararası İktisadi ve İdari İncelemeler Dergisi, Prof. Dr. Talha Ustasüleyman Özel Sayısı, 185-206. https://doi.org/10.18092/ulikidince.581841
Çomaklı Sökmen, Ö. & Yılmaz, M. (2020). Stokastik parametre değerlerine sahip hiyerarşik çinli postacı problemi ve bir uygulama . Journal of the Institute of Science and Technology, 10 (4) , 2520-2531. https://doi.org/10.21597/jist.777939
Dantzig, G., Fulkerson, R. & Johnson, S. (1954). Solution of a large-scale traveling-salesman problem. Journal of The Operations Research Society of America, 2(4), 393-410. https://doi.org/10.1287/opre.2.4.393
Dantzig, G. B. & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80-91. https://doi.org/10.1287/mnsc.6.1.80
Desticioğlu, B. & Özyörük, B. (2019). Stokastik talepli araç rotalama problemi için literatür taraması. savunma Bilimleri Dergisi, 18(36), 181-222. https://doi.org/10.17134/khosbd.642156,
Dror, M. (2002). Vehicle routing with stochastic demands: Models & computational methods. In Modeling Uncertainty (pp. 625-649). Springer.
Dişkaya, F. (2018). Yeşil lojistik yönetiminde ulusal karayolu yük taşımacılığı araç rotalama optimizasyonu [Yayımlanmamış doktora tezi]. Marmara Üniversitesi Sosyal Bilimler Enstitüsü.
Dündar, H. (2020). Sürdürülebilir şehir içi dinamik arp üzerine bir karar destek sistemi [Yayımlanmamış doktora tezi]. Hacettepe Üniversitesi Sosyal Bilimler Enstitüsü.
Düzakın, E. & Demircioğlu, M. (2009). Araç rotalama problemleri ve çözüm yöntemleri. Çukurova Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, 13(1), 68-87.
Eksioglu, B., Vural, A. V. & Reisman, A. (2009). The vehicle routing problem: A taxonomic review. Computers & Industrial Engineering, 57(4), 1472-1483. https://doi.org/10.1016/j.cie.2009.05.009
Ekizler, H. (2011). Araç rotalama probleminin çözümünde karınca kolonisi optimizasyonu algoritmasının kullanılması, [Yayımlanmamış yüksek lisan tezi] İstanbul Üniversitesi Fen Bilimleri Enstitüsü.
Errico, F., Desaulniers, G., Gendreau, M., Rei, W. & Rousseau, L. M. (2018). The vehicle routing problem with hard time windows and stochastic service times. EURO Journal on Transportation and Logistics, 7(3), 223-251. https://doi.org/10.1007/s13676-016-0101-4
Gendreau, M., Laporte, G. & Séguin, R. (1996). Stochastic vehicle routing. European Journal of Operational Research, 88(1), 3-12. https://doi.org/10.1016/0377-2217(95)00050-X
Gültepe, A. (2011). Stokastik eş zamanlı topla-dağıt araç rotalama problemi için melez yaklaşım: Diferansiyel evrim algoritmas [Yayımlanmış yüksek lisan tezi]. Başkent Üniversitesi Fen Bilimleri Enstitüsü.
Han, H. & Ponce Cueto, E. (2015). Waste collection vehicle routing problem: Literature review. PROMET-Traffic & Transportation, 27(4), 345-358. https://doi.org/10.7307/ptt.v27i4.1616
Hillier, F. S. & Lieberman, G. J. (1995). Introduction to mathematical programming. McGrawHill.
Joe, W. & Lau, H. C. (2020). Deep reinforcement learning approach to solve dynamic vehicle routing problem with stochastic customers. In Proceedings of the International Conference on Automated Planning and Scheduling 30,394-402.
Jin, M., Liu, K. & Eksioglu, B. (2008). A column generation approach for the split delivery vehicle routing problem. Operations Research Letters, 36(2), 265-270. https://doi.org/10.1016/j.orl.2007.05.012
Kayacı Çodur, M. & Yılmaz, M. (2020). A time-dependent hierarchical Chinese postman problem. Cent Eur J Oper Res 28, 337-366. https://doi.org/10.1007/s10100-018-0598-8
Keskintürk, T., Topuk, N. & Özyeşil, O. (2015). Araç rotalama problemleri ve çözüm yöntemleri. İşletme Bilimi Dergisi, 3(2), 77-107.
Keskintürk, T., Kiremitci, B. & Kiremitci, S. (2016). 2-Opt algoritması ve başlangıç çözümünün algoritma sonuçları üzerindeki etkisi. Endüstri Mühendisliği, 27(3), 2-12.
Kulaç, S. & Çağıl, G. (2019). Bir iç lojistik sistem probleminin, araç rotalama çözüm yöntemleri ile iyileştirilmesi. Uluslararası Mühendislik Araştırma ve Geliştirme Dergisi, 11(2), 528-541. https://doi.org/10.29137/umagd.495518
Kızıloğlu, K. (2017). Stokastik talepli çok depolu araç rotalama problemi için sezgisel bir çözüm yaklaşımı [ Yayımlanmamış yüksek lisan tezi] Gazi Üniversitesi Fen Bilimleri Enstitüsü.
Kurul F. C. (2013). Araç rotalama problemi [Yayımlanmamış yüksek lisan tezi]. Yıldız Teknik Üniversitesi Fen Bilimleri Enstitüsü.
Kumar, S. N. & Panneerselvam, R. (2012). A survey on the vehicle routing problem and its variants. Scientific Reserarch 4: 66-74. https://doi.org/10.4236/iim.2012.43010
Küçük, M. K. & Çavdur, F. (2019). Zaman pencereli bölünmüş-dağıtımlı araç rotalama ile afet sonrası yardım malzemesi dağıtımı planlaması. Uludağ University Journal of The Faculty of Engineering, 24(2), 127-146. https://doi.org/10.17482/uumfd.427047
Laporte, G. (1992). The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3), 345-358. https://doi.org/10.1016/0377-2217(92)90192-C
Larsen, A. (2000). The dynamic vehicle routing problem [Doctoral dissertation] Institute of Mathematical Modelling, Technical University of Denmark.
Lee, C. G., Epelman, M. A., White III, C. C. & Bozer, Y. A. (2006). A shortest path approach to the multiple-vehicle routing problem with split pick-ups. Transportation research part B: Methodological, 40(4), 265-284. https://doi.org/10.1016/j.trb.2004.11.004
Lei, H., Laporte, G. & Guo, B. (2012). A generalized variable neighborhood search heuristic for the capacitated vehicle routing problem with stochastic service times. Top, 20(1), 99-118. https://doi.org/10.1007/s11750-011-0188-6
Lei, H., Laporte, G. & Guo, B. (2012). Districting for routing with stochastic customers. EURO Journal on Transportation and Logistics, 1(1-2), 67-85. https://doi.org/10.1007/s13676- 012-0005-x
Li, F., Golden, B. & Wasil, E. (2007). The open vehicle routing problem: Algorithms, large-scale test problems, and computational results. Computers & operations research, 34(10), 2918- 2930. https://doi.org/10.1016/j.cor.2005.11.018
Li, X., Tian, P. & Leung, S. C. (2010). Vehicle routing problems with time windows and stochastic travel and service times: Models and algorithm. International Journal of Production Economics, 125(1), 137-145. https://doi.org/10.1016/j.ijpe.2010.01.013
Marinakis, Y., Iordanidou, G. R. & Marinaki, M. (2013). Particle swarm optimization for the vehicle routing problem with stochastic demands. Applied Soft Computing, 13(4), 1693- 1704. https://doi.org/10.1016/j.asoc.2013.01.007
Marković, D., Petrovć, G., Ćojbašić, Ž. & Stanković, A. (2020). The vehicle routing problem with stochastic demands in an urban area–a case study. Facta Universitatis, Series: Mechanical Engineering, 18(1), 107-120. https://doi.org/10.22190/FUME190318021M
Malandraki, C. & Daskin, M. S. (1992). Time dependent vehicle routing problems: Formulations, properties and heuristic algorithms. Transportation science, 26(3), 185-200. https://doi.org/10.1287/trsc.26.3.185
Mendoza, J. E., Castanier, B., Guéret, C., Medaglia, A. L. & Velasco, N. (2010). A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands. Computers & Operations Research, 37(11), 1886-1898. https://doi.org/10.1016/j.cor.2009.06.015
Montemanni, R., Gambardella, L. M., Rizzoli, A. E. & Donati, A. V. (2003). A new algorithm for a dynamic vehicle routing problem based on ant colony system. In Second international workshop on freight transportation and logistics, 1(1), 27-30.
Norouzi, N., Sadegh-Amalnick, M. & Alinaghiyan, M. (2015). Evaluating of the particle swarm optimization in a periodic vehicle routing problem. Measurement, 62, 162-169. https://doi.org/10.1016/j.measurement.2014.10.024
Oyola, J., Arntzen, H. & Woodruff, D. L. (2018). The stochastic vehicle routing problem, a literature review, part I: models. EURO Journal on Transportation and Logistics, 7(3), 193-221. https://doi.org/10.1007/s13676-016-0100-5
Pala, O. & Aksaraylı, M. (2018). Çok amaçlı kapasite kısıtlı araç rotalama problemi çözümünde bir karınca kolonisi optimizasyon algoritması yaklaşımı. Alphanumeric Journal, 6(1), 37-48. https://doi.org/10.17093/alphanumeric.366852
Reyes-Rubiano, L., Ferone, D., Juan, A. A. & Faulin, J. (2019). A simheuristic for routing electric vehicles with limited driving ranges and stochastic travel times. SORT, 1, 3-24. https://doi.org/10.2436/20.8080.02.77
Taha, H. A. (2013). Operations research: an introduction. Pearson Education India. Salavati-Khoshghalb, M., Gendreau, M., Jabali, O. & Rei, W. (2019). A rule-based recourse for the vehicle routing problem with stochastic demands. Transportation Science, 53(5), 1334- 1353. https://doi.org/10.1287/trsc.2018.0876
Salavati-Khoshghalb, M., Gendreau, M., Jabali, O. & Rei, W. (2019). An exact algorithm to solve the vehicle routing problem with stochastic demands under an optimal restocking policy. European Journal of Operational Research, 273(1), 175-189. https://doi.org/10.1016/j.ejor.2018.07.039
Sampaio, A., Kinable, J., Veelenturf ,L. P. & Woensel, T. V. (2019). A scenario-based approach for the vehicle routing problem with roaming delivery locations under stochastic travel times, Optimization Online.
Shapiro, A., Dentcheva, D. & Ruszczyński, A. (2014). Lectures on stochastic programming: modeling and theory. Society for Industrial and Applied Mathematics.
Sörensen, K. & Sevaux, M. (2009). A practical approach for robust and flexible vehicle routing using metaheuristics and Monte Carlo sampling. Journal of Mathematical Modelling and Algorithms, 8(4), 387-407.
Şahin, Y. & Karagül, K. (2019). Gezgin satıcı probleminin melez akışkan genetik algoritma (MAGA) kullanarak çözümü. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 25(1), 106-114. https://doi.org/10.5505/pajes.2018.81084
Şeker, Ş. (2007). Araç rotalama problemleri ve zaman pencereli stokastik araç rotalama problemine genetik algoritma yaklasımı [ Yayımlanmamış yüksek lisan tezi]. Yıldız Teknik Üniversitesi Fen Bilimleri Enstitüsü.
Toth, P. & Vigo, D. (2002). The vehicle routing problem. Society for Industrial and Applied Mathematics.
Toth, P. & Vigo, D. (Eds.). (2014). Vehicle routing: problems, methods, and applications. Society for Industrial and Applied Mathematics.
Ulutaş, A., Bayrakçıl, A. O. & Kutlu, B. (2017). Araç rotalama probleminin tasarruf algoritması ile çözümü: sivas’ta bir ekmek fırını için uygulama. Cumhuriyet Üniversitesi İktisadi ve İdari Bilimler Dergisi, 18(1), 185-197.
Werner, A. (2005). Bilevel stochastic programming problems: Analysis and Application to Telecommunications.
Yeun L. C., Ismaıl W. R., Omar K. & Zırour M. (2008). Vehicle routing problem: models and solutions. Journal of Quality Measurement and Analysis JQMA, 4(1), 205-218.
Zhang, D., Cai, S., Ye, F., Si, Y. W. & Nguyen, T. T. (2017). A hybrid algorithm for a vehicle routing problem with realistic constraints. Information Sciences, 394, 167-182. https://doi.org/10.1016/j.ins.2017.02.028
Zhou, F., He, Y. & Zhou, L. (2019). Last mile delivery with stochastic travel times considering dual services. IEEE Access, 7, 159013-159021. https://doi.org/10.1109/ACCESS.2019.2950442

Turkish Studies - Economics, Finance, Politics-Cover

ISSN: 2667-5625
Yayın Aralığı: Yılda 4 Sayı
Başlangıç: 2006
Yayıncı: ASOS Eğitim Bilişim Danışmanlık Otomasyon Yayıncılık Reklam Sanayi ve Ticaret LTD ŞTİ