1 Introduction

The vehicle routing problem is the most studied combinatorial optimization problem in transport and logistics. The issue concerns the distribution of goods between depots and customers (Toth and Vigo 2002) along a set of routes for a fleet of vehicles where an objective function (e.g., total distance, total routing cost) is optimized. Customer demand must be met and vehicle capacities respected. Solving a basic vehicle routing problem involves two elements: the assignment of all customers to a trip and the sequence in which each are visited. The basic version of the vehicle routing problem is called the capacitated vehicle routing problem (CVRP). The CVRP considers a homogeneous fleet of vehicles with a fixed capacity (in terms of weight or number of items) which delivers goods from a depot to customer locations. Split deliveries are not allowed. The CVRP can be extended to the VRP with time windows (VRPTW) by specifying time windows in which deliveries need to take place. Another variant is the VRP with pickups and deliveries (VRPPD) in which orders may be picked up and delivered. For each order, an origin (pickup location) and a destination (delivery location) are specified (Parragh et al. 2008), while both operations may occur at a same location. When only a single vehicle is considered, the VRPPD reduces to a traveling salesman problem with pickup and delivery (TSPPD). A third common extension of the basic CVRP is the VRP with backhauls (VRPB), in which pickups and deliveries may be combined in a single tour; yet, all delivery requests need to be performed before the empty vehicle can collect goods from customer locations (Toth and Vigo 2002).

The classic vehicle routing problem described in the previous paragraph has been studied extensively in the last decades. A review of solution methods can be found in Laporte (2009). In real life, companies are faced with several additional constraints which greatly increase the complexity of the problem. Examples of such complicating constraints or attributes include maximum route length and duration, incompatibilities between goods and vehicles and loading constraints. Rich vehicle routing problems (RVRP) refer to those taking some of these additional realistic constraints into account (Battarra et al. 2009). We refer to Vidal et al. (2013) for a synthesis and analysis of solution methods dealing with rich vehicle routing problems.

This paper focuses on the integration of loading constraints in vehicle routing problems and reviews the relevant literature. A survey conducted by the authors among several Belgian logistics service providers pointed out that these are faced with complex loading problems when planning their route (e.g., multi-dimensional packing constraints, unloading sequence constraints, stability constraints and axle weight limits). Ignoring these constraints may compromise planning and induce last-minute changes resulting in additional costs. Developing vehicle routing models which incorporate loading constraints, therefore, is critical to efficient route planning. The packing scheme of the vehicle changes each time a load is picked up or delivered, which implies that loading constraints should not only be monitored at the time of departure, but throughout the trip. Loading constraints play an important role, not just in planning road but also maritime and air transport.

The combination of routing and loading problems is a fairly recent domain of research. Since Iori and Martello’s review (Iori and Martello 2010) up to 2010 of 31 papers concerning vehicle routing and loading constraints, contributions to this field have soared over the last couple of years. This paper extends these authors’ overview (Iori and Martello 2010) by covering 76 papers. It also discusses the loading constraints more thoroughly and uses the classification of Bortfeldt and Wäscher (2013) to identify them. In case rich (other than loading) constraints are included, mention is made in the description of the models. Besides, our paper offers a broad perspective as it not only focuses on road transport, but also considers maritime and air transport as well as automated guided vehicles. It discusses the various papers in comparative perspective and identifies future research directions.

Section 2 describes relevant problem characteristics for the VRP. Section 3 identifies loading problems that may be considered in combination with routing problems. Section 4 provides an overview of the literature concerning vehicle routing problems in combination with loading problems. Section 5 presents conclusions and opportunities for further research.

2 Problem characteristics of VRP

We refer to Toth and Vigo (2002), Cordeau et al. (2007) and Golden et al. (2008) for a general discussion of the VRP. This section describes the main characteristics likely to influence the solution of a vehicle routing problem, i.e. characteristics of the vehicle fleet and of the cargo, (time-dependent) travel times, the legal framework, transportation requests and the objective function.

Characteristics of the vehicle fleet such as vehicle capacity, configuration of the loading space and unloading possibilities largely determine the solution to the problem. The capacity of vehicles may be specified in terms of weight, number of items or volume. The loading space of the vehicle often influences the capacity. The loading space is determined by the measurements of the vehicle such as length, width and height, and may have a specific configuration. For example, vehicles may be divided into multiple compartments allowing for the transportation of goods that need to be kept segregated. Besides, a tank truck may be divided into compartments to prevent the liquid accumulating in the front of the truck when this comes to a halt (due to mass in motion). The configuration of the loading space may also make it possible to load goods into several piles. Finally, vehicles differ in the ways in which they can be loaded or unloaded. A vehicle may be loaded via the rear (rear loading), the long side and/or via the top side. A homogeneous vehicle fleet consists of vehicles having the same vehicle characteristics. In a heterogeneous fleet, vehicles may differ in terms of capacity, loading space or other relevant vehicle characteristics.

Characteristics of the cargo include the measurements and fragility of the items as well as orientation issues. Measurements may determine whether an item fits into a container or not. Often, items are assumed to have a rectangular shape in two dimensions and a cuboid shape in three dimensions to make the loading process easier. Items can be fragile (e.g., porcelain) or non-fragile (e.g. newspapers) which may bear on the loading possibilities into a container. They may have specific orientation constraints, e.g. several require a fixed orientation with respect to height. This means they cannot be placed upside down but have a pre-determined top. Cargo may consist of homogeneous or heterogeneous items. In the latter case, compatibility issues of product pairs may arise. More specifically, certain products are not allowed to be transported together in the same vehicle or vehicle compartment. Furthermore, some product types (e.g., frozen or refrigerated items) require to be transported in adapted containers or container compartments.

Travel time on a certain route may vary at different times of travel (e.g., traffic congestion).

Legal limitations on driving time specify the maximum time a truck driver may drive each day as well as the minimum duration and frequency of breaks during his working shift. Next, rules concerning the loading of vehicles (e.g., European Best Practice Guidelines on Cargo Securing for Road TransportFootnote 1) may apply. Road speed limits are used to regulate the speed of the trucks and may therefore influence the solution of the VRP.

Transportation requests are either for a pickup, a delivery or both. Split deliveries or split pickups are mostly not allowed, which implies that each customer is visited but once. Customers may specify time windows within which the delivery or pickup must take place. These time windows may be hard or soft. Soft time windows imply that deliveries may occur outside the time windows, in which case a penalty cost is incurred by the transportation company, while hard time windows do not allow delivery outside the time windows. As already mentioned, when time windows are specified, the problem is called a VRP with time windows (VRPTW).

Multiple objectives are relevant when considering the VRP with loading constraints: the minimization of the number of vehicles, total cost, total route length and total time are often considered. In addition, balanced routes and maximization of volume utilization may also feature as objectives.

3 Loading constraints

Loading problems arise when goods cannot be placed freely in a container or vehicle because several constraints have to be taken into account. An overview of packing problems discussed in the literature can be found in Wäscher et al. (2007). In a state-of-the-art review of container loading problems, Bortfeldt and Wäscher (2013) identify several types of loading constraints which are container related, item related, cargo related or load related. Container-related constraints concern the container or vehicle in which the items are placed. Item-related constraints refer to individual items, whereas cargo-related constraints address a subset of items. Load-related constraints relate to the result of the packing process. The following paragraphs briefly discuss loading constraints that may be relevant in combination with vehicle routing problems. The classification is mainly based on the taxonomy of Bortfeldt and Wäscher (2013).

3.1 Classical (multi-) dimensional packing constraints

