A hybrid genetic algorithm for the vehicle routing problem with three-dimensional loading constraints
RAIRO - Operations Research - Recherche Opérationnelle, Tome 46 (2012) no. 1, pp. 63-82.

This paper addresses a Three-Dimensional Loading Capacitated Vehicle Routing Problem (3L-CVRP) which combines a three-dimensional loading problem and vehicle routing problem in distribution logistics. The problem requires the combinatorial optimization of a feasible loading solution and a successive routing of vehicles to satisfy client demands, where all vehicles must start and terminate at a central depot. In spite of its clear practical significance in the real world of distribution management, 3L-CVRP in literature is very limited for its high combinatorial complexity. We solve this problem by a hybrid approach which combines Genetic Algorithm and Tabu Search (GATS). Genetic algorithm is developed for vehicle routing and tabu search for three-dimensional loading, while these two algorithms are integrated for the combinatorial problem. We computationally evaluate this hybrid genetic algorithm on all publicly available test instances, and obtain new best solutions for several instances.

DOI : 10.1051/ro/2012008
Classification : 97M40
Mots-clés : vehicle routing, three-dimensional loading, genetic algorithm, tabu search 
@article{RO_2012__46_1_63_0,
     author = {Miao, Lixin and Ruan, Qingfang and Woghiren, Kevin and Ruo, Qi},
     title = {A hybrid genetic algorithm for the vehicle routing problem with three-dimensional loading constraints},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {63--82},
     publisher = {EDP-Sciences},
     volume = {46},
     number = {1},
     year = {2012},
     doi = {10.1051/ro/2012008},
     mrnumber = {2934893},
     zbl = {1241.90015},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2012008/}
}
TY  - JOUR
AU  - Miao, Lixin
AU  - Ruan, Qingfang
AU  - Woghiren, Kevin
AU  - Ruo, Qi
TI  - A hybrid genetic algorithm for the vehicle routing problem with three-dimensional loading constraints
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2012
SP  - 63
EP  - 82
VL  - 46
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2012008/
DO  - 10.1051/ro/2012008
LA  - en
ID  - RO_2012__46_1_63_0
ER  - 
%0 Journal Article
%A Miao, Lixin
%A Ruan, Qingfang
%A Woghiren, Kevin
%A Ruo, Qi
%T A hybrid genetic algorithm for the vehicle routing problem with three-dimensional loading constraints
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2012
%P 63-82
%V 46
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2012008/
%R 10.1051/ro/2012008
%G en
%F RO_2012__46_1_63_0
Miao, Lixin; Ruan, Qingfang; Woghiren, Kevin; Ruo, Qi. A hybrid genetic algorithm for the vehicle routing problem with three-dimensional loading constraints. RAIRO - Operations Research - Recherche Opérationnelle, Tome 46 (2012) no. 1, pp. 63-82. doi : 10.1051/ro/2012008. http://www.numdam.org/articles/10.1051/ro/2012008/

[1] B. Andreas, A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints. Comput. Oper. Res. 39 (2012) 2248-2257. | Zbl

[2] B.M. Baker and M.A. Ayechew, A genetic algorithm for the vehicle routing problem. Comput. Oper. Res. 30 (2003) 787-800. | MR | Zbl

[3] B.S. Baker, E.G. Coffman Jr., and R.L. Rivest, Orthogonal packings in two dimensions. SIAM J. Comput. 9 (1980) 846-855. | MR | Zbl

[4] A. Bortfeldt and H. Gehring, A hybrid genetic algorithm for the container loading problem. Eur. J. Oper. Res. 131 (2001) 143-161. | Zbl

[5] J. Cordeau and G. Laporte, Tabu search heuristics for the vehicle routing problem. Metaheuristic Optimization via Memory and Evolution 30 (2005) 145-163. | MR | Zbl

[6] J. Cordeau, M. Gendreau, A. Hertz, G. Laporte and J. Sormany, New heuristics for the vehicle routing problem. Logistics Systems : Design and Optimization (2005) 279-297. | Zbl

[7] T.G Crainic, G. Perboli and R. Tadei, Extreme point-based heuristics for three-dimensional bin packing. Informs J. Comput. 20 (2008) 368-384. | MR | Zbl

[8] T.G. Crainic, G. Perboli and R. Tadei, TS2PACK : A two-level tabu search for the three-dimensional bin packing problem. Eur. J. Oper. Res. 195 (2009) 744-760. | Zbl

[9] K.F. Doerner, G. Fuellerer, R.F. Hartl, M. Gronalt, and M. Iori, Metaheuristics for the vehicle routing problem with loading constraints. Networks 49 (2007) 294-307. | MR | Zbl

[10] C. Duhamel, P. Lacomme, A. Quilliot and H. Toussaint, A multi-start evolutionary local search for the two-dimensional loading capacitated vehicle routing problem. Comput. Oper. Res. 38 (2011) 617-640. | Zbl

[11] M. Eley, Solving container loading problems by block arrangement. Eur. J. Oper. Res. 141 (2002) 393-409. | MR | Zbl

[12] O. Faroe, D. Pisinger and M. Zachariasen, Guided local search for the three-dimensional bin-packing problem. Informs J. Comput. 15 (2003) 267-283. | MR | Zbl

