Kapasiteli araç rotalama problemi için makine öğrenmesi ve matematiksel programlama temelli hibrid bir çözüm önerisi

Yıl 2024, Cilt: 39 Sayı: 2, 741 - 756, 30.11.2023

Özgür Sanlı , Zühal Kartal

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

Cited By: 1

Öz

Bu çalışmada, kapasiteli araç rotalama probleminin (KARP) çözümü için makine öğrenmesi teknikleri ile matematiksel programlama formülasyonlarını hibridleştiren iki aşamalı bir yaklaşım önerilmiştir. KARP'ın çözümü için ilk aşamada makine öğrenmesi algoritmaları ile düğümlerin hangi araçlara atanacağına karar verildikten sonra ortaya çıkan kümelerin toplam talep miktarının her bir aracın kapasitesini aşmaması kapasite dengeleme algoritması adı verilen bir metot tarafından garantilenmiştir. İkinci aşamada ise, her bir araç depodan tur oluşturmak için başlar ve gezgin satıcı problemi (GSP) matematiksel modelini kullanarak en kısa kat edilen mesafeyi bulmak için atanan tüm düğümleri ziyaret eder. KARP 'ın nihai çözümü, tüm TSP rotalarının birleştirilmesiyle oluşturulmuştur. Bu çalışmada kullanılan makine öğrenmesi algoritmaları denetimli öğrenme kategorisi altında; K-En yakın Komşuluk algoritması (K-NN) ve lojistik regresyon (LR) algoritmalarıyken; denetimsiz öğrenme kategorisi için, K-Ortalamalar (K-Means) algoritmasıdır. Önerilen yaklaşım için, farklı araç sayıları ile literatürden farklı veri setleri kullanılarak duyarlılık analizleri gerçekleştirilmiştir. Sonuç olarak önerilen hibrid yaklaşımın test problemlerinin çoğunda KARP'ın matematiksel modelinin çözümüne göre daha iyi sonuçlar verdiği gösterilmiştir.

Anahtar Kelimeler

Kapasiteli Araç Rotalama Problemi, Makine Öğrenmesi ve Matematiksel Modelleme Hibrid Yaklaşım, Lojistik Regresyon, K-Means, K-NN

Kaynakça

