A Solution Proposal to Vehicle Routing Problem with Integer Linear Programming: A Distributor Company Sample

  • Adem Tüzemen Gaziosmanpaşa University
  • ÇAĞDAŞ YILDIZ Gaziosmanpaşa University

Abstract

It was aimed to minimize the total distance of the routes under the capacity constraint of the routes that a distributor company has drawn in the direction of the demands. To this end, a route to Gebze-based steel production and distribution was drawn up to meet all the demands of a fabrication plant. In order to determine the minimum total distance routes, the solution recommendation by adapting the Capacity Constrained Vehicle Routing Problem (CVRP) which is one of the basic route problems using Branch and Cut algorithm of 0-1 Integer Linear Programming (ILP) was introduced. Distances between the nodes that make up the route are measured via Google Maps. Optimal solutions were obtained by using LINDO computer software to solve the problem.

.

Author Biographies

Adem Tüzemen, Gaziosmanpaşa University

Dr.

Department Of Production Management And Marketing

Gaziosmanpaşa University

 

ÇAĞDAŞ YILDIZ, Gaziosmanpaşa University

PhD Student

Gaziosmanpaşa University

Department Of Production Management And Marketing

References

Akhand M. A. H., Peya Z. J. & K. Murase (2017). Capacitated Vehicle Routing Problem Solving Using Adaptive Sweep And Velocity Tentative Pso, Article Published in International Journal Of Advanced Computer Science And Applications (Ijacsa), 8(12).

Başkaya, Z. & Öztürk, B. A. (2005). Tamsayılı Programlamada Dal Kesme Yöntemi Ve Bir Ekmek Fabrikasında Oluşturulan Araç Rotalama Problemine Uygulanması, Uludağ Üniversitesi İktisadi Ve İdari Bilimler Fakültesi Dergisi, 24(1), 101-114.

Berger, J. & Barkaouı, M. (2003). A Hybrid Genetic Algorithm For The Capacitated Vehicle Routing Problem, In Genetic And Evolutionary Computation Conference, 646-656.

Beullens, P., Muyldermans, L., Cattrysse, D. & Van Oudheusden, D. (2003). A Guided Local Search Heuristic For The Capacitated Arc Routing Problem, European Journal Of Operational Research, 147(3), 629-643.

Bozyer, Z., Alkan, A. & Fığlalı, A. (2014). Kapasite Kısıtlı Araç Rotalama Probleminin Çözümü İçin Önce Grupla Sonra Rotala Merkezli Sezgisel Algoritma Önerisi, Bilişim Teknolojileri Dergisi, 7(2).

Chandran, B. & Raghavan, S. (2008). Modeling And Solving The Capacitated Vehicle Routing Problem On Trees, In The Vehicle Routing Problem: Latest Advances And New Challenges. 239-261.

Chrıstofıdes, N., Mıngozzı, A. & Toth, P. (1981). Exact Algorithms For The Vehicle Routing Problem, Based On Spanning Tree And Shortest Path Relaxations, Mathematical Programming, 20(1), 255-282.

Clarke, G. & Wrıght, J. W. (1964). Scheduling Of Vehicles From A Central Depot To A Number Of Delivery Points, Operations Research, 12(4), 568-581.

Çolak, S. & Güler, H. (2009). Dağıtım Rotaları Optimizasyonu İçin Meta Sezgisel Bir Yaklaşım, İktisadi Ve İdari Bilimler Fakültesi Dergisi, 11(2), 171 – 190.

Dantzıg, G., Fulkerson, R. & Johnson, S. (1954). Solution Of A Large-Scale Traveling-Salesman Problem, Journal Of The Operations Research Society Of America, 2(4), 393-410.

Desrochers, M., Desrosıers, J. & Solomon, M. (1992). A New Optimization Algorithm For The Vehicle Routing Problem With Time Windows, Operations Research, 40(2), 342-354.

