A Decision Support System Based on Hybrid Metaheuristic for Solving the Constrained Capacitated Vehicle Routing Problem: The Tunisian Case

详细信息    查看全文

• 关键词：CVRP ; Hybrid ILS ; VND metaheuristic ; ILS ; VND ; Decision support systems ; Geographical information system
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9692
• 期：1
• 页码：695-704
• 全文大小：902 KB
• 参考文献：1.Dantzig, G.B., Ramser, J.H.: The truck dispatching problem. Manage. Sci. 6, 80–91 (1959)MathSciNet CrossRef MATH
  2.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)MathSciNet CrossRef MATH
  3.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)MathSciNet CrossRef MATH
  4.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)MathSciNet CrossRef MATH
  5.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)MathSciNet CrossRef
  6.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)CrossRef
  7.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)MathSciNet CrossRef MATH
  8.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)CrossRef MATH
  9.Yi, T., Fan, W.: An effective tabu search approach with improved loading algorithms for the 3L-CVRP. Comput. Oper. Res. 55, 127–140 (2015)MathSciNet CrossRef
  10.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)CrossRef
  11.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)
  12.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)MathSciNet CrossRef MATH
  13.Silvia, M., Irene, L.: An ant colony algorithm for the capacitated vehicle routing. Electron. Disc. Math. 18, 181–186 (2014)MathSciNet MATH
  14.Lourenco, H.R., Martin, O., Stutzle, T.: Iterated Local Search. Kluwer Academic Publishers, Norwell, pp. 321–353 (2002)
  15.Clarke, G., Wright, J.W.: Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res. 12, 568–581 (1964)CrossRef
  16.Li, F., Golden, B.L., Wasil, E.A.: Very large-scale vehicle routing: new test problems. Comput. Oper. Res. 32, 1165–1179 (2005)CrossRef MATH
  17.Pisinger, D., Ropke, S.: A general heuristic for vehicle routing problems. Comput. Oper. Res. 34, 2403–2435 (2007)MathSciNet CrossRef MATH
  18.Groer, C., Golden, B.L., Wasil, E.A.: A parallel algorithm for the vehicle routing problems. INFORMS J. Comput. 23, 315–330 (2011)MathSciNet CrossRef MATH
  
• 作者单位：Marwa Harzi (19)
  Saoussen Krichen (20)
  
  19. VPNC Laboratory, Higher Institute of Management, University of Tunis, Tunis, Tunisia
  20. LARODEC Laboratory, Higher Institute of Management, University of Tunis, Tunis, Tunisia
  
• 丛书名：Artificial Intelligence and Soft Computing
• ISBN：978-3-319-39378-0
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9692

文摘

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.