Research Article
BibTex RIS Cite

Tektürel zaman pencereli araç rotalama problemi için eniyilenmiş altın oran sarmalı başlangıç çözümlü uyarlanmış büyük komşuluk arama algoritması

Year 2024, Volume: 39 Issue: 2, 797 - 810, 30.11.2023

Alperen Ekrem Çelikdin

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

Abstract

Zaman pencereli tektürel sığalı araç rotalama problemlerinde, müşteri taleplerini zamanında ve en düşük maliyetle karşılamak amaçlanmaktadır. NP-Zor olarak tanımlanan bu problem tipinde optimal çözümü bulmak her zaman mümkün olmadığından sezgisel yöntemlerle en makul çözüm aranmaktadır. Uygulama kolaylığı ve çeşitli yerel arama araçları nedeniyle sıklıkla tercih edilen bu buluşsal çözümlerden biri de büyük komşuluk arama algoritmasıdır.
Genellikle müşterilerin araçlara ilk ataması rastlantısal yapılır ve ardından yerel arama operatörleri ile iyileştirmeler sağlanır. Çağın ihtiyaçlarına bağlı olarak karmaşıklık düzeyi arttıkça, komşuluk yerel arama alanının belirli bir algoritmaya göre başlatılması çözüm hızını ve kalitesini artırmada önem taşımaktadır. Belirtilen sebeplerle, bu çalışma ile daha çok mimarlık ve sanatsal alanda kullanımıyla daha sık karşılaşılan altın oran yaklaşımı yenilikçi bir buluşsal yönteme eklenerek ARP alan yazınına katkıda bulunmak amaçlandı. Altın oran sarmalının müşterilere en yakın noktalardan dönüş yapacak şekilde eniyilenmiş sarmalı ile ilk çözümün başlatıldığı bir uyarlama yapıldı. Müşterilerin araçlara ilk ataması, bu yenilikçi yöntemde kümeleme ile başlamaktadır ve güzergahlar yerel arama operatörleri tarafından iyileştirilmektedir. Bu uyarlama ile alan yazında sıklıkla tercih edilen Solomon test problemlerinin en iyi bilinen sonuçlarında %6,53 e varan önemli iyileşmeler sağlanmıştır.

Keywords

Zaman pencereli araç rotalama problemi eniyilenmiş altın oran sarmalı kümelemesi uyarlanmış büyük komşuluk arama sezgisel algoritma

