İki aşamalı yer seçimi ve eş zamanlı topla dağıt araç rotalama problemi: Karışık tam sayılı matematiksel model ve sezgisel yaklaşım

Ece Arzu Yıldız, (Gazi Üniversitesi, Mühendislik Fakültesi, Endüstri Mühendisliği Bölümü, Ankara, Türkiye)
İsmail Karaoğlan, (Konya Teknik Üniversitesi, Mühendislik ve Doğa Bilimleri Fakültesi, Endüstri Mühendisliği Bölümü, Konya, Türkiye)
Fulya Altıparmak (Gazi Üniversitesi, Mühendislik Fakültesi, Endüstri Mühendisliği Bölümü, Ankara, Türkiye)
Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi
8 3
Yıl: 2021 Cilt: 36 Sayı: 2 Sayfa Aralığı: 807 - 822 Metin Dili: Türkçe DOI: 10.17341/gazimmfd.591293 İndeks Tarihi: 29-07-2022

İki aşamalı yer seçimi ve eş zamanlı topla dağıt araç rotalama problemi: Karışık tam sayılı matematiksel model ve sezgisel yaklaşım

Öz:
Bu çalışmada İki Aşamalı Yer Seçimi ve Eş Zamanlı Topla Dağıt Araç Rotalama Problemi (2A/YSETDARP) ele alınmıştır. Bu problemde amaç, fabrika, depo ve müşterilerden oluşan iki aşamalı bir dağıtım ağında en düşük maliyet ile hangi tesislerin hangi aday bölgelere kurulacağı ve her aşamada rotalama faaliyetlerinin nasıl gerçekleşeceğini belirlemektir. Rotalama faaliyetleri iki yönlü olup birincil tesislerden (fabrika) ikincil tesislere (depo) ve ikincil tesislerden müşterilere yapılacak olan dağıtım, müşterilerden ikincil tesislere ve ikincil tesislerden birincil tesislere gönderilmek üzere toplama faaliyetlerini kapsamaktadır. 2A/YS-ETDARP’nin çözümü için iki indisli düğüm tabanlı karışık tamsayılı bir matematiksel model önerilmiştir. Problem NP-Zor problemler sınıfında yer aldığından dolayı büyük boyutlu problemlerin çözümü için Clarke-Wright algoritmasına dayalı bir çözüm kurucu sezgisel algoritma geliştirilmiştir. Sezgisel algoritmanın performansını değerlendirmek için literatürden elde edilmiş değişik veri setleri üzerinde deneysel bir çalışma yapılmıştır. Deneysel çalışma sonucunda sezgisel algoritmanın orta ve büyük boyutlu problemlere çok kısa sürelerde iyi çözümler ürettiği görülmüştür. Dolayısıyla bu çalışmanın literatüre katkısı küçük boyutlu problemlerin çözümü için etkin bir matematiksel modelin sunulması, orta ve büyük boyutlu problemlerin çözümü için çok hızlı ve kaliteli çözüm üreten bir çözüm kurucu algoritmanın geliştirilmesidir.
Anahtar Kelime: iki aşamalı yer seçimi ve araç rotalama problemi tam sayılı programlama sezgisel yaklaşım eş zamanlı topla dağıt

A mixed integer mathematical model and a heuristic approach for two echelon location routing problem with simultaneous pickup and delivery

