Capacitated Vehicle Routing Problem (CVRP)¶

In this tutorial, we consider the capacitated vehicle routing problem (CVRP), a type of vehicle routing problem (VRP).

Specific applications include

• Delivery scheduling in the postal and other transportation industries
• Scheduling in garbage collection and street cleaning

A vehicle routing problem is a problem of determining efficient delivery routes from a depot to multiple cities. More specifically, the problem determines the allocation of delivery vehicles and cities, and the order in which the cities are visited, to minimize the total distance traveled by the delivery vehicles, the total cost, and so on. The routing problem can be interpreted as a generalization of the traveling salesperson problem.

The capacitated vehicle routing problem addressed in this tutorial is the above routing problem with an additional load constraint on each vehicle. In other words, each delivery vehicle must satisfy the load constraints while making deliveries --- they cannot carry loads heavier than their payload. This problem can be interpreted as a "traveling salesperson problem + knapsack problem".

Here, we consider the case where there is only one delivery location (depot), and the demand in each city and the vehicle capacity take only integer values.

Formulation¶

First, define the constants and variables needed for the formulation.

Constants¶

• $N$: Number of cities
• $L$: Maximum number of cities that can be visited without exceeding the carrying capacity + 2 (origin + destination)
• $K$: Number of vehicles
• $Q$: Maximum payload of each vehicle, integer
• $W_i$: Integer representing the weight of the load to be delivered to city $i$.
• $D_{i\to j}$: Real number representing the distance from city $i$ to city $j$ (city $0$ = depot) ($i, j \in \{0,1,\dots,N \}$)

Variables¶

• $x_{i,j,k} \in \{0, 1\} \quad (i \in \{1, \dots , L\}, j \in \{0, \dots, N\}, k \in \{1, \dots, K\})$
  Binary variable indicating whether vehicle $k$ chooses city $j$ as $i$th city to visit ($x_{i,j,k}=1\Leftrightarrow$ vehicle $k$ chooses city $j$ as $i$-th city to visit)

  We then consider the constraints that the variables must satisfy.

Constraints¶

We need the following four constraints.

1. All vehicles start from and end at the depot (city $0$)
2. Vehicle $k$ visits only one $i$-th location
3. City $j$ (excluding the depot) is visited exactly once by any vehicle
4. The total weight of the loads carried by vehicle $k$ is less than or equal to $Q$

These conditions can be expressed as follows:

1. All vehicles start from and end at the depot (city $0$)
   $$ x_{1,j,k} = \begin{cases} 1 \quad (j = 0) \\ 0 \quad (j \neq 0) \end{cases} \\ $$ $$ x_{L,j,k} = \begin{cases} 1 \quad (j = 0) \\ 0 \quad (j \neq 0) \end{cases} $$

2. Vehicle $k$ visits only one $i$-th location
   $$ \sum_{j=0}^N x_{i,j,k} = 1 \quad (i \in \{1, \dots, L\}, k \in \{1, \dots, K\}) $$

3. City $j$ (excluding the depot) is visited exactly once by any vehicle
   $$ \sum_{i=1}^L \sum_{k=1}^K x_{i,j,k}=1 \quad (j \in \{1, \dots, N\}) $$

4. The total weight of the loads carried by the vehicle $k$ is less than or equal to $Q$
   $$ \sum_{i=1}^L \sum_{j=1}^N w_j x_{i,j,k} \leq Q \quad (k \in \{1, \dots, K\}) $$

Objective Function¶

In this CVRP, we minimize the total distance traveled by the vehicle. The total distance traveled by a vehicle can be expressed in the following equation.

$$ \sum_{k=1}^K\sum_{i=1}^L\sum_{j_1=0}^N\sum_{j_2=0}^N D_{j_1\to j_2}x_{i,j_1,k}x_{i+1,j_2,k} $$

Explanation of Constraint Expressions¶

This section provides a more intuitive explanation using concrete examples.

The following is an example of a variable assignment that satisfies the constraint conditions, summarized in a table for each vehicle. The horizontal axis represents the alphabetical name of the city (the depot is the starting point), and the vertical axis represents the order of the cities to be visited (0 means departing from the depot, 9 means arriving at the depot at the end). If a square in the table is $1$, it means that the vehicle will visit the city.

• Vehicle 1 ($k=1$)

$x_{i,j,1}$	depot	A	B	C	D	E	F	G	H	I
0 (start)	1	0	0	0	0	0	0	0	0	0
1	0	1	0	0	0	0	0	0	0	0
2	0	0	0	1	0	0	0	0	0	0
3	0	0	0	0	0	1	0	0	0	0
4	0	0	0	0	0	0	1	0	0	0
5	1	0	0	0	0	0	0	0	0	0
6	1	0	0	0	0	0	0	0	0	0
7	1	0	0	0	0	0	0	0	0	0
8	1	0	0	0	0	0	0	0	0	0
9 (end)	1	0	0	0	0	0	0	0	0	0

