A rich vehicle routing problem arising in the replenishment of automated teller machines
A rich vehicle routing problem arising in the replenishment of automated teller machines
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 fromthe depot, as well as from the branches to efficiently manage the inventoryshortages at ATMs. This rich VRP variant concerns with the joint multiple depots,pickup and delivery, multi-trip, and homogeneous fixed vehicle fleet. Wefirst mathematically formulate the problem as a mixed-integer linear programmingmodel. We then apply a Geographic Information System (GIS)-basedsolution method, which uses a tabu search heuristic optimization method, to areal dataset of one of the major bank. Our numerical results show that we areable to obtain solutions within reasonable solution time for this new and challengingpractical problem. The paper presents computational and managerialresults by analyzing the trade-offs between various constraints.
___
- Özceylan, E., Uslu, A., Erba¸s, M., Çetinkaya,
C., ˙I¸sleyen, S. K. (2017). Optimizing the locationallocation
problem of pharmacy warehouses: A case
study in Gaziantep. An International Journal of Optimization
and Control: Theories & Applications
(IJOCTA), 7, 117–129.
- Laporte, G. (2009). Fifty years of vehicle routing.
Transportation Science, 43, 408–416.
- Toth, P. Vigo, D., eds. (2014). Vehicle routing: Problems,
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 definition.
European Journal of Operational Research,
241, 1–14.
- Karaoglan, A. D., Gonen, D., Ucmus, E. (2011). Aircraft
routing and scheduling: A case study in an airline
company. An International Journal of Optimization
and Control: Theories & Applications (IJOCTA),
1, 27–43.
- Karagul, K., Gungor, I. (2014). A case study of heterogeneous
fleet vehicle routing problem: Touristic
distribution application in Alanya. An International
Journal of Optimization and Control: Theories & Applications
(IJOCTA), 4, 67–76.
- Van Anholt, R. G., Coelho, L. C., Laporte, G., Vis,
I. F. (2016). An inventory-routing problem with pickups
and deliveries arising in the replenishment of automated
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 heterogeneous
dial-a-ride problem with multiple depots. Transportation
Research Part B, 67, 166–186.
- Contardo, C., Martinelli, R. (2014). A new exact algorithm
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.
- Koç, Ç ., 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.
- 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 programming
for the vehicle routing problem with multiple
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
transportation of live animals to avoid the spread of
diseases. Transportation Science, 38, 197–209.
- Battarra, M., Cordeau, J-F., Iori, M. (2014). Pickupand-delivery
problems for goods transportation. In
Toth, P. Vigo, D., eds. Vehicle Routing: Problems,
Methods, and Applications (pp. 161–192). MOSSIAM
Series on Optimization, Philadelphia.
- Berbeglia, G., Cordeau, J.-F., Gribkovskaia, I., Laporte,
G. (2007). Static pickup and delivery problems:
A classification scheme and survey. TOP: An Official
Journal of the Spanish Society of Statistics and Operations
Research, 15, 1–31.
- Koç, Ç ., Laporte, G. (2018). Vehicle routing with
backhauls: Review and research perspectives. Computers
& Operations Research, 91, 79–91.
- Parragh, S. N., Doerner, K. F., Hartl, R. F. (2008a). A
survey on pickup and delivery problems. Part I: Transportation
between customers and depot. Journal f¨ur
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 f¨ur Betriebswirtschaft, 58, 81–117.
- 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.
- Bozkaya, B., Yanik, S., Balcisoy, S. (2010). A GISbased
optimization framework for competitive multifacility
location-routing problem. Networks and Spatial
Economics, 10, 297–320.
- Samanlioglu, F. (2013). A multi-objective mathematical
model for the industrial hazardous waste locationrouting
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 approach
for e-tailing. European Journal of Operational
Research, 236, 879–890.
- Krichen, S., Faiz, S., Tlili, T., Tej, K. (2014). Tabubased
GIS for solving the vehicle routing problem. Expert
Systems with Applications, 41, 6483–6493.
- Vlachopoulou, M., Silleos, G., Manthou, V. (2001).
Geographic information systems in warehouse site selection
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.
- Brand˜ao, J. (2009). A deterministic tabu search algorithm
for the fleet size and mix vehicle routing problem.
European Journal of Operational Research, 195,
716–728.
- Brandao, 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.