27  Delivery Routing with Lexicographic Objectives

NoteSource and adaptation

Based on Lost baggage distribution, Section 12.27 of Williams (2013). New six-customer delivery instance using complete feasible-route enumeration. Open delivery routes do not need to return within the delivery deadline. The results below solve the stated instance and are not presented as the numerical answer to an unmodified textbook problem.

27.1 Problem Statement

A depot at (0,0) dispatches vans to six customers at (2,1), (1,4), (4,3), (6,1), (5,5), and (2,6). Travel time is five minutes per unit of Euclidean distance. Service time is zero and vehicle load is unrestricted. Each route starts at the depot and finishes at its last customer, without a required return trip in the deadline. All deliveries must finish within 60 minutes. First minimize the number of vans; among solutions using that number, minimize the longest route duration. Every customer must be visited exactly once.

27.1.1 Delivery coordinates

Node (0 = depot) East North
0 0 0
1 2 1
2 1 4
3 4 3
4 6 1
5 5 5
6 2 6

27.2 Model Formulation

For each nonempty customer subset, enumerate all orders and retain a shortest open route. Discard subsets whose shortest route exceeds 60 min. Let \(R\) be the resulting route set, \(a_{ir}\) indicate route membership, and \(d_r\) be its duration. Choose route binaries \(y_r\) and \(T\in[0,60]\).

\[\sum_r a_{ir}y_r=1\quad\forall i,\qquad T\ge d_ry_r\quad\forall r.\] \[\min\ 61\sum_r y_r+T.\]

Since \(T\) can vary by at most 60 min, one additional van always costs more than any improvement in \(T\). The scalar objective therefore implements the stated lexicographic priorities exactly. Route enumeration is complete for this small instance; it does not scale to large delivery networks.

All decision variables and units refer to the problem statement above. Continuous variables are nonnegative unless explicitly stated otherwise; binary and integer domains are specified in the equations and code.

27.3 Pyomo Implementation

The following Python implementation uses Pyomo and HiGHS. Run from the workbook root so that the models package and shared helpers are importable. The shared solver and audit functions check optimal termination before loading values, then verify every active constraint, variable bound, and integer domain. Any imported earlier-chapter model supplies the data and balances already explained there.

The full source is problem27.py. To solve and print this problem independently:

~/.venvs/optim/bin/python -m models.common 27
import itertools
import math
import pyomo.environ as pyo
from models.common import frame

COORD = [(0, 0), (2, 1), (1, 4), (4, 3), (6, 1), (5, 5), (2, 6)]
ROUTES = []
for size in range(1, 7):
    for subset in itertools.combinations(range(1, 7), size):
        duration, path = min(
            (sum(5 * math.dist(COORD[a], COORD[b]) for a, b in zip((0,) + p, p)), p)
            for p in itertools.permutations(subset)
        )
        if duration <= 60:
            ROUTES.append((path, duration))


def build():
    m = pyo.ConcreteModel()
    m.R = pyo.RangeSet(0, len(ROUTES) - 1)
    m.y = pyo.Var(m.R, domain=pyo.Binary)
    m.T = pyo.Var(bounds=(0, 60))
    m.cover = pyo.Constraint(
        range(1, 7),
        rule=lambda m, i: sum(m.y[r] for r in m.R if i in ROUTES[r][0]) == 1,
    )
    m.longest = pyo.Constraint(m.R, rule=lambda m, r: m.T >= ROUTES[r][1] * m.y[r])
    m.obj = pyo.Objective(expr=61 * sum(m.y[r] for r in m.R) + m.T)
    return m


def check(m):
    selected = [ROUTES[r] for r in m.R if pyo.value(m.y[r]) > 0.5]
    visits = [i for route, _ in selected for i in route]
    assert sorted(visits) == list(range(1, 7))
    assert abs(max(d for _, d in selected) - pyo.value(m.T)) < 1e-6
    # Independent subset dynamic programming for the lexicographic pair.
    best = {0: (0, 0.0)}
    for mask in range(1, 64):
        choices = []
        for path, d in ROUTES:
            bits = sum(1 << (i - 1) for i in path)
            if bits & mask == bits and mask ^ bits in best:
                k, t = best[mask ^ bits]
                choices.append((k + 1, max(t, d)))
        if choices:
            best[mask] = min(choices)
    assert best[63][0] == len(selected) and abs(best[63][1] - pyo.value(m.T)) < 1e-6


def tables(m):
    selected = [ROUTES[r] for r in m.R if pyo.value(m.y[r]) > 0.5]
    return {
        "routes": frame(
            [
                [j + 1, "0 → " + " → ".join(map(str, path)), duration]
                for j, (path, duration) in enumerate(selected)
            ],
            ["Van", "Open route", "Duration (min)"],
        ),
        "priorities": frame(
            [["Vans", len(selected)], ["Longest route (min)", pyo.value(m.T)]],
            ["Criterion", "Value"],
        ),
    }


def plot(m):
    selected = [d for r, (path, d) in enumerate(ROUTES) if pyo.value(m.y[r]) > 0.5]
    return (
        [f"Van {j + 1}" for j in range(len(selected))],
        selected,
        "Route duration (min)",
    )

# Solve, audit constraints, and run domain-specific checks.
from models.common import solve, audit
model = solve(build())
audit(model)
check(model)
for name, result_table in tables(model).items():
    print(name)
    print(result_table.to_string(index=False))

27.4 Optimal Solution

The solver reports optimal termination. The objective is 169.607256 lexicographic score = 61 × vans + longest route minutes (minimize). The largest violation across active constraints, variable bounds, and integer domains is 3.33e-15 in the corresponding model units. The problem-specific checks also pass. These checks establish numerical consistency with the stated model, not the validity of its assumptions for a real facility.

27.4.1 Routes

Van Open route Duration (min)
1 0 → 1 → 3 → 4 39.4646
2 0 → 2 → 6 → 5 47.6073

27.4.2 Priorities

Criterion Value
Vans 2
Longest route (min) 47.6073
Figure 27.1: Selected open delivery routes. No return travel is counted.

Tables round numerical values for reading; feasibility checks use the original solver values. Multiple optimal decisions may exist. Machine-readable result records the solver status and package versions. Figure-generation code is in figures/workbook.py.

27.5 Brief Discussion

The first-priority optimum uses 2 vans. Among those fleet-minimal plans, the smallest longest delivery time is 47.607 min.

Minimizing total distance is different from minimizing the longest route. The fleet count takes strict priority here. Retaining only the shortest route for each subset is valid because every route with that subset serves the same customers and a longer duration is dominated. Experiment: impose return-to-depot travel and compare the required vans.