Öz:
This study considers Two Echelon Location Routing Problem with Simultaneous Pickup and Delivery (2E/LRP-SPD). In a two-echelon distribution network consisting of factories, warehouses and customers, the aim is to determine which facilities will be opened in which candidate regions and routing activities to be carried out among them. Routing activities include distributing and collecting activities. While distributing activities are performed from primary facilities (factory) to secondary facilities (depots) and secondary facilities to customers, collecting activities are done from customers to the secondary facilities and from secondary facilities to primary facilities. We propose a two-index node based mixed integer programming formulation for the 2E-LRPSPD. As the problem is in NP-Hard problem class, a constructive heuristic algorithm based on Clarke-Wright algorithm is developed to solve medium- and large- size problems. The performance of the heuristic approach is investigated on test instances derived from literature. Computational results show that heuristic algorithm gives good quality solutions for medium- and large-size instances in a very short computation time. Thus, the contribution of this study to the literature is to present an efficient mathematical model for solving small-size problems and to develop a constructive heuristic algorithm that produces very fast and high-quality solutions for medium and large-size problems.
Anahtar Kelime: integer programming

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık
  • 1. Drezner, Z. Steiner, G., Wesolowsky, G.O., OneFacility Location with Rectilinear Tour Distances, Naval Research Logistics Quarterly 32, 39 l-405, 1985.
  • 2. Köksalan, M., Süral, H., Kırca, O., A LocationDistribution Application for a Beer Company, European Journal of Operational Research, 80, 16-24,1995.
  • 3. Karaoğlan, İ., Altıparmak, F., A Memetic Algorithm for the Capacitated Location-Routing Problem with Mixed Backhauls, Computers and Operations Research, 55, 200-216, 2015.
  • 4. Prodhon, C., Prins, C., A Survey on Recent Research on Location-Routing Problems, European Journal of Operations Research, 238, 1-17, 2014.
  • 5. Salhi, S. and Rand, G., The Effect of Ignoring Routes When Locating Depots, European Journal of Operational Research, 39, 150-156, 1989.
  • 6. Barış, S., Facility Location Decisions Under Vehicle Routing Considerations, Yüksek Lisans Tezi, Bilkent Üniversitesi, Fen Bilimleri Enstitüsü, Ankara, 2002.
  • 7. Karaoğlan, İ., Altıparmak, F., Kara, İ., Dengiz, B., A Branch and Cut Algorithm for the Location-Routing Problem with Simultaneous Pickup and Delivery, European Journal of Operational Research, 211(2), 318- 332, 2011.
  • 8. Min, H., Jayaraman, V., Srivastava, R., Combined Location-Routing Problems: A Synthesis and Future Research Directions, European Journal of Operational Research, 108, 1–15, 1998.
  • 9. Nagy, G., Salhi, S., Location-Routing: Issues, Models and Methods, European Journal of Operational Research, 177, 649-672, 2007.
  • 10. Drexl, M., Schneider, M., A Survey of Location Routing Problem, Technical Report LM-2013-03, 2013.
  • 11. Crainic, T. G.,Sgalambro, A., Service Network Design Models for Two-Tier City Logistics, Optimization Letters, 8, 1375–1387, 2014.
  • 12. Boccia, M., Crainic, T.G., Sforza, A., Sterle, C., Location-Routing Models for Designing a Two-Echelon Freight Distribution System, Technical Report 2011- 06, CIRRELT, Montreal, 2011.
  • 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, 126-141, 2005.
  • 14. Keçeci B., Altıparmak 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.
  • 15. Aydoğdu B, Özyörük B., Mathematical Model and Heuristic Approach for Solving Dynamic Vehicle Routing Problem with Simultaneous Pickup and Delivery: Random Iterative Local Search Variable Neighborhood Descent Search, Journal of the Faculty of Engineering and Architecture of Gazi University, 35 (2), 563-580, 2020.
  • 16. Bayrak A., Ö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-480, 2017.
  • 17. Hornstra, R., Silva, A., Roodbergen K. J., Coelho, L. C., The Vehicle Routing Problem with Simultaneous Pickup and Delivery and Handling Costs, Computers and Operations Research, 115, 104858, 2020.
  • 18. Can Atasagun G., Karaoğlan İ., A Mathematical Model for the Time Dependent Vehicle Routing Problem with Simultaneous Pick-up and Delivery, Journal of the Faculty of Engineering and Architecture of Gazi University,34 (4), 1743-1756, 2019.
  • 19. Parragh, S.N., Doerner, K.F., Hartl, R.F., A Survey on Pickup and Delivery Problems Part I: Transportation Between Customers and Depot, Journal für Betriebswirtschaft, 58 (1), 21-51, 2008.
  • 20. Berbeglia, G., Cordeau, J., Gribkovskaia, I., Laporte, G., Static Pickup and Delivery Problems: A Classification Scheme and Survey, Top, 15, 1–31, 2007.
  • 21. Koç, Ç., Laporte, G., Tükenmez, İ., A Review of Vehicle Routing with Simultaneous Pickup and Delivery, Computers and Operations Research, 122, 104987, 2020.
  • 22. Belgin, Ö., Karaoğlan, İ., Altıparmak, F., Two-Echelon Vehicle Routing Problem with Simultaneous Pickup and Delivery: Mathematical Model and Heuristic Approach, Computers & Industrial Engineering, 115, 1-16, 2018.
  • 23. Demircan-Yıldız, E. A., Karaoğlan, İ., Altıparmak, F., Two Echelon Location Routing Problem with Simultaneous Pickup and Delivery: Mixed Integer Programming Formulations and Comparative Analysis, Lecture Notes on Computer Science, 9855, Editör: Paias, A., Ruthmair, M., Voß, Springer, 275-289, 2016.
  • 24. Clarke, G., Wright, J. V., Scheduling of Vehicles from Central Depot to a Number of Delivery Points, Operations Research, 12, 568-581, 1964.
  • 25. Boccia, M., Crainic, T.G., Sforza, A., Sterle, C., A Metaheuristic for a Two Echelon Location-Routing Problem, Lecture Notes in Computer Science, Springer, 6049, Editör: Festa, P., Berlin, 288-301, 2010.
  • 26. Nguyen VP., Prins C., Prodhon C., A Multi-Start Evolutionary Local Search for the Two-Echelon Location Routing Problem, Lecture Notes in Computer Science, 6373, Editör: Blesa M.J., Blum C., Raidl G., Roli A., Sampels M., Springer, Berlin, Heidelberg, 88-102, 2010.
  • 27. Nguyen, V.P., Prins, C., Prodhon, C., A Multi Start Iterative Local Search with Tabu List and Path Relinking for the Two-Echelon Location Routing Problem, Engineering Applications of Artificial Intelligence, 25, 56-71, 2012.
  • 28. Nguyen, V.P., Prins, C., Prodhon, C., Solving the TwoEchelon Location Routing Problem by a GRASP Reinforced by a Learning Process and Path Relinking, European Journal of Operational Research, 216, 113- 126, 2012.
  • 29. Nikbakhsh, E., Zegordi, S., A Heuristic Algorithm and a Lower Bound for the Two-Echelon Location-Routing Problem with Soft Time Window Constraints, Scientia Iranica Transaction E: Industrial Engineering, 17, 36- 47, 2010.
  • 30. Contardo, C., Hemmelmayr, V., Crainic, T.G., Lower and Upper Bounds for the Two-Echelon Capacitated Location-Routing Problem, Computers & Operations Research, 39, 3185-3199, 2012.
  • 31. Govindan, K., Jafarian, A., Khodaverdi, R., Devika, K., Two Echelon Multiple Vehicle Location–Routing Problem with Time Windows for Optimization of Sustainable Supply Chain Network of Perishable Food, International Journal of Production Economics, 152, 9- 28, 2014.
  • 32. Bala, K., Brcanov, D., Gvozdenovic, N., Two-Echelon Location Routing Synchronized with Production Schedules and Time Windows, Central European Journal of Operations Research, 25, 525-543, 2017.
  • 33. Pichka, K., Bajgiran, A.H., Petering, M.E.H., Jang, J., Yue, X., The Two Echelon Open Location Routing Problem: Mathematical Model and Hybrid Heuristic, Computers & Industrial Engineering, 121, 97-112, 2018.
  • 34. Veenstra, M., Roodbergen, K., Coelho, L., Zhu, S., A Simultaneous Facility Location and Vehicle Routing Problem Arising in Healthcare Logistics in the Netherlands, European Journal of Operational Research, 268, 703-715, 2018.
  • 35. Wang, Y., Assogba, K., Liu, Y., Ma, X., Xu, M., Wang, Y., Two-Echelon Location-Routing Optimization with Time Windows Based on Customer Clustering, Expert Systems with Applications, 104, 244-260, 2018.
  • 36. Grüler, A., Juan, A., Klüter, A.,Rabe, M. A SimulationOptimization Approach for the Two-Echelon Location Routing Problem Arising in the Creation of Urban Consolidation Centres, Simulation in Produktion und Logistik, 17, 129-138, 2017.
  • 37. Darvish, M., Archetti, C., Coelho, L., Speranza, M. G., Flexible Two-Echelon Location Routing Problem, European Journal of Operational Research, 277, 1124– 1136, 2019.
  • 38. Yu, Z., Zhou, Y., Liu, X.F., The Two-Echelon MultiObjective Location Routing Problem Inspired by Realistic Waste Collection Applications: The Composable Model and a Metaheuristic Algorithm, Applied Soft Computing Journal, Applied Soft Computing Journal, 94, 106477, 2020.
  • 39. Karaoğlan, İ., Altıparmak, F., Kara, İ., Dengiz, B., The Location-Routing Problem with simultaneous Pickup and Delivery: Formulations and a Heuristic Approach, Omega, 40 (4), 465-477, 2012.
  • 40. Yu, V., Lin, S., Multi-start Simulated Annealing Heuristic for the Location Routing Problem with Simultaneous Pickup and Delivery. Applied Soft Computing, 24, 284-290, 2014.
  • 41. Yu, V., Lin, S., Solving the Location-Routing Problem with Simultaneous Pickup and Delivery by Simulated Annealing, International Journal of Production Research, 54 (2), 526-549, 2016.
  • 42. Abedinzadeh, S., Ghoroghi, A., Afshar, S., Barkhordari, M., A Two-Echelon Green Supply Chain with Simultaneous Pickup and Delivery, International Journal of Transportation Engineering and Technology, 3 (2), 12-18, 2017.
  • 43. Rahmani, Y., Cherif-Khettaf, W.R., Oulamara, A., The Two-Echelon Multi-Products Location-Routing Problem with Pickup and Delivery: Formulation and Heuristic Approaches, International Journal of Production Research, 54 (4), 999-1019, 2016.
  • 44. Fan, H., Wu, J., Li, X., Jiang, X., Presenting a MultiStart Hybrid Heuristic for Solving the Problem of TwoEchelon Location-Routing Problem with Simultaneous Pickup and Delivery (2E-LRPSPD), Journal of Advanced Transportation, 2020, 9743841, 2020.
  • 45. Cordeau, J.F., Gendreau, M., Laporte, G., Potvin, J.Y., and Semet, F., A Guide to Vehicle Routing Heuristic, The Journal of the Operational Research Society, 53, 512-522, 2002.
  • 46. Gajpal, Y., Abad, P., Saving-Based Algorithms for Vehicle Routing Problem with Simultaneous Pickup and Delivery, The Journal of the Operational Research Society, 61, 10,1498-1509, 2010.
  • 47. Johnson, D.S., Aragon, C.R., McGeogh, L.A., and Schevon, C., Optimization by Simulated Annealing: An Experimental Evaluation: Part 1. Graph Partitioning, Operations Research, Cilt 37, 865-891, 1989.
  • 48. 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, 1034–42, 1999.
  • 49. Angelelli, E., Mansini, R., The Vehicle Routing Problem with Time Windows and Simultaneous Pickup and Delivery, Quantitative Approaches to Distribution Logistics and Supply Chain Management, 519, Editörler: Klose, A., Speranza, M. G., Van Wassenhove, L. N., Springer, Berlin, 249-267, 2002.
  • 50. Archetti, C., Sperenza M. G., A Survey on Matheuristics for Routing Problems, EURO Journal on Computational Optimization, 2, 223–246, 2014.
  • 51. Yıldırım U.M., Çatay B., An Ant Colony-Based Matheuristic Approach for Solving a Class of Vehicle Routing Problems, Computational Logistics, ICCL 2015, Lecture Notes in Computer Science, 9335, Editörler: Corman F., Voß S., Negenborn R. , Springer, Cham, 2015.
  • 52. Boschetti, M., Maniezzo, V., A Set Covering Based Matheuristic for a Real-World City Logistics Problem, International Transactions in Operations Research, 22, 169-196, 2015.
  • 53. Kramer, R., Subramanian, A., Vidal, T., Cabral, L., A Matheuristic Approach for the Pollution-Routing Problem, European Journal of Operations Research, 243, 523-539, 2015.
  • 54. Mancini, S., A Real-Life Multi Depot Multi Period Vehicle Routing Problem with a Heterogeneous Fleet: Formulation and Adaptive Large Neighborhood Search based Matheuristic, Transportation Research Part C, 70, 100-112, 2016.