This constraint entails that items cannot overlap and should be thoroughly packed inside the vehicle. In a three-dimensional loading problem, the length, width and height of the vehicle are considered to verify this constraint. In a one-dimensional or two-dimensional loading problem, respectively, a single or two dimensions are taken into consideration. In a bin packing problem (BPP), items are placed into a minimum number of identical bins (=vehicles). In a strip packing problem (SPP), items are placed in an open-ended rectangle with infinite height with the objective of minimizing the total height.

3.2 Cargo-related constraints

3.2.1 Complete-shipment constraints

In case the vehicle capacity cannot accommodate all items, some items will be left behind. Complete-shipment constraints may be specified when a subset of items needs to be shipped together, i.e. either all or none can be loaded (Bortfeldt and Wäscher 2013). Shipping companies that operate in the tramp market face complete-shipments constraints in ship scheduling. Tramp shipping companies select cargoes at the spot market and construct routes to maximize profit (Fagerholt et al. 2013). A single order on the spot market may consist of several cargoes from different origins, i.e. the service company must service all of these or none at all.

3.2.2 Allocation constraints

Allocation constraints may be specified when multiple vehicles or containers are considered. Two types of allocation constraints have been identified: connectivity constraints and separation constraints (Bortfeldt and Wäscher 2013). Connectivity constraints require that items of a certain subset are shipped in the same container or vehicle. In VRP literature it is common that each customer is visited only once and by a single vehicle (split deliveries are not allowed). It is therefore necessary that all items demanded by a customer are shipped in the same vehicle. As a result, connectivity constraints are incorporated in most VRP models (e.g., Gendreau et al. 2006; Tarantilis et al. 2009; Fuellerer et al. 2010; Ruan et al. 2013). Secondly, separation constraints may be specified to prevent that certain types of products are shipped in the same container or vehicle. Separation constraints may be relevant when different types of goods (e.g., food and toxic items) may not be transported together in the same vehicle. An example may be found in Battarra et al. (2009) where a distinction is made between three types of commodities: vegetables, fresh products (e.g., milk and meat) and non-perishable items. A variation of this constraint has been investigated in the multi-compartment VRP. The multi-compartment VRP allows the transport of different types of goods in separate compartments in the same vehicle. Applications of VRPs with multiple compartments can be found in the distribution of petrol (different types of petrol transported in one vehicle) (e.g., Brown and Graves 1981; Cornillier et al. 2008a) and food (e.g., a refrigerated compartment and a regular compartment in one vehicle) (Chajakis and Guignard 2003), waste collection (Muyldermans and Pang 2010), on-farm milk collection (Dooley et al. 2005) and ship scheduling (Fagerholt and Christiansen 2000a).

Allocation constraints may be specified when multiple vehicles or containers are considered. Two types of such constraints have been identified: connectivity and separation constraints (Bortfeldt and Wäscher 2013). Connectivity constraints require that the items of a certain subset are shipped in the same container or vehicle. In VRP literature, each customer is usually visited only once and by a single vehicle (split deliveries are not allowed). All items requested by a customer, therefore, need to be shipped in the same vehicle. As a result, connectivity constraints are incorporated in most VRP models (e.g. Gendreau et al. 2006; Tarantilis et al. 2009; Fuellerer et al. 2010; Ruan et al. 2013). Separation constraints may be specified to prevent certain types of products being shipped in the same container or vehicle. Separation constraints are relevant when different types of goods (e.g., food and toxic items) may not be transported together in the same vehicle. An example may be found in Battarra et al. (2009) where a distinction is made between three types of commodities: vegetables, fresh products (e.g., milk and meat) and non-perishable items. A variation of this constraint has been investigated in the multi-compartment VRP. The multi-compartment VRP allows the transport of different types of goods in separate compartments of the same vehicle. Applications of VRPs with multiple compartments can be found in the distribution of petrol (different types of petrol transported in one vehicle) (e.g., Brown and Graves 1981; Cornillier et al. 2008a) and food (e.g., a refrigerated compartment and a regular compartment within the same vehicle) (Chajakis and Guignard 2003), waste collection (Muyldermans and Pang 2010), on-farm milk collection (Dooley et al. 2005) and ship scheduling (Fagerholt and Christiansen 2000a).

3.2.3 Positioning constraints

The location of the items inside the vehicle may be restricted by positioning constraints. Absolute as well as relative positioning restrictions may be specified (Bortfeldt and Wäscher 2013). Absolute constraints refer specifically to a place inside the vehicle where the items may or may not be stored. Relative constraints allow or restrict the placement of the item relative to the positions of other items. An example of relative constraints may be found in Lurkin and Schyns (2013). The authors present an airline container loading problem in which they specify a minimum distance required within the airplane between dangerous goods and other goods. In multi-drop situations, a vehicle has multiple drop-off points in one trip. These situations usually require sequence-based loading, which can be seen as a combination of relative and absolute constraints. Sequence-based loading ensures that no consignment is placed in such a way that it blocks the removal of items to be delivered earlier on the route. This constraint is commonly used in VRPs (e.g. Iori et al. 2007; Gendreau et al. 2006; Moura 2008; Doerner et al. 2007) and is sometimes referred to as a last-in-first-out (LIFO) constraint. It is important to note, though, that only when a single dimension is considered, it is truly LIFO that is applied, since in a two- and three-dimensional problem items can be placed beside each other.

3.3 Container-related constraints

3.3.1 Weight limits

The total weight of items in the vehicle or container should not exceed the weight capacity of the vehicle. Weight limits are a standard feature in VRPs. In several types of vehicles (truck, airplane, ship), weight capacity may be an important restriction when transporting heavy cargo.

3.3.2 Weight distribution constraints

To ensure the stability of the vehicle, it is important to balance the cargo weight aboard. Several authors propose achieving an even weight distribution by ensuring that the center of gravity (CG) of the load be close to the midpoint of the container (e.g. Amiouny et al. 1992; Gehring and Bortfeldt 1997; Davies and Bischoff 1999; Bortfeldt and Wäscher 2013; Paquay et al. 2013). Limbourg et al. (2012) propose an approach for loading ULDs (unit loading devices) into an aircraft. To ensure its balance, the authors not only take the center of gravity into consideration, but also minimize the moment of inertia. The minimization of the moment of inertia leads to a more dense packing of the load around the CG, which reduces stress on the aircraft structure and leads to better aircraft manoeuvrability (Limbourg et al. 2012). Although weight distribution is an important issue in practice (Davies and Bischoff 1999), to our knowledge, it is only considered once in combination with routing problems. Øvstebø et al. (2011) introduce weight distribution constraints in a maritime transportation problem. To ensure the stability of the ship, the torque from the cargo on the ship (making the ship lean sideways) and the distance between the bottom of the ship and its center of gravity are considered.

Closely related to weight balance aboard is the distribution of the cargo over the axles of the vehicle. A truck has several axles (or at least two: one for the tractor and another for the trailer). The axle weight is the total weight (cargo weight plus truck weight) placed on an axle. This is illustrated in Fig. 1. When item j is placed onto a vehicle, the weight of the item is divided over the axle of the tractor and that of the trailer. \(F_K^j\) represents the weight of item j placed on the axle of the tractor. \(F_A^j\) represents the weight of item j on the axle of the trailer. Axle weight limits impose a huge challenge for transportation companies. Transporters face high fines when violating these limits while the current routeplanning software does not incorporate axle weight constraints. Legislation about axle weight limits varies between countries [for an overview of the axle weight limits in Europe, the reader is referred to the International Transport Forum (2011)]. Lim et al. (2013) address axle weight constraints in a container loading problem. They develop a heuristic method to tackle the single container loading problem with axle weight constraints. To our knowledge, Pollaris et al. (2014) are the only authors who consider axle weight limits in a VRP. They propose a mixed integer linear programming model to solve the problem to optimality.

Fig. 1
figure 1

Axle weight tractor and trailer (figure adapted from TruckScience)

