Abstract
Various metaheuristic approaches have emerged in recent years to solve the capacitated vehicle routing problem (CVRP), a well-known \(\mathcal {NP}-\) hard problem in routing. In CVRP, the objective is to design the route set at a lower cost for a homogenous fleet of vehicles, starting from and going back to the depot, to meet the needs and expectations of all the customers. In this paper, we propose an ILS-VND approach which is a hybrid of Iterated Local Search (ILS) and Variable Neighborhood Descent (VND) approaches. Although both ILS and VND approaches, independently provide good solutions, we found that the hybrid approach gives better solutions than either approach independently. We demonstrate the effectiveness of our approach through experiments carried out on widely used benchmark instances. Numerical experiments show that the proposed method outperforms other local searches and metaheuristics. We also, propose a Decision Support System (DSS) that integrates a Geographical Information System (GIS) to solve the problem under scrutiny. In order to demonstrate the performance of the proposed DSS in terms of solution quality, we apply it for a real case on the city of Jendouba in the north west of Tunisia. The results are then highlighted in a cartographic format using Google Maps.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Dantzig, G.B., Ramser, J.H.: The truck dispatching problem. Manage. Sci. 6, 80–91 (1959)
Alba, E., Dorronsoro, B.: Computing nine new best-so-far solutions for capacitated VRP with a cellular genetic algorithm. Inform. Process. Lett. 6, 225–230 (2006)
Roberto, B., Aristide, M., Roberto, R.: Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints. Eur. J. Oper. Res. 218, 1–6 (2012)
Claudio, C., Rafael, M.: A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints. Discrete Optim. 12, 129–146 (2014)
Juan, C.R., Afsar, H.M., Christian, P.: Mathematical formulations and exact algorithm for the multitrip cumulative capacitated single-vehicle routing problem. Eur. J. Oper. Res. 249, 93–104 (2016)
Leonardo, J., Reinaldo, M.: Heuristic algorithms for a three-dimensional loading capacitated vehicle routing problem in a carrier. Comput. Indus. Eng. 88, 110–130 (2015)
Thibaut, V., Teodor, G.C., Michel, G., Christian, P.: Heuristics for multi-attribute vehicle routing problems: a survey and synthesis. Eur. J. Oper. Res. 231, 1–21 (2013)
Augerat, P., Belenguer, J.M., Benavent, E., Corbern, A., Naddef, D.: Separating capacity constraints in the CVRP using tabu search. Eur. J. Oper. Res. 106, 546–557 (1998)
Yi, T., Fan, W.: An effective tabu search approach with improved loading algorithms for the 3L-CVRP. Comput. Oper. Res. 55, 127–140 (2015)
Lijun, W., Zhenzhen, Z., Defu, Z., Andrew, L.: A variable neighborhood search for the capacitated vehicle routing problem with two-dimensional loading constraints. Eur. J. Oper. Res. 243, 798–814 (2015)
Diego, C., Nabil, A., Dominique, F., Daniele, V.: An iterated local search for the multi-commodity multi-trip vehicle routing problem with time windows. Comput. Oper. Res. 51, 257–267 (2014)
Sandra, U.N., Christian, P., Roberto, W.C.: An effective memetic algorithm for the cumulative capacitated vehicle routing problem. Comput. Oper. Res. 37, 1877–1885 (2010)
Silvia, M., Irene, L.: An ant colony algorithm for the capacitated vehicle routing. Electron. Disc. Math. 18, 181–186 (2014)
Lourenco, H.R., Martin, O., Stutzle, T.: Iterated Local Search. Kluwer Academic Publishers, Norwell, pp. 321–353 (2002)
Clarke, G., Wright, J.W.: Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res. 12, 568–581 (1964)
Li, F., Golden, B.L., Wasil, E.A.: Very large-scale vehicle routing: new test problems. Comput. Oper. Res. 32, 1165–1179 (2005)
Pisinger, D., Ropke, S.: A general heuristic for vehicle routing problems. Comput. Oper. Res. 34, 2403–2435 (2007)
Groer, C., Golden, B.L., Wasil, E.A.: A parallel algorithm for the vehicle routing problems. INFORMS J. Comput. 23, 315–330 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Harzi, M., Krichen, S. (2016). A Decision Support System Based on Hybrid Metaheuristic for Solving the Constrained Capacitated Vehicle Routing Problem: The Tunisian Case. In: Rutkowski, L., Korytkowski, M., Scherer, R., Tadeusiewicz, R., Zadeh, L., Zurada, J. (eds) Artificial Intelligence and Soft Computing. ICAISC 2016. Lecture Notes in Computer Science(), vol 9692. Springer, Cham. https://doi.org/10.1007/978-3-319-39378-0_59
Download citation
DOI: https://doi.org/10.1007/978-3-319-39378-0_59
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-39377-3
Online ISBN: 978-3-319-39378-0
eBook Packages: Computer ScienceComputer Science (R0)