et al. (2013) study the heterogeneous fleet vehicle routing problem (2L-HFVRP). They propose six packing heuristics to check the feasibility of loading (presented in Table 1.1) and simulated annealing with a heuristic local search (SA-HLS) for the routing problem.
Zacharidis et al. (2013) present a static move description algorithm.
Dominguez et al. (2016) study the 2L-CVRP with a heterogeneous fleet using the multi-start biased randomized algorithm and the touching perimeter algorithm for the packing problem.
Wei et al. (2015) propose a variable neighborhood search (VNS) approach for solving the 2L-CVRP and adapt the skyline heuristic to examine loading constraints.
Wei et al. (2017) propose the simulated annealing (SA) algorithm to solve 2 |SO| L, 2 |SR| L, 2 |UO| L and 2 |UR| L versions of the 2L-CVRP.
Sbai et al. (2017) propose a new heuristic based on an adaptive genetic algorithm (GA) for solving the 2L-CVRP, considering only the unrestricted loading case.
Sabar et al. (2020) present a heterogeneous fleet 2L-CVRP, denoted as 2L-HFVRP. They propose a two-stage method: the routing stage and the packing stage. The problem is solved using MA for the routing stage and five heuristics (presented in Table 1.1) for the packing stage.
Coté et al. (2020) introduce a stochastic variant of the 2L-CVRP, known as the S2L-CVRP, where the size of some items is uncertain at the time the vehicle routes are planned. They use a lower bounding functional, called L-cuts, to solve the problem.
Figure 1.1. An example of a 2L-CVRP solution
1.2.2. Problem description
2L-CVRP is defined (Gendreau et al. 2008) on a complete undirected graph G = (V, E), where V = {0, …, n} is the vertex set and E = { (i, j )| i, j ϵV, i ≠ j} is the edge set characterized by a cost ci j. A set of v homogeneous vehicles are located at the depot, each one is identified by D, W and H representing the weight capacity, the width and the height, respectively. Let A = W*H denote the loading area. The demand of client i {1, …, n} consists of mi items of total weight di: item Iil {l=1, …, mi} has width wil and height hil. Let ai =
1.2.3. The 2L-CVRP variants
In the literature, several variants of the 2L-VRP have been defined, such as the 2L-CVRP with time constraints, the 2L-CVRP with backhaul constraints and the 2L-CVRP with pickup and delivery constraints. Some constraints are related to the loading configuration: (1) oriented loading, where items cannot be rotated; (2) sequential loading, where items should be loaded in reverse according to customer visits; (3) unrestricted loading, allowing items to be reloaded during the routing process; and (4) non-oriented or rotated loading, allowing items to be rotated 90° inside the vehicle. Four versions of the 2L-CVRP (2|SO|L, 2|SR|L, 2|UO|L and 2|UR|L) are designed.
1.2.3.1. The 2L-CVRP with time constraints
For the 2L-CVRP with time windows (2L-CVRPTW), a time window is assigned to each customer during which the customer demand is met. Attanasio et al. (2007) consider a variant of the 2L-CVRP where each shipment must take place within a multi-day time window (TW). They propose a cutting plane framework in which a simplified integer linear program (ILP) is solved. Items are allowed to be rotated and sequence-based loading is assumed.
Khebbache-Hadji et al. (2013) consider the weight limit of the vehicles as an additional constraint. The authors propose a memetic algorithm (MA) for both the routing and packing problems. Sbai et al. (2017) use a new heuristic based on an adaptive GA to solve the 2L-CVRP and designed an adaptive least wasted first (ALWF) heuristic to check the feasibility of the loading problem. Sbai et al. (2017) present an adaptive GA for solving the 2L-CVRP with time windows; the results improved the quality of the proposed solutions. Guimarans et al. (2018) propose a hybrid simheuristic algorithm to solve a version of the 2L-CVRP with stochastic travel times.
Song et al. (2019) consider the multi-objective VRP with loading and time window constraints, presented as a mixed integer linear programming (MILP) model. A generalized variable neighborhood search (GVNS) algorithm is designed to solve the MILP.
1.2.3.2. The 2L-CVRP with backhaul
In 2L-CVRP with backhaul (2L-CVRPB), a vehicle can deliver (linehaul), then collect goods from customers (backhaul) and bring back items to the depot. All linehaul must be done before the backhaul. Once customer demands are designed as a set of 2D rectangular weighted items, the problem is considered as a 2L-VRPB.
Pinto et al. (2015) studied the VRP with mixed backhaul using an insert heuristic and a bottom-left heuristic (BLH) for the packing aspect. Also, Dominguez et al. (2016) proposed a hybrid algorithm: the biased-randomized heuristic and a large neighborhood search metaheuristic framework to solve the 2L-VRPB.
In the same case, Zachariadis et al. (2017) described a local search (LS) approach for solving the 2L-VRPSDP and the 2L-VRPCB. Pinto et al. (2017) proposed a VNS algorithm for solving the 2L-VRPB.
1.2.3.3. 2L-CVRP with pickup and delivery constraints
In the 2L-CVRP with pickup and delivery constraints, delivery items are unloaded and additional pickup items are loaded onto the vehicle. Likewise, the VRP with pickup and delivery (PD) and 2D loading constraints is only researched in two works. The first one is proposed by Malapert et al. (2008) for solving the 2L-VRPPD. The second one is introduced by Zachariadis et al. (2016), the VRP with simultaneous pickup and delivery (2L-SPD) with LIFO constraints using a local search algorithm.
1.2.4. Computational analysis
Gendreau et al. (2008) and Iori et al. (2007) generated the 180 2L-CVRP instances by extending the 36 well-known classical CVRP instances introduced by Toth and Vigo (2002). In particular, each customer is associated with a set of 2D items. In addition, the loading surface (L, W) is fixed as (40, 20) for all instances, and the available vehicle number is specified. According to the characteristics of the items demanded, five classes of the item demand characteristics introduced by Iori et al. (2007) are generated and available at http://www.or.deis.unibo.it/research.html.
For Class 1, each customer is assigned to one item of unit length and width so that packing is always feasible. Therefore, Class 1 can be regarded as a pure CVRP which is used to evaluate the performance of proposed algorithms, in terms of the routing aspect.
For Classes 2–5, customer demand mi is included at three given intervals. The unrestricted and sequential versions share the same test data, but sequential 2L-CVRP should account for additional unloading constraints when examining the feasibility of routes.
1.3. The capacitated vehicle routing problem with three-dimensional loading constraints
The