Full size image

3.4 Item-related constraints

3.4.1 Loading priorities

Loading priorities play a role in the packing process when vehicle capacity is not sufficient to accommodate all items. The decision as to which items are shipped or left behind may depend on factors such as product shelf life and delivery deadlines (Bischoff and Ratcliff 1995). Several papers in the literature on aircraft loading (e.g., Fok and Chun 2004; Chan et al. 2006; Vancroonenburg et al. 2014) consider loading priorities to select the items to be loaded.

The incorporation of priorities in vehicle routing problems is considered in orienteering problems where a score or priority is assigned to each location. Since the literature on orienteering problems does not consider any other loading constraints, those papers dealing with the orienteering problem are not considered in what follows. For a recent survey of research on the orienteering problem, we refer to Vansteenwegen et al. (2011).

3.4.2 Orthogonality constraints

In the literature devoted to packing, it is often assumed that items have a rectangular shape. In most papers (e.g., Gendreau et al. 2006; Moura and Oliveira 2009; Iori et al. 2007; Fuellerer et al. 2010), the edges of the items are assumed to be packed orthogonal or parallel with the edges of the vehicle. This constraint is often used in combination with two- and three-dimensional loading constraints.

3.4.3 Orientation constraints

The orientation of items may be fixed with respect to the height, width and length of the vehicle. The vertical orientation is often fixed to prevent the item being damaged when put upside down in the container. A fixed vertical orientation constraint is also denoted as a “this-way-up!” constraint, referring to items that are marked with a “this-way-up!” label (Bortfeldt and Homberger 2013). The horizontal orientation of the items can be fixed as well (e.g. Junqueira et al. 2012). This may be necessary when items can only be accessed via a particular side (e.g., pallets that need to be accessed by forklifts) (Bortfeldt and Wäscher 2013). However, in most papers incorporating orientation constraints, the items are allowed to rotate 90 degrees on the width–length (horizontal) plane (e.g. Gendreau et al. 2006; Tarantilis et al. 2009; Fuellerer et al. 2010; Zhu et al. 2012; Ruan et al. 2013). This constraint is frequently used in VRPs with two- and three-dimensional loading constraints.

3.4.4 Stacking constraints

When items are placed on top of each other in the vehicle, the items may be damaged by the pressure of items placed above them. Stacking constraints (also denoted as load-bearing strength constraints or fragility constraints) prevent this from happening. The load-bearing strength of an item is the maximum pressure that can be applied on this item before damage takes place(Junqueira et al. 2013). The load-bearing strength may vary across different vertical orientations of this item (Ratcliff and Bischoff 1998). The box contents (solid contents vs. less solid contents) and loading conditions (humidity, duration of loading, way of stacking...) may also influence the load-bearing strength of an item (Bortfeldt and Wäscher 2013). Fragile items can be defined as items that cannot bear any pressure from other items, indicating that no item can be placed upon this item. Some models in the literature (e.g., Gendreau et al. 2006; Tarantilis et al. 2009; Fuellerer et al. 2010; Ruan et al. 2013) allow for fragile items being placed upon other such items, but forbid non-fragile items to be placed upon fragile ones. Stacking constraints have been considered in several papers concerning three-dimensional loading VRPs (e.g. Gendreau et al. 2006; Tarantilis et al. 2009; Fuellerer et al. 2010; Ruan et al. 2013; Junqueira et al. 2013).

3.5 Load-related constraints

3.5.1 Stability constraints

When items are stacked on top of each other in the vehicle, the items have to be supported by other items or by the floor to ensure vertical (or static) stability of the cargo. Vertical stability constraints specify the minimum supporting area of each item (e.g., as a percentage of the base area of the item). Horizontal (or dynamic) stability of the cargo refers to the support of the lateral faces of items in the container to prevent items moving around in the container (Junqueira et al. 2013). The literature concerning three-dimensional VRPs often takes vertical stability constraints into account (e.g., Gendreau et al. 2006; Fuellerer et al. 2010; Bortfeldt 2012; Zhu et al. 2012; Ruan et al. 2013). According to the authors, horizontal stability constraints have not yet been considered explicitly in routing models in literature.

4 Integration of loading constraints in vehicle routing problems

The integration of loading constraints in VRPs is a recent domain of research. Both problems belong to the NP-hard type of optimization problems. Combining these problems is therefore very challenging, but leads to a better overall logistical solution. A survey conducted among several Belgian logistics service providers revealed that these are faced with important loading problems in route planning. Pollaris et al. (2013) point out that if a planning does not take into account axle weight constraints, it is likely that it contains axle weight violations for some trucks and ad hoc changes need to be made in the planning to make it feasible. Developing VRP models that incorporate loading constraints is critical, therefore, to efficient route planning. This section reviews the literature on the integration of vehicle routing and loading problems. Since loading constraints also apply in a maritime transport context, we include the papers introducing these constraints in routing problems for maritime transport in our discussion. To our knowledge, there exists no literature on the integration of loading constraints in a routing model in an air transport context.

The papers dealing with the combination of routing and loading problems may be placed in one of the following categories defined on the basis of the type of routing problem and the loading characteristics dealt with: two-dimensional loading CVRP (2L-CVRP), three-dimensional loading CVRP (3L-CVRP), multi-pile VRP, multi-compartments VRP, pallet packing VRP (PPVRP), Minimum multiple trip VRP (MMTVRP) with incompatible commodities, Traveling salesman problem with pickups and deliveries (TSPPD) with LIFO/FIFO constraints, double TSP with Pickups and deliveries with multiple stacks (DTSPMS) and vehicle routing problem with pickups and deliveries (VRPPD) with additional loading constraints. This classification is similar to that used by Iori and Martello (2010). For each category, we give an overview of the loading constraints using the classification of Bortfeldt and Wäscher (2013). Table 1 overviews the papers on 2L-CVRP and 3L-CVRP. Table 2 overviews those concerning the multi-pile VRP, multi-compartments VRP, PPVRP and the MMTVRP with incompatible commodities. Table 3 overviews the categories concerning the PDPs.

Table 1 Papers on 2L-CVRP and 3L-CVRP
Full size table
Table 2 Papers on multi-pile VRP, multi-compartments VRP, Pallet-Packing VRP and MMTVRP with incompatible commodities
Full size table
Table 3 Papers on TSPPD with LIFO/FIFO constraints, DTSPMS, VRPPD with loading constraints
Full size table

Except for one paper (Fagerholt et al. 2013), complete-shipment constraints and loading priorities do not apply in the models, since the capacity of the vehicle fleet is assumed to be sufficient to accommodate all items. Connectivity constraints, on the other hand, are standard features in routing models with multiple vehicles, since it is often assumed that all the items of a customer have to be shipped in the same vehicle. Vertical stability constraints and stacking constraints are only relevant when the height dimension is taken into account. Orthogonality and orientation constraints only apply when at least two dimensions are considered.

The papers of each category are discussed in what follows. It generally appears that few other rich constraints (besides loading constraints) are included in the current VRP models with loading constraints. When models do include other real-life characteristics (such as time windows or a heterogeneous vehicle fleet), these are mentioned. In most papers described in this survey, the objective function is to minimize total routing costs or travel distance. If not, this is mentioned in the description of the problem. Another observation is that problems in which more than one dimension is considered (2L-CVRP, 3LCVRP, pallet packing VRP) are mostly solved by means of a two-stage approach. The routing problem acts as the main problem and iteratively calls exact or heuristic methods to solve the packing subproblem (Tao and Wang 2013). The methods for solving the packing problem are mostly based on bin packing literature (e.g., Baker et al. 1980; Lodi et al. 1999; Martello and Vigo 1998). Maximum touching perimeter (or touching area in the three-dimensional case) and bottom-left-fill are often used to solve two- and three-dimensional packing problems heuristically (e.g., Iori et al. 2007; Gendreau et al. 2006; Tarantilis et al. 2009; Tao and Wang 2013; Dominguez et al. 2014), while branch-and-bound methods and lower bounds are usually employed to deal with packing problems exactly (e.g., Iori et al. 2007; Fuellerer et al. 2009; Gendreau et al. 2008). For each category with multi-dimensional loading, a paragraph describes how the packing problem is generally dealt with. For the other categories, the loading part is usually not that complex, which does not make it necessary to apply heuristics merely for the packing problem. In the latter case, the loading constraints are usually incorporated in the vehicle routing problem (e.g., Cordeau et al. 2010; Petersen and Madsen 2009; Cherkesly et al. 2014a).

