Dinamik eş zamanlı topla dağıt araç rotalama probleminin çözümü için matematiksel model ve sezgisel yaklaşım: Rassal iteratif yerel arama değişken komşu iniş algoritması

Öz

 Firmaların dağıtım ve toplama taleplerini karşılayacak en uygun rotaların bulunması için Araç Rotalama Problemleri (ARP) sıkça kullanılmaktadır. Gerçek hayatta, gün içerisinde gelen yeni toplama taleplerinin dolaşımda olan araçlar tarafından karşılanması taşıma maliyetlerini azaltacaktır. Bu bağlamda müşterilerden gelen yeni toplama taleplerinin dolaşımda olan araçlar tarafından karşılanabilmesi amacıyla Dinamik Eş Zamanlı Topla-Dağıt Araç Rotalama Problemi (DETD_ARP) için yeni bir matematiksel model geliştirilmiştir.  Geliştirilen matematiksel modelin etkinliğini araştırmak için literatürde yer alan test problemleri kullanılmış ve sonuçlar değerlendirilmiştir. Matematiksel model ile elde edilen sonuçlar değerlendirilmiş ve problem boyutu arttıkça çözüm süresinin üstel olarak arttığı görülmüştür. Bu çalışma kapsamında problemin kısa sürede çözebilmek için sezgisel algoritmalardan faydalanılmıştır. Rassal İteratif Yerel Arama Değişken Komşu İniş (R – İYA – DKİ) algoritması adında yeni bir algoritma geliştirilmiştir.  R – İYA – DKİ’de üst(hyper) sezgiseller kullanılarak komşuluk yapılarının uygulama sırası azalan permütasyon yöntemine göre sürekli olarak değiştirilmiştir. Geliştirilen algoritmanın etkinliğini değerlendirmek için çalışma kapsamında matematiksel model ile elde edilen sonuçlar kullanılmıştır. Sonuçlara bakıldığında geliştirilen sezgisel algoritmanın matematiksel model ile elde edilen sonuçlara yakın sonuçlar verdiği görülmüştür. Son olarak ve büyük boyutlu problemler önerilen R – İYA – DKİ algoritması ile çözülmüş ve sonuçlar paylaşılmıştır.

Anahtar Kelimeler

• Dinamik,eşzamanlı topla-dağıt,araç rotalama problemi,karma tam sayılı matematiksel modelleme,üst sezgisel,yerel arama,değişken komşu arama

Kaynakça

1. Dantzig, G. B., and Ramser, J. H., The Truck Dispatching Problem. Management Science, 6(1), 80-91,1959.
2. Clarke, G. and Wright, J. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12, 568–581,1964.
3. Erol, V., Araç rotalama problemleri için popülasyon ve komşuluk tabanlı metasezgisel bir algoritmanın tasarımı ve uygulaması, Yüksek Lisans Tezi, Yıldız Teknik Üniversitesi Fen Bilimleri Enstitüsü, İstanbul, 2006.
4. Laporte, G., The traveling salesman problem, the vehicle routing problem, and their ımpact on combinatorial optimization, International Journal of Strategic Decision Sciences, 1(2), 82-92, 2010.
5. Weise T., P. A., Planning and packing problems, solving real-world vehicle routing problems with evolutionary algorithms, Natural Intelligence for Scheduling, Warsaw: Springer, 2010.
6. Göksal, F., Eşzamanlı topla-dağıt araç rotalama problemi için sezgisel yaklaşımlar: genetik algoritma ve kuş sürüsü eniyileme, Yüksek Lisans Tezi, Gazi Üniversitesi, Fen Bilimleri Enstitüsü, Ankara, 2010.
7. Ropke, S., Pisinger., D., A unified heuristic for a large class of vehicle routing problems with backhauls, European Journal of Operational Research, 171(3), 750-775, 2006.
8. Min, H., The multiple vehicle routing problem with simultaneous delivery and pickup points, Transportation Research A, 23(5), 377- 386, 1989.

