Mutually exclusive groups¶

Mutually exclusive groups are a powerful feature that lets PyVRP choose one client from a set of alternatives. Such alternatives often arise in applications where deliveries can be dropped off at different locations (for example, one of several delivery points in a large complex), or when there are multiple, disjunctive time windows (for example, morning or evening delivery). PyVRP’s client groups provide a general way to model such situations. Each client group represents a set of alternative clients, and exactly one client must be serviced from each group.

[1]:

import matplotlib.pyplot as plt

import pyvrp
import pyvrp.plotting
import pyvrp.stop

Choosing from alternatives¶

Let’s demonstrate this with an example where we introduce two client groups. Each group consists of two clients, and we ask PyVRP to select which client to visit in each group.

[2]:

COORDS = [(456, 320), (312, 418), (114, 80), (570, 160), (684, 240)]
GROUPS = [0, 0, 1, 1]

[3]:

m = pyvrp.Model()

depot = m.add_depot(x=COORDS[0][0], y=COORDS[0][1])
m.add_vehicle_type(2)

# Create the client groups. Clients are assigned to their group below.
groups = [m.add_client_group(required=True) for _ in range(2)]

for idx in range(1, len(COORDS)):
    m.add_client(
        x=COORDS[idx][0],
        y=COORDS[idx][1],
        group=groups[GROUPS[idx - 1]],  # assign group
        required=False,
    )

for frm in m.locations:
    for to in m.locations:
        distance = abs(frm.x - to.x) + abs(frm.y - to.y)
        m.add_edge(frm, to, distance=distance)

res = m.solve(stop=pyvrp.stop.MaxRuntime(1))

PyVRP v0.14.0a0

Solving an instance with:
    1 depot
    4 clients
    2 vehicles (1 vehicle type)

    Iters    Time |      Current OK    Candidate OK         Best OK

Search terminated in 1.00s after 50121 iterations.
Best-found solution has cost 1032.

Solution results
================
    # routes: 1
     # trips: 1
   # clients: 2
   objective: 1032
    distance: 1032
    duration: 0
# iterations: 50121
    run-time: 1.00 seconds

Let’s see which clients PyVRP chose to visit, and annotate each client with its group label:

[4]:

_, ax = plt.subplots(figsize=(8, 8))
pyvrp.plotting.plot_solution(res.best, m.data(), plot_clients=True, ax=ax)

for client in m.clients:  # annotate client group label
    ax.text(client.x + 10, client.y + 10, f"{client.group}")

PyVRP visits the clients in each group that are closest to the depot.

Conclusion¶

You now know how to use PyVRP’s mutually exclusive client groups. Mutually exclusive groups are a powerful feature for modelling services, such as choosing between multiple delivery locations (for example, different drop-off points) or choosing between different time windows (such as morning or evening delivery).