Skip to main content
Log in

Vehicle routing problems with loading constraints: state-of-the-art and future directions

  • Regular Article
  • Published:
OR Spectrum Aims and scope Submit manuscript

Abstract

Distributors are faced with loading constraints in their route planning, e.g.,multi-dimensional packing constraints, unloading sequence constraints, stability constraints and axle weight limits. Ignoring these constraints impairs planning and induces last-minute changes resulting in additional costs. Developing vehicle routing models incorporating loading constraints is critical to more efficient route planning. The last couple of years has seen a huge increase of contributions to this field of research with almost 60 % of these being published after 2009. Our contribution is twofold. First, we overview the recent developments in the literature on all vehicle types in which loading constraints play a key role (trucks, airplanes, ships, and automated guided vehicles), using a state-of-the-art classification scheme to identify the loading constraints considered in each article. Second, we identify research gaps and opportunities for future research.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

Notes

  1. http://ec.europa.eu/transport/road_safety/vehicles/doc/cargo_securing_guidelines_en.

References

  • Alba M, Cordeau J, Dell’Amico M, Iori M (2011) A branch-and-cut algorithm for the double traveling salesman problem with multiple stacks. INFORMS J Comput 25(1):41–55

    Article  Google Scholar 

  • Amiouny S, Bartholdi J, Zhang J (1992) Balanced loading. Oper Res 40(2):238–246

    Article  Google Scholar 

  • Aprile D, Egeblad J, Garavelli A, Lisi S, Pisinger D (2007) Logistics optimization: vehicle routing with loading constraints. In: Proceedings of the 19th international conference on production research

  • Arbib C, Marinelli F, Servillio M (2009) On the pickup and delivery travelling salesman problem with LIFO loading. In: Proceedings of the international network optimisation conference 2009, Pisa, Italy

  • Attanasio A, Fuduli A, Ghiani G, Triki C (2007) Integrated shipment dispatching and packing problems: a case study. J Math Modell Algorithms 6(1):77–85

    Article  Google Scholar 

  • Avella P, Boccia M, Sforza A (2004) Solving a fuel delivery problem by heuristic and exact approaches. Eur J Oper Res 152(1):170–179

    Article  Google Scholar 

  • Baker B, Coffman E Jr, Rivest R (1980) Orthogonal packings in two dimensions. SIAM J Comput 9(4):846–855

    Article  Google Scholar 

  • Battarra M, Monaci M, Vigo D (2009) An adaptive guidance approach for the heuristic solution of a minimum multiple trip vehicle routing problem. Comput Oper Res 36(11):3041–3050

    Article  Google Scholar 

  • Bischoff E, Ratcliff MSWM (1995) Issues in the development of approaches to container loading. Omega 23(4):377–390

    Article  Google Scholar 

  • Bortfeldt A (2012) A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints. Comput Oper Res 39(9):2248–2257

    Article  Google Scholar 

  • Bortfeldt A, Homberger J (2013) Packing first, routing second a heuristic for the vehicle routing and loading problem. Comput Oper Res 40(3):873–885

    Article  Google Scholar 

  • Bortfeldt A, Wäscher G (2013) Constraints in container loading a state-of-the-art review. European J Oper Res 229(1)

  • Braekers K, Caris A, Janssens G (2014) Exact and metaheuristic approach for a general heterogeneous dial-a-ride problem with multiple depots. Trans Res Part B Methodol 67:166–186

    Article  Google Scholar 

  • Brown GG, Graves GW (1981) Real-time dispatch of petroleum tank trucks. Manag Sci 27(1):19–32

    Article  Google Scholar 

  • Carrabs F, Cordeau J, Laporte G (2007a) Variable neighborhood search for the pickup and delivery traveling salesman problem with LIFO loading. INFORMS J Comput 19(4):618–632

    Article  Google Scholar 

  • Carrabs F, Cerulli R, Cordeau J (2007b) An additive branch-and-bound algorithm for the pickup and delivery traveling salesman problem with LIFO or FIFO loading. INFOR Inf Syst Oper Res 45(4):223–238

    Google Scholar 

  • Carrabs F, Cerulli R, Speranza MG (2013) A branch-and-bound algorithm for the double travelling salesman problem with two stacks. Networks 61(1):58–75

    Article  Google Scholar 

  • Ceschia S, Schaerf A, Stützle T (2013) Local search techniques for a routing-packing problem. Comput Ind Eng 66(4):1138–1149

    Article  Google Scholar 

  • Chajakis ED, Guignard M (2003) Scheduling deliveries in vehicles with multiple compartments. J Global Optim 26(1):43–78

    Article  Google Scholar 

  • Chan F, Bhagwat R, Kumar N, Tiwari M, Lam P (2006) Development of a decision support system for air-cargo pallets loading problem: a case study. Expert Syst Appl 31(3):472–485

    Article  Google Scholar 

  • Cheang B, Gao X, Lim A, Qin H, Zhu W (2012) Multiple pickup and delivery traveling salesman problem with last-in-first-out loading and distance constraints. Eur J Oper Res 223(1):60–75

    Article  Google Scholar 

  • Cherkesly M, Desaulniers G, Laporte G (2014a) Branch-price-and-cut algorithms for the pickup and delivery problem with time windows and last-in-first-out loading. Trans Sci. doi:10.1287/trsc.2014.0535

  • Cherkesly M, Desaulniers G, Laporte G (2014b) A population-based metaheuristic for the pickup and delivery problem with time windows and lifo loading. Technical report, Les Cahiers du GERAD, G-2014-66, GERAD, Montréal

  • Clarke G, Wright JW (1964) Scheduling of vehicles from a central depot to a number of delivery points. Oper Res 12(4):568–581

    Article  Google Scholar 

  • Cordeau J, Laporte G, Savelsbergh MW, Vigo D (2007) Chapter 6 vehicle routing. In: Barnhart C, Laporte G (eds) Transportation, handbooks in operations research and management science, Elsevier 14:367–428

  • Cordeau J, Iori G, Mand Laporte, Salazar Gonzalez J (2010) A branch-and-cut algorithm for the pickup and delivery traveling salesman problem with LIFO loading. Networks 55(1):46–59

    Article  Google Scholar 

  • Cordeau J, Dell’ Amico M, Iori M (2010b) Branch-and-cut for the pickup and delivery traveling salesman problem with FIFO loading. Computers & Operations Research 37(5):970–980

    Article  Google Scholar 

  • Cornillier F, Boctor FF, Laporte G, Renaud J (2008a) An exact algorithm for the petrol station replenishment problem. J Oper Res Soc 59(5):607–615

    Article  Google Scholar 

  • Cornillier F, Boctor FF, Laporte G, Renaud J (2008b) A heuristic for the multi-period petrol station replenishment problem. Eur J Oper Res 191(2):295–305

    Article  Google Scholar 

  • Cornillier F, Laporte G, Boctor FF, Renaud J (2009) The petrol station replenishment problem with time windows. Comput Oper Res 36(3):919–935

    Article  Google Scholar 

  • Cornillier F, Boctor F, Renaud J (2012) Heuristics for the multi-depot petrol station replenishment problem with time windows. Eur J Oper Res 220(2):361–369

    Article  Google Scholar 

  • Côté J, Gendreau M, Potvin J (2012a) Large neighborhood search for the pickup and delivery traveling salesman problem with multiple stacks. Networks 60(1):19–30

    Article  Google Scholar 

  • Côté J, Archetti C, Speranza M, Gendreau J, Mand Potvin (2012b) A branch-and-cut algorithm for the pickup and delivery traveling salesman problem with multiple stacks. Networks 60(4):212–226

    Article  Google Scholar 

  • Davies A, Bischoff E (1999) Weight distribution considerations in container loading. Eur J Oper Res 114(3):509–527

    Article  Google Scholar 

  • Derigs U, Gottlieb J, Kalkoff J, Piesche M, Rothlauf F, Vogel U (2011) Vehicle routing with compartments: applications, modelling and heuristics. OR Spectr 33(4):885–914

    Article  Google Scholar 

  • Doerner K, Fuellerer G, Hartl R, Gronalt M, Iori M (2007) Metaheuristics for the vehicle routing problem with loading constraints. Networks 49(4):294–307

    Article  Google Scholar 

  • Dominguez O, Juan AA, Faulin J (2014) A biased-randomized algorithm for the two-dimensional vehicle routing problem with and without item rotations. Int Trans Oper Res 21(3):375–398

    Article  Google Scholar 

  • Dooley A, Parker W, Blair H (2005) Modelling of transport costs and logistics for on-farm milk segregation in new zealand dairying. Comput Electron Agric 48(2):75–91

    Article  Google Scholar 

  • Duhamel C, Lacomme P, Quilliot A, Toussaint H (2011) A multi-start evolutionary local search for the two-dimensional loading capacitated vehicle routing problem. Comput Oper Res 38(3):617–640

    Article  Google Scholar 

  • Dumitrescu I, Ropke S, Cordeau J, Laporte G (2010) The traveling salesman problem with pickup and delivery: polyhedral results and a branch-and-cut algorithm. Math Program 121(2):269–305

    Article  Google Scholar 

  • El Fallahi A, Prins C (2008) A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem. Comput Oper Res 35(5):1725–1741

    Article  Google Scholar 

  • Erdogan G, Cordeau J, Laporte G (2009) The pickup and delivery traveling salesman problem with first-in-first-out loading. Comput Oper Res 36(6):1800–1808

    Article  Google Scholar 

  • Fagerholt K, Christiansen M (2000a) A combined ship scheduling and allocation problem. J Oper Res Soc 51(7):834–842

    Article  Google Scholar 

  • Fagerholt K, Christiansen M (2000b) A travelling salesman problem with allocation, time window and precedence constraints an application to ship scheduling. Int Trans Oper Res 7(3):231–244

    Article  Google Scholar 

  • Fagerholt K, Hvattum L, Johnsen T, Korsvik J (2013) Routing and scheduling in project shipping. Ann Oper Res 207(1):67–81

    Article  Google Scholar 

  • Fallahi AE, Prins C (2008) A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem. Comput Oper Res 35(5):1725–1741

    Article  Google Scholar 

  • Felipe A, Ortuño MT, Tirado G (2009b) The double traveling salesman problem with multiple stacks: a variable neighborhood search approach. Comput Oper Res 36(11):2983–2993

    Article  Google Scholar 

  • Felipe A, Ortuño M, Tirado G (2011) Using intermediate infeasible solutions to approach vehicle routing problems with precedence and loading constraints. Eur J Oper Res 211(1):66–75

    Article  Google Scholar 

  • Fok K, Chun A (2004) Optimizing air cargo load planning and analysis. In: Proceedings of the international conference on computing, communications and control technologies 2004, Austin Texas, USA

  • Fuellerer G, Doerner KF, Hartl RF, Iori M (2009) Ant colony optimization for the two-dimensional loading vehicle routing problem. Comput Oper Res 36(3):655–673

    Article  Google Scholar 

  • Fuellerer G, Doerner KF, Hartl RF, Iori M (2010) Metaheuristics for vehicle routing problems with three-dimensional loading constraints. Eur J Oper Res 201(3):751–759

    Article  Google Scholar 

  • Gehring H, Bortfeldt A (1997) A genetic algorithm for solving the container loading problem. Int Trans Oper Res 4(5/6):401–418

    Article  Google Scholar 

  • Gendreau M, Iori M, Laporte G, Martello S (2006) A tabu search algorithm for a routing and container loading problem. Trans Sci 40(3):342–350

    Article  Google Scholar 

  • Gendreau M, Iori M, Laporte G, Martello S (2008) A tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints. Networks 51(1):4–18

    Article  Google Scholar 

  • Golden B, Raghavan S, Wasil E (2008) The vehicle routing problem: latest advances and new challenges. Operations research/computer science interfaces, 43, Springer, New York

  • International Transport Forum (2011) Permissible maximum weights of trucks in europe. http://www.internationaltransportforum.org/IntOrg/road/pdf/weights

  • Iori M, Martello S (2010) Routing problems with loading constraints. TOP 18(1):4–27

    Article  Google Scholar 

  • Iori M, Salazar-González JJ, Vigo D (2007) An exact approach for the vehicle routing problem with two-dimensional loading constraints. Trans Sci 41(2):253–264

    Article  Google Scholar 

  • Junqueira L, Morabito R (2012) Three-dimensional container loading models with cargo stability and load bearing constraints. Comput Oper Res 39(1):74–85

    Article  Google Scholar 

  • Junqueira L, Oliveira J, Carravilla M, Morabito R (2013) An optimization model for the vehicle routing problem with practical three-dimensional loading constraints. Int Trans Oper Res 20(5):645–666

    Article  Google Scholar 

  • Khebbache-Hadji S, Prins C, Yalaoui A, Reghioui M (2013) Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows. Cent Eur J Oper Res 21(2):307–336

    Article  Google Scholar 

  • Ladany SP, Mehrez A (1984) Optimal routing of a single vehicle with loading and unloading constraints. Trans Plan Technol 8(4):301–306

    Article  Google Scholar 

  • Laporte G (2009) Fifty years of vehicle routing. Trans Sci 43(4):408–416

    Article  Google Scholar 

  • Leung S, Zhou X, Zhang D, Zheng J (2011) Extended guided tabu search and a new packing algorithm for the two-dimensional loading vehicle routing problem. Comput Oper Res 38(1):205–215

    Article  Google Scholar 

  • Leung SC, Zhang Z, Zhang D, Hua X, Lim MK (2013) A meta-heuristic algorithm for heterogeneous fleet vehicle routing problems with two-dimensional loading constraints. Eur J Oper Res 225(2):199–210

    Article  Google Scholar 

  • Levitin G, Abezgaouz R (2003) Optimal routing of multiple-load AGV subject to LIFO loading constraints. Comput Oper Res 30(3):397–410

    Article  Google Scholar 

  • Li Y, Lim A, Oon W, Qin H, Tu D (2011) The tree representation for the pickup and delivery traveling salesman problem with LIFO loading. Eur J Oper Res 212(3):482–496

    Article  Google Scholar 

  • Lim A, Ma H, Qiu C, Zhu W (2013) The single container loading problem with axle weight constraints. Int J Prod Econ 144:358–369

    Article  Google Scholar 

  • Limbourg S, Schyns M, Laporte G (2012) Automatic aircraft cargo load planning. J Oper Res Soc 63(9):1271–1283

    Article  Google Scholar 

  • Lodi A, Martello S, Vigo D (1999) Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems. INFORMS J Comput 11(4):345–357

    Article  Google Scholar 

  • Lurkin V, Schyns M (2013) The airline container loading problem with pickup and delivery. Working paper HEC-University of Liége

  • Lusby RM, Larsen J (2011) Improved exact method for the double TSP with multiple stacks. Networks 58(4):290–300

    Article  Google Scholar 

  • Lusby RM, Larsen J, Ehrgott M, Ryan D (2010) An exact method for the double TSP with multiple stacks. Int Trans Oper Res 17(5):637–652

    Article  Google Scholar 

  • Malapert A, Guéret C, Jussien N, Langevin A, Rousseau L (2008) Two-dimensional pickup and delivery routing problem with loading constraints. In: Proceedings of the 1st CPAIOR workshop on bin packing and placement constraints (BPPC’08)

  • Martello S, Vigo D (1998) Exact solution of the two-dimensional finite bin packing problem. Manag Sci 44(3):388–399

    Article  Google Scholar 

  • Martello S, Pisinger D, Vigo D (2000) The three-dimensional bin packing problem. Oper Res 48(2):256–267

    Article  Google Scholar 

  • Martinez L, Amaya C (2013) A vehicle routing problem with multi-trips and time windows for circular items. J Oper Res Soc 64:1630–1643

    Article  Google Scholar 

  • Massen F, Deville Y, Van Hentenryck P (2012) Pheromone-based heuristic column generation for vehicle routing problems with black box feasibility. International conference on integration of AI and OR techniques in constraint programming for combinatorial optimization problems (CPAIOR2012). Springer LNCS, Nantes, France, pp 260–274

  • Mendoza JE, Castanier B, Guéret C, Medaglia AL, Velasco N (2010) A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands. Comput Oper Res 37(11):1886–1898

    Article  Google Scholar 

  • Miao L, Ruan Q, Woghiren K, Ruo Q (2012) A hybrid genetic algorithm for the vehicle routing problem with three-dimensional loading constraints. RAIRO Oper Res 46(1):63–82

    Article  Google Scholar 

  • Moura A (2008) A multi-objective genetic algorithm for the vehicle routing with time windows and loading problem. In: Bortfeldt A, Homberger J, Kopfer H, Pankratz G, Strangmeier R (eds) Intelligent Decision Support. Current Challenges and Approaches, Gabler, pp 187–201

    Chapter  Google Scholar 

  • Moura A, Oliveira J (2009) An integrated approach to the vehicle routing and container loading problems. OR Spectr 31(4):775–800

    Article  Google Scholar 

  • Muyldermans L, Pang G (2010) A guided local search procedure for the multi-compartment capacitated arc routing problem. Comput Oper Res 37(9):1662–1673

    Article  Google Scholar 

  • Øvstebø B, Hvattum LM, Fagerholt K (2011) Routing and scheduling of roro ships with stowage constraints. Trans Res Part C Emerg Technol 19(6):1225–1242

  • Paquay C, Schyns M, Limbourg S (2013) A mixed integer programming formulation for the three dimensional bin packing problem deriving from an air cargo application. Int Trans Oper Res (forthcoming). doi:10.1111/itor.12111

  • Parragh S, Doerner K, Hartl R (2008) A survey on pickup and delivery problems part ii: transportation between pickup and delivery locations. J für Betrieb 58(2):81–117

    Article  Google Scholar 

  • Petersen HL, Madsen O (2009) The double travelling salesman problem with multiple stacks formulation and heuristic solution approaches. Eur J Oper Res 198(1):139–147

    Article  Google Scholar 

  • Petersen HL, Archetti C, Speranza MG (2010) Exact solutions to the double travelling salesman problem with multiple stacks. Networks 56(4):229–243

    Article  Google Scholar 

  • Pollaris H, Braekers K, Caris A, Janssens GK (2013) The capacitated vehicle routing problem with loading constraints. In: Bruzzone A, Gronalt M, Merkuryev Y, Piera M (eds) Proceedings of the international conference on harbor maritime and multimodal logistics M & S, 2013. Greece, Athens, pp 7–12

  • Pollaris H, Braekers K, Caris A, Janssens GK, Limbourg S (2014) Capacitated vehicle routing problem with sequence based pallet loading and axle weight constraints. EURO J Trans Logist (forthcoming). doi:10.1007/s13676-014-0064-2

  • Ratcliff M, Bischoff E (1998) Allowing for weight considerations in container loading. Oper Res Spektr 20(1):65–71

    Article  Google Scholar 

  • Ren J, Tian Y, Sawaragi T (2011) A relaxation method for the three-dimensional loading capacitated vehicle routing problem. In: 2011 IEEE/SICE international symposium on system integration (SII), pp 750–755

  • Ruan Q, Zhang Z, Miao L, Shen H (2013) A hybrid approach for the vehicle routing problem with three-dimensional loading constraints. Comput Oper Res 40(6):1579–1589

    Article  Google Scholar 

  • Strodl J, Doerner K, Tricoire F, Hartl R (2010) On index structures in hybrid metaheuristics for routing problems with hard feasibility checks: an application to the 2-dimensional loading vehicle routing problem. In: Blesa M, Blum C, Raidl G, Roli A, Sampels M (eds) Hybrid metaheuristics lecture notes in computer science, vol 6373. Springer, Berlin, pp 160–173

    Chapter  Google Scholar 

  • Tao Y, Wang F (2013) An effective tabu search approach with improved loading algorithms for the 3l-cvrp. Comput Oper Res doi:10.1016/j.cor.2013.10.017

  • Tarantilis C, Zachariadis E, Kiranoudis C (2009) A hybrid metaheuristic algorithm for the integrated vehicle routing and three-dimensional container-loading problem. IEEE Trans Intell Trans Syst 10(2):255–271

  • Toth P, Vigo D (2002) The vehicle routing problem. Monographs on discrete mathematics and applications. Society for Industrial and Applied Mathematics, Philadelphia

    Google Scholar 

  • Tricoire F, Doerner K, Hartl R, Iori M (2011) Heuristic and exact algorithms for the multi-pile vehicle routing problem. OR Spectr 33(4):931–959

    Article  Google Scholar 

  • Vancroonenburg W, Verstichel J, Tavernier K (2014) Automatic air cargo selection and weight balancing: a mixed integer programming approach. Trans Res E Logist Trans Rev 65:70–83

    Article  Google Scholar 

  • Vansteenwegen P, Souffriau W, Van Oudheusden D (2011) The orienteering problem: a survey. Eur J Oper Res 209(1):1–10

    Article  Google Scholar 

  • Vidal T, Crainic T, Gendreau M, Prins C (2013) Heuristics for multi-attribute vehicle routing problems: a survey and synthesis. Eur J Oper Res 231(1):1–21

    Article  Google Scholar 

  • Wäscher G, Hauner H, Schumann H (2007) An improved typology of cutting and packing problems. Eur J Oper Res 183(3):1109–1130

    Article  Google Scholar 

  • Wei L, Zhang D, Chen Q (2009) A least wasted first heuristic algorithm for the rectangular packing problem. Comput Oper Res 36(5):1608–1614

    Article  Google Scholar 

  • Wisniewski MA, Ritt M, Buriol LS (2012) A tabu search algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints. Tech. rep., Institute of Informatics at UFRGS, http://inf.ufrgs.br/mrpritt/Publications/P37-sbpo-2011a

  • Xu H, Chen ZL, Rajagopal S, Arunapuram S (2003) Solving a practical pickup and delivery problem. Trans Sci 37(3):347–364

    Article  Google Scholar 

  • Zachariadis E, Tarantilis C, Kiranoudis C (2009) A guided tabu search for the vehicle routing problem with two-dimensional loading constraints. Eur J Oper Res 195(3):729–743

    Article  Google Scholar 

  • Zachariadis E, Tarantilis C, Kiranoudis C (2012) The pallet-packing vehicle routing problem. Trans Sci 46(3):341–358

    Article  Google Scholar 

  • Zachariadis E, Tarantilis C, Kiranoudis C (2013a) Designing vehicle routes for a mix of different request types, under time windows and loading constraints. Eur J Oper Res 229(2):303–317

    Article  Google Scholar 

  • Zachariadis E, Tarantilis C, Kiranoudis C (2013b) Integrated distribution and loading planning via a compact metaheuristic algorithm. Eur J Oper Res 228(1):56–71

    Article  Google Scholar 

  • Zhu W, Qin H, Lim A, Wang L (2012) A two-stage tabu search algorithm with enhanced packing heuristics for the 3L-CVRP and M3L-CVRP. Comput Oper Res 39(9):2178–2195

    Article  Google Scholar 

Download references

Acknowledgments

This work is supported by the Interuniversity Attraction Poles Programme initiated by the Belgian Science Policy Office (COMEX project: Combinatorial Optimization: Metaheuristics and Exact methods).

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Hanne Pollaris.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Pollaris, H., Braekers, K., Caris, A. et al. Vehicle routing problems with loading constraints: state-of-the-art and future directions. OR Spectrum 37, 297–330 (2015). https://doi.org/10.1007/s00291-014-0386-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00291-014-0386-3

Keywords

Navigation