Optimization and Machine Learning. Patrick Siarry

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.

      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.

      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

.

      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.

      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.


Скачать книгу