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.  Zbl1251.90013
  2. B.M. Baker and M.A. Ayechew, A genetic algorithm for the vehicle routing problem. Comput. Oper. Res.30 (2003) 787–800.  Zbl1026.90013
  3. B.S. Baker, E.G. CoffmanJr., and R.L. Rivest, Orthogonal packings in two dimensions. SIAM J. Comput.9 (1980) 846–855.  Zbl0447.68080
  4. A. Bortfeldt and H. Gehring, A hybrid genetic algorithm for the container loading problem. Eur. J. Oper. Res.131 (2001) 143–161.  Zbl0979.90101
  5. J. Cordeau and G. Laporte, Tabu search heuristics for the vehicle routing problem. Metaheuristic Optimization via Memory and Evolution30 (2005) 145–163.  Zbl1072.90054
  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.  Zbl1130.90416
  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.  Zbl1243.90088
  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.  Zbl1161.90012
  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.  Zbl1141.90336
  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.  Zbl1201.90026
  11. M. Eley, Solving container loading problems by block arrangement. Eur. J. Oper. Res.141 (2002) 393–409.  Zbl1081.90610
  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.  Zbl1238.90112
  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.  Zbl1157.90335
  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.  Zbl1173.90511
  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.  Zbl1094.90050
  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.  Zbl1146.90012
  18. B.E. Gillett and R.M. Leland, A heuristic algorithm for the vehicle-dispatch problem. Oper. Res.22 (1974) 340–349.  Zbl0274.90013
  19. M. Iori, Metaheuristic algorithms for combinatorial optimization problems. Ph.D. thesis, Italy (2004).  Zbl1134.90300
  20. M. Iori, Metaheuristic algorithms for combinatorial optimization problems. Quart. J. Oper. Res.3 (2005) 163–166.  Zbl1134.90300
  21. M. Iori and S. Martello, Routing problems with loading constraints. TOP18 (2010) 4–27.  Zbl1279.90146
  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.  Zbl1251.90240
  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.  Zbl1029.90012
  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.  Zbl1034.90500
  27. S. Martello, D. Pisinger and D. Vigo, The three-dimensional bin packing problem. Oper. Res.48 (2000) 256–267.  Zbl1106.90371
  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.  Zbl1165.90603
  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.  Zbl1018.68784
  30. D. Pisinger, Heuristics for the container loading problem. Eur. J. Oper. Res.141 (2002) 382–392.  Zbl1081.90613
  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.  Zbl1061.90024
  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).  Zbl0979.00026
  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.  Zbl1229.90039
  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. Zbl1155.90331

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.