Eksıoglu, B., Vural, A. V. & Reısman, A. (2009). The Vehicle Routing Problem: A Taxonomic Review, Computers And Industrial Engineering, 57(4), 1472-1483.

El Hassanı, A. H., Bouhafs, L. & Koukam, A. (2008). A Hybrid Ant Colony System Approach For The Capacitated Vehicle Routing Problem And The Capacitated Vehicle Routing Problem With Time Windows, in Vehicle Routing Problem. Intech.

Faulın, J., Juan, A., Lera, F. & Grasman, S. (2011). Solving The Capacitated Vehicle Routing Problem With Environmental Criteria Based On Real Estimations in Road Transportation: A Case Study, Procedia-Social And Behavioral Sciences, 20, 323-334.

Fısher, M. L. (1994). Optimal Solution Of Vehicle Routing Problems Using Minimum K-Trees, Operations Research, 42(4), 626-642.

Gendreau, M., Hertz, A. & Laporte, G. (1994). A Tabu Search Heuristic For The Vehicle Routing Problem, Management Science, 40(10), 1276-1290.

Gillett, B. E. & Mıller, L. R. (1974). A Heuristic Algorithm For The Vehicle-Dispatch Problem”, Operations Research, 22(2), 340-349.

Helal, N., Pıchon, F., Porumbel, D., Mercıer, D. & Lefevre, É. (2016). The Capacitated Vehicle Routing Problem With Evidential Demands: A Belief-Constrained Programming Approach, In International Conference On Belief Functions, 212-221.

Hosseınabadı, A. A. R., Rostamı, N. S. H., Kardgar, M., Mırkamalı, S. & Abraham, A. (2017). A New Efficient Approach For Solving The Capacitated Vehicle Routing Problem Using The Gravitational Emulation Local Search Algorithm, Applied Mathematical Modelling, 49, 663-679.

Karagül, K., Tokat, S., Aydemir, E. (2016). Kapasite Kısıtlı Araç Rotalama Problemlerinde Başlangıç Rotalarının Kurulması İçin Yeni Bir Algoritma, Mühendislik Bilimleri Ve Tasarım Dergisi, 4(3), 215-226.

Keskintürk, T., Topuk, N. & Özyeşil, O. (2015). Araç Rotalama Problemleri Ve Çözüm Yöntemleri, İşletme Bilimi Dergisi, 3(2), 77-107.

Kirci, P. (2016). An Optimization Algorithm For A Capacitated Vehicle Routing Problem With Time Windows, Sādhanā, 41(5), 519-529.

Lal, P., Ganapathy, L., Sambandam, N. & Vachajıtpan, P. (2009). Heuristic Methods for Capacitated Vehicle Routing Problem, International Journal Of Logistics And Transport, 4, 343-352.

Laporte, G. & Nobert, Y. (1983). A Branch and Bound Algorithm for the Capacitated Vehicle Routing Problem, Operations-Research-Spektrum, 5(2), 77-85.

Laporte, G., Louveaux, F. & Mercure, H. (1992). The Vehicle Routing Problem With Stochastic Travel Times, Transportation Science, 26(3), 161-170.

Laporte, G., Nobert, Y. & Desrochers, M. (1985). Optimal Routing Under Capacity And Distance Restrictions, Operations Research, 33(5), 1050-1073.

Letchford, A. N. & Salazar-González, J. J. (2015). Stronger Multi-Commodity Flow Formulations Of The Capacitated Vehicle Routing Problem, European Journal Of Operational Research, 244(3), 730-738.

Letchford, A. N., Lysgaard, J. & Eglese, R. W. (2007). A Branch-And-Cut Algorithm For The Capacitated Open Vehicle Routing Problem, Journal Of The Operational Research Society, 58(12), 1642-1651.

Lın, S. W., Lee, Z. J., Yıng, K. C. & Lee, C. Y. (2009). Applying Hybrid Meta-Heuristics For Capacitated Vehicle Routing Problem, Expert Systems With Applications, 36(2), 1505-1512.

