The vehicle routing problem consists of determining a set of routes for a fleet of vehicles to meet the demands of a given set of customers. The development and improvement of techniques for finding better solutions to this optimization problem have attracted considerable interest since such techniques can yield significant savings in transportation costs. The heterogeneous fleet vehicle routing problem is distinguished by the consideration of a heterogeneous fleet of vehicles, which is a very common scenario in real-world applications, rather than a homogeneous one. Hybrid versions of metaheuristics that incorporate data mining techniques have been applied to solve various optimization problems, with promising results. In this paper, we propose hybrid versions of a multi-start heuristic for the heterogeneous fleet vehicle routing problem based on the Iterated Local Search metaheuristic through the incorporation of data mining techniques. The results obtained in computational experiments show that the proposed hybrid heuristics demonstrate superior performance compared with the original heuristic, reaching better average solution costs with shorter run times.
Accepté le :
DOI : 10.1051/ro/2017072
Mots clés : Hybrid metaheuristic, data mining, heterogeneous fleet vehicle routing problem
@article{RO_2018__52_3_661_0,
author = {Rodrigues de Holanda Maia, Marcelo and Plastino, Alexandre and Vaz Penna, Puca Huachi},
title = {Hybrid data mining heuristics for the heterogeneous fleet vehicle routing problem},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {661--690},
publisher = {EDP-Sciences},
volume = {52},
number = {3},
year = {2018},
doi = {10.1051/ro/2017072},
mrnumber = {3868439},
zbl = {1405.90031},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2017072/}
}
TY - JOUR AU - Rodrigues de Holanda Maia, Marcelo AU - Plastino, Alexandre AU - Vaz Penna, Puca Huachi TI - Hybrid data mining heuristics for the heterogeneous fleet vehicle routing problem JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2018 SP - 661 EP - 690 VL - 52 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2017072/ DO - 10.1051/ro/2017072 LA - en ID - RO_2018__52_3_661_0 ER -
%0 Journal Article %A Rodrigues de Holanda Maia, Marcelo %A Plastino, Alexandre %A Vaz Penna, Puca Huachi %T Hybrid data mining heuristics for the heterogeneous fleet vehicle routing problem %J RAIRO - Operations Research - Recherche Opérationnelle %D 2018 %P 661-690 %V 52 %N 3 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2017072/ %R 10.1051/ro/2017072 %G en %F RO_2018__52_3_661_0
Rodrigues de Holanda Maia, Marcelo; Plastino, Alexandre; Vaz Penna, Puca Huachi. Hybrid data mining heuristics for the heterogeneous fleet vehicle routing problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 3, pp. 661-690. doi : 10.1051/ro/2017072. http://www.numdam.org/articles/10.1051/ro/2017072/
[1] , and , TTT plots: a perl program to create time-to-target plots. Optimiz. Lett. 1 (2007) 355–366 | DOI | MR | Zbl
[2] , and , Routing a heterogeneous fleet of vehicles, in The Vehicle Routing Problem: Latest Advances and New Challenges, edited by , and . Springer US, New York NY, USA (2008) 3–27 | MR | Zbl
[3] and , A unified exact method for solving different classes of vehicle routing problems. Math. Program. 120 (2009) 347–380 | DOI | MR | Zbl
[4] , , and , A hybrid data mining GRASP with path-relinking. Comput. Oper. Res. 40 (2013) 3159–3173 | DOI | Zbl
[5] , A deterministic tabu search algorithm for the fleet size and mix vehicle routing problem. Eur. J. Oper. Res. 195 (2009) 716–728 | DOI | Zbl
[6] , A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem. Comput. Oper. Res. 38 (2011) 140–151 | DOI | MR | Zbl
[7] and , A column generation approach to the heterogeneous fleet vehicle routing problem. Comput. Oper. Res. 34 (2007) 2080–2095 | DOI | Zbl
[8] , , and , A multi-thread GRASPxELS for the heterogeneous capacitated vehicle routing problem, in Hybrid Metaheuristics, edited by . Springer Berlin Heidelberg, (2013) 237–269 | DOI
[9] , and , A GRASPxELS with depth first search split procedure for the HVRP. Tech. Report LIMOS/RR-10-08. Laboratoire d’Informatique, de Modélisation et d’Optimisation des Systèmes (2010)
[10] , and , Efficient frameworks for greedy split and new depth first search split procedures for routing problems. Comput. Oper. Res. 38 (2011) 723–739 | DOI | MR | Zbl
[11] and , Greedy randomized adaptive search procedures. J. Global Optim. 6 (1995) 109–133 | DOI | MR | Zbl
[12] and , The vehicle scheduling problem with multiple vehicle types. J. Oper. Res. Soc. 39 (1988) 577–583 | DOI | Zbl
[13] , and , A new intuitional algorithm for solving heterogeneous fixed fleet routing problems: Passenger pickup algorithm. Appl. Math. Comput. 181 (2006) 1552–1567 | Zbl
[14] , , and , A tabu search heuristic for the heterogeneous fleet vehicle routing problem. Comput. Oper. Res. 26 (1999) 1153–1173 | DOI | Zbl
[15] , , and , The fleet size and mix vehicle routing problem. Comput. Oper. Res. 11 (1984) 49–66 | DOI | Zbl
[16] and , Efficiently using prefix-trees in mining frequent itemsets, in Proc. of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations (2003)
[17] , and , Extending the hybridization of metaheuristics with data mining to a broader domain, in Proc. 16th Int. Conf. Enterprise Infor. Sys. SCITEPRESS (2014) 395–406
[18] , and , Extending the hybridization of metaheuristics with data mining: Dealing with sequences. Intell. Data Anal. 20 (2016) 1133–1156 | DOI
[19] , and , Data mining: Concepts and techniques. 3rded. Morgan Kaufmann Publishers Inc. San Francisco, CA, USA (2011) | Zbl
[20] , , , and , Industrial aspects and literature survey: Fleet composition and routing. Comput. Oper. Res. 37 (2010) 2041–2061 | DOI | MR | Zbl
[21] , and , A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem. Eur. J. Oper. Res. 197 (2009) 509–518 | DOI | Zbl
[22] , , and , Thirty years of heterogeneous vehicle routing. Eur. J. Oper. Res. 249 (2016) 1–21 | DOI | MR | Zbl
[23] and , A hybrid algorithm of local search for the heterogeneous fixed fleet vehicle routing problem. J. Appl. Ind. Math. 9 (2015) 503–518 | DOI | MR
[24] and , Complexity of vehicle routing and scheduling problems. Networks 11 (1981) 221–227 | DOI
[25] , and , A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem. Comput. Oper. Res. 34 (2007) 2734–2742 | DOI | Zbl
[26] , A hybrid population heuristic for the heterogeneous vehicle routing problems. Transp. Res. Part E Logist. Transp. Rev. 54 (2013) 67–78 | DOI
[27] , and , An effective genetic algorithm for the fleet size and mix vehicle routing problems. Transp. Res. Part E Logist. Transp. Rev. 45 (2009) 434–445 | DOI
[28] , and , Iterated local search, in Handbook of Metaheuristics, edited by and . Kluwer Academic Publishers Dordrecht, Netherlands (2003) 321–353 | MR | Zbl
[29] , Multi-start methods, in Handbook of Metaheuristics, edited by and . Kluwer Academic Publishers Dordrecht, Netherlands (2003) 355–368 | DOI | MR | Zbl
[30] , , , and , Making a state-of-the-art heuristic faster with data mining. Ann. Oper. Res. 263 (2018) 141–162 | DOI | MR | Zbl
[31] , and , An iterated local search heuristic for the heterogeneous fleet vehicle routing problem. J. Heuristics 19 (2013) 201–232 | DOI
[32] , , and , New compound neighborhoods structures for the heterogeneous fixed fleet vehicle routing problem, in Proc. of the XLV Brazilian Symp. Oper. Res. (2013) 3623–3633
[33] , , , and , Adaptive and multi-mining versions of the DM-GRASP hybrid metaheuristic. J. Heuristics 20 (2014) 39–74 | DOI
[34] , , , , , and , A hybrid data mining metaheuristic for the p-median problem, in Proc. ofthe 2009 SIAM Int. Conf. Data Mining, edited by , , and . SIAM 2009 305–316 | DOI | MR
[35] , , , and , A hybrid data mining metaheuristic for the p-median problem. Stat. Anal. Data Min. 4 (2011) 313–335 | DOI | MR | Zbl
[36] ,Two memetic algorithms for heterogeneous fleet vehicle routing problems. Eng. Appl. Artif. Intell. 22 (2009) 916–928 | DOI
[37] , and , Hybridization of GRASP metaheuristic with data mining techniques. J. Math. Model. Algorithms 5 (2006) 23–41 | DOI | MR | Zbl
[38] , , and , Hybridization of GRASP metaheuristic with data mining techniques, in Proc. of the First International Workshop on Hybrid Metaheuristics (2004) 69–78 | MR | Zbl
[39] , and , Applications of the DM-GRASP heuristic: a survey. Int. Trans. Oper. Res. 15 (2008) 387–416 | DOI | MR | Zbl
[40] , , , and , A hybrid GRASP with data mining for efficient server replication for reliable multicast, in GLOBECOM ’06. IEEE (2006) 1–6
[41] , , and , A hybrid GRASP with data mining for the maximum diversity problem, in Hybrid Metaheuristics, edited by , , and . Springer Berlin Heidelberg (2005) 116–127 | DOI
[42] , , and , A hybrid algorithm for the heterogeneous fleet vehicle routing problem. Eur. J. Oper. Res. 221 (2012) 285–295 | DOI | MR | Zbl
[43] , A heuristic column generation method for the heterogeneous fleet VRP. RAIRO: OR 33 (1999) 1–14 | DOI | Numdam | MR | Zbl
[44] , and , A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem. Eur. J. Oper. Res. 152 (2004) 148–158 | DOI | MR | Zbl
[45] and , An overview of vehicle routing problems, in The Vehicle Routing Problem, edited by and . SIAM Philadelphia, PA, USA (2001) 1–26 | MR | Zbl
[46] , , and , A unified solution framework for multi-attribute vehicle routing problems. Eur. J. Oper. Res. 234 (2014) 658–673 | DOI | MR | Zbl
[47] and , Tabu search variants for the mix fleet vehicle routing problem. J. Oper. Res. Soc. 53 (2002) 768–782 | DOI | Zbl
Cité par Sources :