References

  • J.H. Dantzig, G. B., and Ramser, The truck dispatching problem, Manage. Sci. 80–91, 1959.
  • G. Laporte, Fifty years of vehicle routing, Transp. Sci. 43, 408–416, 2009.
  • X. Huang, B. Cao, Research on contract logistics mathematical model and system based on Lindo and Baidu map, Adv. Mater. Res. 452–453, 894–899, 2012.
  • Ş.T. Yildiz, B. Çiçekdeş, A Genetic Algorithm Approach for a Real Life Fleet Size and Mix Vehicle Routing Problem : A Case Study in an Automotive Company, 5, 29–46, 2019.
  • O. Tellez, S. Vercraene, F. Lehuédé, O. Péton, O. Tellez, S. Vercraene, F. Lehuédé, O. Péton, T. Monteiro, The fleet size and mix dial-a-ride problem with reconfigurable vehicle capacity To cite this version : HAL Id : hal-01619103 The fleet size and mix dial-a-ride problem with reconfigurable vehicle capacity, 2017.
  • I. Rodríguez-Martín, J.J. Salazar-González, H. Yaman, The periodic vehicle routing problem with driver consistency, Eur. J. Oper. Res. 273, 575–584, 2019.
  • H. Küçükaydın, Column generation based matheuristics for a vehicle routing problem with time windows and variable start time, Journal of the Faculty of Engineering and Architecture of Gazi University, 34, 2061–2078, 2019.
  • D. Zhang, S. Cai, F. Ye, Y.W. Si, T.T. Nguyen, A hybrid algorithm for a vehicle routing problem with realistic constraints, Inf. Sci. (Ny). 394–395, 167–182, 2017.
  • R. Liu, Z. Jiang, A hybrid large-neighborhood search algorithm for the cumulative capacitated vehicle routing problem with time-window constraints, Appl. Soft Comput. J. 80, 18–30, 2019.
  • Y. Kuo, Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem, Comput. Ind. Eng. 59, 157–165, 2010.
  • Ç.K. Karaoğlan, A mathematical model for the time-dependent vehicle routing problem, Journal of the Faculty of Engineering and Architecture of Gazi University, 29, 549–558, 2014.
  • A.H.G. Lenstra, J. K.; Rinnooy Kan, Complexity of Vehicle Routing and Scheduling Problems, Networks. 11, 221–227, 1979.
  • P. Shaw, Using constraint programming and local search methods to solve vehicle routing problems, Lect. Notes Comput. Sci. (Including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), 1520, 417–431, 1998.
  • S. Ropke, D. Pisinger, An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transp. Sci. 40, 455–472, 2006.
  • J.Y. Potvin, J.M. Rousseau, A parallel route building algorithm for the vehicle routing and scheduling problem with time windows, Eur. J. Oper. Res. 66, 331–340, 1993.
  • C.E. Miller, R.A. Zemlin, A.W. Tucker, Integer Programming Formulation of Traveling Salesman Problems, J. ACM. 7, 1960.
  • T. College, M. Journal, Misconceptions about the Golden Ratio Author ( s ): George Markowsky Source : The College Mathematics Journal , Vol . 23 , No . 1 ( Jan ., 1992 ), pp . 2-19 Published by : Mathematical Association of America Stable URL : http://www.jstor.org/stable/268619, 23 2–19, 2010.
  • B. Keçeci, F. Altiparmak, İ. 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.
  • M. Demir, Sezgisel yöntemlerde altın oran, Doktora Tezi, İnönü Üniversitesi, Fen Bilimleri Enstitüsü, Malatya, 2015.
  • M.M. Solomon, Algorithms for the Vehicle Routing and Scheduling Problems With Time Window Constraints., Oper. Res. 35, 254–265, 1987.
  • R. Bent, P. Van Hentenryck, A two-stage hybrid local search for the vehicle routing problem with time windows, Transp. Sci. 38, 515–530, 2004.
  • M. Chen, L. Gao, Q. Chen, Z. Liu, Dynamic Partial Removal: A Neural Network Heuristic for Large Neighborhood Search, 1–10, 19 Mayıs 2020, http://arxiv.org/abs/2005.09330 adresinden 19 Mayıs 2022 tarihinde erişildi.
  • O.M. Gonzalez, C. Segura, S.I.V. Pena, C. Leon, A memetic algorithm for the Capacitated Vehicle Routing Problem with Time Windows, in: 2017 IEEE Congr. Evol. Comput. CEC 2017 - Proc., 2582–2589, 2017.
  • N.A. Kyriakakis, M. Marinaki, Y. Marinakis, A hybrid ant colony optimization-variable neighborhood descent approach for the cumulative capacitated vehicle routing problem, Comput. Oper. Res. 134, 105397, 2021.
  • X. Song, D. Jones, N. Asgari, T. Pigden, Multi-objective vehicle routing and loading with time window constraints: a real-life application, Ann. Oper. Res. 291, 799–825, 2020.
  • C. Groër, B. Golden, E. Wasil, A library of local search heuristics for the vehicle routing problem, Math. Program. Comput. 2, 79–101, 2010.
  • D. Rezgui, J. Chaouachi Siala, W. Aggoune-Mtalaa, H. Bouziri, Application of a variable neighborhood search algorithm to a fleet size and mix vehicle routing problem with electric modular vehicles, Comput. Ind. Eng. 130, 537–550, 2019.
  • A. Hoff, H. Andersson, M. Christiansen, G. Hasle, A. Løkketangen, Industrial aspects and literature survey: Fleet composition and routing, Comput. Oper. Res. 37, 2041–2061, 2010.

Year 2024, Volume: 39 Issue: 2, 797 - 810, 30.11.2023

Alperen Ekrem Çelikdin

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

Abstract

