On the complexity of routing problems

Exact optimization methods generally cannot find the optimal solution of high-dimensional routing problems in reasonable time.

Thus, sulutions for combinatorial optimization problems (COPs) such as the traveling salesman problem (TSP) and the vehicle routing problem (VRP) typically cannot be determined for realistic instance sizes.

Combinatorial optimization problems (COPs)

Combinatorial optimization problems (COPs) are a class of optimization problems with discrete decision variables and a finite search space, although still too large for an exhaustive search to be a realistic option (Korte & Vygen, 2012). Many real-life problems (e.g., vehicle routing problem, scheduling problem, etc.) can be formulated as COPs.

The formal representation of a COP is as follows:

\[ \begin{align*} \text{Minimize} \; c(x) \\ \text{subject to:} \\g(x) \geq b \\ x \geq 0, x \in f \end{align*} \]

where the inequalities \(g(x) \geq b\) and \(x \geq 0\) are the constraints that specify a convex polytope over which the objective function \(c(x)\) is to be minimized, and \(f\) is the finite set of feasible solutions that satisfy the constraints.

A large part of COPs belong to the NP-Hard class of optimization problems, which require exponential time to be solved to optimality (Talbi, 2009).

Study case 1: Symmetric Traveling Salesman Problem (TSP)

For a symmetric TSP with \(n\) nodes, the number of possible solutions is given by:

\[ \frac{(n-1)!}{2}. \]

For example, for a node set \(N=\{0,1,2,3\}\), i.e., \(n=|N|=4\), \(\frac{3!}{2}= 6\) unique routes can be generated:

  • 1, 2, 3 = 3, 2, 1 \(\rightarrow\) (0, 1, 2, 3, 0)
  • 1, 3, 2 = 2, 3, 1 \(\rightarrow\) (0, 1, 3, 2, 0)
  • 2, 1, 3 = 3, 1, 2 \(\rightarrow\) (0, 2, 1, 3, 0)

Below, we plot the solution space of an example instance:

The best solutions:

Best solution: (0, 1, 5, 4, 2, 8, 3, 7, 6, 0)- (Cost:   3.37)

Study case 2: Vehicle Routing Problem (VRP)

In this example, we are going to explore the possible schedules of one of the most famous combinatorial optimiziation problems: the Vehicle Routing Problem (VRP).

Our goal is to answer:

In how many ways \(k\) distinguishable vehicles can visit \(n\) customers?

Assuming distinguishable vehicles, if \(k=3\) and \(n=4\), for example, the following routes are different:

  • ((0, 0), (0, 1, 0), (0, 2, 3, 4, 0)),
  • ((0, 0), (0, 2, 3, 4, 0), (0, 1, 0)),
  • ((0, 1, 0), (0, 2, 3, 4, 0), (0, 0)),
  • ((0, 1, 0), (0, 0), (0, 2, 3, 4, 0)),
  • ((0, 2, 3, 4, 0), (0, 0), (0, 1, 0)), and
  • ((0, 2, 3, 4, 0), (0, 1, 0), (0, 0)).
Note

Routes are formatted as a tuple: (route vehicle 1, route_vehicle 2, ..., route_vehicle k), where route vehicle k = (depot, customer 1, customer 2, ..., customer n_k, depot).

Step 1: Counting customer-vehicle assignments

First we are going to answer:

In how many ways can we assign \(n\) customers to \(k\) vehicles?

Let us assume customers 1, 2, 3, and 4 (i.e., \(n=4\)) must picked picked up by vehicles 1, 2, and 3 (i.e., \(k=3\)):

Vehicle 1 Vehicle 2 Vehicle 3 Way Representation
🧍 🧍 🧍 🧍 Customers 1,2,3, and 4 picked up by Vehicle 1 ((0,1,2,3,4,0),(0,0),(0,0))
🧍 🧍 🧍 🧍 Customers 1,2, and 3 picked up by Vehicle 1 and customer 4 picked up by Vehicle 2 ((0,1,2,3,0),(0,4,0),(0,0))
🧍 🧍 🧍 🧍 Customers 1 and 2 picked up by vehicle 1 and customers 3 and 4 picked up by Vehicle 2 ((0,1,2,0),(0,3,4,0),(0,0))

Using the stars and bars method, the solutions presented above could be represented as:

  • 🧍🧍🧍🧍┃┃
  • 🧍🧍🧍┃🧍┃
  • 🧍🧍┃🧍🧍┃

The bars “┃” mark the separation between customers being serviced by different vehicles. Notice that one fewer bar is used since there is no need to service more customers after the last user.