4.1 Two-dimensional loading CVRP

In the two-dimensional loading CVRP (2L-CVRP), the customers’ requests and the measurements of the vehicles are expressed in two dimensions. Width and length are usually taken into account, whereas height is not. In real-life applications, this problem arises in distribution logistics when items cannot be stacked on top of each other because of their weight, fragility or large dimensions (Strodl et al. 2010). Examples of applications may be found in the distribution of large kitchen appliances such as refrigerators, large mechanical components or fragile items such as porcelain. Two papers propose an exact method (Iori et al. 2007; Martinez and Amaya 2013). Sequence-based loading as well as multiple vehicles are assumed in most (see Table 1). When height is not considered, stacking constraints and vertical stability constraints are not applicable to the problems. A single paper assumes a heterogeneous fleet (Leung et al. 2013) and three papers consider time windows (Attanasio et al. 2007; Khebbache-Hadji et al. 2013; Martinez and Amaya 2013). A mathematical formulation for a 2L-CVRP is presented by Martinez and Amaya (2013); Dominguez et al. (2014) and Pollaris et al. (2014).

Iori et al. (2007) are the first to address a 2L-CVRP. They develop a branch-and-bound algorithm and solve the problem to optimality for up to 35 customers. The 2L-CVRP has been solved heuristically by means of Tabu search (TS) (Gendreau et al. 2008), guided TS (Zachariadis et al. 2009), extended guided TS (Leung et al. 2011) and a local search metaheuristic (Zachariadis et al. 2013b). Fuellerer et al. (2009) employ an ant colony optimization (ACO) method for a similar problem, with a small alteration in the loading constraints. The items are allowed to rotate 90 degrees on the horizontal plane.

Attanasio et al. (2007) consider a variant of the 2L-CVRP based on a consolidation and dispatching problem of a multinational chemical company. Each shipment must take place within a multi-day time window, spanning from the manufacturing date to a given deadline. Only two dimensions are considered because all items and bins have the same height. Attanasio et al. (2007) develop a heuristic based on a cutting plane framework in which a simplified integer linear program (ILP) is solved. Items are allowed to rotate and sequence-based loading is assumed. Strodl et al. (2010) develop a variable neighbourhood search (VNS) to address the routing problem and formulate a heuristic and an exact procedure for the two-dimensional loading problem. Items have a fixed orientation and sequence-based loading is not considered. Duhamel et al. (2011) address the 2L-CVRP without sequence-based loading. They solve the problem using a two-stage approach. First, the 2L-CVRP is converted into a resource constraint project scheduling problem-CVRP (RCPSP-CVRP) by relaxing the bin packing constraints. The items in the packing problem are represented by activities in the RCPSP. Each activity has a duration (length of item) and requirement of resource (width of item). A route is feasible if the makespan of the RCPSP does not exceed the length of the vehicle (Duhamel et al. 2011). The RCPSP-CVRP is solved with a greedy randomized adaptive search procedure (GRASP) in an evolutionary local search (ELS) framework. In the second step, the feasibility of the best RCPSP-CVRP solutions with the 2L-CVRP constraints are checked by transforming the RCPSP-CVRP solutions into 2L-CVRP solutions. According to the authors, this approach saves a lot of computation time because a packing plan is computed only for the best RCPSP-CVRP solutions. Leung et al. (2013) develop a simulated annealing (SA) model to solve the 2L-CVRP with heterogeneous fleet. The packing constraints that are considered in this model are the same as in Iori et al. (2007). The vehicles have different weight capacities and different measurements.

Martinez and Amaya (2013) consider a VRP with multi-trips, time windows and two-dimensional circular loading constraints. A homogeneous fleet is considered and sequence-based loading is not assumed. The problem is based on a real-life problem faced by a home delivery service transporting perishable circular-shaped products. A mixed integer non-linear programming mathematical model is developed to solve small-size problems (up to 17 customers). Furthermore, a two-step heuristic method is proposed to handle instances of realistic size. In the first step, an initial solution is built using a sequential insertion heuristic. In the second step this solution is improved with a TS algorithm.

Pollaris et al. (2014) present a mixed ILP model for the CVRP with sequence-based pallet loading and axle weight constraints. This is a special case of 2L-CVRP in which all items are homogeneous pallets and may be placed in two horizontal rows in the vehicles. The model takes into account weight restrictions on the axles of the tractor and trailer of the vehicle at all times (i.e. at the depot as well as after each delivery). The authors compare the model to the CVRP with sequence-based pallet loading without axle weight restrictions and conclude that not including axle weight restrictions may induce major violations of axle weight limits.

Dominguez et al. (2014) develop a biased-randomized algorithm for the 2L-CVRP with and without item rotations. The problem assumes a homogeneous vehicle fleet and sequence-based loading is not considered. The algorithm uses a multi-start approach and combines at each restart a biased randomization of a savings-based routing algorithm as proposed by Clarke and Wright (1964) for the routing part with a multi-start biased-randomized version of the best fit packing heuristic to check loading feasibility. In the first biased randomization process, the savings list of the edges is randomized using a biased probability distribution (geometric distribution). For the loading feasibility check, first a biased randomization is applied on the list of items to be loaded. Next, the best fit heuristic is used, beginning with the items at the top of the list. If after several iterations, the best fit heuristic does not find a feasible loading scheme, the proposed route will be assumed to be infeasible and a new randomization is applied on the savings list of the edges which will again be followed by a loading feasibility check.

Finally, Khebbache-Hadji et al. (2013) develop a heuristic solution method to solve the 2L-CVRP with time windows (2L-CVRPTW) without sequence-based loading.

The packing feasibility check in the above papers consists of a mix of several types of solution methods (heuristic as well as exact). Commonly used methods include the bottom-left-fill heuristic (e.g., Iori et al. 2007; Zachariadis et al. 2009; Fuellerer et al. 2009), maximum touching perimeter (e.g., Zachariadis et al. 2009; Strodl et al. 2010; Khebbache-Hadji et al. 2013), lower bounds (e.g., Iori et al. 2007; Gendreau et al. 2006; Fuellerer et al. 2009) and branch-and-bound (e.g., Iori et al. 2007; Gendreau et al. 2006; Fuellerer et al. 2009; Strodl et al. 2010). If a combination of heuristic and exact algorithms is used, first the heuristics are applied, and when they do not find a feasible solution, the exact method is used to solve the packing problem.

4.2 Three-dimensional loading CVRP

In the three-dimensional loading CVRP (3L-CVRP), the three dimensions of the vehicle are taken into account and the customer’s demand also consists of three-dimensional items. Since the height dimension is considered, additional loading constraints concerning fragility and vertical stability of the cargo may be specified. This problem is frequently encountered in distribution logistics when items may be stacked on top of each other in a container. Examples of applications of the 3L-CVRP are found in the distribution of furniture, household appliances, soft drinks and staple goods (Ruan et al. 2013). Sequence-based loading is incorporated in most models as shown in Table 1. Most papers assume a homogeneous fleet, while only three papers consider time windows (Moura 2008; Moura and Oliveira 2009; Bortfeldt and Homberger 2013). An exact solution method and a formulation of the 3L-CVRP is provided by Junqueira et al. (2013).

