Читать книгу Optimization and Machine Learning - Patrick Siarry - Страница 23

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.