A rich vehicle routing problem arising in the replenishment of automated teller machines
DOI:
https://doi.org/10.11121/ijocta.01.2018.00572Keywords:
Vehicle routing, GIS, tabu search, recirculation automated teller machinesAbstract
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.
Downloads
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.
Downloads
Published
How to Cite
Issue
Section
License
Articles published in IJOCTA are made freely available online immediately upon publication, without subscription barriers to access. All articles published in this journal are licensed under the Creative Commons Attribution 4.0 International License (click here to read the full-text legal code). This broad license was developed to facilitate open access to, and free use of, original works of all types. Applying this standard license to your work will ensure your right to make your work freely and openly available.
Under the Creative Commons Attribution 4.0 International License, authors retain ownership of the copyright for their article, but authors allow anyone to download, reuse, reprint, modify, distribute, and/or copy articles in IJOCTA, so long as the original authors and source are credited.
The readers are free to:
- Share — copy and redistribute the material in any medium or format
- Adapt — remix, transform, and build upon the material
- for any purpose, even commercially.
- The licensor cannot revoke these freedoms as long as you follow the license terms.
under the following terms:
- Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
This work is licensed under a Creative Commons Attribution 4.0 International License.