Gendreau et al. (2006) are the first to address the 3L-CVRP. Their model includes sequence-based loading, stacking and vertical stability constraints and a fixed vertical orientation of the items in the vehicles (the items are allowed to be rotated by 90 degrees on the width–length plane). The same problem is solved heuristically with ACO (Fuellerer et al. 2010), a combination of TS and guided local search (Tarantilis et al. 2009), honey bee optimization (Ruan et al. 2013), TS (Bortfeldt 2012; Wisniewski et al. 2012) (Zhu et al. 2012) and a combination of a genetic algorithm (GA) with a TS method (GATS) (Miao et al. 2012). Ren et al. (2011) develop a hierarchical method to solve the 3L-CVRP. In the subordinated module, a branch-and-bound method is applied to find a solution for the modified 3L-CVRP in which the loading constraints are relaxed and replaced by a volume-ratio constraint. Next, a container loading algorithm is used to check whether the items of the customers of each minimum cost route generated by the branch-and-bound algorithm can feasibly be loaded into the container. A superior module repeats this process and varies the volume ratio until all items are feasibly loaded. Aprile et al. (2007) develop a simulating annealing heuristic (SA) to solve the 3L-CVRP. With respect to loading constraints, only the classical three-dimensional packing constraints are included in their model. Tao and Wang (2013) use a TS method to solve the 3L-CVRP heuristically. To the best of our knowledge, this heuristic is currently one of the best in terms of solution quality and computational efficiency for the 3L-CVRP defined by Gendreau et al. (2006). While the TS for the routing part is quite simple, the authors employ two mechanisms from 3D bin packing literature to help exploit the loading space better. First, a least waste packing heuristic (Wei et al. 2009) is employed which aims at minimizing the space wasted when packing an item into a vehicle. Second, the mechanism for updating new potential points or positions in the container at which items may be loaded is a combination of normal points and corner points. While normal points are widely used, corner points have not yet been used in the 3L-CVRP literature. Corner points follow the concept of envelope and are introduced by Martello et al. (2000) for 3D bin packing.

Junqueira et al. (2013) are to the authors’ knowledge the first to propose an exact method to solve the 3L-CVRP. They assume a homogeneous vehicle fleet, sequence-based loading, stacking constraints, orientation constraints and stability constraints. The authors take into account the unloading pattern of the items at customer places. By specifying a maximum reach length of the worker or forklift, they avoid items being placed on top of items of other customers that cannot be reached. An ILP is proposed to solve small-sized instances (number of customers \(<\)15).

Bortfeldt and Homberger (2013) develop a two-stage method, called Packing first–Routing second for the 3L-CVRP with Time windows (3L-CVRPTW). In the first stage, the packing problem is solved for each customer separately. The resulting packing plans minimize the total loading length of the boxes of each customer in a vehicle. In the second stage, vehicle routes are constructed with the constraint that the sum of the loading lengths (calculated in the first stage) may not exceed the length of the loading space of the vehicle. After these stages, a packing plan is determined for the previously generated routes. Moura (2008) develops a multi-objective GA to solve the 3L-CVRPTW. The problem presented has three objectives: minimization of the number of vehicles, minimization of the total distance traveled and maximization of volume utilization. The model considers sequence-based loading, orientation constraints and stability constraints. Moura and Oliveira (2009) develop a sequential and a hierarchical approach to solve the 3L-CVRPTW. The objectives are to minimize the number of vehicles and the total route time. In the hierarchical approach, the loading problem is seen as a subproblem of the routing problem. The routes are planned first, and afterwards, for each route, the items are packed into the vehicles. As in Moura (2008), the model considers sequence-based loading, orientation constraints and stability constraints. In the sequential approach, the container loading and the vehicle routes are planned at the same time. The unloading sequence constraint is relaxed in this solution approach.

Massen et al. (2012) develop a column generation-based heuristic method for vehicle routing problems with black box feasibility (VRPBB). In the VRPBB the routes of the basic VRP need to satisfy a number of unknown constraints. A black box algorithm is used to verify the feasibility of a route. Their approach is tested on the 3L-CVRP as well as on the multi-pile VRP.

Ceschia et al. (2013) consider the 3L-CVRP with sequence-based loading and a (weakly) heterogeneous vehicle fleet. They consider stacking and stability constraints, orientation constraints, the maximum reach length of a worker or forklift as well as the possibility of split deliveries. Ceschia et al. (2013) solve the problem in one stage using a local search approach that combines SA and large neighbourhood search (LNS).

Maximum touching area and bottom-left-fill are often employed to check the loading feasibility in the 3L-CVRP literature (e.g., Gendreau et al. 2006; Fuellerer et al. 2010; Zhu et al. 2012; Wisniewski et al. 2012; Ruan et al. 2013). These heuristics are extensions of the bottom-left-fill and maximum touching perimeter methods from 2D bin packing literature. Tao and Wang (2013) employ, in combination with maximum touching area, a least waste algorithm. Junqueira et al. (2013) solve the 3L-CVRP with an ILP in which they incorporate the 3D loading feasibility check.

4.3 Multi-pile VRP

The multi-pile vehicle routing problem (MP-VRP) is introduced by Doerner et al. (2007). They develop a TS method and an ACO heuristic to solve a real-world transportation problem regarding the transport of wooden chipboards. For every order, chipboards of the same type (small or large) are grouped into a unique item, which is placed onto a single pallet. The vehicle is divided into three piles on which pallets can be stacked. Pallets containing large chipboards can extend over multiple piles. The other pallets can be placed into a single pile. An example of a loading plan of a multi-pile vehicle is shown in Fig. 2 where each color represents a particular customer’s items. Because of this specific configuration of pallets placed into multiple piles, the original problem in three dimensions can be reduced to a single-dimension problem. In all papers on this problem that we found, a homogeneous vehicle fleet is assumed. A single paper proposes an exact solution method (Tricoire et al. 2011).

Fig. 2
figure 2

Example of a multi-pile vehicle (figure adapted from Massen et al. 2012)

Full size image

Tricoire et al. (2011) develop a combination of VNS and branch-and-cut to solve the MP-VRP exactly for instances with up to 44 customers and heuristically for large-sized instances. Tricoire et al. (2011) propose a general formulation for the VRP, but do not formulate the packing problem. The authors use a pool of feasible packing solutions in their branch-and-cut algorithm. These solutions are generated with a packing heuristic or a dynamic programming method. Massen et al. (2012) test a column generation method for vehicle routing problems with black box feasibility (VRPBB) on the MP-VRP.

Doerner et al. (2007) and Tricoire et al. (2011) both use a heuristic algorithm as well as dynamic programming to check the loading feasibility. The heuristic algorithm computes in a preprocessing phase the minimum height of the items of every customer and of the combined loading of the items of any pair of customers. Whenever a route is processed, this information is used to compute an upper bound for the total height of the load in the vehicle.

4.4 Multi-compartments VRP

The multi-compartments VRP is related to the multi-pile VRP. Vehicles with multiple compartments allow the transportation of heterogeneous products in separate compartments in the same vehicle. A compartment may not always be compatible with every type of product and certain product pairs cannot be loaded together into the same compartment (Derigs et al. 2011). Vehicle routing problems with compartments are encountered in industries like petrol and food distribution, waste collection, on-farm milk collection and ship scheduling. This section discusses papers dealing with multi-compartments VRP. In several papers, a heterogeneous vehicle fleet and/or time windows are considered and various exact solution methods have been developed as shown in Table 2. El Fallahi et al. (2008) present a formulation for the multi-compartments VRP. Cornillier et al. (2008b), Cornillier et al. (2009) and Cornillier et al. (2012) provide formulations for, respectively, the petrol station replenishment problem (PSRP), the PSRP with time windows (PSRP-TW) and the multi-depot PSRP-TW.

