Route Determination for Capacitated Vehicle Routing Problem with Two Different Hybrid Heuristic Algorithm

Abstract

In today's competitive environment, time is very important. Companies that use time effectively always outperform others. Each area has specific methods to use the time effectively. In delivering the goods, it is possible to use the time effectively by carrying out the shipment with appropriate route and vehicle. Proper routing is the most important step of a consignment. In this study, routes were determined for the capacity vehicle locating problems. The tour developers in the literature are compared to each other by making applications for the main ones of the heuristic methods. Comparisons of two different hybrid solution methods have been made. First, the initial solution was developed with the KTA Algorithm, a new algorithm developed in recent years for the determination of routes, and then the route was developed with Van Breedam heuristic methods. In the other hybrid solution, an initial solution was first created with the saving algorithm and a solution was developed using the Kinderwater-Savelsbergh method. Finally, comparison of these two hybrid methods has been done to determine which is more effective in this type of problem.

Keywords

• Capacitated Vehicle Routing,Kinderwater-Savelsbergh Heuristic,KTA Algorithm,Van Breedam Heuristic,Saving Algorithm

References

1. Toth, P., Vigo, D., ‘The vehicle routing problem’, SIAM Monographs on Discrete Mathematics and Applications, SIAM Publishing, Philadelphia, PA, 2001.
2. Wei, L., Zhang, Z., Zhang, D., Leung, S.C.H., ‘A simulated annealing algorithm for the capacitated vehicle routing problem with two dimensional loading constraints’, European Journal of Operational Research, 1-17, 2017.
3. Banos, R., Ortega, J., Gil, C., Marquez, A.L., Toro, F.D., ‘A hybrid meta-heuristic for multi-objective vehicle routing problems with time windows’, Computers & Industrial Engineering, 65, 286-296, 2013.
4. Donati, A.V., Montemanni, R., Casagrande, N., Rizzoli, A.E., Gambardella, L.M., ‘Time dependent vehicle routing problem with a multi ant colony system’, European Journal of Operational Research, 185, 1174-1191, 2008.
5. Molina, J.C., Eguia, I., Racero, J., Guerrero, F., ‘Multi-objectivevehicle routing problem with cost and emission functions’, Procedia-Social and Behavioral Sciences, 160, 254-263, 2014.
6. Keskintürk, T., Topuk, N., Özyeşil, O., ‘Araç rotalama problemleri ile çözüm yöntemlerinin sınıflandırılması ve bir uygulama’, İşletme Bilimi Dergisi, 3(2), 2015.
7. Mungwattana, A., Manisri, T., Charauenpol, K., Janssens, G.K., ‘A solution fort he bi-objective vehicle routing problem with time windows using local search and genetic algorithms’, International Journal for Traffic and Transport Engineering, 6(2), 149-158, 2016.
8. Karagül, K., Tokat, S., Aydemir, E., ‘Kapasite kısıtlı araç rotalama problemlerinde başlangıç noktalarının kurulması için yeni bir algoritma’, Journal of Engineering Sciences and Design, 4(3), 215-226, 2016.

9. Hosseinabadi, A.A.R., Rostami, N.S.H., Kardgar, M., Mirkamali, S., Abraham, A., ‘A new efficient approach for solving the capacitated vehicle routing problem using the gravitational emulation local search algorithm’, Applied Mathematical Modelling, 49, 663-679, 2017.
10. Ke, L., Feng, Z., ‘A two phase metaheuristic for the cumulative capacitated vehicle routing problem’, Computers & Operations Research, 40, 633-638, 2013.
11. Jin, J., Crainic, T.G., Lokketangen, A., ‘A cooperative parallel metaheuristic for the capacitated vehicle routing problem’, Computers & Industrial Engineering, 44, 33-41, 2014.
12. Janquiera, L., Morabito R., ‘Heuristic algorithms for a three dimensional loading capacitated vehicle routing problem in a carrier’, Computers & Industrial Engineering, 88, 110-130, 2015.
13. Letchford, A.N., Salazar-Gonzalez, J.J., ‘Stronger multi-comodity flow formulations of the capacitated vehicle routing problem’, European Journal of Operational Research, 244, 730-738, 2015.
14. Akpinar, S., ‘Hybrid large neighbourhood search algorithm for capacitated vehicle routing problem’, Expert Systems With Applications, 61, 28-38, 2016.
15. Exposito-Izquierdo, Rossi, A., Sevaux, M., ‘A two-level solution approach to solve the clustered capacitated vehicle routing problem’, Computers & Industrial Engineering, 91, 274-280, 2016.
16. Keskintürk, T., Kiremitçi, B., Kiremitçi, S., ‘2-opt algoritması ve başlangıç çözümünün algoritma sonuçları üzerindeki etkisi’, Endüstri Mühendisliği Dergisi, 27(3), 2-12, 2016.
17. Eryavuz, M., Gencer, C., ‘Araç rotalama problemine ait bir uygulama’, Süleyman Demirel Üniversitesi, İktisadi ve İdari Bilimler Fakültesi, 6(1), 139-155, 2001.
18. Mohammed, M.A., Ghani, M.K.A., Hamed, R.I., Mostafa, S.A., Ibrahim, D.A., Jameel, H.K., Alallah, A.H., ‘Solving vehicle routing problem by using improved k-nearest neighborhood algorithm for best solution’, Journal of Computational Science, 21, 232-240, 2017.
19. Huber, S., Geiger, M.J., ‘Order matters – a variable neighborhood search fort he swap-body vehicle routing problem’, European Journal of Operational Research, 263, 419-445, 2017.
20. Laporte, G., Gendreau, M., Potvin, J.Y., Semet, F., ‘Classical and modern heuristics fort he vehicle routing problem’, International Transactions in Operational Research, 7, 285-300, 2000.
21. Kennedy, J., Eberhart, R.C., ‘Particle swarm optimization’, Proc. of the IEEE Int. Conference on Neural Networks, 4, 1942-1948, 1995.
22. Wilke, D.N., ‘Analysis of the particle swarm optimization algorithm’, Master Thesis, Mechanical and Aeronatutical Engineering, University of Pretoria, 2005.
23. Yılmaz, Ş., ‘Çok depolu araç rotalama probleminin karınca kolonisi optimizasyonu ile modellenmesi ve bir çözüm önerisi’, Yüksek Lisans Tezi, Yıldız Teknik Üniversitesi, Fen Bilimleri Enstitüsü, 2008.
24. Van Breedam, A., ‘Comparing descent heuristics and metaheuristics for the vehicle routing problem’, Computers & Operations Research, 28, 289-315.
25. Laporte, G., Semet, F., ‘Classical heuristics for the vehicle routing problem’, Les Cahiers du GERAD, G-98-54, Canada, 1999.
26. Lysgaard, J., ‘Clarke & Wright’s savings algorithm’, Department of Management Science and Logistics, The Aarhus School of Business, Fuglesans Alle 4, DK-8210 Aarhus V, September, 1997.
27. Gambardella, L.M., Taillard, E.D., Dorigo, M., ‘Ant colonies fort he quadratic assignment problem’, The Journal of the Operational Research Society, 50(2), 167-176, 1999.