A hybrid genetic algorithm for the vehicle routing problem with three-dimensional loading constraints

Lixin Miao; Qingfang Ruan; Kevin Woghiren; Qi Ruo

RAIRO - Operations Research (2012)

  • Volume: 46, Issue: 1, page 63-82
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Miao, Lixin, et al. "A hybrid genetic algorithm for the vehicle routing problem with three-dimensional loading constraints." RAIRO - Operations Research 46.1 (2012): 63-82. <http://eudml.org/doc/276393>.

@article{Miao2012,
abstract = {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.},
author = {Miao, Lixin, Ruan, Qingfang, Woghiren, Kevin, Ruo, Qi},
journal = {RAIRO - Operations Research},
keywords = {Vehicle routing; three-dimensional loading; genetic algorithm; tabu search; vehicle routing},
language = {eng},
month = {5},
number = {1},
pages = {63-82},
publisher = {EDP Sciences},
title = {A hybrid genetic algorithm for the vehicle routing problem with three-dimensional loading constraints},
url = {http://eudml.org/doc/276393},
volume = {46},
year = {2012},
}

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
DA - 2012/5//
PB - EDP Sciences
VL - 46
IS - 1
SP - 63
EP - 82
AB - 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.
LA - eng
KW - Vehicle routing; three-dimensional loading; genetic algorithm; tabu search; vehicle routing
UR - http://eudml.org/doc/276393
ER -

References

top
  1. B. Andreas, A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints. Comput. Oper. Res.39 (2012) 2248–2257.  
  2. B.M. Baker and M.A. Ayechew, A genetic algorithm for the vehicle routing problem. Comput. Oper. Res.30 (2003) 787–800.  
  3. B.S. Baker, E.G. CoffmanJr., and R.L. Rivest, Orthogonal packings in two dimensions. SIAM J. Comput.9 (1980) 846–855.  
  4. A. Bortfeldt and H. Gehring, A hybrid genetic algorithm for the container loading problem. Eur. J. Oper. Res.131 (2001) 143–161.  
  5. J. Cordeau and G. Laporte, Tabu search heuristics for the vehicle routing problem. Metaheuristic Optimization via Memory and Evolution30 (2005) 145–163.  
  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.  
  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.  
  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.  
  9. K.F. Doerner, G. Fuellerer, R.F. Hartl, M. Gronalt, and M. Iori, Metaheuristics for the vehicle routing problem with loading constraints. Networks49 (2007) 294–307.  
  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.  
  11. M. Eley, Solving container loading problems by block arrangement. Eur. J. Oper. Res.141 (2002) 393–409.  
  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.  
  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.  
  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.  
  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.  
  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. Networks51 (2008) 4–18.  
  18. B.E. Gillett and R.M. Leland, A heuristic algorithm for the vehicle-dispatch problem. Oper. Res.22 (1974) 340–349.  
  19. M. Iori, Metaheuristic algorithms for combinatorial optimization problems. Ph.D. thesis, Italy (2004).  
  20. M. Iori, Metaheuristic algorithms for combinatorial optimization problems. Quart. J. Oper. Res.3 (2005) 163–166.  
  21. M. Iori and S. Martello, Routing problems with loading constraints. TOP18 (2010) 4–27.  
  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. SatoYamashita, Three-dimensional container loading models with cargo stability and load bearing constraints. Comput. Oper. Res.39 (2012) 74–85.  
  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.  
  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.  
  27. S. Martello, D. Pisinger and D. Vigo, The three-dimensional bin packing problem. Oper. Res.48 (2000) 256–267.  
  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 Science24 (2002) 95–102.  
  30. D. Pisinger, Heuristics for the container loading problem. Eur. J. Oper. Res.141 (2002) 382–392.  
  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.  
  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).  
  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).  
  35. F. Tricoire, K. Doerner, R. Hartl and M. Iori, Heuristic and exact algorithms for the multi-pile vehicle routing problem. OR-Spectrum33 (2011) 931–959.  
  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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.