To our knowledge, Brown and Graves (1981) are the first to consider the dispatching of petroleum tank trucks. Each tank truck has several compartments which may carry different types of petroleum. The authors develop an automated real-time dispatch system for the distribution of petroleum products for a major US oil company. Each order includes several gasoline products, jointly constituting a full truckload. Avella et al. (2004) also consider a real-life case of a company that supplies petrol to fuel pumps. Several less than truckload orders may be shipped in a single truck. They propose a solution method that uses a savings-based routing algorithm for the generation of routes and a best fit decreasing heuristic for the packing problem. They also develop an exact method that uses a branch-and-price algorithm, based on a set partitioning formulation, which can solve instances with up to 60 stations. The PSRP has been studied by Cornillier et al. (2008a, b, 2009, 2012). The aim of the PSRP is to optimize the delivery of several petroleum products to petrol stations. Compartments can only hold one type of product and, since the compartments do not have flow meters, the content of one compartment may not be split between petrol stations. Cornillier et al. (2008b) consider the multi-period PSRP, while Cornillier et al. (2012) consider the PSRP-TW with multiple depots. The exact algorithm of Cornillier et al. (2009) solves instances with up to 200 stations.

Fagerholt and Christiansen (2000a) consider the Ship scheduling and allocation problem (SSAP) derived from a real-life case of the transport of mineral fertilizers by a bulk ship. The problem is similar to a pickup and delivery problem with time windows and multiple compartments. The compartments are flexible and are constructed by partitioning the loading space. The authors present a set partitioning approach to solve the problem exactly for instances with up to 70 customers. Fagerholt and Christiansen (2000b) focus on a subproblem of the SSAP studied by Fagerholt and Christiansen (2000a). More precisely, they consider the traveling salesman problem with allocation, time windows and precedence constraints (TSP-ATWPC). They develop a dynamic programming algorithm to solve the problem exactly for instances with up to 70 customers.

Chajakis and Guignard (2003) consider the distribution of goods to convenience stores in vehicles with multiple compartments. They develop two integer programming models for two possible cargo space layouts. Approximation schemes based on Langrangian relaxation are presented to solve these problems exactly for instances with up to 240 customers. Dooley et al. (2005) use a GA for the on-farm collection problem of milk. The model may be used to evaluate alternative transport management strategies with regard to milk collection.

El Fallahi et al. (2008) construct a memetic algorithm with a post-optimization phase based on path relinking and a TS algorithm to solve the VRP with multiple compartments. Note that a memetic algorithm is a GA combined with a local search procedure to intensify the search. The authors assume that each compartment is dedicated to a single product. The demand of a customer for a given product type cannot be split between vehicles, but different product types of the same customer order can be split between several vehicles. Since order splitting is allowed, connectivity constraints are not included in the model. The results are compared with cases in literature in which order splitting is not allowed and conclude that order splitting improves the results on average. Secondly, the authors conclude that TS provides slightly better results than the memetic algorithm, but also requires more computation time. Mendoza et al. (2010) also construct a memetic algorithm to solve the VRP with multiple compartments and take into account stochastic demands.

Muyldermans and Pang (2010) construct a guided local search metaheuristic to solve the VRP with multiple compartments. Their research is based on a one-dimensional co-collection problem of waste. Homogeneous vehicles with multiple compartments are used to co-collect different types of waste. Derigs et al. (2011) implement a portfolio of different heuristics to solve the VRP with multiple compartments.

4.5 Pallet packing VRP

The pallet packing VRP (PPVRP) is introduced by Zachariadis et al. (2012). Customer demand is for three-dimensional rectangular boxes which are first feasibly stacked onto pallets. These pallets are then loaded into the vehicles. The items demanded by a single customer must be stacked onto the same pallet. Many real-world applications of the PPVRP arise in distribution logistics. Examples may be found in the grocery and pharmaceutical industry. Distribution centers receive orders from grocery stores and manually pick and palletize the items of the orders for each store and send them to the store locations (Zachariadis et al. 2012). In the pharmaceutical industry, items are grouped into cardboard boxes which are palletized and transported from the production or distribution center to pharmacies (Zachariadis et al. 2012). To our knowledge, a formulation for the pallet packing VRP has not been provided yet.

Zachariadis et al. (2012) develop a local search metaheuristic strategy to solve the basic PPVRP and the PPVRP with time windows (PPVRPTW). They assume that every pallet can be unloaded at all times, without having to move any other pallet. Because of this assumption, sequence-based loading of the pallets into the vehicle is not required. Sequence-based loading of the boxes onto the pallets is not assumed either. Orientation, orthogonality as well as vertical stability constraints are considered for the loading of the boxes onto the pallets. Zachariadis et al. (2013a) consider a variant of the PPVRP: the Pickup and delivery routing problem with time windows and pallet loading (PDRP-TWP). The key difference with the PPVRPTW is that two types of requests are considered in the PDRP-TWP, namely plane delivery requests and paired pickup and delivery requests. Zachariadis et al. (2013a) extend the metaheuristic developed in Zachariadis et al. (2012) to deal with the paired pickup and delivery requests. The model takes into account the same routing and loading constraints as in Zachariadis et al. (2012).

With respect to the 3D loading feasibility check for the packing of boxes onto pallets, the above papers employ a heuristic that packs each box in the minimum volume cuboid that can accommodate this box in addition to the packing heuristics used in 3L-CVRP literature (bottom-left-fill and maximum touching area) (Zachariadis et al. 2012). This heuristic aims at finding a high degree of pallet volume utilization. The models also make use of a memory structure that keeps track of feasible and infeasible packing structures to avoid making the same feasibility check twice.

4.6 Minimum multiple trip VRP with incompatible commodities

Battarra et al. (2009) consider the minimum multiple trip VRP (MMTVRP) with time windows and incompatible commodities. Vehicles may perform multiple routes within a single trip (i.e. working shift) which is limited in total duration. The objective is to minimize the total number of multiple trips. Three types of incompatible products (vegetables, fresh products and non-perishable items) are considered. Incompatible means that they cannot be transported together in a single vehicle. One-dimensional loading is considered. Battarra et al. (2009) propose a two-phase heuristic which decomposes the problem into two subproblems. In the first subproblem, a set of routes is determined using a VRPTW heuristic. In the second subproblem, the routes are aggregated into multiple trips by means of a packing heuristic. To the authors’ knowledge, an exact method or a problem formulation has not yet been developed for the MMTVRP with incompatible commodities.

4.7 Traveling salesman problem with pickups and deliveries with LIFO/FIFO constraints

In a VRPPD, items can both be picked up at and delivered to customers, as opposed to the general VRPs in which items are only delivered at customer locations. In the TSPPD a single route needs to be constructed. Applications of the TSPPD may be found in the routing of automated guided vehicles which move items between workstations, in dial-a-ride systems where passengers are transported between different pickup and delivery locations and in less-than-truckload transportation (Dumitrescu et al. 2010). Papers concerning the TSPPD provide exact methods as well as heuristics to solve the problem and all consider, to the authors’ knowledge, one-dimensional loading. The sequence-based loading constraint can therefore be reduced to a LIFO constraint. First-in-first-out (FIFO) is also sometimes assumed as can be seen in Table 3. Furthermore, various models include time windows. Orthogonality constraints, orientation constraints and stacking constraints are not relevant, since only one-dimensional models have been developed. Formulations for the TSPPD with LIFO loading are presented by Arbib et al. (2009) and Cordeau et al. (2010), while a formulation for the TSPPD with FIFO loading is presented by Erdogan et al. (2009) and Cordeau et al. (2010b). Côté et al. (2012b) present a formulation for the TSPPD with multiple stacks and LIFO loading. Øvstebø et al. (2011) give a formulation for the TSP on roll-on/roll-off (RoRo) ships.

