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.

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.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2017072
Classification : 90B06, 90C27, 90C59
Mots-clés : Hybrid metaheuristic, data mining, heterogeneous fleet vehicle routing problem
Rodrigues de Holanda Maia, Marcelo 1 ; Plastino, Alexandre 1 ; Vaz Penna, Puca Huachi 1

1 
@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] R.M. Aiex, M.G.C. Resende and C.C. Ribeiro, TTT plots: a perl program to create time-to-target plots. Optimiz. Lett. 1 (2007) 355–366 | DOI | MR | Zbl

[2] R. Baldacci, M. Battarra and D. Vigo, Routing a heterogeneous fleet of vehicles, in The Vehicle Routing Problem: Latest Advances and New Challenges, edited by B. Golden, S. Raghavan and E. Wasil. Springer US, New York NY, USA (2008) 3–27 | MR | Zbl

[3] R. Baldacci and A. Mingozzi, A unified exact method for solving different classes of vehicle routing problems. Math. Program. 120 (2009) 347–380 | DOI | MR | Zbl

[4] H. Barbalho, I. Rosseti, S.L. Martins and A. Plastino, A hybrid data mining GRASP with path-relinking. Comput. Oper. Res. 40 (2013) 3159–3173 | DOI | Zbl

[5] J. Brandão, 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] J. Brandão, A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem. Comput. Oper. Res. 38 (2011) 140–151 | DOI | MR | Zbl

[7] E. Choi and D.W. Tcha, A column generation approach to the heterogeneous fleet vehicle routing problem. Comput. Oper. Res. 34 (2007) 2080–2095 | DOI | Zbl

[8] C. Duhamel, C. Gouinaud, P. Lacomme and C. Prodhon, A multi-thread GRASPxELS for the heterogeneous capacitated vehicle routing problem, in Hybrid Metaheuristics, edited by E.G. Talbi. Springer Berlin Heidelberg, (2013) 237–269 | DOI

[9] C. Duhamel, P. Lacomme and C. Prodhon, 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] C. Duhamel, P. Lacomme and C. Prodhon, 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] T.A. Feo and M.G.C. Resende, Greedy randomized adaptive search procedures. J. Global Optim. 6 (1995) 109–133 | DOI | MR | Zbl

[12] J.A. Ferland and P. Michelon, The vehicle scheduling problem with multiple vehicle types. J. Oper. Res. Soc. 39 (1988) 577–583 | DOI | Zbl

[13] C. Gencer, İ. Top and E.K. Aydogan, A new intuitional algorithm for solving heterogeneous fixed fleet routing problems: Passenger pickup algorithm. Appl. Math. Comput. 181 (2006) 1552–1567 | Zbl

[14] M. Gendreau, G. Laporte, C. Musaraganyi and É.D. Taillard, A tabu search heuristic for the heterogeneous fleet vehicle routing problem. Comput. Oper. Res. 26 (1999) 1153–1173 | DOI | Zbl

[15] B. Golden, A. Assad, L. Levy and F. Gheysens, The fleet size and mix vehicle routing problem. Comput. Oper. Res. 11 (1984) 49–66 | DOI | Zbl

[16] G. Grahne and J. Zhu, Efficiently using prefix-trees in mining frequent itemsets, in Proc. of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations (2003)

[17] M. Guerine, I. Rosseti and A. Plastino, 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] M. Guerine, I. Rosseti and A. Plastino, Extending the hybridization of metaheuristics with data mining: Dealing with sequences. Intell. Data Anal. 20 (2016) 1133–1156 | DOI

[19] J. Han, M. Kamber and J. Pei, Data mining: Concepts and techniques. 3rded. Morgan Kaufmann Publishers Inc. San Francisco, CA, USA (2011) | Zbl

[20] A. Hoff, H. Andersson, M. Christiansen, G. Hasle and A. Løkketangen, Industrial aspects and literature survey: Fleet composition and routing. Comput. Oper. Res. 37 (2010) 2041–2061 | DOI | MR | Zbl

[21] A. Imran, S. Salhi and N.A. Wassan, A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem. Eur. J. Oper. Res. 197 (2009) 509–518 | DOI | Zbl

[22] Ç. Koç, T. Bektaş, O. Jabali and G. Laporte, Thirty years of heterogeneous vehicle routing. Eur. J. Oper. Res. 249 (2016) 1–21 | DOI | MR | Zbl

[23] Y.A. Kochetov and A.V. Khmelev, 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] J.K. Lenstra and A.H.G.R. Kan, Complexity of vehicle routing and scheduling problems. Networks 11 (1981) 221–227 | DOI

[25] F. Li, B. Golden and E. Wasil, A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem. Comput. Oper. Res. 34 (2007) 2734–2742 | DOI | Zbl

[26] S. Liu, A hybrid population heuristic for the heterogeneous vehicle routing problems. Transp. Res. Part E Logist. Transp. Rev. 54 (2013) 67–78 | DOI

