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

Çağrı Koç, Mehmet Erbaş, Eren Ozceylan

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

Full Text:

PDF

References


O¨ zceylan, E., Uslu, A., Erba¸s, M., C¸ etinkaya, [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.

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

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

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.

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.

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

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.

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.

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.

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. Transportation Research Part B, 67, 166–186.

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.

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.

Koc¸, C¸ ., Karaog˘lan, 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.

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.

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

Xu, H., Chen, Z. L., Rajagopal, S., Arunapuram, S. (2003). Solving a practical pickup and delivery problem. Transportation Science, 37, 347–364.

Sigurd, M., Pisinger, D., Sig, M. (2004). Scheduling allocation problem of pharmacy warehouses: A case study in Gaziantep. An International Journal of Op- timization and Control: Theories & Applications (IJOCTA), 7, 117–129.

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.

Berbeglia, G., Cordeau, J.-F., Gribkovskaia, I., La- porte, G. (2007). Static pickup and delivery problems: A classification scheme and survey. TOP: An Official Journal of the Spanish Society of Statistics and Oper- ations Research, 15, 1–31.

Koc¸, C¸ ., Laporte, G. (2018). Vehicle routing with backhauls: Review and research perspectives. Com- puters & Operations Research, 91, 79–91.

Parragh, S. N., Doerner, K. F., Hartl, R. F. (2008a). A survey on pickup and delivery problems. Part I: Trans- portation between customers and depot. Journal fu¨r Betriebswirtschaft, 58, 21–51.

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 fu¨r Betriebswirtschaft, 58, 81–117.

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.

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.

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.

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.

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.

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

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

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

Branda˜o, J. (2009). A deterministic tabu search algo- rithm for the fleet size and mix vehicle routing prob- lem. European Journal of Operational Research, 195, 716–728.

Branda˜o, J. (2011). A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem. Computers & Operations Research, 38, 140–151.

Gendreau, M., Hertz, A., Laporte, G. (1994). A tabu search heuristic for the vehicle routing problem. Management Science, 40, 1276–1290.




DOI: http://dx.doi.org/10.11121/ijocta.01.2018.00572

Refbacks

  • There are currently no refbacks.


Copyright (c) 2018 Çağrı Koç, Mehmet Erbaş, Eren OZCEYLAN

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

footer_771

   ithe_170     crossref_284         ind_131_43_x_117_117  Scopus  EBSCO_Host    ULAKBIM   PROQUEST   ZBMATH more...