Ladany and Mehrez (1984) make the first contribution to the TSPPD with LIFO constraints. The motivation for their study is a real-world delivery problem in which reshuffling of goods inside a container causes costs and time losses. They are the first to deal with the problem of reshuffling in optimal routing design and are able to solve instances exactly with up to three requests. Later, Pacheco (1997, in (Iori and Martello 2010)) developed a heuristic method to solve the TSPPD with LIFO constraints, while Carrabs et al. (2007a) developed a VNS. Carrabs et al. (2007b) develop an additive branch-and-bound method to solve the same problem exactly for instances with up to 43 vertices. In the same paper, a branch-and-bound algorithm is applied to the TSPPD with FIFO loading. Erdogan et al. (2009) and Cordeau et al. (2010b) also consider the TSPPD with FIFO loading. Cordeau et al. (2010b) tackle the problem with a branch-and-cut method and are able to solve instances with up to 43 vertices. Arbib et al. (2009) present a linear programming formulation of the TSPPD with LIFO loading. The authors solve the problem with up to 21 vertices using CPLEX 9.0. Cordeau et al. (2010) develop a branch-and-cut method to solve the TSPPD with LIFO for instances with up to 25 requests. Li et al. (2011) build upon and improve the VNS of Carrabs et al. (2007a) to solve the problem heuristically.

Levitin and Abezgaouz (2003) consider the routing of an Automated guided vehicle (AGV) which is used for carrying multiple pallets between workstations. Each additional pallet is placed on top of the pallets that are already carried by the AGV. To avoid rearranging the pallets at the workstations, a LIFO policy is assumed. They develop an exact algorithm to solve the problem with up to 100 vertices.

Côté et al. (2012a) consider the TSPPD with multiple stacks with LIFO loading. A LNS is proposed to solve the problem heuristically. Côté et al. (2012b) propose a branch-and-cut algorithm for the same problem and are able to solve instances with up to 43 vertices.

Øvstebø et al. (2011) examine a similar problem on roll-on/roll-off (RoRo) ships that transport cargo on wheels. The ship contains several decks and each deck may be divided into several lanes in which the cargo may be placed. The lanes may be compared to stacks in a truck. Sequence-based loading, stability constraints as well as time windows are considered, where the former is modeled as a soft constraint. A penalty cost is incurred if the constraint is violated. According to the authors, this corresponds to reality because although reshuffling cargo represents an inconvenience, this may be allowed in RoRo setting if supplementary cargo can be carried. Two types of stability measures concerning weight distribution are considered. The first one refers to the torque from the cargo on the ship that makes the ship lean sideways which should be within limits at all times. The second stability measure refers to the distance of the ship’s bottom deck to the center of gravity of the ship which should be less than some specified ceiling at all times. The aim of the problem is to maximize the revenue from cargo carried from optional nodes minus a penalty for cargo not carried from mandatory nodes, a penalty for violating the sequence-based loading constraint, travel cost and cost of ship usage. A mixed integer programming model is used to solve the problem exactly for instances with up to eight requests. A heuristic method which consists of a TS and a squeaky wheel optimization construction heuristic is developed to solve larger instances.

4.8 Double traveling salesman problem with pickups and deliveries with multiple stacks

The double traveling salesman problem with multiple stacks (DTSPMS) is proposed by Petersen and Madsen (2009). Pickup and delivery of goods are performed in two separate networks. All pickups are made before any delivery can take place. The goods cannot be repacked or vertically stacked. The goods can be placed in several rows (horizontal stacks). In each row the LIFO principle needs to be obeyed. It is assumed that each order consists of a single item. The problem is based on a real-world application in which in a first phase a container is loaded onto a truck to perform pickup operations and returned by that truck to a depot or terminal. In a second phase, the container is loaded onto a train, ship, plane or another truck and transported to another depot or terminal. In the depots or terminals, there are no facilities to repack the items inside the container. In the final phase, the container is again transferred to a truck which performs the delivery operations (Petersen and Madsen 2009). A solution for the DTSPMS consists of a pickup and a delivery tour with a corresponding feasible packing plan for the items in the container. The total combined distance of the pickup and delivery tour is minimized. In Fig. 3 an example of a simple DTSPMS with four items and two stacks is displayed. Items are picked up in the pickup tour (a) and delivered in the delivery tour (b). A possible feasible packing plan can be found in the last picture (c). The vehicle starts at the pickup depot at node \(0\), loads items \(h\), \(i\), \(j\) and \(k\) and returns to the pickup depot. Then the vehicle goes to the delivery depot and delivers items \(i\), \(k\), \(h\) and \(j\) and returns to the delivery depot. The loading of the items in the stack is done from bottom to top and the unloading from top to bottom. In the loading plan can be seen that the LIFO constraints in both stacks are satisfied. All DTSPMS models take into account one-dimensional packing constraints and LIFO loading in each stack. Several exact solution methods have been developed as may be seen in Table 3. A formulation of the DTSPMS is presented by Petersen and Madsen (2009). To our knowledge, none of the papers tackling the DTSPMS include time windows.

Fig. 3
figure 3

A simple DTSPMS example with a pickup tour (a), a delivery tour (b) and a loading plan (c) (figure from Alba et al. 2011)

Full size image

Petersen and Madsen (2009) develop four metaheuristics to tackle the problem: iterated local search (ILS), TS, SA and LNS. In the ILS, the method of the steepest descent is used as local search strategy. This means that after each random restart, the solution providing the best improvement is chosen. According to the authors, results indicate that the LNS performs much better than the other methods. Felipe et al. (2009b) develop four new neighbourhood structures for the DTSPMS which are implemented in a VNS and an SA method. Lusby et al. (2010) propose an exact algorithm to solve the DTSPMS for instances with up to 18 requests. They first generate a set of pickup tours and a set of delivery tours. In a second step, combinations of delivery and pickup tours are matched in the TSP matching problem, which verifies whether the combinations generate a feasible packing plan. Only the k-best delivery and pickup tours in terms of length are considered. Petersen et al. (2010) propose several different modeling approaches for an exact solution of the DTSPMS. First, a branch-and-cut approach is used on the mathematical programming formulation of the problem introduced in Petersen and Madsen (2009) which is called the ’precedence’ model. Next, a variation of the precedence model is proposed and solved with a branch-and-cut approach. Finally, two new different mathematical formulations [the flow model and the TSP with Infeasible paths (TSPIP)] are developed. To solve the flow model, again a branch-and-cut approach is used. For the TSPIP a decomposition approach is used to solve the problem. The solution of the TSPIP with a decomposition approach turned out to be the most successful approach in which the problem is solved exactly for instances with up to 25 requests. Lusby and Larsen (2011) improve the exact method developed by Lusby et al. (2010) by including an additional preprocessing technique: the longest common subsequence between the pickup and the delivery tour. This preprocessing technique significantly decreases the number of matching problems that need to be solved. This makes it possible to consider more matching problems in the same amount of time and dramatically improves the efficiency of the solution method. The authors are able to solve instances with up to 28 requests. Alba et al. (2011) develop a branch-and-cut algorithm to solve the DTSPMS exactly for instances with up to 25 requests. Felipe et al. (2011) improve the previously developed VNS in Felipe et al. (2009b) by allowing intermediate infeasible solutions. Carrabs et al. (2013) consider the double TSP with two stacks. They develop a branch-and-bound algorithm to solve this problem exactly for instances with up to 29 requests.