• Vehicle 2 ($k=2$)

$x_{i,j,2}$	depot	A	B	C	D	E	F	G	H	I
0 (start)	1	0	0	0	0	0	0	0	0	0
1	1	0	0	0	0	0	0	0	0	0
2	1	0	0	0	0	0	0	0	0	0
3	1	0	0	0	0	0	0	0	0	0
4	0	0	1	0	0	0	0	0	0	0
5	0	0	0	0	0	0	0	1	0	0
6	0	0	0	0	0	0	0	0	0	1
7	1	0	0	0	0	0	0	0	0	0
8	1	0	0	0	0	0	0	0	0	0
9 (end)	1	0	0	0	0	0	0	0	0	0

• Vehicle 3 ($k=3$)

$x_{i,j,3}$	depot	A	B	C	D	E	F	G	H	I
0 (start)	1	0	0	0	0	0	0	0	0	0
1	0	0	0	0	1	0	0	0	0	0
2	0	0	0	0	0	0	0	0	1	0
3	1	0	0	0	0	0	0	0	0	0
4	1	0	0	0	0	0	0	0	0	0
5	1	0	0	0	0	0	0	0	0	0
6	1	0	0	0	0	0	0	0	0	0
7	1	0	0	0	0	0	0	0	0	0
8	1	0	0	0	0	0	0	0	0	0
9 (end)	1	0	0	0	0	0	0	0	0	0

The above-mentioned constraint "2: Vehicle $k$ visits only one $i$th location" corresponds to a single "$1$" appearing in each row (horizontal line) of the above decision variable table and can be expressed by the following equation:

$$ \sum_{j=0}^N x_{i,j,k} = 1 \quad (i \in \{1, \dots, L\}, k \in \{1, \dots, K\}) $$

Also, the constraint "3: City $j$ (excluding the depot) is visited exactly once by any vehicle" corresponds to a single "$1$" appearing in each column (vertical line) except the depot for all vehicles combined, and can be expressed as follows:

$$ \sum_{i=1}^L \sum_{k=1}^K x_{i,j,k}=1 \quad (j \in \{1, \dots, N\}) $$

While these constraints ensure that each city is visited exactly once by any vehicle, the formulation allows that the delivery depot to be visited any number of times. Therefore, post-processing is performed so that each vehicle visits a depot only twice, once at the start of the delivery and once at the end of the delivery. Specifically, if $1$ appears in the "depot" column except for rows 0 and 9 in the table, it is ignored (considered as $0$). The travel distance for the route obtained after this post-processing is equal to or shorter than that before the post-processing, which can be proven by using the triangular inequality.

Implementation¶

We will now implement the above formulation and constraints using Fixstars Amplify.

Problem definition and visualization¶

First, let us define the variables needed to optimize the present problem. The number of vehicles is set to 2, the number of cities to 10, and the transportation demand for each city is randomly generated. Also, adjust capacity to be a solvable condition. The dimension is [number of cities + number of depots = number of cities + 1].

Next, the coordinates of each city are randomly generated. Generate $D_{i \to j}$ by computing the coordinate distances between all cities $i,j$.

Create a list of colors to be used when plotting the problem.

Define the function plot_solution to plot the coordinates of the cities.

The plot_solution function displays the defined problem. The car-shaped pins represent the location of the depot (start and end points), and the human-shaped pins represent the points to be visited.

Upper bound of cities to visit¶

To reduce the size of the decision variable, an upper bound on the number of cities that can be visited by a single car is estimated in advance.

The following upperbound_of_tour function estimates the maximum number of cities that can be visited without exceeding the load capacity by the following steps:

1. Selecting the city with the lowest delivery demand (weight) among the cities not yet selected, and subtracting that city's demand from the maximum load capacity
2. Repeating step 1 until the maximum load capacity becomes negative, and the number of iterations is the upper limit of the number of cities to visit

Constructing QUBO formulation¶

Next, we define the necessary decision variables, using Amplify's BinarySymbolGenerator. For a total of $N+1$ cities and depots, we will visit at most $L$ cities with $K$ vehicles, so we define the QUBO variable as a three-dimensional array of $L \times (N+1) \times K$ as follows (see the definitions of constants in the Formulation section).

As mentioned in the section, Formulation, the constraints are:

1. All vehicles start from and end at the depot (city $0$)
2. Vehicle $k$ visits only one $i$-th location
3. City $j$ (excluding the depot) is visited exactly once by any vehicle
4. The total weight of the loads carried by vehicle $k$ is less than or equal to $Q$

In other words,