[27] S. Liu, W. Huang and H. Ma, 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] H.R. Lourenço, O.C. Martin and T. Stützle, Iterated local search, in Handbook of Metaheuristics, edited by F. Glover and G.A. Kochenberger. Kluwer Academic Publishers Dordrecht, Netherlands (2003) 321–353 | MR | Zbl

[29] R. Martí, Multi-start methods, in Handbook of Metaheuristics, edited by F. Glover and G.A. Kochenberger. Kluwer Academic Publishers Dordrecht, Netherlands (2003) 355–368 | DOI | MR | Zbl

[30] D. Martins, G.M. Vianna, I. Rosseti, S.L. Martins and A. Plastino, Making a state-of-the-art heuristic faster with data mining. Ann. Oper. Res. 263 (2018) 141–162 | DOI | MR | Zbl

[31] P.H.V. Penna, A. Subramanian and L.S. Ochi, An iterated local search heuristic for the heterogeneous fleet vehicle routing problem. J. Heuristics 19 (2013) 201–232 | DOI

[32] P.H.V. Penna, T. Vidal, L.S. Ochi and C. Prins, 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] A. Plastino, B. Barbalho, L.F.M. Santos, R. Fuchshuber and S.L. Martins, Adaptive and multi-mining versions of the DM-GRASP hybrid metaheuristic. J. Heuristics 20 (2014) 39–74 | DOI

[34] A. Plastino, E.R. Fonseca, R. Fuchshuber, S.L. Martins, A.A. Freitas, M. Luis and S. Salhi, A hybrid data mining metaheuristic for the p-median problem, in Proc. ofthe 2009 SIAM Int. Conf. Data Mining, edited by H. Park, K. Wang, C. Apte and M.J. Zaki. SIAM 2009 305–316 | DOI | MR

[35] A. Plastino, R. Fuchshuber, S.L. Martins, A.A. Freitas and A. Salhi, A hybrid data mining metaheuristic for the p-median problem. Stat. Anal. Data Min. 4 (2011) 313–335 | DOI | MR | Zbl

[36] C. Prins,Two memetic algorithms for heterogeneous fleet vehicle routing problems. Eng. Appl. Artif. Intell. 22 (2009) 916–928 | DOI

[37] M.H. Ribeiro, A. Plastino and S.L. Martins, Hybridization of GRASP metaheuristic with data mining techniques. J. Math. Model. Algorithms 5 (2006) 23–41 | DOI | MR | Zbl

[38] M.H. Ribeiro, V.A. Trindade, A. Plastino and S.L. Martins, Hybridization of GRASP metaheuristic with data mining techniques, in Proc. of the First International Workshop on Hybrid Metaheuristics (2004) 69–78 | MR | Zbl

[39] L.F. Santos, S.L. Martins and A. Plastino, Applications of the DM-GRASP heuristic: a survey. Int. Trans. Oper. Res. 15 (2008) 387–416 | DOI | MR | Zbl

[40] L.F. Santos, R. Milagres, C.V. Albuquerque, S. Martins and A. Plastino, A hybrid GRASP with data mining for efficient server replication for reliable multicast, in GLOBECOM ’06. IEEE (2006) 1–6

[41] L.F. Santos, M.H. Ribeiro, A. Plastino and S.L. Martins, A hybrid GRASP with data mining for the maximum diversity problem, in Hybrid Metaheuristics, edited by M.J. Blesa, C. Blum, A. Roli and M. Sampels. Springer Berlin Heidelberg  (2005) 116–127 | DOI

[42] A. Subramanian, P.H.V. Penna, E. Uchoa and L.S. Ochi, A hybrid algorithm for the heterogeneous fleet vehicle routing problem. Eur. J. Oper. Res. 221 (2012) 285–295 | DOI | MR | Zbl

[43] É.D. Taillard, A heuristic column generation method for the heterogeneous fleet VRP. RAIRO: OR 33 (1999) 1–14 | DOI | Numdam | MR | Zbl

[44] C.D. Tarantilis, C.T. Kiranoudis and V.S. Vassiliadis, A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem. Eur. J. Oper. Res. 152 (2004) 148–158 | DOI | MR | Zbl

[45] P. Toth and D. Vigo, An overview of vehicle routing problems, in The Vehicle Routing Problem, edited by P. Toth and D. Vigo. SIAM Philadelphia, PA, USA (2001) 1–26 | MR | Zbl

[46] T. Vidal, T.G. Crainic, M. Gendreau and C. Prins, A unified solution framework for multi-attribute vehicle routing problems. Eur. J. Oper. Res. 234 (2014) 658–673 | DOI | MR | Zbl

[47] N.A. Wassan and I.H. Osman, Tabu search variants for the mix fleet vehicle routing problem. J. Oper. Res. Soc. 53 (2002) 768–782 | DOI | Zbl

Cité par Sources :