A GIS-BASED OPTIMIZATION METHOD FOR A VEHICLE ROUTING PROBLEM ARISING AT A SUPERMARKET STORE CHAIN

Year 2018, Volume: 36 Issue: 3, 741 - 766, 01.09.2018

Eren Özceylan Çağrı Koç Mehmet Erbaş

Abstract

This paper describes a Multi-Trip Heterogeneous Fixed Fleet Vehicle Routing Problem (MTHFFVRP) arising at one of the major retail chain in Turkey. The paper presents a GIS-based optimization method, based on a tabu search algorithm, that can be used to store, analyze and visualize all data as well as model solutions in geographic format. The solution method is applied on a real dataset of the supermarket store chain operates in Turkey. The paper presents computational and managerial results by analyzing the trade-offs between various parameters such as demand, number of vehicles, vehicle speed and capacity, and also a single-trip version of the problem. According to the one of the results, the total en-route time is increased by 5.18%, 4.25% and 1.82%, when the capacity of each vehicle type is decreased by 30%, 20% and 10%, respectively.

Keywords

Geographical information system, vehicle routing, multi-trip, heterogeneous fleet, tabu search

References

• [1] ArcGIS, 2016. ArcGIS Network Analyst Tutorial. <http://desktop.arcgis.com/en/arcmap/latest/extensions/network-analyst/about-the-network-analyst-tutorial-exercises.htm>.
• [2] Baldacci, R., Battarra, M., Vigo, D. 2008. Routing a heterogeneous fleet of vehicles. In B. L. Golden, S. Raghavan, E. A. Wasil, eds. The Vehicle Routing Problem: Latest Advances and New Challenges (pp. 1–25). Springer, New York.
• [3] BİM Inc., 2017. B˙IM Inc.’s hard-discount concept. <http://english.bim.com.tr/Category/627/bim-philosophy.aspx>.
• [4] Bozkaya, B., Yanik, S., Balcisoy, S., 2010. A GIS-based optimization framework for competitive multi-facility location-routing problem. Networks and Spatial Economics 10, 297–320.
• [5] Casas, I., Malik, A., Delmelle, E. M., Karwan, M. H., Batta, R., 2007. An automated network generation procedure for routing of unmanned aerial vehicles (UAVs) in a GIS environment. Networks and Spatial Economics 7, 153–176.
• [6] Cattaruzza, D., Absi, N., Feillet, D., Vidal, T., 2014. A memetic algorithm for the multi trip vehicle routing problem. European Journal of Operational Research 236, 833–848.
• [7] Cattaruzza, D., Absi, N., Feillet, D., 2016. Vehicle routing problems with multiple trips. 4OR, 1–37.
• [8] Crainic, T. G., Gajpal, Y., Gendreau, M., 2015. Multi-zone multi-trip vehicle routing problem with time windows. INFOR: Information Systems and Operational Research 53, 49–67.
• [9] Custodio, A. L., Oliveira, R. C., 2006. Redesigning distribution operations: a case study on integrating inventory management and vehicle routes design. International Journal of Logistics: Research and Applications 9, 169–187.
• [10] Demirel, H., Korkutan, M., Shoman, W., Alganc, U., 2017. Geographic information system (GIS) based accessibility analysis for highway transportation. Sigma Journal of Engineering and Natural Sciences 8, 339–344.
• [11] Fried, T., Munnich, L., Horan, T., Hilton, B., 2018. Evolving supply chains and local freight flows: A geographic information system analysis of Minnesota cereal grain movement. Transportation Research Record, <https://doi.org/10.1177/0361198118759952>.
• [12] Glover, F.W., Laguna, M., 1998. Tabu search. Kluwer Academic, Massachusetts. Google Maps, 2017. <https://maps.google.com>.
• [13] Koç C.¸ Karaoglan, I., 2016. The green vehicle routing problem: A heuristic based exact solution approach. Applied Soft Computing 39, 154–164.
• [14] Koç C.¸ Bektas, T., Jabali, O., Laporte, G., 2015. A hybrid evolutionary algorithm for heterogeneous fleetvehicle routing problems with time windows. Computers & Operations Research, 64, 11–27.
• [15] Koç C., Bektas, T., Jabali, O., Laporte, G., 2016. Thirty years of heterogeneous vehicle routing. European Journal of Operational Research 249, 1–21.
• [16] Krichen, S., Faiz, S., Tlili, T., Tej, K., 2014. Tabu-based GIS for solving the vehicle routing problem. Expert Systems with Applications 41, 6483–6493.
• [17] Laporte, G. 2009. Fifty years of vehicle routing. Transportation Science 43, 408–416.
• [18] Min, H., Melachrinoudis, E., 2016. A model-based decision support system for solving vehicle routing and driver scheduling problems under hours of service regulations. International Journal of Logistics Research and Applications 19, 256–277.
• [19] Mingozzi, A., Roberti, R., Toth, P., 2013. An exact algorithm for the multitrip vehicle routing problem.
• [20] INFORMS Journal on Computing 25, 193–207.
• [21] Olivera, A., Viera, O., 2007. Adaptive memory programming for the vehicle routing problem with multiple trips. Computers & Operations Research 34, 28–47.
• [22] Pasha, U., Hoff, A., Hvattum, L. M., 2016. Simple heuristics for the multi-period fleet size and mix vehicle routing problem. INFOR: Information Systems and Operational Research 54, 97–120.
• [23] Prins, C., 2002. Efficient heuristics for the heterogeneous fleet multitrip VRP with application to a large-scale real case. Journal of Mathematical Modelling and Algorithms 1, 135–150.
• [24] Samanlioglu, F., 2013. A multi-objective mathematical model for the industrial hazardous waste locationrouting problem. European Journal of Operational Research 226, 332–340.
• [25] Toth, P. Vigo, D., eds. 2014. Vehicle routing: Problems, methods, and applications. MOS-SIAM Series on Optimization, Philadelphia.
• [26] Yanik, S., Bozkaya, B., deKervenoael, R., 2014. A new VRPPD model and a hybrid heuristic solution approach for e-tailing. European Journal of Operational Research 236, 879–890.
• [27] Yu, B., Ma, N., Cai, W., Li, T., Yuan, X., Yao, B., 2013. Improved ant colony optimisation for the dynamic multi-depot vehicle routing problem. International Journal of Logistics Research and Applications 16, 144–157.