Classic VRPs¶

This notebook shows how to use PyVRP to solve two classic variants of the VRP: the capacitated vehicle routing problem (CVRP), and the vehicle routing problem with time windows (VRPTW). It builds on the tutorial by solving much larger instances, and going into more detail about the various plotting tools and diagnostics available in PyVRP.

A CVRP instance is defined on a complete graph \(G=(V,A)\), where \(V\) is the vertex set and \(A\) is the arc set. The vertex set \(V\) is partitioned into \(V=\{0\} \cup V_c\), where \(0\) represents the depot and \(V_c=\{1, \dots, n\}\) denotes the set of \(n\) customers. Each arc \((i, j) \in A\) has a weight \(d_{ij} \ge 0\) that represents the travel distance from \(i \in V\) to \(j \in V\). Each customer \(i \in V_c\) has a demand \(q_{i} \ge 0\). The objective is to find a feasible solution that minimises the total distance.

A VRPTW instance additionally incorporates time aspects into the problem. For the sake of exposition we assume the travel duration \(t_{ij} \ge 0\) is equal to the travel distance \(d_{ij}\) in this notebook. Each customer \(i \in V_c\) has a service time \(s_{i} \ge 0\) and a (hard) time window \(\left[e_i, l_i\right]\) that denotes the earliest and latest time that service can start. A vehicle is allowed to arrive at a customer location before the beginning of the time window, but it must wait for the window to open to start the delivery. Each vehicle must return to the depot before the end of the depot time window \(H\). The objective is to find a feasible solution that minimises the total distance.

Let’s first import what we will use in this notebook.

[1]:

import matplotlib.pyplot as plt
from tabulate import tabulate
from vrplib import read_solution

from pyvrp import read, solve
from pyvrp.plotting import (
    plot_coordinates,
    plot_instance,
    plot_result,
    plot_route_schedule,
)
from pyvrp.stop import MaxIterations, MaxRuntime

The capacitated VRP¶

Reading the instance¶

We will solve the X-n439-k37 instance, which is part of the X instance set that is widely used to benchmark CVRP algorithms. The function pyvrp.read reads the instance file and converts it to a ProblemData instance. We pass the argument round_func="round" to compute the Euclidean distances rounded to the nearest integral, which is the convention for the X benchmark set. We also load the best known solution to evaluate our solver later on.

[2]:

INSTANCE = read("data/X-n439-k37.vrp", round_func="round")
BKS = read_solution("data/X-n439-k37.sol")

Let’s plot the instance and see what we have.

[3]:

_, ax = plt.subplots(figsize=(8, 8))
plot_coordinates(INSTANCE, ax=ax)
plt.tight_layout()

Solving the instance¶

We will use the default solve method that PyVRP provides for data instances.

[4]:

result = solve(INSTANCE, stop=MaxIterations(2000), seed=42, display=False)
print(result)

Solution results
================
    # routes: 37
     # trips: 37
   # clients: 438
   objective: 37428
    distance: 37428
    duration: 37428
# iterations: 2000
    run-time: 2.73 seconds