APA DEMIRCAN-YILDIZ E, KARAOGLAN I, ALTIPARMAK F (2021). İki aşamalı yer seçimi ve eş zamanlı topla dağıt araç rotalama problemi: Karışık tam sayılı matematiksel model ve sezgisel yaklaşım. , 807 - 822. 10.17341/gazimmfd.591293
Chicago DEMIRCAN-YILDIZ Ece Arzu,KARAOGLAN Ismail,ALTIPARMAK FULYA İki aşamalı yer seçimi ve eş zamanlı topla dağıt araç rotalama problemi: Karışık tam sayılı matematiksel model ve sezgisel yaklaşım. (2021): 807 - 822. 10.17341/gazimmfd.591293
MLA DEMIRCAN-YILDIZ Ece Arzu,KARAOGLAN Ismail,ALTIPARMAK FULYA İki aşamalı yer seçimi ve eş zamanlı topla dağıt araç rotalama problemi: Karışık tam sayılı matematiksel model ve sezgisel yaklaşım. , 2021, ss.807 - 822. 10.17341/gazimmfd.591293
AMA DEMIRCAN-YILDIZ E,KARAOGLAN I,ALTIPARMAK F İki aşamalı yer seçimi ve eş zamanlı topla dağıt araç rotalama problemi: Karışık tam sayılı matematiksel model ve sezgisel yaklaşım. . 2021; 807 - 822. 10.17341/gazimmfd.591293
Vancouver DEMIRCAN-YILDIZ E,KARAOGLAN I,ALTIPARMAK F İki aşamalı yer seçimi ve eş zamanlı topla dağıt araç rotalama problemi: Karışık tam sayılı matematiksel model ve sezgisel yaklaşım. . 2021; 807 - 822. 10.17341/gazimmfd.591293
IEEE DEMIRCAN-YILDIZ E,KARAOGLAN I,ALTIPARMAK F "İki aşamalı yer seçimi ve eş zamanlı topla dağıt araç rotalama problemi: Karışık tam sayılı matematiksel model ve sezgisel yaklaşım." , ss.807 - 822, 2021. 10.17341/gazimmfd.591293
ISNAD DEMIRCAN-YILDIZ, Ece Arzu vd. "İki aşamalı yer seçimi ve eş zamanlı topla dağıt araç rotalama problemi: Karışık tam sayılı matematiksel model ve sezgisel yaklaşım". (2021), 807-822. https://doi.org/10.17341/gazimmfd.591293
APA DEMIRCAN-YILDIZ E, KARAOGLAN I, ALTIPARMAK F (2021). İki aşamalı yer seçimi ve eş zamanlı topla dağıt araç rotalama problemi: Karışık tam sayılı matematiksel model ve sezgisel yaklaşım. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 36(2), 807 - 822. 10.17341/gazimmfd.591293
Chicago DEMIRCAN-YILDIZ Ece Arzu,KARAOGLAN Ismail,ALTIPARMAK FULYA İki aşamalı yer seçimi ve eş zamanlı topla dağıt araç rotalama problemi: Karışık tam sayılı matematiksel model ve sezgisel yaklaşım. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 36, no.2 (2021): 807 - 822. 10.17341/gazimmfd.591293
MLA DEMIRCAN-YILDIZ Ece Arzu,KARAOGLAN Ismail,ALTIPARMAK FULYA İki aşamalı yer seçimi ve eş zamanlı topla dağıt araç rotalama problemi: Karışık tam sayılı matematiksel model ve sezgisel yaklaşım. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, vol.36, no.2, 2021, ss.807 - 822. 10.17341/gazimmfd.591293
AMA DEMIRCAN-YILDIZ E,KARAOGLAN I,ALTIPARMAK F İki aşamalı yer seçimi ve eş zamanlı topla dağıt araç rotalama problemi: Karışık tam sayılı matematiksel model ve sezgisel yaklaşım. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2021; 36(2): 807 - 822. 10.17341/gazimmfd.591293
Vancouver DEMIRCAN-YILDIZ E,KARAOGLAN I,ALTIPARMAK F İki aşamalı yer seçimi ve eş zamanlı topla dağıt araç rotalama problemi: Karışık tam sayılı matematiksel model ve sezgisel yaklaşım. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2021; 36(2): 807 - 822. 10.17341/gazimmfd.591293
IEEE DEMIRCAN-YILDIZ E,KARAOGLAN I,ALTIPARMAK F "İki aşamalı yer seçimi ve eş zamanlı topla dağıt araç rotalama problemi: Karışık tam sayılı matematiksel model ve sezgisel yaklaşım." Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 36, ss.807 - 822, 2021. 10.17341/gazimmfd.591293
ISNAD DEMIRCAN-YILDIZ, Ece Arzu vd. "İki aşamalı yer seçimi ve eş zamanlı topla dağıt araç rotalama problemi: Karışık tam sayılı matematiksel model ve sezgisel yaklaşım". Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 36/2 (2021), 807-822. https://doi.org/10.17341/gazimmfd.591293
Sayfa Oluşturulma Tarihi
23-04-2024 21:47

İLETİŞİM

TÜBİTAK ULAKBİM TR Dizin

Yüzüncüyıl, İşçi Blokları Mahallesi

Muhsin Yazıcıoğlu Caddesi No:51/C

06530 Çankaya / ANKARA +90 (312) 298 92 00

trdizin@tubitak.gov.tr

TÜBİTAK ULAKBİM Ulusal Akademik Ağ ve Bilgi Merkezi Cahit Arf Bilgi Merkezi © Tüm Hakları Saklıdır. Gizlilik Politikası Kullanım Şartları