A rich vehicle routing problem arising in the replenishment of automated teller machines

© 2018 by the Author(s). This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution -Noncommercial 4.0 International License (CC-by the license) ( https://creativecommons.org/licenses/by-nc/4.0/ )

Download PDF

Cite

XML

Abstract

This paper introduces, models, and solves a rich vehicle routing problem (VRP) motivated by the case study of replenishment of automated teller machines (ATMs) in Turkey. In this practical problem, commodities can be taken from the depot, as well as from the branches to efficiently manage the inventory shortages at ATMs. This rich VRP variant concerns with the joint multiple depots, pickup and delivery, multi-trip, and homogeneous fixed vehicle fleet. We first mathematically formulate the problem as a mixed-integer linear programming model. We then apply a Geographic Information System (GIS)-based solution method, which uses a tabu search heuristic optimization method, to a real dataset of one of the major bank. Our numerical results show that we are able to obtain solutions within reasonable solution time for this new and challenging practical problem. The paper presents computational and managerial results by analyzing the trade-offs between various constraints.

Keywords

Vehicle routing

GIS

tabu search

recirculation automated teller machines

Conflict of interest

The authors declare they have no competing interests.

References

[1] O(¨)zceylan, E., Uslu, A., Erba>s, M., C>etinkaya,C., I(˙)>sleyen, S. K. (2017). Optimizing the location-allocation problem of pharmacy warehouses: A case study in Gaziantep. An International Journal of Op- timization and Control: Theories & Applications (IJOCTA), 7, 117–129.

[2] Laporte, G. (2009). Fifty years of vehicle routing. Transportation Science, 43, 408–416.

[3] Toth, P. Vigo, D., eds. (2014). Vehicle routing: Prob- lems, methods, and applications. MOS-SIAM Series on Optimization, Philadelphia.

[4] Lahyani, R., Khemakhem, M., Semet, F. (2015). Rich vehicle routing problems: From a taxonomy to a def- inition. European Journal of Operational Research, 241, 1–14.

[5] Karaoglan, A. D., Gonen, D., Ucmus, E. (2011). Air- craft routing and scheduling: A case study in an air- line company. An International Journal of Optimiza- tion and Control: Theories & Applications (IJOCTA), 1, 27–43.

[6] Karagul, K., Gungor, I. (2014). A case study of het- erogeneous 丑eet vehicle routing problem: Touristic distribution application in Alanya. An International Journal of Optimization and Control: Theories & Ap- plications (IJOCTA), 4, 67–76.

[7] Van Anholt, R. G., Coelho, L. C., Laporte, G., Vis, I. F. (2016). An inventory-routing problem with pick- ups and deliveries arising in the replenishment of au- tomated teller machines. Transportation Science, 50, 1077–1091.

[8] Karagul, K., Aydemir, E., Tokat, S. (2016). Using 2- Opt based evolution strategy for travelling salesman problem. An International Journal of Optimization and Control: Theories & Applications (IJOCTA), 6, 103–113.

[9] Crevier, B., Cordeau, J. F., Laporte, G. (2007). The multi-depot vehicle routing problem with inter-depot routes. European Journal of Operational Research, 176, 756–773.

[10] Braekers, K., Caris, A., Jenssens, G. K. (2014). Exact and meta-heuristic approach for a general heteroge- neous dial-a-ride problem with multiple depots. Trans- portation Research Part B, 67, 166–186.

[11] Contardo, C., Martinelli, R. (2014). A new exact al- gorithm for the multi-depot vehicle routing problem under capacity and route length constraints. Discrete Optimization, 12, 129–146.

[12] Montoya-Torres, J. R., Franco, J. L., Isaza, S. N., Jimnez, H. F., Herazo-Padilla, N. (2015). A literature review on the vehicle routing problem with multiple depots. Computers & Industrial Engineering, 79, 115– 129.

[13] Ko>c, C>., Karao◇glan, I(˙) . (2012). A mathematical model for the vehicle routing problem with time windows and multiple use of vehicles. Journal of the Faculty of Engineering and Architecture of Gazi University, 27, 569–576.

[14] 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.

[15] Olivera, A., Viera, O. (2007). Adaptive memory pro- gramming for the vehicle routing problem with multi- ple trips. Computers & Operations Research, 34, 28– 47.

[16] Xu, H., Chen, Z. L., Rajagopal, S., Arunapuram, S.(2003). Solving a practical pickup and delivery prob- lem. Transportation Science, 37, 347–364.

[17] Sigurd, M., Pisinger, D., Sig, M. (2004). Scheduling transportation of live animals to avoid the spread of diseases. Transportation Science, 38, 197–209.

[18] Battarra, M., Cordeau, J-F., Iori, M. (2014). Pickup- and-delivery problems for goods transportation. In Toth, P. Vigo, D., eds. Vehicle Routing: Prob- lems, Methods, and Applications (pp. 161–192). MOS- SIAM Series on Optimization, Philadelphia.

[19] Berbeglia, G., Cordeau, J.-F., Gribkovskaia, I., La- porte, G. (2007). Static pickup and delivery problems: A classiﬁcation scheme and survey. TOP: An O伍cial Journal of the Spanish Society of Statistics and Oper- ations Research, 15, 1–31.

[20] Ko>c, C>., Laporte, G. (2018). Vehicle routing with backhauls: Review and research perspectives. Com- puters & Operations Research, 91, 79–91.

[21] Parragh, S. N., Doerner, K. F., Hartl, R. F. (2008a). A survey on pickup and delivery problems. PartI: Trans- portation between customers and depot. Journal f¨ur Betriebswirtschaft, 58, 21–51.

[22] Parragh, S. N., Doerner, K. F., Hartl, R. F. (2008b). A survey on pickup and delivery problems. Part II: Transportation between pickup and delivery locations. Journal f¨ur Betriebswirtschaft, 58, 81–117.

[23] Casas, I., Malik, A., Delmelle, E. M., Karwan, M. H., Batta, R. (2007). An automated network genera- tion procedure for routing of unmanned aerial vehicles (UAVs) in a GIS environment. Networks and Spatial Economics, 7, 153–176.

[24] Bozkaya, B., Yanik, S., Balcisoy, S. (2010). A GIS- based optimization framework for competitive multi- facility location-routing problem. Networks and Spa- tial Economics, 10, 297–320.

[25] Samanlioglu, F. (2013). A multi-objective mathemati- cal model for the industrial hazardous waste location- routing problem. European Journal of Operational Research, 226, 332–340.

[26] Yanik, S., Bozkaya, B., de Kervenoael, R. (2014). A new VRPPD model and a hybrid heuristic solution ap- proach for e-tailing. European Journal of Operational Research, 236, 879–890.

[27] Krichen, S., Faiz, S., Tlili, T., Tej, K. (2014). Tabu- based GIS for solving the vehicle routing problem. Ex- pert Systems with Applications, 41, 6483–6493.

[28] Vlachopoulou, M., Silleos, G., Manthou, V. (2001). Geographic information systems in warehouse site se- lection decisions. International Journal of Production Economics, 71, 205–212.

[29] ArcGIS, (2017). ArcGIS Network Analyst Tutorial. http://desktop.arcgis.com/en/arcmap/.

[30] Glover, F.W., Laguna, M. (1998). Tabu search. Kluwer Academic, Massachusetts.

[31] Brand˜ao, J. (2009). A deterministic tabu search algo- rithm for the 丑eet size and mix vehicle routing prob- lem. European Journal of Operational Research, 195, 716–728.

[32] Brand˜ao, J. (2011). A tabu search algorithm for the heterogeneous ﬁxed 丑eet vehicle routing problem. Computers & Operations Research, 38, 140–151.

[33] Gendreau, M., Hertz, A., Laporte, G. (1994). A tabu search heuristic for the vehicle routing problem. Man- agement Science, 40, 1276–1290.

Previous article in this issue

Next article in this issue

An International Journal of Optimization and Control: Theories & Applications, Electronic ISSN: 2146-5703 Print ISSN: 2146-0957, Published by AccScience Publishing