$$ \begin{align*} (1) \quad & x_{1,j,k} = \begin{cases} 1 \quad (j = 0) \\ 0 \quad (j \neq 0) \end{cases} \\ & x_{L,j,k} = \begin{cases} 1 \quad (j = 0) \\ 0 \quad (j \neq 0) \end{cases} \\ (2)\quad & \sum_{j=0}^N x_{i,j,k} = 1 \quad (i \in \{1, \dots, L\}, k \in \{1, \dots, K\})\\ (3)\quad & \sum_{i=1}^L \sum_{k=1}^K x_{i,j,k}=1 \quad (j \in \{1, \dots, N\})\\ (4)\quad & \sum_{i=1}^L \sum_{j=1}^N w_j x_{i,j,k} \leq Q \quad (k \in \{1, \dots, K\})\\ \end{align*}. $$

Note that $x_{i,j,k}$ corresponds to vehicle $k$ visits city $j$ as $i$-th location.

We will use the less_equal function to express inequality constraints and the equal_to function to express equality constraints. Also, the coefficient that determines the weight of the constraint term is implemented as $\max (d_{ij})$. This at least avoids the situation where the objective function is favored over the constraint term.

Constraint (1): all vehicles start from and end at the depot (city 0)¶

The constraint equation is expressed as follows.

$$ \begin{align*} x_{1,j,k} = \begin{cases} 1 \quad (j = 0) \\ 0 \quad (j \neq 0) \end{cases} \\ x_{L,j,k} = \begin{cases} 1 \quad (j = 0) \\ 0 \quad (j \neq 0) \end{cases} \end{align*} $$

We achieve this constraint by prefixing. Prefixing allows us to reduce the number of variables to be solved. Create a function that directly assigns values as follows.

To prefix the values of the variables, do x[i][j][k] = 1 or x[i][j][k] = 0. The assignment operation to the decision variables must be performed before defining the objective functions or constraint equations.

Constraint (2): vehicle $k$ visits only one $i$-th location¶

This constraint is already expressed by the following equation in the Formulation section.

$$ \sum_{j=0}^N x_{i,j,k} = 1 \quad (i \in \{1, \dots, L\}, k \in \{1, \dots, K\}) $$

This constraint equation is implemented as follows.

Constraint (3): city $j$ (excluding the depot) is visited exactly once by any vehicle¶

As already mentioned in the Formulation section, this constraint is expressed as:

$$ \sum_{i=1}^L \sum_{k=1}^K x_{i,j,k}=1 \quad (j \in \{1, \dots, N\}).$$

This equation is implemented as follows:

Constraint (4): the total weight of the loads carried by vehicle $k$ is less than or equal to $Q$¶

This constraint is expressed by the following equation.

$$ \sum_{i=1}^L \sum_{j=1}^N w_j x_{i,j,k} \leq Q \quad (k \in \{1, \dots, K\}) $$

This constraint expression can be implemented using less_equal. Also, although not necessary in the present problem setup, we will specify InequalityFormulation.RelaxationQuadra as the method argument to less_equal. While this method is not a strict penalty function for this constraint, it keeps from generating many auxiliary variables internally, can handle real number coefficients, and thus increases solvability under large problem size conditions.

See https://amplify.fixstars.com/en/docs/constraint.html#constraint-inequality-relaxation for further information.

Objective function¶

The objective this time is to minimize the total distance traveled by the vehicles, and the objective function may be written as follows:

$$ \sum_{k=1}^K\sum_{i=1}^L\sum_{j_1=0}^N\sum_{j_2=0}^N D_{j_1\to j_2}x_{i,j_1,k}x_{i+1,j_2,k} $$

The einsum function is used to compute the objective function. More information about the einsum function can be found here.

Based on the pre-assignment-based constraint, the three constraint equations, and the objective function implemented so far, we can now construct a QUBO model for CVRP as follows. Here, we set the weight for the constraint equations as np.max(distance_matrix).

Setting up Amplify client¶

Let us use the Amplify Annealing Engine (AE) client.

Then we will instantiate the Solver class with the client we just created, and we will execute the solution based on the QUBO model.

Post-processing and solution visualization¶

The next step is to post-process and visualize the results.

In the following we define the function onehot2_sequence to format the obtained solution and the function process_sequence to perform post-processing as described above. The onehot2_sequence function creates a numbered list in visit order from the one-hot binary vector returned by Solver as follows.

Note that the following type hints are compatible with Python 3.9 or later. If you are using an older environment (Python 3.8), such as in a local environment, run from __future__ import annotations additionally.

Create the process_sequence function, which will return the list created by the onehot2_sequence function with the extra visits to the depot removed as described in described. Using the triangular inequality, we can prove that the distance traveled after post-processing is less than or equal to the distance traveled before post-processing.

Now let's extract and visualize the result.

We pass the solution x_values to the decode method of the decision variable array x and assign the result to the variable array.

Then, post-process the result using onehot2_sequence and process_sequence that we defined earlier.

The plot_solution function, defined earlier in the Implementation section, visualizes the post-processed solution. The optimized route that each vehicle should take is displayed on the map.