İki aşamalı eş zamanlı topla-dağıt araç rotalama problemi için matematiksel programlama tabanlı sezgisel yaklaşım

Yıl 2021, Cilt: 36 Sayı: 3, 1565 - 1580, 24.05.2021

Önder Belgin , İsmail Karaoğlan , Fulya Altıparmak

https://doi.org/10.17341/gazimmfd.687959

Cited By: 2

Öz

Bu çalışma iki aşamalı eş zamanlı topla-dağıt araç rotalama problemi (2A-ETDARP) üzerindedir. 2A-ETDARP için iki indisli düğüm tabanlı karışık tamsayılı programlama modeli geliştirilmiş ve bu model geçerli eşitsizlikler kullanılarak güçlendirilmiştir. Ayrıca, 2A-ETDARP’ın türevleri sunulmuş ve bunlar için karışık tamsayılı programlama modelleri uyarlanmıştır. Problemi ve türevlerini çözmek için değişken komşu iniş algoritması ile yerel aramanın birlikte kullanıldığı bir genel amaçlı sezgisel ve karışık tamsayılı programlamaya dayalı bir matsezgisel önerilmiştir. Önerilen matsezgiselin performansı 2A-ETDARP ve türevleri üzerinde literatürde yer alan test problemleri kullanılarak analiz edilmiştir. Deneysel çalışmalar sonucunda 10 depo ve 100 müşteriye kadar olan 564 test probleminin 390 tanesinde temel problem olan 2A-ETDARP için eniyi çözümler elde edilmiştir. Benzer tatmin edici sonuçlar problemin aynı veri setini kullanan diğer türevleri için de elde edilmiştir.

Anahtar Kelimeler

: Lojistik, iki aşamalı araç rotalama problemi, eş zamanlı topla-dağıt, matsezgisel, değişken komşu iniş arama

Kaynakça

