Optimization and Machine Learning. Patrick Siarry
Читать онлайн книгу.
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.
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.
Tao and Wang (2015) propose a simple TS algorithm for the routing problem and a least waste algorithm for the packing problem.
Junqueira et al. (2013) propose an ILP exact method to solve small-scale instances of the 3L-CVRP (number of customers <15). 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 sites to be solved.
Hokima et al. (2016) propose two branch-and-cut algorithms for the 3L-CVRP variant with only an LIFO constraint but no fragility and stability constraints. In addition, the authors propose an iterated local search (ILS) method for the routing sub-problem.
Vega et al. (2020) propose a hybrid heuristic that combines a greedy randomized adaptive search procedure (GRASP) heuristic and a Clarke and Wright savings (CWS) algorithm.
1.3.2. Problem description
The 3L-CVRP is defined as follows (Gendreau et al. 2006). Let G = (V, E) be a complete graph, where V = {0, 1, …, n} is a set of n + 1 vertices and E the complete set of edges connecting each vertex pair.
Vertex 0 corresponds to the depot, while vertices {1, …, n} are the n customers to be served. Each edge is denoted by (i, j) and has an associated routing cost cij where (i, j = 0, …, n).
It is also given a fleet of v homogeneous vehicles, each one is characterized by four variants D, W, H and L presented the capacity, the width W, the height H and the length L, respectively. Each vehicle has an opening on the rear for the loading/unloading operations. We suppose the opening to be as large as the vehicle (W* H).
The demand of customer i consists of a set of mi items whose total weight is di (i = 1, …, n). Each item k of customer i is denoted by Iik and is a 3D cuboid, having width wik, height hik and length lik (i = 1, …, n, k = 1, …, mi ).
The total demand asked by a customer i is denoted by
The 3L-CVRP calls for finding a set of at most v routes where minimizing the total travel cost with ensuring that the constraint 3D of each item is respected. A 3D loading is feasible if it does not exceed the vehicle weight capacity D and if there exists a placement of the items in the vehicle volume that satisfies both the classical 3D-BPP constraints (items do not overlap and are completely contained by the bins/vehicles) and a series of operational constraints. Figure 1.2 illustrates an example of 3L-CVRP solution.
Figure 1.2. An example of a 3L-CVRP solution
1.3.3. 3L-CVRP variants
The most studied 3L-CVRP variants are 3L-CVRP with time windows, 3L-CVRP with backhauls and 3L-CVRP with pickup and delivery. The 3L-CVRP is integrated with 3D-BPP constraints such as last in-first out (LIFO); rotation of items; vertical stability; fragility and weight limit.
1.3.3.1. 3L-CVRP with time windows
Moura (2008) presented three objectives organized as follows, to minimize the number of vehicles and the total distance and to maximize the volume used, respectively. Moura and Oliveira (2009) developed a sequential approach (using LS and GRASP heuristics) and a hierarchical approach (using constructive; post constructive; and local search phase) 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 sub-problem of the routing problem.
Bortfeldt and Homberger (2013) described two steps: the first one is to pack items into vehicles with respect to the capacity of each vehicle and the second one consists of designing a route sequence.
Zhang et al. (2017) proposed a hybrid approach by combining TS and the artificial bee colony (ABC) algorithm to solve a VRP with pallet loading and time window constraints.
The problem considers the LIFO constraint; fragility and orientation are not considered. Moura et al. (2019) presented a MILP model. The model allows all boxes to rotate in 3D and they may also have fixed or limited orientation. The boxes could be loaded in multiple layers formed by different sized and shaped boxes.
Vega et al. (2019) studied VRP with 3D loading constraints and additional constraints such as time windows and capacity constraints. They proposed a nonlinear mixed integer program (NLMIP). Pace et al. (2015) considered a constraint of a heterogeneous fleet of vehicles for the 3L-CVRPTW. Iterated local search (ILS) and simulated annealing (SA) are proposed to solve the problem.
1.3.3.2.