References

  • J.H. Dantzig, G. B., and Ramser, The truck dispatching problem, Manage. Sci. 80–91, 1959.
  • G. Laporte, Fifty years of vehicle routing, Transp. Sci. 43, 408–416, 2009.
  • X. Huang, B. Cao, Research on contract logistics mathematical model and system based on Lindo and Baidu map, Adv. Mater. Res. 452–453, 894–899, 2012.
  • Ş.T. Yildiz, B. Çiçekdeş, A Genetic Algorithm Approach for a Real Life Fleet Size and Mix Vehicle Routing Problem : A Case Study in an Automotive Company, 5, 29–46, 2019.
  • O. Tellez, S. Vercraene, F. Lehuédé, O. Péton, O. Tellez, S. Vercraene, F. Lehuédé, O. Péton, T. Monteiro, The fleet size and mix dial-a-ride problem with reconfigurable vehicle capacity To cite this version : HAL Id : hal-01619103 The fleet size and mix dial-a-ride problem with reconfigurable vehicle capacity, 2017.
  • I. Rodríguez-Martín, J.J. Salazar-González, H. Yaman, The periodic vehicle routing problem with driver consistency, Eur. J. Oper. Res. 273, 575–584, 2019.
  • H. Küçükaydın, Column generation based matheuristics for a vehicle routing problem with time windows and variable start time, Journal of the Faculty of Engineering and Architecture of Gazi University, 34, 2061–2078, 2019.
  • D. Zhang, S. Cai, F. Ye, Y.W. Si, T.T. Nguyen, A hybrid algorithm for a vehicle routing problem with realistic constraints, Inf. Sci. (Ny). 394–395, 167–182, 2017.
  • R. Liu, Z. Jiang, A hybrid large-neighborhood search algorithm for the cumulative capacitated vehicle routing problem with time-window constraints, Appl. Soft Comput. J. 80, 18–30, 2019.
  • Y. Kuo, Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem, Comput. Ind. Eng. 59, 157–165, 2010.
  • Ç.K. Karaoğlan, A mathematical model for the time-dependent vehicle routing problem, Journal of the Faculty of Engineering and Architecture of Gazi University, 29, 549–558, 2014.
  • A.H.G. Lenstra, J. K.; Rinnooy Kan, Complexity of Vehicle Routing and Scheduling Problems, Networks. 11, 221–227, 1979.
  • P. Shaw, Using constraint programming and local search methods to solve vehicle routing problems, Lect. Notes Comput. Sci. (Including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), 1520, 417–431, 1998.
  • S. Ropke, D. Pisinger, An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transp. Sci. 40, 455–472, 2006.
  • J.Y. Potvin, J.M. Rousseau, A parallel route building algorithm for the vehicle routing and scheduling problem with time windows, Eur. J. Oper. Res. 66, 331–340, 1993.
  • C.E. Miller, R.A. Zemlin, A.W. Tucker, Integer Programming Formulation of Traveling Salesman Problems, J. ACM. 7, 1960.
  • T. College, M. Journal, Misconceptions about the Golden Ratio Author ( s ): George Markowsky Source : The College Mathematics Journal , Vol . 23 , No . 1 ( Jan ., 1992 ), pp . 2-19 Published by : Mathematical Association of America Stable URL : http://www.jstor.org/stable/268619, 23 2–19, 2010.
  • B. Keçeci, F. Altiparmak, İ. 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.
  • M. Demir, Sezgisel yöntemlerde altın oran, Doktora Tezi, İnönü Üniversitesi, Fen Bilimleri Enstitüsü, Malatya, 2015.
  • M.M. Solomon, Algorithms for the Vehicle Routing and Scheduling Problems With Time Window Constraints., Oper. Res. 35, 254–265, 1987.
  • R. Bent, P. Van Hentenryck, A two-stage hybrid local search for the vehicle routing problem with time windows, Transp. Sci. 38, 515–530, 2004.
  • M. Chen, L. Gao, Q. Chen, Z. Liu, Dynamic Partial Removal: A Neural Network Heuristic for Large Neighborhood Search, 1–10, 19 Mayıs 2020, http://arxiv.org/abs/2005.09330 adresinden 19 Mayıs 2022 tarihinde erişildi.
  • O.M. Gonzalez, C. Segura, S.I.V. Pena, C. Leon, A memetic algorithm for the Capacitated Vehicle Routing Problem with Time Windows, in: 2017 IEEE Congr. Evol. Comput. CEC 2017 - Proc., 2582–2589, 2017.
  • N.A. Kyriakakis, M. Marinaki, Y. Marinakis, A hybrid ant colony optimization-variable neighborhood descent approach for the cumulative capacitated vehicle routing problem, Comput. Oper. Res. 134, 105397, 2021.
  • X. Song, D. Jones, N. Asgari, T. Pigden, Multi-objective vehicle routing and loading with time window constraints: a real-life application, Ann. Oper. Res. 291, 799–825, 2020.
  • C. Groër, B. Golden, E. Wasil, A library of local search heuristics for the vehicle routing problem, Math. Program. Comput. 2, 79–101, 2010.
  • D. Rezgui, J. Chaouachi Siala, W. Aggoune-Mtalaa, H. Bouziri, Application of a variable neighborhood search algorithm to a fleet size and mix vehicle routing problem with electric modular vehicles, Comput. Ind. Eng. 130, 537–550, 2019.
  • A. Hoff, H. Andersson, M. Christiansen, G. Hasle, A. Løkketangen, Industrial aspects and literature survey: Fleet composition and routing, Comput. Oper. Res. 37, 2041–2061, 2010.