The number of ways to distribute customers to vehicles correspond to the number of ways symbols “🧍🧍🧍🧍┃┃” can be combined. With 7 symbols, we must choose 2 of them to be customer separators. Thus:

There are \({6 \choose 2} = 15\) ways to distribute \(4\) customers to \(3\) vehicles (or, alternatively, 15 ways of choosing 2 symbols among 6 to be separators).

The ways are as follows:

k=4 vehicles can pick up n=4 customers in 15 different ways.

# Ways (vehicles are separated by '|'):
  1  ┃┃🧍🧍🧍🧍
  2  ┃🧍┃🧍🧍🧍
  3  ┃🧍🧍┃🧍🧍
  4  ┃🧍🧍🧍┃🧍
  5  ┃🧍🧍🧍🧍┃
  6  🧍┃┃🧍🧍🧍
  7  🧍┃🧍┃🧍🧍
  8  🧍┃🧍🧍┃🧍
  9  🧍┃🧍🧍🧍┃
 10  🧍🧍┃┃🧍🧍
 11  🧍🧍┃🧍┃🧍
 12  🧍🧍┃🧍🧍┃
 13  🧍🧍🧍┃┃🧍
 14  🧍🧍🧍┃🧍┃
 15  🧍🧍🧍🧍┃┃

The number of ways is given by the formula:

\[{n + k - 1 \choose k - 1} = \frac{(n + k - 1)!}{(k-1)!(n+k-1-(k-1)!} = \frac{(n + k - 1)!}{(k-1)!n!},\]

which can be applied using the comb function:

k=3 vehicles can pick up n=4 customers in 15 different ways.

Step 2: Counting vehicle-route schedules

Knowing how many ways customers can be assigned to vehicles, we can now calculate the total number of possible routes for each assignment, that is:

Given a customer-vehicle assignment, in how many ways each vehicle can pick up its customers?

Similarly to the TSP (a one-vehicle VRP) \(n\) customers can be visited in \(n!\) ways. Each possible customer permutation can be further divided into \({n + k - 1 \choose k - 1}\) ways using the ‘┃’ separators.

For example, the sequence of visits (1,2,3,4) can be split among 3 vehicles as follows:

  1  1234┃┃
  2  123┃4┃
  3  123┃┃4
  4  12┃34┃
  5  12┃3┃4
  6  12┃┃34
  7  1┃234┃
  8  1┃23┃4
  9  1┃2┃34
 10  1┃┃234
 11  ┃1234┃
 12  ┃123┃4
 13  ┃12┃34
 14  ┃1┃234
 15  ┃┃1234

Total size of solution space

Through steps 1 and 2, we can calculate the total size of the solution space as

\[\text{n. of customer permutations} \times \text{n. of vehicle-customer assignments},\]

which is given by the formula:

\[n!{n + k - 1 \choose k - 1} = n! \frac{(n + k - 1)!}{(k-1)!n!} = \frac{(n + k - 1)!}{(k-1)!}.\]

For example:

\(k=3\) vehicles can pick up \(n=4\) customers in \(4!{6 \choose 2} = 24 \times 15 = 360\) ways.

Below, we show how the size of the solution space explodes for increasing combinations of number of customers \(n\) and number of vehicles \(k\):

N. of vehicle-customer schedules
N. of customers (n) N. of vehicles (k)
5 3 2,520
5 15,120
10 240,240
25 3 5,444,434,725,209,175,970,119,942,144
5 368,406,749,739,154,269,232,085,073,920
10 813,582,448,852,524,689,603,239,037,894,656
50 3 4.03E+67
5 9.62E+69
10 3.82E+74
100 3 4.81E+161
5 4.29E+164
10 3.98E+170

Typically, exact algorithms can solve to optimality relatively small instances involving around 100 customers.

For \(n=100\) customers and \(k=3\) vehicles there are about \(4.8\times 10^{161}\) possible schedules. For the sake of comparison, there are between \(10^{78}\) and \(10^{82}\) atoms in the observable universe [↗]!

Plotting the solution space

In the following we use an exhaustive search to find all possible solutions for a random VRP instance with fleet size n_vehicles and number of customers n_customers.

Warning

Large inputs will lead to extensive computational times!

Below, we plot the best solutions (i.e., those with min. cost). Vehicles are represented by different colors and the arrows show the visiting order. Notice that because we assume vehicles are distinguishable, a single schedule is considered several times but with different vehicle assigments.

What if vehicles are indistinguishable?

If vehicles are indistinguishable, a common practice in 2-index VRP formulations, we have fewer solutions:

Further analysis

  • How the solution space changes if time window and capacity constraints are considered (i.e., CVRP, VRPTW)?
  • How the solution space changes if we consider customer pickups and deliveries (i.e., VRPPD)?

References