Routes
------
Route #1: 417 424 368 290 356 190 125 291 174 313 265 165
Route #2: 36 258 70 104 60 185 143 147 82 32 362 136
Route #3: 435 211 347 206 145 200 139 57 296 375 43 281
Route #4: 77 364 259 30 222 310 178 160 292 382 192 235
Route #5: 421 418 416 407 122 366 384 403 17 412 83 352
Route #6: 207 387 397 184 390 62 371 408 395 287 161 58
Route #7: 124 99 216 106 182 78 256 96 179 81
Route #8: 413 432 351 266 329 319 338 289 253 257 138 246
Route #9: 422 353 195 308 270 406 92 275 41 202 149 172
Route #10: 170 142 205 219 282 273 320 284 269 120 332 399
Route #11: 111 20 128 186 54 27 100 51 164 199 151 163
Route #12: 361 331 220 240 302 255 152 177 135 157 73 175
Route #13: 105 370 410 267 299 392 218 239 42 335 71 155
Route #14: 279 52 198 214 272 123 64 10 37 357 363 300
Route #15: 325 312 438 385 250 345 166 162 346 228 381 404
Route #16: 431 344 197 7 153 215 193 15 159 65 137 251
Route #17: 132 4 34 230 67 16 112 378 21 11 181 84
Route #18: 107 306 314 148 85 12 48 180
Route #19: 44 249 337 423 391 372 264 241 280 393 237 121
Route #20: 210 22 56 75 196 274 116 113 109 90 140 134
Route #21: 233 420 396 309 252 297 225 388 409 110 303 245
Route #22: 254 9 263 55 298 278 33 288 238 305 358 231
Route #23: 415 318 294 23 93 14 307 18 436 373 50 194
Route #24: 414 217 236 59 187 434 2 169 3 411 348 326
Route #25: 68 69 277 45 49 94 212 46 40 247 203 167
Route #26: 271 285 101 402 428 89 293 339 66 126 86 315
Route #27: 28 430 248 19 330 108 340 327 389 343 24 401
Route #28: 189 61 130 80 88 173 118 91 154 144 334 146
Route #29: 8 311 133 425 349 223 386 400 97 72 260 26
Route #30: 25 204 176 79 131 6 1 367 426 5 31 333
Route #31: 38 156 427 398 317 276 226 355 429 365 359 295
Route #32: 437 323 243 321 383 376 47 286 350 341 98 283
Route #33: 244 209 354 103 379 301 117 63 74 13 394 171
Route #34: 324 229 268 377 433 242 360 342 221 227 380 115
Route #35: 262 261 129 191 158 29 87 102 127 119 76 201
Route #36: 369 336 419 304 322 374 208 141 35 232 39 53
Route #37: 183 150 224 188 234 405 168 95 328 213 114 316

[5]:

gap = 100 * (result.cost() - BKS["cost"]) / BKS["cost"]
print(f"Found a solution with cost: {result.cost()}.")
print(f"This is {gap:.1f}% worse than the best known", end=" ")
print(f"solution, which is {BKS['cost']}.")

Found a solution with cost: 37428.
This is 2.8% worse than the best known solution, which is 36391.

We’ve managed to find a very good solution quickly!

The Result object also contains useful statistics about the optimisation. We can now plot these statistics as well as the final solution use plot_result.

[6]:

fig = plt.figure(figsize=(15, 9))
plot_result(result, INSTANCE, fig)
fig.tight_layout()

The Objectives plot gives an overview of the solution quality over the course of the search. The bottom-left figure shows iteration runtimes in seconds. Finally, the Solution plot shows the best observed solution.

The VRP with time windows¶

Reading the instance¶

We start with a basic example that loads an instance and solves it using the standard configuration used by the solve method. For the basic example we use one of the well-known Solomon instances.

We again use the function pyvrp.read. We pass the argument round_func="dimacs" following the DIMACS VRP challenge convention, this computes distances and durations truncated to one decimal place.

[7]:

INSTANCE = read("data/RC208.vrp", round_func="dimacs")
BKS = read_solution("data/RC208.sol")

Let’s plot the instance and see what we have. The function plot_instance will plot time windows, delivery demands and coordinates, which should give us a good impression of what the instance looks like. These plots can also be produced separately by calling the appropriate plot_* function: see the API documentation for details.

[8]:

fig = plt.figure(figsize=(12, 6))
plot_instance(INSTANCE, fig)

Solving the instance¶

[9]:

result = solve(INSTANCE, stop=MaxIterations(1000), seed=42, display=False)
print(result)

Solution results
================
    # routes: 4
     # trips: 4
   # clients: 100
   objective: 7801
    distance: 7801
    duration: 17801
# iterations: 1000
    run-time: 0.62 seconds

Routes
------
Route #1: 90 65 82 99 52 57 83 64 49 19 18 48 21 23 25 77 58 75 97 59 87 86 74 24 22 20 66
Route #2: 81 61 42 44 39 38 36 35 37 40 43 41 72 71 93 94 96 54
Route #3: 69 98 88 2 6 79 73 78 12 14 47 17 16 15 13 9 11 10 53 60 7 8 46 45 4 5 3 1 70 100 55 68
Route #4: 92 95 67 62 50 34 31 29 27 26 28 30 32 33 76 89 63 85 51 84 56 91 80

