Constructive Heuristics for the Vehicle Routing Problem

Deliver your goods to your customers like a pro

Motivation

Imagine that you work in a company that also has three truck drivers to deliver products to customers. The truck drivers are doing their best to cope with the increasing demand, but now they are turning to you to optimize their route. Each of the three needs a list of customers to visit, including the order. They all start their journey from the same depot, and they want to visit each customer only once. At the end of the day, everyone has to return to the depot again to load their trucks for the next day.

This problem is a simple case of the vehicle routing problem (VRP), a problem that is related to the traveling salesman problem as discussed here:

But while you only have a single “truck” in the TSP, you can have several ones in the VRP.

Some facts

The vehicle routing problem is an NP-complete problem, meaning that there is probably no polynomial time algorithm to solve it. This follows directly from the fact that it is a generalization of the traveling salesman problem. And if the TSP is NP-hard already, so is the VRP.

The easiest algorithm would be brute-force, i.e., we try all different possible assignments to the drivers as well as orders in which each of them can visit their customers. But how many possibilities are there? For the TSP we got n!, and that is what we should retrieve from our general formula with k drivers for k = 1.

Here is a short version of the math: if you assign n₁ to driver 1, n₂ to driver 2, …, nₖ to driver k, then there are n! permutations, just as in the TSP case. But how many ways are there to assign the nᵢ customers to driver i for all i? It turns out that there are C(n-1, k-1) ways, where C is the binomial coefficient — meaning that we have C(n-1, k-1)·n! permutations we have to try, which is O(nᵏ⁻¹·n!). This is valid if each driver should get at least 1 customer to serve, so there are no empty tours. And for k = 1 we get n! again since C(n, 0) = 1.

Let us write some heuristics that are faster than this!

Constructive Heuristics

Since the run time of a naive brute-force algorithm is too high, we want to settle with algorithms that might not be optimal but are much faster. So, let us create a map with some locations to visit first.

import random
import matplotlib.pyplot as plt

plt.style.use("fivethirtyeight")
random.seed(123)

cities = [(0.5, 0.5)] + [(random.random(), random.random()) for _ in range(30)]

plt.scatter(
    [city[0] for city in cities],
    [city[1] for city in cities],
)
plt.axis("off")

I used the same data in my TSP article, here I just added the starting depot at position (0.5, 0.5).

Since you need the distances between the cities to do this comfortably, let us pre-compute them.

import math

distance_matrix = [
    [
        math.sqrt((start_city[0] - end_city[0])**2 + (start_city[1] - end_city[1])**2)
        for end_city in cities
    ]
    for start_city in cities
]

Nearest city heuristic

Just as in my TSP article, a simple solution is to always move to the city closest to where some driver is now. At the beginning, each driver is at the depot. We find the closest city to this one and assign it to driver 1 as their first destination. In the second iteration, we have to find the city that is closest to either driver 1 or the depot. If it is closer to the depot than driver 1, assign it to driver 2 as their first destination. If it is closer to the current location of driver 1, then they have to visit this city as well since it is close anyway.

So, in each iteration, you have to check all the cities and append it to the tour of driver i with the closest last city so far. If the three drivers have the tours [[0, 1, 2], [0, 3], [0]], and we want to insert city 4, we append it to driver 1’s tour (after the 2), to driver 2’s tour (after the 3) and driver 3’s tour (after the 0) and see which distance is the shortest: 2–4, 3–4, or 0–4.

You basically start with tours for each driver that only contain the depot and successively make them longer.

You can implement this idea like this:

def nearest_city(distance_matrix, depot, n_vehicles):
    unvisited_cities = set(range(len(distance_matrix))) - {depot}
    tours = [[depot] for vehicle in range(n_vehicles)]
    lengths = [0 for vehicle in range(n_vehicles)]

    while unvisited_cities:  # O(n)
        min_distance, closest_city, best_vehicle = min(
            (
                (distance_matrix[tours[vehicle][-1]][city], city, vehicle)
                for city in unvisited_cities
                for vehicle in range(n_vehicles)
            ),
            key=lambda x: x[0],
        )  # O(kn)
        tours[best_vehicle].append(closest_city)
        lengths[best_vehicle] += min_distance
        unvisited_cities.remove(closest_city)

    return [
        {"tour": tours[vehicle] + [depot], "length": lengths[vehicle] + distance_matrix[tours[vehicle][-1]][depot]}
        for vehicle in range(n_vehicles)
    ]

Let us plot the result!

