Optimization and Machine Learning. Patrick Siarry

Чтение книги онлайн.

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 c_{i 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 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.2 presents a comparative study of the existing literature for the 3L-CVRP, including solution methods, variants and constraints.

      1.3.1. Solution methods

      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.