Lysgaard, J., Letchford, A. N. & Eglese, R. W. (2004). A New Branch-And-Cut Algorithm For The Capacitated Vehicle Routing Problem, Mathematical Programming, 100 (2), 423-445.

Mester, D. & Bräysy, O. (2005). Active Guided Evolution Strategies for Large-Scale Vehicle Routing Problems with Time Windows, Computers And Operations Research, 32(6), 1593-1614.

Mohammed, M. A., Ghanı, M. K. A., Hamed, R. I., Mostafa, S. A., Ahmad, M. S. & Ibrahım, D. A. (2017). Solving Vehicle Routing Problem by Using Improved Genetic Algorithm For Optimal Solution, Journal Of Computational Science, 21, 255-262.

Mostafa, N. & Eltawıl A. (2017). A. Solving The Heterogeneous Capacitated Vehicle Routing Problem Using K-Means Clustering And Valid Inequalities.

Pala O. & Aksaraylı M. (2017). Çok Amaçlı Kapasite Kısıtlı Araç Rotalama Problemi Çözümünde Bir Karınca Kolonisi Optimizasyon Algoritması Yaklaşımı, Ulaştırma Ve Lojistik Ulusal Kongresi, 26-27 Ekim 2017, İstanbul.

Pecın, D., Pessoa, A., Poggı, M. & Uchoa, E. (2017). Improved Branch-Cut-And-Price For Capacitated Vehicle Routing, Mathematical Programming Computation, 9(1), 61-100.

Rıbeıro, G. M. & Laporte, G. (2012), An Adaptive Large Neighborhood Search Heuristic For The Cumulative Capacitated Vehicle Routing Problem, Computers And Operations Research, 39(3), 728-735.

Solomon, M. M. (1987), Algorithms For The Vehicle Routing And Scheduling Problems With Time Window Constraints, Operations Research, 35(2), 254-265.

Takes, F. W. & Kosters, W. A. (2010). Applying Monte Carlo Techniques To The Capacitated Vehicle Routing Problem, In Proceedings Of 22th Benelux Conference On Artificial Intelligence.

Tavakkolı-Moghaddam, R., Safaeı, N., Kah, M. M. O. & Rabbani, M. (2007). A New Capacitated Vehicle Routing Problem With Split Service For Minimizing Fleet Cost By Simulated Annealing, Journal Of The Franklin Institute, 344(5), 406-425.

Toklu, N. E., Montemannı, R., Gambardella, L. M. (2013). An Ant Colony System For The Capacitated Vehicle Routing Problem With Uncertain Travel Costs, in Swarm Intelligence (Sıs), 2013 Ieee Symposium On, 32-39, Ieee.

Toth, P. & Vıgo, D. (2014). Vehicle Routing: Problems, Methods, And Applications, Society For Industrial And Applied Mathematics.

Venkatesan, S. R., Logendran, D., Chandramohan, D. (2011). Optimization Of Capacitated Vehicle Routing Problem Using Pso, International Journal Of Engineering Science And Technology (Ijest), 3(10), 7469-7477.

Wren, A. & Carr, J. D. (1971). Computers İn Transport Planning And Operation.

Wu, D. Q., Dong, M., Lı, H. Y. & Lı, F. (2016). Vehicle Routıng Problem With Time Windows Using Multi-Objectıve Co-Evolutionary Approach, Evolutionary Computation, 7(2), 204-223.

Published
2019-06-29
How to Cite
Tüzemen, A., & YILDIZ, ÇAĞDAŞ. (2019). A Solution Proposal to Vehicle Routing Problem with Integer Linear Programming: A Distributor Company Sample. International Journal of Contemporary Economics and Administrative Sciences, 9(1), 46-78. https://doi.org/10.5281/zenodo.3262231
Section
Articles