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

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