Abstract
In this article we present a Vehicle Routing Problem (VRP) faced by a large distribution company in the Northeast of Spain. The company distributes products from its central facilities to a chain of around 400 stores all over the country. One of the peculiarities of the VRP of this company – which is common among real-life VRPs – is the presence of a heterogeneous fleet where vehicles with different capacities can make multiple trips during a single day. This variant of the problem, which we refer as Heterogeneous Fleet and Multi-trip VRP, has been barely studied in the literature. To solve the problem, we use an algorithm based on the well-known savings heuristic with a biased-randomization effect and three local search operations. Our approach is simple to implement as it needs few parameters and no fine-tuning processes, which are usually cumbersome and require experts’ involvement. We obtain savings of around 12 per cent in transportation costs, which represent around €30 000 saved per week.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Baldacci, R., Battarra, M. and Vigo, D. (2008) Routing a heterogeneous fleet of vehicles. In: B. Golden, S. Raghavan and E.E. Wasil (eds.) The Vehicle Routing Problem: Latest Advances and New Challenges. New York: Springer, pp. 3–27.
Brandao, J. (2011) A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem. Computers and Operations Research 38 (1): 140–151.
Clarke, G. and Wright, J. (1964) Scheduling of vehicles from a central depot to a number of delivering points. Operations Research 12 (4): 568–581.
Croes, G. (1958) A method for solving traveling salesman problems. Operations Research 6 (6): 791–812.
Dantzig, G. and Ramser, J. (1959) The truck dispatching problem. Management Science 6 (1): 80–91.
Euchi, J. and Chabchoub, H. (2010) A hybrid tabu search to solve the heterogeneous fixed fleet vehicle routing problem. Logistics Research 2 (1): 3–11.
Gendreau, M., Laporte, G., Musaraganyi, C. and Taillard, E.D. (1999) A tabu search heuristic for the heterogeneous fleet vehicle routing problem. Computers & Operations Research 26 (12): 1153–1173.
Golden, B., Assad, A., Levy, L. and Gheysens, F. (1984) The fleet size and mix vehicle-routing problem. Computers & Operations Research 11 (1): 49–66.
Juan, A.A., Faulin, J., Jorba, J., Caceres, J. and Marques, J. (2011a) Using parallel & distributed computing for solving real-time vehicle routing problems with stochastic demands. Annals of Operations Research, http://link.springer.com/article/10.1007/s10479-011-0918-z.
Juan, A.A., Faulin, J., Jorba, J., Riera, D., Masip, D. and Barrios, B. (2011b) On the use of Monte Carlo simulation, cache and splitting techniques to improve the Clarke and Wright savings heuristics. Journal of the Operational Research Society 62 (6): 1085–1097.
Juan, A.A., Faulin, J., Ruiz, R., Barrios, B. and Caballé, S. (2010) The SR-GCWS hybrid algorithm for solving the capacitated vehicle routing problem. Applied Soft Computing 10 (1): 215–224.
Laporte, G. (2009) Fifty years of vehicle routing. Transportation Science 43 (4): 408–416.
Li, F., Golden, B. and Wasil, E. (2007) A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem. Computers and Operations Research 34 (9): 2734–2742.
Lourenço, H.R., Juan, A.A., Caceres-Cruz, J. and Grasas, A. (2013) A savings-based randomized heuristic for the heterogeneous fleet multi-trip vehicle routing problem. Working paper, Universitat Pompeu Fabra.
Osman, I.H. and Salhi, S. (1996) Local search strategies for the mix fleet routing problem. In: V. J. Rayward-Smith, I. H. Osman, C. R. Reeves and G. D. Smith (eds.). Modern Heuristics Search Methods. Chichester, UK: Wiley, pp. 131–153.
Prins, C. (2002) Efficient heuristics for the heterogeneous fleet multitrip VRP with applications to a large-scale real case. Journal of Mathematical Modelling and Algorithms 1 (2): 135–150.
Prins, C. (2009) Two memetic algorithms for heterogeneous fleet vehicle routing problems. Engineering Applications of Artificial Intelligence 22 (6): 916–928.
Rand, G.K. (2009) The life and times of the savings method for vehicle routing problems. Orion 25 (2): 125–145.
Tarantilis, C.D., Kiranoudis, C.T. and Vassiliadis, V.S. (2004) A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem. European Journal of Operational Research 152 (1): 148–158.
Toth, P. and Vigo, D. (eds.) (2002) The Vehicle Routing Problem. Monographs on Discrete Mathematics and Applications. Philadelphia, PA: SIAM.
Acknowledgements
This work has been partially supported by the Spanish Ministry of Science and Innovation (ECO2009-11307, TRA2010-21644-C03) and the CYTED-HAROSA Network (CYTED2010-511RT0419), in the context of the IN3-ICSO program (http://dpcs.uoc.edu) and the Business Analytics Research Group (http://www.upf.edu/barg/). We acknowledge the personnel of the distribution company for their cooperation in this project.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Grasas, A., Caceres-Cruz, J., Lourenço, H. et al. Vehicle routing in a Spanish distribution company: Saving using a savings-based heuristic. OR Insight 26, 191–202 (2013). https://doi.org/10.1057/ori.2013.2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/ori.2013.2