There are 28 citations in total.

Details

Primary Language Turkish
Subjects Engineering
Journal Section Makaleler
Authors

Alperen Ekrem Çelikdin 0000-0002-2215-3812

Early Pub Date October 18, 2023
Publication Date November 30, 2023
Submission Date May 24, 2022
Acceptance Date April 19, 2023
Published in Issue Year 2024 Volume: 39 Issue: 2

Cite

APA Çelikdin, A. E. (2023). Tektürel zaman pencereli araç rotalama problemi için eniyilenmiş altın oran sarmalı başlangıç çözümlü uyarlanmış büyük komşuluk arama algoritması. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 39(2), 797-810. https://doi.org/10.17341/gazimmfd.1120447
AMA Çelikdin AE. Tektürel zaman pencereli araç rotalama problemi için eniyilenmiş altın oran sarmalı başlangıç çözümlü uyarlanmış büyük komşuluk arama algoritması. GUMMFD. November 2023;39(2):797-810. doi:10.17341/gazimmfd.1120447
Chicago Çelikdin, Alperen Ekrem. “Tektürel Zaman Pencereli Araç Rotalama Problemi için Eniyilenmiş altın Oran Sarmalı başlangıç çözümlü uyarlanmış büyük komşuluk Arama Algoritması”. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 39, no. 2 (November 2023): 797-810. https://doi.org/10.17341/gazimmfd.1120447.
EndNote Çelikdin AE (November 1, 2023) Tektürel zaman pencereli araç rotalama problemi için eniyilenmiş altın oran sarmalı başlangıç çözümlü uyarlanmış büyük komşuluk arama algoritması. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 39 2 797–810.
IEEE A. E. Çelikdin, “Tektürel zaman pencereli araç rotalama problemi için eniyilenmiş altın oran sarmalı başlangıç çözümlü uyarlanmış büyük komşuluk arama algoritması”, GUMMFD, vol. 39, no. 2, pp. 797–810, 2023, doi: 10.17341/gazimmfd.1120447.
ISNAD Çelikdin, Alperen Ekrem. “Tektürel Zaman Pencereli Araç Rotalama Problemi için Eniyilenmiş altın Oran Sarmalı başlangıç çözümlü uyarlanmış büyük komşuluk Arama Algoritması”. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 39/2 (November 2023), 797-810. https://doi.org/10.17341/gazimmfd.1120447.
JAMA Çelikdin AE. Tektürel zaman pencereli araç rotalama problemi için eniyilenmiş altın oran sarmalı başlangıç çözümlü uyarlanmış büyük komşuluk arama algoritması. GUMMFD. 2023;39:797–810.
MLA Çelikdin, Alperen Ekrem. “Tektürel Zaman Pencereli Araç Rotalama Problemi için Eniyilenmiş altın Oran Sarmalı başlangıç çözümlü uyarlanmış büyük komşuluk Arama Algoritması”. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, vol. 39, no. 2, 2023, pp. 797-10, doi:10.17341/gazimmfd.1120447.
Vancouver Çelikdin AE. Tektürel zaman pencereli araç rotalama problemi için eniyilenmiş altın oran sarmalı başlangıç çözümlü uyarlanmış büyük komşuluk arama algoritması. GUMMFD. 2023;39(2):797-810.