[en] 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.
Disciplines :
Quantitative methods in economics & management
Author, co-author :
Pollaris, Hanne
Braekers, Kris
Caris, An
Janssens, Gerrit K.
Limbourg, Sabine ; Université de Liège - ULiège > HEC-Ecole de gestion : UER > UER Opérations : Logistique
Language :
English
Title :
Vehicle routing problems with loading constraints: State-of-the-art and future directions
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
Bibliography
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
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
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
Baker B, Coffman E Jr, Rivest R (1980) Orthogonal packings in two dimensions. SIAM J Comput 9(4):846–855
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
Bischoff E, Ratcliff MSWM (1995) Issues in the development of approaches to container loading. Omega 23(4):377–390
Bortfeldt A (2012) A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints. Comput Oper Res 39(9):2248–2257
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
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
Brown GG, Graves GW (1981) Real-time dispatch of petroleum tank trucks. Manag Sci 27(1):19–32
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
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
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
Ceschia S, Schaerf A, Stützle T (2013) Local search techniques for a routing-packing problem. Comput Ind Eng 66(4):1138–1149
Chajakis ED, Guignard M (2003) Scheduling deliveries in vehicles with multiple compartments. J Global Optim 26(1):43–78
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
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
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
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
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
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
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
Cornillier F, Laporte G, Boctor FF, Renaud J (2009) The petrol station replenishment problem with time windows. Comput Oper Res 36(3):919–935
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
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
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
Davies A, Bischoff E (1999) Weight distribution considerations in container loading. Eur J Oper Res 114(3):509–527
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
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
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
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
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
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
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
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
Fagerholt K, Christiansen M (2000a) A combined ship scheduling and allocation problem. J Oper Res Soc 51(7):834–842
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
Fagerholt K, Hvattum L, Johnsen T, Korsvik J (2013) Routing and scheduling in project shipping. Ann Oper Res 207(1):67–81
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
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
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
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
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
Gehring H, Bortfeldt A (1997) A genetic algorithm for solving the container loading problem. Int Trans Oper Res 4(5/6):401–418
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
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
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
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
Junqueira L, Morabito R (2012) Three-dimensional container loading models with cargo stability and load bearing constraints. Comput Oper Res 39(1):74–85
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
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
Ladany SP, Mehrez A (1984) Optimal routing of a single vehicle with loading and unloading constraints. Trans Plan Technol 8(4):301–306
Laporte G (2009) Fifty years of vehicle routing. Trans Sci 43(4):408–416
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
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
Levitin G, Abezgaouz R (2003) Optimal routing of multiple-load AGV subject to LIFO loading constraints. Comput Oper Res 30(3):397–410
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
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
Limbourg S, Schyns M, Laporte G (2012) Automatic aircraft cargo load planning. J Oper Res Soc 63(9):1271–1283
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
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
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
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
Martello S, Pisinger D, Vigo D (2000) The three-dimensional bin packing problem. Oper Res 48(2):256–267
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
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
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
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
Moura A, Oliveira J (2009) An integrated approach to the vehicle routing and container loading problems. OR Spectr 31(4):775–800
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
Ø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
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
Petersen HL, Archetti C, Speranza MG (2010) Exact solutions to the double travelling salesman problem with multiple stacks. Networks 56(4):229–243
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
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
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
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
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
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
Vansteenwegen P, Souffriau W, Van Oudheusden D (2011) The orienteering problem: a survey. Eur J Oper Res 209(1):1–10
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
Wäscher G, Hauner H, Schumann H (2007) An improved typology of cutting and packing problems. Eur J Oper Res 183(3):1109–1130
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
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
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
Zachariadis E, Tarantilis C, Kiranoudis C (2012) The pallet-packing vehicle routing problem. Trans Sci 46(3):341–358
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
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
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
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.