Patrick Siarry - Optimization and Machine Learning

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.

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.

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.

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.

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.

The 3L-CVRP integrates two of the most studied optimization problems: the CVRP and the 3D-BPP. The problem aims to minimize total traveling cost while respecting the three-dimensionality constraint of customer demands. The 3L-CVRP has many transportation applications (Ruan et al . 2013), such as the distribution of kitchen components, mechanical components, household appliances, soft drinks and staple goods. Table 1.2presents a comparative study of the existing literature for the 3L-CVRP, including solution methods, variants and constraints.

Gendreau et al . (2006) study the first work reporting a combination of CVRP and 3D loading; they proposed a TS algorithm for both the routing and loading problem. They presented sequence-based loading, stacking and vertical stability constraints and a fixed vertical orientation of the items in the vehicles. The work is motivated by a real furniture distribution decision in Italy. Aprile et al . (2007) developed an SA to solve the 3L-CVRP.

Tarantilis et al . (2009) combine the TS and guided LS (GLS) to solve the 3L-CVRP black box feasibility. Fuellerer et al . (2010) addressed the 3L-CVRP with large-size instances and to solve the problem they used the ACO for the routing, and Ren et al . (2011) proposed a branch-and-bound for the routing sub-problem and a container loading algorithm to verify the packing of an item into the corresponding vehicle. Massen et al . (2012) presented a column generation-based heuristic method for vehicle routing problems with black box feasibility (VRPBB).

Bortfeldt (2012) proposes a TS and tree search algorithm (TRSA) where the first one is for the routing problem and the second one for the packing problem. Zhu et al . (2012) studied the 3L-CVRP using a TS algorithm.

Wisniewski et al . (2011) describe a TS and a first-improvement LS for the routing problem. On the other hand, the loading is efficiently done by a randomized bottom-left based algorithm. Miao et al . (2012) solve the 3L-CVRP problem using GA and TS (GATS) for the routing and packing sub-problem, respectively.

Ruan et al . (2013) propose a bee mating optimization (HBMO) for the routing problem and six loading heuristics (Back-Left-Low, Left-Back-Low, Max-Touching-Area-W, Max-Touching-Area-No-Walls-W, Max-Touching Area-L and Max-Touching-No-Walls-L algorithms) for 3D loading.

Ceschia et al . (2013) address the 3L-CVRP with sequence-based loading and a heterogeneous vehicle fleet. They proposed an LS approach that combines SA and large neighborhood search (LNS) to solve the problem in one stage. 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.