Abstract
The Heterogeneous Fleet Vehicle Routing Problem with Time Windows (HFVRPTW) is here introduced. This combinatorial optimization problem is an extension of the well-known Vehicle Routing Problem (VRP), which belongs to the \(\mathcal {NP}\)-Hard class. As a corollary, our problem belongs to this class, a fact that promotes the development of approximative methods.
A mathematical programming formulation for the HFVRPTW is presented, and an exact solution method using CPLEX is implemented. A GRASP/VND methodology is also developed, combining five different local searches. The effectiveness of our proposal is studied in relation with the exact solver. Our proposal outperforms the exact CPLEX in terms of CPU times, and finds even better solutions under large-sized instances, where the exact solver halts after ten hours of continuous execution.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Baldacci, R., Bartolini, E., Mingozzi, A., Roberti, R.: An exact solution framework for a broad class of vehicle routing problems. Comput. Manage. Sci. 7(3), 229–268 (2010)
Bernal, J., Escobar, J.W., Linfati, R.: A granular tabu search algorithm for a real case study of a vehicle routing problem with a heterogeneous fleet and time windows. J. Ind. Eng. Manage. 10(4), 646 (2017)
Cömert, S., Yazgan, H.R., Sertvuran, I., Şengül, H.: A new approach for solution of vehicle routing problem with hard time window: an application in a supermarket chain. Sādhanā 42(12), 2067–2080 (2017). https://doi.org/10.1007/s12046-017-0754-1
Dantzig, G.B., Ramser, J.H.: The truck dispatching problem. Manage. Sci. 6(1), 80 (1959)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)
Hansen, P.: Variable neighborhood search. In: Handbook of Heuristics. Springer International Publishing (2018)
Jiang, J., Ng, K.M., Poh, K.L., Teo, K.M.: Vehicle routing problem with a heterogeneous fleet and time windows. Exp. Syst. Appl. 41(8), 3748–3760 (2014)
Karp, R.M.: Reducibility among Combinatorial Problems, pp. 85–103. Springer, Boston (1972). https://doi.org/10.1007/978-1-4684-2001-2_9
Mor, A., Speranza, M.G.: Duality in nonlinear programming: a simplified applications-oriented development. 4OR - Q. J. Oper. Res. 18(2), 129–149 (2020)
Nagata, Y., Bräysy, O., Dullaert, W.: A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows. Comput. Oper. Res. 37(4), 724–737 (2010)
Pessoa, A., Sadykov, R., Uchoa, E.: Enhanced branch-cut-and-price algorithm for heterogeneous fleet vehicle routing problems. Eur. J. Oper. Res. 270, 530–543 (2018)
Pop, P.C., Fuksz, L., Marc, A.H.: A variable neighborhood search approach for solving the generalized vehicle routing problem. In: Polycarpou, M., de Carvalho, A.C.P.L.F., Pan, J.-S., Woźniak, M., Quintian, H., Corchado, E. (eds.) HAIS 2014. LNCS (LNAI), vol. 8480, pp. 13–24. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07617-1_2
Resende, M., Ribeiro, C.: Optimization by GRASP. Springer (2016). https://doi.org/10.1007/978-1-4939-6530-4
Schneider, M., Sand, B., Stenger, A.: A note on the time travel approach for handling time windows in vehicle routing problems. Comput. Oper. Res. 40(10), 2564–2568 (2013)
Solomon, M.M.: On the worst-case performance of some heuristics for the vehicle routing and scheduling problem with time window constraints. Networks 16(2), 161–174 (1986)
Taha, A., Hachimi, M., Moudden, A. : A discrete bat algorithm for the vehicle routing problem with time windows. In: 2017 International Colloquium on Logistics and Supply Chain Management (LOGISTIQUA), pp. 65–70, April 2017
Taş, D., Jabali, O., Van Woensel, T.: A vehicle routing problem with flexible time windows. Comput. Oper. Res. 52, 39–54 (2014)
Acknowledgements
This work is partially supported by Project ANII FCE_1_2019_1_156693 Teoría y Construcción de Redes de Máxima Confiabilidad, MATHAMSUD 19-MATH-03 Rare events analysis in multi-component systems with dependent components and STIC-AMSUD ACCON Algorithms for the capacity crunch problem in optical networks.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Barrero, L., Robledo, F., Romero, P., Viera, R. (2021). A GRASP/VND Heuristic for the Heterogeneous Fleet Vehicle Routing Problem with Time Windows. In: Mladenovic, N., Sleptchenko, A., Sifaleras, A., Omar, M. (eds) Variable Neighborhood Search. ICVNS 2021. Lecture Notes in Computer Science(), vol 12559. Springer, Cham. https://doi.org/10.1007/978-3-030-69625-2_12
Download citation
DOI: https://doi.org/10.1007/978-3-030-69625-2_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-69624-5
Online ISBN: 978-3-030-69625-2
eBook Packages: Computer ScienceComputer Science (R0)