[10]:

cost = result.cost() / 10
gap = 100 * (cost - BKS["cost"]) / BKS["cost"]
print(f"Found a solution with cost: {cost}.")
print(f"This is {gap:.1f}% worse than the optimal solution,", end=" ")
print(f"which is {BKS['cost']}.")

Found a solution with cost: 780.1.
This is 0.5% worse than the optimal solution, which is 776.1.

We’ve managed to find a (near) optimal solution in a few seconds!

[11]:

fig = plt.figure(figsize=(15, 9))
plot_result(result, INSTANCE, fig)
fig.tight_layout()

We can also inspect some statistics of the different routes, such as route distance, various durations, the number of stops and total delivery amount.

[12]:

solution = result.best
routes = solution.routes()

data = [
    {
        "num_stops": len(route),
        "distance": route.distance(),
        "service_duration": route.service_duration(),
        "wait_duration": route.wait_duration(),
        "time_warp": route.time_warp(),
        "delivery": route.delivery(),
    }
    for route in routes
]

tabulate(data, headers="keys", tablefmt="html")

[12]:

We can inspect the routes in more detail using the plot_route_schedule function. This will plot distance on the x-axis, and time on the y-axis, separating actual travel/driving time from waiting and service time. The clients visited are plotted as grey vertical bars indicating their time windows. In some cases, there is slack in the route indicated by a semi-transparent region on top of the earliest time line. The grey background indicates the remaining load of the truck during the route, where the (right) y-axis ends at the vehicle capacity.

[13]:

fig, axarr = plt.subplots(2, 2, figsize=(15, 9))
for idx, (ax, route) in enumerate(zip(axarr.flatten(), routes)):
    plot_route_schedule(
        INSTANCE,
        route,
        title=f"Route {idx}",
        ax=ax,
        legend=idx == 0,
    )

fig.tight_layout()

Each route begins at a given start_time, that can be obtained as follows. Note that this start time is typically not zero, that is, routes do not have to start immediately at the beginning of the time horizon.

[14]:

solution = result.best
shortest_route = min(solution.routes(), key=len)

shortest_route.start_time()

[14]:

2849

Some of the statistics presented in the plots above can also be obtained from the route schedule, as follows:

[15]:

data = [
    {
        "location": visit.location,  # Client or depot location of visit
        "start_service": visit.start_service,
        "end_service": visit.end_service,
        "service_duration": visit.service_duration,
        "wait_duration": visit.wait_duration,  # if vehicle arrives early
    }
    for visit in shortest_route.schedule()
]

tabulate(data, headers="keys", tablefmt="html")

[15]:

Solving a larger VRPTW instance¶

To show that PyVRP can also handle much larger instances, we will solve one of the largest Gehring and Homberger VRPTW benchmark instances. The selected instance - RC2_10_5 - has 1000 clients.

[16]:

INSTANCE = read("data/RC2_10_5.vrp", round_func="dimacs")
BKS = read_solution("data/RC2_10_5.sol")

[17]:

fig = plt.figure(figsize=(15, 9))
plot_instance(INSTANCE, fig)

Here, we will use a runtime-based stopping criterion: we give the solver 30 seconds to compute.

[18]:

result = solve(INSTANCE, stop=MaxRuntime(30), seed=42, display=False)

[19]:

cost = result.cost() / 10
gap = 100 * (cost - BKS["cost"]) / BKS["cost"]
print(f"Found a solution with cost: {cost}.")
print(f"This is {gap:.1f}% worse than the best-known solution,", end=" ")
print(f"which is {BKS['cost']}.")

Found a solution with cost: 26175.9.
This is 1.5% worse than the best-known solution, which is 25797.5.

[20]:

plot_result(result, INSTANCE)
plt.tight_layout()

Conclusion¶

In this notebook, we used PyVRP’s solve functionality to solve a CVRP instance with 438 clients to near-optimality, as well as several VRPTW instances, including a large 1000 client instance. Moreover, we demonstrated how to use the plotting tools to visualise the instance and statistics collected during the search procedure.