def plot(result, cities, colors="rgbcmyk"):
    plt.scatter(
        [city[0] for city in cities],
        [city[1] for city in cities],
    )
    
    total_length = 0
    for vehicle in range(len(result)):
        plt.plot(
            [cities[result[vehicle]["tour"][i]][0] for i in range(len(result[vehicle]["tour"]))],
            [cities[result[vehicle]["tour"][i]][1] for i in range(len(result[vehicle]["tour"]))],
            c=colors[vehicle], linewidth=1, zorder=-1
        )
        total_length += result[vehicle]["length"]

    plt.title(f"Length = {total_length:.2f}")

    plt.axis("off")


result = nearest_city(distance_matrix, depot=0, n_vehicles=3)
plot(result, cities)

I am not sure if this result is optimal but it looks very reasonable! The run time of this algorithm is O(k·n²) since finding the best city and tour to insert costs time O(k·n) and we have to do it for each city, i.e., n times, also see the comments in the code. Regarding the memory requirement, we only have to store the output, which is O(n+k).

Greedy insertion heuristic

This one is also analogous to the TSP version. All drivers start with incomplete tours [0], where 0 is the depot. These are sub-tours, i.e., tours that do not visit all cities. You want to add cities to these subtours until all subtours of all drivers together contain every city.

Assume that we have 10 cities, and we created the following sub-tours so far for drivers 1, 2, and 3:

1. 0–1–3–0
2. 0–2–7–6–0
3. 0–4–0

We now want to insert city 5 somewhere. We could do this in the following places:

1. 0–5–1–3–0, 0–1–5–3–0, 0–1–3–5–0
2. 0–5–2–7–6–0, 0–2–5–7–6–0, 0–2–7–5–6–0, 0–2–7–6–5–0
3. 0–5–4–0, 0–4–5–0

We do the same for the other remaining cities 8, 9, and 10, and then pick the city, tour, and position within the tour which increases the sum of all the tour lengths the least. Repeat until all cities are inserted into some tour.

I will show you how to implement it now. Be aware, that it looks quite complicated, but it is the natural extension of the TSP. if you have trouble following the code, check out my article about constructive heuristics for the TSP that I linked above.

def greedy_insert(distance_matrix, depot, n_vehicles):
    unvisited_cities = set(range(len(distance_matrix))) - {depot}
    tours = [[depot, depot] for vehicle in range(n_vehicles)]
    lengths = [0 for vehicle in range(n_vehicles)]

    while unvisited_cities:  # O(n)
        best_length, best_city, best_vehicle, best_i = min(
            (
                (
                    lengths[vehicle]
                    - distance_matrix[tours[vehicle][i - 1]][tours[vehicle][i]]
                    + distance_matrix[tours[vehicle][i - 1]][city]
                    + distance_matrix[city][tours[vehicle][i]],
                    city,
                    vehicle,
                    i,
                )
                for city in unvisited_cities  # O(n)
                for vehicle in range(n_vehicles)  # O(k)
                for i in range(1, len(tours[vehicle]))  # O(n)
            ),
            key=lambda x: x[0],
        )
        tours[best_vehicle] = tours[best_vehicle][:best_i] + [best_city] + tours[best_vehicle][best_i:]
        lengths[best_vehicle] = best_length
        unvisited_cities.remove(best_city)

    return [{"tour": tours[vehicle], "length": lengths[vehicle]} for vehicle in range(n_vehicles)]

The result does not look as nice as the nearest neighbor heuristic, but it is still quite good:

The algorithm has a time complexity of O(k·n³), and a space complexity of O(n+k) for storing the result.

Conclusion

In this article, we have generalized the traveling salesman problem by introducing a fleet of salesmen that have to visit all the cities exactly once, excluding the starting city.

It is a very natural problem that delivery companies have to solve on a daily basis. As with many interesting problems, it is also NP-complete, so usually, we have to resort to heuristic algorithms. These algorithms will probably not yield the optimal answer, but a sufficiently good one, if the heuristic is good enough and the data is not too difficult to handle.

We could also improve each of the tours again, using strategies such as 2-opt, as we did for the TSP in this article:

And since we have several tours, you can even try to merge tours of different drivers!

Extensions

You can make the VRP even harder by introducing challenges such as

• time windows: you cannot deliver your goods at any time, but only in certain time intervals
• heterogeneous fleet: maybe some of your trucks can carry a heavier load than others, or cannot drive as far
• multiple depots: assigning drivers to different starting depots adds more complexity

We might tackle this in a future article!

I hope that you learned something new, interesting, and valuable today. Thanks for reading!

If you have any questions, write me on LinkedIn!