• Sitek, P. and Wikarek, J. A novel integrated approach to the modelling and solving of the two-echelon capacitated vehicle routing problem, Production & Manufacturing Research, 2014, 2(1), 326-340.
• Min, H. The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transportation Research Part A: General, 1989, 23, 377–386.
• Berbeglia, G, Cordeau, JF, Gribkovskaia, I., Laporte, G. (2007). Static pickup and delivery problems: a classification scheme and survey. TOP, 15: 1–31.
• Parragh, SN, Doerner, KF, Hartl, RF. (2008). A survey on pickup and delivery problems. Part I: Transportation between customers and depot. Journal für Betriebswirtschaft, 58(1): 21-51.
• Corberán, A., Letchford, A.N. and Sanchis, J. M. A cutting plane algorithm for the general routing problem, Math. Program, 2001, (90), 291-316.
• Shu, J., Wang, G. and Zhang, K. Logistics distribution network design with two commodity categories, Journal of the Operational Research Society, 2013, 64, 1400-1408.
• Monroy-Licht, M., Amaya, C.A. and Langevin, A. The rural postman problem with time windows, CIRRELT, 2013, 2013(69), 1-20.
• Sun, J., Meng, Y. and Tan, G. An integer programming approach for the Chinese postman problem with time-dependent travel time, Journal of Combinatorial Optimization, 2015, 29(3), 565-588.
• Crainic, T.G., Ricciardi, N. and Storchi, G. Models for evaluating and planning city logistics systems, Transportation Science, 2009, 43, 432-454.
• Jepsen, M., Ropke, S. and Spoorendonk, S. A Branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem, Transportation Science, 2013, 47, 23–37.
• Perboli, G. New families of valid inequalities for the two-echelon vehicle routing problem, Electronic Notes in Discrete Mathematics, 2010, 36, 639–646.
• Baldacci, R., Mingozzi, A., Roberti R. and Wolfler Calvo, R. An exact algorithm for the two-echelon capacitated vehicle routing problem, Operations Research, 2013, 61(2), 298-314.
• Santos, F.A., Cunha, A. S. and Mateus, G. R. Branch-and-price algorithms for the two-echelon capacitated vehicle routing problem, Optimization Letter, 2013, 7, 1537–1547.
• Sitek, P. and Wikarek, J. A novel integrated approach to the modelling and solving of the two-echelon capacitated vehicle routing problem, Production & Manufacturing Research, 2014, 2(1), 326-340.
• Soysal, M., Bloemhof-Ruwaard, J.M. and Bektas, T. The time-dependent two-echelon capacitated vehicle routing problem with environmental considerations, 32nd International Journal of Production Economics, 2015, 164, 366-378.
• Crainic, T.G., Mancini, S., Perboli, G. and Tadei, R. Clustering based heuristics for the two-echelon vehicle routing problem, CIRRELT, 2008, 2008(46), 1-28.
• Crainic, T.G., Perboli, G., Mancini, S. and Tadei, R. Two-echelon vehicle routing problem: A satellite location analysis, Procedia Social and Behavioral Sciences, 2010, 2, 5944-5955.
• Meihua, W., Xuhong, T., Shan, C., and Shumin, W. Hybrid ant colony optimization algorithm for two echelon vehicle routing problem, Procedia Engineering, 2011, 15, 3361-3365.
• Hemmelmayr, V.C., Cordeau, J.F. and Crainic, T.G. An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics, Computers & Operations Research, 2012, 39, 3215-3228.
• Grangier, P., Gendreau, M., Lehuédéa, F. and Rousseau, L.M. An adaptive large neighborhood search for the two- echelon multiple-trip vehicle routing problem with satellite synchronization, European Journal of Operational Research, 2016, 254, 80-91.
• Kergosien, Y., Lente, C.H., Billaut, J.C. and Perrin, S. Metaheuristic algorithms for solving two inter connected vehicle routing problems in a hospital complex, Computers &Operations Research, 2013, 40, 2508-2518.
• Breunig, U., Schmid, V., Hartl, R.F. and Vidal, T. A large neighbourhood based heuristic for two-echelon routing problems, Computers & Operations Research, 2016, 76, 208-225.
• Zeng, Z., Xu, W., Xu, Z. and Shao, W. A hybrid GRASP+VND heuristic for the two- echelon vehicle routing problem, Mathematical Problems in Engineering, 2014, 1-11.
• Cetinkaya, C., Karaoglan, I. and Gokcen, H. Two-stage vehicle routing problem with arc time windows: A mixed integer programming formulation and a heuristic approach, European Journal of Operational Research, 2013, 230, 539-550.
• Ahmadizar, F., Zeynivand, M. and Arkat, M. Two-level vehicle routing with cross-docking in a three-echelon supply chain: A genetic algorithm approach, Applied Mathematical Modelling, 2015, 39, 7065-7081.
• Crainic, T. G., Mancini, S., Perboli, G., and Tadei, R. GRASP with path relinking for the two-echelon vehicle routing problem, Advances in Metaheuristics, Operations Research/Computer Science Interfaces Series, 2013, 53, 113–125.
• Perboli, G., Tadei, R. and Vigo, D. The two-echelon capacitated vehicle routing problem: Models and math-based heuristics, Transportation Science, 2011, 45(3), 364-380.
• Wang, K., Shao, Y. and Zhou, W. Matheuristic for a two-echelon capacitated vehicle routing problem with environmental considerations in city logistics service. Transportation Research Part D, 2017, 57, 262-276.
• Dell’Amico, M., Righini, G. and Salani, M. A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection. Transportation Science, 2006, 40, 235–247.
• Subramanian, A., Uchoa, E., Pessoa, A. and Ochi, L.S., Branch-and-cut with lazy separation for the vehicle routing problem with simultaneous pickup and delivery, Operations Research Letters, 2011, 39 (5), 338-341.
• Subramanian, A., Uchoa, E., Pessoa, A. and Ochi, L. Branch-cut-and-price for the vehicle routing problem with simultaneous pickup and delivery. Optimization Letters, 2013, 7, 1569–1581.
• Salhi, S. and Nagy, G. A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling, Journal of the Operational Research Society, 1999, 50, 1034-1042.
• Dethloff, J. Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up. OR-Spektrum, 2001, 23, 79–96.
• Nagy, G. and Salhi, S. Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries, European Journal of Operational Research, 2005, 162, 126-141.
• Crispim, J. and Brandao, J. Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls. Journal of the Operational Research Society, 2005, 56, 1296–1302.
• Chen, J. F., and Wu, T. H. Vehicle routing problem with simultaneous deliveries and pickups. Journal of the Operational Research Society, 2005, 57, 579–587.
• Montane, F.A.T, Galvão, R.D. A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service, Computers & Operations Research, 2006, 33(3), 595-619.
• Bianchessi, N. and Righini, G. Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery. Computers & Operations Research, 2007, 34, 578–594.
• Zachariadis, E. E. and Kiranoudis, C. T. A local search metaheuristic algorithm for the vehicle routing problem with simultaneous pick-ups and deliveries. Expert Systems with Applications, 2011, 38, 2717–2726.
• Ropke, S. and Pisinger, D. A unified heuristic for a large class of Vehicle Routing Problems with Backhauls. European Journal of Operational Research, 2006, 171, 750–775.
• Wassan, N., Wassan, A. H. and Nagy, G. A reactive tabu search algorithm for the vehicle routing problem with simultaneous pickups and deliveries. Journal of Combinatorial Optimization, 2008, 15, 368–386.
• Gajpal, Y. and Abad, P. An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup. Computers & Operations Research, 2009, 36, 3215–3223.
• Ai, T. J. and Kachitvichyanukul, V. A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research, 2009, 36, 1693–1702.
• Zachariadis, E. E., Tarantilis, C. D. and Kiranoudis, C. T. An adaptive memory methodology for the vehicle routing problem with simultaneous pick-ups and deliveries. European Journal of Operational Research, 2010, 202, 401–411.
• Subramanian, A., Drummond, L. M.A., Bentes, C., Ochi, L. S. and Farias, R. A. parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research, 2010, 37, 1899–1911.
• Jun, Y., & Kim, B.I. New best solutions to VRPSPD benchmark problems by a perturbation based algorithm. Expert Systems with Applications, 2012, 39, 5641–5648.
• Tasan, A. S. and Gen, M. A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries. Computers & Industrial Engineering, 2012, 62, 755–761.
• Goksal, F.P., Karaoglan, I. and Altiparmak, F. A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery. Computers & Industrial Engineering, 2009, 65, 39–53.
• Polat, O., Kalayci, C. B., Kulak, O. and Gunther, 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, 2015, 242(2), 369–382.
• Avci, M. and Topaloglu, S. An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries. Computers & Industrial Engineering, 2015, 83, 15–29.
• Li, J., Pardalos, P. M., Sun, H., Pei, J., and Zhang, Y. Iterated local search embedded adaptive neighborhood selection approach for the multi-depot vehicle routing problem with simultaneous deliveries and pickups. Expert Systems with Applications, 2015, 42, 3551–3561.
• Kalayci, C.B. and Kaya, C. An ant colony system empowered variable neighborhood search algorithm for the vehicle routing problem with simultaneous pickup and delivery, Expert Systems with Applications, 2016, 66, 163-175.
• Gong, G., Deng, Q., Gong, X., Zhang, L., Wang, H. and Xie, H. A bee evolutionary algorithm for multiobjective vehicle routing problem with simultaneous pickup and delivery. Mathematical Problems in Engineering, 2018, 1-21.
• Belgin, O., Karaoğlan, I. and Altiparmak, F. Two-echelon vehicle routing problem with simultaneous pickup and delivery: Mathematical model and heuristic approach, Computers & Industrial Engineering, 2018, 115, 1-16.
• Gouveia, L. A result on projection for the vehicle routing problem, European Journal of Operational Research, 1995, 85, 610-624.
• Letchford, A.N. and Salazar-Gonzalez, J.J. Projection results for vehicle routing, Mathematical Programming, 2006, 105, 251-274.
• Laporte, G., Nobert, Y. and Pelletier, P. Hamiltonian location problems, European Journal of Operational Research, 1983, 12, 82-89.
• Boschetti, M., Maniezzo V., Roffilli M. and Röhler A.B., Matheuristics: optimization, simulation and control. In: Blesa M., Blum C., Raidl G., Roli A. and Sampels M. (Editors) Hybrid metaheuristics, Lecture Notes in Computer Science, vol 6373. Springer, Berlin, 2010, 171–177
• Archetti, C. and Speranza, M.G. A survey on matheuristics for routing problems. EURO Journal on Computational Optimization, 2014, 2(4), 223-246.
• Karaoglan, I., Altiparmak, F., Kara, I. and Dengiz, B. A branch and cut algorithm for the location-routing problem with simultaneous pickup and delivery, European Journal of Operational Research, 2011, 211, 318-332.
• Christofides, N. and Eilon, S. An algorithm for the vehicle dispatching problem, Operational Research Quarterly, 1969, 20(3), 309-318.
• Angelelli, E. and Mansini, R. Quantitative approaches to distribution logistics and supply chain management, A. Klose, M. G. Speranza, and L. N.Van Wassenhove (Editors), Berlin: Springer-Verlag, 2002, 249-267.