[13] G. Fuellerer, K.F. Doerner, R.F. Hartl and M. Iori, Ant colony optimization for the two-dimensional loading vehicle routing problem. Comput. Oper. Res. 36 (2009) 655-673. | Zbl

[14] G. Fuellerer, K.F. Doerner, R.F. Hartl and M. Iori, Metaheuristics for vehicle routing problems with three-dimensional loading constraints. Eur. J. Oper. Res. 201 (2010) 751-759. | Zbl

[15] R. Fukasawa, H. Longo, J. Lysgaard, M.P.D. Aragão, M. Reis, E. Uchoa and R.F. Werneck, Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Program. 106 (2006) 491-511. | MR | Zbl

[16] M. Gendreau, M. Iori, G. Laporte and S. Martello, A tabu search algorithm for a routing and container loading problem. Trans. Sci. 40 (2006) 342-350.

[17] M. Gendreau, M. Iori, G. Laporte and S. Martello, A Tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints. Networks 51 (2008) 4-18. | MR | Zbl

[18] B.E. Gillett and R.M. Leland, A heuristic algorithm for the vehicle-dispatch problem. Oper. Res. 22 (1974) 340-349. | Zbl

[19] M. Iori, Metaheuristic algorithms for combinatorial optimization problems. Ph.D. thesis, Italy (2004). | Zbl

[20] M. Iori, Metaheuristic algorithms for combinatorial optimization problems. Quart. J. Oper. Res. 3 (2005) 163-166. | Zbl

[21] M. Iori and S. Martello, Routing problems with loading constraints. TOP 18 (2010) 4-27. | MR | Zbl

[22] M. Iori, J.J. Salazar-Gonzalez and D. Vigo, An exact approach for the vehicle routing problem with two-dimensional loading constraints. Trans. Sci. 41 (2007) 253-264.

[23] L. Junqueira, R. Morabito and D. Sato Yamashita, Three-dimensional container loading models with cargo stability and load bearing constraints. Comput. Oper. Res. 39 (2012) 74-85. | MR | Zbl

[24] S. Khebbache-Hadji, C. Prins, A. Yalaoui and M. Reghioui, Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows. Cent. Eur. J. Oper. Res. (in press) 1-30.

[25] G. Levitin and R. Abezgaouz, Optimal routing of multiple-load AGV subject to LIFO loading constraints. Comput. Oper. Res. 30 (2003) 397-410. | Zbl

[26] A. Lodi, S. Martello and D. Vigo, Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems. Informs J. Comput. 11 (1999) 345-357. | MR | Zbl

[27] S. Martello, D. Pisinger and D. Vigo, The three-dimensional bin packing problem. Oper. Res. 48 (2000) 256-267. | MR | Zbl

[28] S. Martello, D. Pisinger, D. Vigo, E. Den Boef, and J. Korst, Algorithm 864 : general and robot-packable variants of the three-dimensional bin packing problem. ACM Trans. Math. Softw. 33 (2007) 7-17.

[29] F. Pereira, J. Tavares, P. Machado and E. Costa, GVR : a new genetic representation for the vehicle routing problem. Artificial Intelligence and Cognitive Science 24 (2002) 95-102. | Zbl

[30] D. Pisinger, Heuristics for the container loading problem. Eur. J. Oper. Res. 141 (2002) 382-392. | MR | Zbl

[31] M. Reimann, K. Doerner and R.F. Hartl, D-Ants : Savings based ants divide and conquer the vehicle routing problem. Comput. Oper. Res. 31 (2004) 563-591. | Zbl

[32] Q. Ruan, Z. Zhang, L. Miao and H. Shen, A hybrid approach for the vehicle routing problem with three-dimensional loading constraints. Comput. Oper. Res. (in press). | MR

[33] C.D. Tarantilis, E.E. Zachariadis and C.T. Kiranoudis, A hybrid metaheuristic algorithm for the integrated vehicle routing and three-dimensional container-loading problem. IEEE Trans. Intell. Transp. Syst. 10 (2009) 255-271.

[34] P. Toth and D. Vigo, The vehicle routing problem, in SIAM Monographs on Discrete Mathematics and Applications. Philadelphia (2002). | MR | Zbl

[35] F. Tricoire, K. Doerner, R. Hartl and M. Iori, Heuristic and exact algorithms for the multi-pile vehicle routing problem. OR-Spectrum 33 (2011) 931-959. | MR | Zbl

[36] H. Xu, Z. Chen, S. Rajagopal and S. Arunapuram, Solving a practical pickup and delivery problem. Trans. Sci. 37 (2003) 347-364.

[37] T. Yi and W. Fan, A New packing heuristic based algorithm for vehicle routing problem with three-dimensional loading constraints, in IEEE Int. Conf. Automation Science and Engineering (CASE) (2010) 972-977.

[38] E.E. Zachariadis, C.D. Tarantilis and C.T. Kiranoudis, A guided tabu search for the vehicle routing problem with two-dimensional loading constraints. Eur. J. Oper. Res. 195 (2009) 729-743. | Zbl

Cité par Sources :