9. Halse, K., Modeling and solving complex vehicle routing problems, Ph.D thesis, Technical University of Denmark, Institute of Mathematical Statistics and Operations Research, 1992.
10. 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(10), 1034–1042, 1999.
11. Dethloff, J., Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up, OR Spektrum, 23(1), 79-96, 2001.
12. Tang, F.A., Galvao, R.D., Vehicle routing problem with simultaneous pick-up and delivery service, Journal of the Operational Research Society of India, 39, 19-33, 2002.
13. Nagy, G., Salhi, S., Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries, European Journal of Operational Research, 162(1), 126–141, 2005.
14. Crispim, J., Brandao, J., “Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls”, Journal of the Operational Research Society, Cilt 56, 1296–1302, 2005.
15. Dell’Amico, M., Righini, G., Salani, M., “A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection”, Transportation Science, Cilt 40: 2, 235–247, 2006.
16. Chen, J. F., Approaches for the vehicle routing problem with simultaneous deliveries and pickups. Journal of the Chinese Institude of Industrial Engineers,23 (2), 141-150, 2006.
17. Chen, J. F., Wu., T. H., Vehicle routing problem with simultaneous deliveries and pickups, The journal of the Operational Research Society, 57 (5), 579-587, 2006.
18. Montane, F. A. T., Galvao, R. D., A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service, Computers and Operations Research, 33 (3), 595-619, 2006.
19. Gencer, C., Yaşa, Ö., Simultaneous Pick-Up And Delivery Decısıon Support Systems Of Transportatıon Command Shuttle Tour’s, Journal of the Faculty of Engineering and Architecture of Gazi University, 22(3), 437–449, 2007.
20. Wassan, N. A., Wassan, A. H., Nagy, G., A reactive tabu search algorithm for the vehicle routing problem with simultaneous pickups and deliveries, Journal of Combinatorial Optimization, 15(4), 368–86, 2007.
21. Bianchessi, N., Righini, G., “Heuristic Algorithms For The Vehicle Routing Problem With Simultaneous Pick-Up And Delivery”, Computers & Operations Research, 34, 578- 594, 2009.
22. Zachariadis, E. E., Tarantilis, C. D., Kiranoudis, C. T., An adaptive memory methodology optimization for the vehicle routing problem with simultaneous pickups and deliveries, European Journal of Operational Research, 202 (2), 401-411, 2009a.
23. Zachariadis, E. E., Tarantilis, C. D., Kiranoudis, C. T., An adaptive memory methodology optimization for the vehicle routing problem with simultaneous pickups and deliveries. European Journal of Operational Research, 202 (2), 401- 411, 2009b.
24. Ai T., Kachitvichyanukul V., A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery, Computers& Operations Research, 36, 1693-1702, 2009.
25. Gajpal, Y., Abad, P., “An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup”, Computers & Operations Research, 36(12), 3215–3223, 2009.
26. Ç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.
27. Subramanian, A., Drummond, L. M. A., Bentes, C., Ochi, L. S., Farias, R., A parallel heuristic for the Vehicle Routing Problem with Simultaneous Pickup and Delivery, Computers and Operations Research, 37 (11), 1899-1911,2010.
28. Mingyong, L., and Erbao, C., An improved differential evolution algorithm for vehicle routing problem with simultaneous pickups and deliveries and time Windows, Engineering Applications of Artificial Intelligence, 23, 188-195, 2010.
29. Subramanian, A., Uchoa, E., Pessoa, A. A., Ochi, L. S., Branch-and-cut with lazy separation for the vehicle routing problem with simultaneous pickup and delivery, Operations Research Letters, 39, 338-341, 2011.
30. Zachariadis, E. E., Kiranoudis, C. T., A local search metaheuristic algorithm for the vehicle routing problem with simultaneous pick-ups and deliveries. Expert Systems with Applications, 38, 2717-2726,2011.
31. Tasan, A.S., Gen, M., A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries, Computers & Industrial Engineering, 62(3), 755–761, 2012.
32. Wang, H.F., Chen Y.Y, A genetic algorithm for the simultaneous delivery and pickup problems with time window, Computers & Industrial Engineering, 62(1), 84–95, 2012.
33. Cruz, R.C., Silva, T.C.B, Souza M.J.F., Coelho, V.N., Mine M.T., Martins, A.X., GENVNS-TS-CL-PR: A heuristic approach for solving the vehicle routing problem with simultaneous pickup and delivery, Electronic Notes in Discrete Mathematics, 39, 217-224, 2012.
34. Zhang, T., Chaovalitwongse, W.A., Zhang Y., Scatter search for the stochastic travel-time vehicle routing problem with simultaneous pick-ups and deliveries, Computers & Operations Research, 39, 2277–2290, 2012.
35. Goksal, F. P., Karaoglan, I, Altiparmak, F., A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery, Computers and Industrial Engineering, 65 (1), 39-53, 2013.
36. 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.
37. Liu R., Xie, X., Augusto V., Rodriguez C., Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care, European Journal of Operational Research, 230, 475–486, 2013.
38. Avci, M., Topaloğlu, S., An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries, Computers & Industrial Engineering, 83, 15–29, 2015.
39. Gschwind, T., A comparison of column generation approaches to the synchronized pickup and delivery problem. European Journal of Operational Research, 247, 60–71,2015.
40. 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.
41. Wang, C., Mu, D., Zhao, F., Sutherland, J.W., A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup–delivery and time Windows, Computers & Industrial Engineering, 83, 111–122, 2015.
42. Li, J., Pardalos, P.M., Sun, H., Pei, J., 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, 42, 3551–3561, 2015.
43. Zachariadis E.E., Tarantilis C.D. and Kiranoudis, C.T., The vehicle routing problem with simultaneous pick-ups and deliveries and two-dimensional loading constraints. European Journal of Operational Research, 251(2), 369–386, 2016.
44. 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, 66, 163–175, 2016.
45. Iassinovskaia, G., Limbourg, S. and Riane, F., The inventory-routing problem of returnable transport items with time windows and simultaneous pickup and delivery in closed-loop supply chains. International Journal Production Economics, 183, 570–582, 2017.
46. Bayrak, A. ve Özyörük, B., Comparative mathematical models for split delivery simultaneous pickup and delivery vehicle routing problem. Journal of the Faculty of Engineering and Architecture of Gazi University, 32(2), 469-479, 2017.
47. Psaraftis, H.N., Vehicle routing: methods and studies, Elsevier Science Publishers, Amsterdam, 1988.
48. Pillac, V., Gendreau, M., Guéret, C., Medaglia, A.L., A review of dynamic vehicle routing problems, European Journal of Operational Research, 225(1), 1–11, 2013.
49. Taillard, E.D., Gambardella, L.M., Gendreau, M., Potvin, J.-Y., Adaptive memory programming: a unified view of metaheuristics, European Journal of Operational Research, 135(1), 1–16, 2001.
50. Lund K., Madsen O., Rygaard J., Vehicle routing problems with varying degrees of dynamism, Technical report, IMM. Department of Mathematical Modeling, Technical University of Denmark, Kogens, Lyngby, Denmark, 1996.
51. Bent, R.W., Hentenryck, P.V., Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers, 52(6), 977–987, 2004.52. Du, T.C., Li, E.,Y., Chou, D., Dynamic vehicle routing for online B2C delivery, Omega, 33, 33 – 45, 2005.
52. Montemannı, R., Gambardella, L.M., Rızzolı, A.E., Donati, A.V., Ant Colony System for a Dynamic Vehicle Routing Problem, Journal of Combinatorial Optimization, 10, 327–343, 2005.
53. Haghani, A., Jung, S., A dynamic vehicle routing problem with time-dependent travel times, Computers & Operations Research, 32, 2959–2986, 2005.55. Hanshar, F.T., Ombuki-Berman, B.M., Dynamic vehicle routing using genetic algorithms, Applied Intelligence, 27, 89–99, 2007.
54. Cheunga, B.K-S, Choyb, K.L., Lic, C-L., Shid, W., Tange, J., Dynamic routing model and solution methods for fleet management with mobile technologies, International Journal of Production Economics, 113, 694–705, 2008.
55. Liao, T.S., Hu, T-Y., An object-oriented evaluation framework for dynamic vehicle routing problems under real-time information, Expert Systems with Applications, 38, 12548–12558, 2011.
56. Pillac, V., Guéret, C., Medaglia, A.L., An event-driven optimization framework for dynamic vehicle routing, Decision Support Systems, 54, 414–423, 2012.
57. Azi, N., Gendreau, M., Potvin, J-W, A dynamic vehicle routing problem with multiple delivery routes, Annals of Operation Research, 199, 103–112, 2012.
58. Ferrucci, F., Bock, S., Gendreau, M., A pro-active real-time control approach for dynamic vehicle routing problems dealing with the delivery of urgent goods, European Journal of Operational Research, 225,130–141, 2013.
59. Xu, Y., Wang, L., and Yang, Y., Dynamic Vehicle Routing Using an Improved Variable Neighborhood Search Algorithm, Hindawi Publishing Corporation Journal of Applied Mathematics 2013(2013), 12, 2013.
60. Ghannadpoura, S.F., Nooria, S., Tavakkoli-Moghaddam, R., Ghoseiri, K., A multi-objective dynamic vehicle routing problem with fuzzy timewindows: Model, solution and application, Applied Soft Computing, 14, 504–527, 2014.
61. Mavrovouniotis, M., Yang, S., Ant algorithms with immigrants schemes for the dynamic vehicle routing problem, Information Sciences, 294,456–477, 2015.
62. Euchi, J., Yassine, A., Chabchoub, H., The dynamic vehicle routing problem: Solution with hybrid metaheuristic approach, Swarm and Evolutionary Computation, 21, 41-53, 2015.
63. Karaoğlan, İ., Dağıtım Ağları Tasarımında Yer Seçimi Ve Eşzamanlı Topla-Dağıt Araç Rotalama Problemleri, Doktor Tezi, Gazi Üniversitesi, Fen Bilimleri Enstitüsü, Ankara, 2009.
64. Keçeci, B., Heterojen Eş-Zamanlı Topla-Dağıt Araç Rotalama Problemi İçin Matematiksel Modeller Ve Sezgisel Yaklaşımlar, Doktor Tezi, Gazi Üniversitesi, Fen Bilimleri Enstitüsü, Ankara, 2014.
65. Angelelli, E., Mansini, R., Quantitative Approaches to Distribution Logistics and Supply Chain Management, Editörler: Klose, A., Speranza, M. G., Van Wassenhove, L. N., Springer-Verlag, Berlin, 249-267, 2002.