4.9 VRP with pickups and deliveries with additional loading constraints

To our knowledge, seven papers in literature so far consider pickup and delivery problems with multiple vehicles combined with loading constraints. Five of them consider one-dimensional loading. Time windows as well as a heterogeneous vehicle fleet are sometimes included as shown in Table 3. A single paper proposes an exact solution method (Cherkesly et al. 2014a). Fagerholt et al. (2013) present a formulation for the VRPPD with time windows, complete-shipment constraints and connectivity constraints. Cherkesly et al. (2014a) present a formulation for the VRPPD with time windows and LIFO loading. The VRPPD with multiple vehicles is a generalization of the TSPPD. As a consequence, all applications (AGVs, dial-a-ride problems, less-than-truckload transportation...) of the TSPPD may be considered by the VRPPD with the additional possibility of using more than a single vehicle, which is often encountered in real life (Braekers et al. 2014).

Xu et al. (2003) present a practical pickup and delivery problem in which they consider multiple time windows, heterogeneous vehicles, compatibility constraints between items and vehicle types, separation constraints, driver’s work rules and LIFO loading. The authors solve this problem with a hybrid approach in which heuristics are integrated in a column generation framework. Cheang et al. (2012) consider the multiple vehicle pickup and delivery problem with LIFO loading and distance constraints. A homogeneous fleet is assumed. A two-stage method is proposed to solve the problem. In the first stage, the number of vehicles required is minimized using an SA and an ejection pool approach. The second stage minimizes total travel distance using a VNS and a probabilistic TS.

Fagerholt et al. (2013) present a VRPPD with time windows and loading constraints to solve a real-life ship routing and scheduling problem that arises in tramp shipping. Complete-shipment constraints, connectivity constraints and a heterogeneous vehicle fleet are taken into account. The objective function maximizes the revenue from the optional spot cargoes minus the variable sailing and port costs through the planning period. A TS heuristic is proposed to solve the problem.

Cherkesly et al. (2014a) consider the VRPPD with time windows and LIFO loading. They develop three branch-price-and-cut algorithms to solve the problem exactly for instances with up to 75 requests. Cherkesly et al. (2014b) develop a population-based metaheuristic to solve larger instances of the same problem heuristically. In both papers the number of vehicles is first minimized before minimizing the total traveled distance. Zachariadis et al. (2013a) consider the pickup and delivery routing problem with time windows and pallet loading (PDRP-TWP) which is discussed in Sect. 4.5.

Malapert et al. (2008) propose a framework to handle the two-dimensional VRPPD with multiple vehicles and sequence-based loading. Items have to be packed orthogonal to the sides of the loading surface and the orientation of the items is fixed. A constraint programming model is formulated and a simple commitment heuristic is applied, but turned out not to be efficient to solve the problem. According to the authors, most packing techniques use reduction procedures which are not compatible with the sequence-based loading constraint.

4.10 Benchmark instances

In Table 4, an overview of benchmark instances on routing problems with loadings constraints is provided. A distinction is made between different types of problems. For each benchmark instance, the references of papers that use the instances, the number of vertices, the number of instances and the link to the website are provided.

Table 4 Benchmark instances
Full size table

5 Discussion and future research

The above review of the literature on vehicle routing problems with loading constraints shows that although classic VRPs have received a lot of research attention, these often do not reflect the real problems faced by distributors. An important flaw of classic VRPs is their ignorance of several real-life loading constraints. An overview of loading constraints, mainly based on the classification of Bortfeldt and Wäscher (2013), is provided. Recently, a number of papers have addressed the integration of loading constraints in vehicle routing problems. These papers may be placed in the following categories based on the type of routing problem and the loading characteristics: two-dimensional loading CVRP (2L-CVRP), three-dimensional loading CVRP (3L-CVRP), multi-pile VRP, multi-compartments VRP, pallet packing VRP (PPVRP), minimum multiple trip VRP (MMTVRP) with incompatible commodities, traveling salesman problem with pickups and deliveries (TSPPD) with LIFO/FIFO constraints, double TSP with pickups and deliveries with multiple stacks (DTSPMS) and Vehicle routing problem with pickups and deliveries (VRPPD) with additional loading constraints. The latter three categories consider pickup and delivery problems in which items may be picked up and delivered at customer places. For each category the relevant loading constraints that are incorporated into the models are described and the available formulations are discussed. Only a limited number of papers present a problem formulation. An explanation may be that including loading constraints in a routing problem usually makes the problem formulation much more complex. The addition of a three-dimensional loading constraint does not imply adding a single extra row to the formulation, but affects the formulation as a whole. Additionally, due to the complexity of the problem mostly heuristic methods are developed which do not necessarily require a problem formulation.

The complexity of the problem not only depends on the complexity of the routing and loading constraints separately, but is also influenced by the combination of the different constraints. For example, sequence-based loading becomes much more complex in a three-dimensional loading problem than in a one-dimensional problem. The type of transportation request (pickup and delivery of items, or only a single type of request) influences in return the complexity of the sequence-based loading constraint. From the literature survey it is observed that, in most models, the loading constraints are handled as a subproblem of the routing model (e.g., Gendreau et al. 2006; Doerner et al. 2007; Tarantilis et al. 2009; Bortfeldt 2012; Fuellerer et al. 2010; Ruan et al. 2013). First, solutions of the routing problem are computed, and afterwards a feasibility check of the loading constraints is performed. Since loading constraints are often complex, a considerable amount of time may be saved by only checking the best solutions of the routing model. There are some exceptions to this method of incorporating loading constraints in VRP models, such as the sequential approach of Moura and Oliveira (2009) in which the container loading and the vehicle routes are planned at the same time. Another example is the packing first–routing second heuristic of Bortfeldt and Homberger (2013), in which first a feasible packing scheme for each particular customer is computed after which the routes are constructed, followed by an optimization of the overall packing plan of all customers belonging to a single route.

As the combination of vehicle routing problems with loading constraints is a fairly recent domain of research, a number of opportunities for future research can be identified. An interesting path of research could incorporate weight distribution constraints into VRPs. In packing literature, an even weight distribution of the cargo inside the vehicle is often achieved by placing the center of gravity of the load as close as possible to the midpoint of the container. Closely related to balancing cargo weight inside the vehicle is balancing it also over the axles of the vehicle. Axle weight limits pose quite a challenge to transportation companies as they incur high fines in the event of non-compliance. Since weight distribution varies with every pickup or delivery, this should be monitored not just at the point of departure but throughout the journey. To our knowledge, weight distribution constraints as well as axle weight restrictions have only been modeled once in combination with a routing problem by, respectively, (Øvstebø et al. 2011) and (Pollaris et al. 2014).

Another line of future research could focus on pickup and delivery problems with loading constraints. Except for a single paper (Malapert et al. 2008), the current literature concerning PDPs only takes one dimension into account. Next, few solutions methods for PDPs with loading constraints and multiple vehicles have so far been developed. Future research could analyse PDPs with multiple vehicles and multiple dimensions. As for the multi-compartments VRP, one might focus on planning over multiple periods or over multiple trips in a single tour where contamination from load residuals may be considered. A compartment carrying a specific product might not be available after emptying for another product before cleaning. With respect to solution methods, it appears that few exact methods have been devised to solve VRPs with loading constraints. Hence, future research could focus on creating exact methods to solve VRPs with loading constraints to which heuristic solutions may be compared. A final observation is that other rich constraints are rarely incorporated into the current VRP models with loading constraints. Even time windows are not often included in the current models. Including time windows or other additional constraints such as a heterogeneous vehicle fleet, maximum route length and duration or drivers’ regulations in current VRP models with loading constraints would go some considerable way towards making these useful to real-world applications.