• 1. Prescient&Strategic Intelligence, On-Demand Logistics Market Report: By Vehicle Type (Light Commercial Vehicle, Medium/Heavy Commercial Vehicle), End Use (B2B, B2C), Application (E-Commerce, Industrial, Moving and Shifting, P2P Delivery) – Latest Trends, Recent Developments, and Demand Forecast Through 2030, https://www.psmarketresearch.com/market-analysis/on-demand-logistics-market, Ocak 2020.
• 2.Ö.B. Tek, E. Ozgul, Modern Pazarlama İlkeleri: Uygulamalı Yönetimsel Yaklaşım, Birleşik Matbaacılık, 3. Baskı, İzmir, 2010.
• 3. Toth P., Vigo D., The Vehicle Routing Problem, SIAM, 2000.
• 4. Dantzig G.B. ve Ramser J.H., Source: Management Science, Vol. 6, No. 1, 80-91, 1959.
• 5. Clarke G. & Wright, J.W. Scheduling of Vehicles From a Depot to a Number of Delivery Points, Operations Research, 12, 568-581. 1964.
• 6. Laporte G.& Osman H.İ, Routing Problems: A bibliography, Annals of Operations Research, 227-262 ,1995.
• 7. Toth P.& Vigo D., Vehicle Routing Problems, Methods and Applications, SIAM, 2014.
• 8. Gendreau M., Laporte G, Musaraganyi C., Taillard E.D, A tabu search heuristic for the heterogeneous fleet vehicle routing problem, Computers& Operations Research Volume 26, 1153-1173, 1999.
• 9. Oropeza A., Cruz-Chávez M., Cruz-Rosal Martín H., Bernal P., Abarca J.C., Unsupervised Clustering Method for the Capacited Vehicle Routing Problem, Ninth Electronics, Robotics and Automotive Mechanics Conference, Mexico, 2012.
• 10. Solomon M., Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints, Operation Research Volume 35, 254-265, 1987.
• 11. Sujoy R., Andrei S., Jean B., Mourad D., The multi-depot split-delivery vehicle routing problem: Model and solution algorithm, Knowlegde-Based Systems Volume 71, 238-265, 2014.
• 12. Christofides N., Mingozzi A. ve Toth P., State-space relaxation procedures for the computation of bounds to routing problems, Networks, 11,145-164, 1981.
• 13. Agarwal Y., Mathur K., ve Salkin H.M., A set-partitioning-based exact algorithm for the vehicle routing problem, Networks, 19:731-749, 1989.
• 14. Osman I.H., Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research, 41:421-451, 1993.
• 15. Glover F. ve Laguna M., Tabu search. In C.R. Reeves, editor, Modern Heuristic Techniques for Combinatorial Problems, 70-150, Blackwell, Oxford, UK, 1993.
• 16. Barbarosoglu G. ve Ozgur D., A tabu search algorithm for the vehicle routing problem, Computers and Operations Research, 26,255-270, 1999.
• 17. Ropke S. ve Pisinger D., An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation Science, 40,455-472, 2006.
• 18. Blum C. ve Roli A., Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Computing Surveys, 35(3), 268-308, 2003.
• 19. Hopfield, J. J., ve Tank D.W, “‘Neural’ computation of decisions in optimization problems.” Biological Cybernetics 52 (3), 141–152, 1985.
• 20. Baltean-Lugojan R., Bonami P., Misener R., & Tramontani, Selecting cutting planes for quadratic semidefinite outer-approximation via trained neural networks, 2018.
• 21. He H., Daume III H. & Eisner J. M., Learning to search in branch and bound algorithms in Advances in neural information processing systems,3293-3301, 2014.
• 22. Khalil E. B., Dilkina B., Nemhauser G. L., Ahmed S. & Shao Y., Learning to run heuristics in tree search, International Joint Conferences on Artificial Intelligence Organization, 659– 666, 2017.
• 23. Khalil E. B., Le Bodic P., Song L., Nemhauser G., & Dilkina B., Learning to branch inmixed integer programming, In Thirtieth Association for the Advancement of Artificial Intelligence conference on artificial intelligence,2016.
• 24. Lederman G., Rabe M. N., Lee E. A., & Seshia, S. A. Learning heuristics for automated reasoning through deep reinforcement learning, arXiv preprint arXiv:1807.08058 ,2018.
• 25. Amizadeh S., Matusevych S., &Weimer M. Learning to solve circuit-sat: An unsupervised differentiable approach.2018.
• 26. Beasley JE., “Route first—Cluster second methods for vehicle routing.” Omega 11 (4),403-408, 1983.
• 27. Montoya J.A., Guéret C., Mendoza J.E. ve Villegas J.G., “A route first cluster-second heuristic for the Green Vehicle Routing Problem.”, In ROADEF 2014, Bordeaux, France, 2014.
• 28. Fisher, Marshall L., ve Jaikumar R., “A generalized assignment heuristic for vehicle routing.”, Networks 11 (2): 109–124,1981.
• 29. Dondo R ve Cerdá J, “A cluster-based optimization approach for the multidepot heterogeneous fleet vehicle routing problem with time windows.” European Journal of Operational Research 176,1478-1507,2007.
• 30. Asis L.S., Eduardo C., Grossmann E.I, A MILP-based clustering strategy for integrating the operational management of crude oil supply, Computers & Chemical Engineering Volume 145, February 2021.
• 31. Rautela A., Sharma S.K., Bhardwaj P., Distribution planning using capacitated clustering and vehicle routing problem, Journal of Advances in Management Research, JAMR-12-2018-0113,2019.
• 32. Geetha S., Poonthalir G., Vanathi P.T., Improved K-Means Algorithm for Capacitated Clustering Problem, PSG College of Technology, 2009.
• 33. Alesiani F., Ermiş G., Konstantinos G., Constrained Clustering for the Capacitated Vehicle Routing Problem (CC-CVRP), 2022.
• 34. Mostafa N. ve Eltawir A., Solving the Heterogeneous Capacitated Vehicle Routing Problem using K-Means Clustering and Valid Inequalities, Proceedings of the International Conference on Industrial Engineering and Operations Management Rabat, Morocco, April 11-13, 2017.
• 35. Czuba P., Pierzchala D, Ierzchale, Machine Learning methods for solving Vehicle Routing Problems,2021.
• 36. Christofides N, Mingozzi A., Toth P., Sandi C., Combinatorial Optimization, Wiley, Chichester, UK, 315-338, 1979.
• 37. Miller E., Tucker A.W. ve Zemlin R.A., Integer programming formulations and traveling salesman problems, Journal of the ACM, 7:326-329, 1960.
• 38. Applegate D.L., Bixby R.E., Chvatal V., Cook W.J., The traveling salesman problem: a computational study, Princeton University Press, 2006.
• 39. Hand D. J., Principles of data mining, Drug safety 30 (7), 621–622, 2007.
• 40. Wu X., Kumar V., Quinlan J. R., Ghosh J., Yang Q., Top 10 algorithms in data mining. Knowledge and information systems 14 (1), 1–37, 2008.
• 41. Bock J. R. & Gough D. A. Predicting protein–protein interactions from primary structure, Bioinformatics 17 (5), 455–460,2001.
• 42. Mangasarian O. L., Street W. N. & Wolberg W. H. Breast cancer diagnosis and prognosis via linear programming. Operations Research 43 (4), 570–577, 1995.
• 43. Min J. H. & Lee Y.C., Bankruptcy prediction using support vector machine with optimal choice of kernel function parameters, Expert systems with applications, 28 (4), 603–614, 2005.
• 44. Sammut C., Webb G.I., Encyclopedia of Machine Learning, 288, Springer, 2011.
• 45. Fix E., Hodges L, Discriminatory Analysis, Nonparametric Discrimination: Consistency Properties, USAF School of Aviation Medicine, Randolph Field, Texas, 1951.
• 46. Rochat Y., Taillard E., Probabilistic Diversification and Intensification in Local Search for Vehicle Routing. Journal of Heuristics 1(1), 147-167,1995.
• 47. Christophides N, Mingozzi A., Toth P., Sandi C., Combinatorial Optimization, John Wiley & Sons Ltd, 1979.
• 48. Golden B.L., Raghavan S., Wasil E.A., The Vehicle Routing Problem: Latest Advances and New Challenges, Operations Research/Computer Science Interfaces Series, Springer, 2008.