The Truck Dispatching Problem — An Interactive Exploration

Section 1 From Salesman to Fleet

Every package you've ever received, every fuel delivery, every grocery restocking — all are descendants of the problem Dantzig and Ramser formalized in twelve pages.

The story begins with a more famous puzzle. The Traveling Salesman Problem asks: given a set of cities, what is the shortest route that visits each city exactly once and returns to the starting point? Even for a modest 15 cities, there are over 650 billion possible routes. It's one of the hardest problems in computer science.

But in the real world, a single salesman is rarely enough. Dantzig and Ramser considered something harder and more practical: a fleet of trucks, each with a limited capacity, that must deliver specified quantities to a set of stations and return to a central terminal. This is the Truck Dispatching Problem — what we now call the Vehicle Routing Problem (VRP).

Key Insight

The crucial difference from the Traveling Salesman Problem is the capacity constraint. A truck can only carry so much fuel. When $C \ll \sum q_i$ — when the truck capacity is much less than the total demand — the single tour must split into multiple trips, each respecting the capacity limit.

The interactive below lets you feel this transition. Start with a few cities and a single tour. Then impose a capacity constraint and watch the tour fragment into multiple routes — each a little sub-problem demanding coordination.

Figure 1 TSP → VRP: When Capacity Splits the Tour

Drag the stations to rearrange them. In TSP mode, a single optimal tour visits every station. Switch to VRP mode to add a capacity constraint — the tour splits into color-coded routes, each respecting the truck's limit. The terminal is the red node.

Section 2 The Problem, Precisely

Before solving anything, Dantzig and Ramser needed to state the problem with mathematical precision. Their formulation is elegant: a distance matrix, a demand vector, a capacity, and a set of binary decision variables.

The Truck Dispatching Problem

[1] Given $n$ station points $P_1, P_2, \ldots, P_n$ served from a terminal $P_0$.
[2] A distance matrix $[D] = [d_{ij}]$ gives the shortest distance between every pair.
[3] A delivery vector $(Q) = (q_i)$ specifies the demand at each station.
[4] The truck capacity is $C$, where $C > \max q_i$.
[5] Decision variables: $x_{ij} = 1$ if stations $P_i$ and $P_j$ are paired, 0 otherwise.
[6] Minimize total distance $D = \sum_{i,j} d_{ij} x_{ij}$ subject to $\sum_j x_{ij} = 1$ for each station.

The constraint $\sum_j x_{ij} = 1$ ensures every station is connected to exactly one other point — either the terminal $P_0$ or another station $P_j$. This is the heart of the pairing structure that drives the algorithm.

Why Pairings?

The key trick in Dantzig and Ramser's approach is to build solutions through stages of aggregation. In the first stage, individual stations are paired together. In the second stage, pairs are combined into routes. This hierarchical approach keeps the problem manageable — you never have to consider all $n!$ permutations at once.

Figure 2 Build Your Own Dispatch Problem

Click to place stations. Drag to rearrange. Use sliders to set each station's demand $q_i$ and the truck capacity $C$. Watch the distance matrix and constraint checks update in real-time.

Section 3.1 First-Stage Aggregation

The algorithm begins by pairing nearby stations whose combined demand fits within half the truck capacity. This is the foundation on which routes are built.

Dantzig and Ramser's example uses 12 stations with a truck capacity of $C = 6000$ gallons. The demands range from 1100 to 1900 gallons. The number of aggregation stages is determined by:

N = \lceil \log_2 t \rceil

where $t$ is the maximum number of deliveries a truck can make on a single trip. With these demands, $t = 4$ (the four smallest demands sum to 4900 < 6000, but five would exceed it), giving $N = 2$ stages.

In the first stage, pairs of stations are considered. A pairing $(P_i, P_j)$ is admissible only if $q_i + q_j \leq C/2 = 3000$. Stations with combined demand exceeding this threshold are marked with a star (★) — they cannot be paired in this stage.

Figure 3 The Aggregation Machine

The triangular matrix from Table 1. Click any pair to check if it's admissible. Step through the algorithm to watch pairs form and the map update.

Section 3.3 Rapid Corrections

The starting solution — every station directly connected to the terminal — is obviously wasteful. Rapid corrections greedily improve it by connecting nearby stations to each other instead.

The algorithm scans for pairs of stations with small inter-station distances $d_{ij}$. When such a pair is found, the two stations are disconnected from the terminal and connected to each other: $x_{i,j} = 1$ replaces $x_{0,i}$ or $x_{0,j}$ in the basis.

In the paper's example, the first four rapid corrections reduce the total inter-pair distance from 364 to 170 units — a 53% improvement in just four steps.

Figure 4 Greedy Improvement

Total distance: 364units

Watch each greedy swap: a non-basic entry with small $d_{ij}$ replaces a terminal connection. The total distance counter ticks down with each improvement.

Section 3.4 The Delta Function

When greedy swaps run out, Dantzig and Ramser introduce a powerful criterion: the delta function, which tells you exactly how much each potential swap would improve (or worsen) the solution.

The delta function is defined as:

\delta_{ij}^{(n)} = \pi_i^{(n)} + \pi_j^{(n)} - d_{ij}

where $\pi_i^{(n)}$ and $\pi_j^{(n)}$ are constants (dual variables) determined so that $\delta_{ij} = 0$ for all basic (currently active) entries. For non-basic entries, $\delta_{ij} > 0$ means the total distance decreases if we bring that pair into the solution. When all $\delta_{ij} \leq 0$ for non-basic entries, we've found the optimum for this stage.

Connection to LP Duality

The $\pi$ values are essentially dual variables — shadow prices from linear programming. The delta function is the reduced cost. This is the same optimality criterion used in Dantzig's own simplex method, applied here to the pairing problem. When all reduced costs are non-positive, you're at the optimum.

Figure 5 The Optimality Lens

The delta function visualized as a heatmap over the triangular matrix. Green cells indicate improvement opportunities; red cells would make things worse. Watch the landscape flatten as iterations converge to optimality.

Section 3.5 Second-Stage Aggregation

With stations now paired, the algorithm zooms out. The pairs become new "super-nodes" — aggregates — and the pairing process repeats at a higher level, building complete truck routes.

The first-stage aggregation produces seven aggregates: $A_1 = \{P_1, P_2\}$, $A_2 = \{P_3, P_4\}$, $A_3 = \{P_5\}$, $A_4 = \{P_6, P_{10}\}$, $A_5 = \{P_7, P_8\}$, $A_6 = \{P_9\}$, $A_7 = \{P_{11}, P_{12}\}$.

A new distance table is constructed for routes through pairs of aggregates. For example, the distance for the aggregate pair $(A_4, A_5)$ is the length of the minimal loop $P_0 \to P_6 \to P_7 \to P_{10} \to P_9 \to P_0$ (taking care that no loop crosses itself). The same LP pairing algorithm then minimizes total distance at this aggregate level.

Figure 6 Zoom Out — Aggregates Become Nodes

Watch the first-stage pairs morph into aggregate nodes. The new distance table is computed, and the pairing algorithm runs again to form complete routes.

Section 3.6 Fractional Solutions

Sometimes the LP relaxation can't decide. When the optimal solution contains fractional values — $x_{ij} = \frac{1}{2}$ — it means multiple pairings are equally viable, and we must choose.

In the paper's example, the second-stage solution contains three fractional entries involving aggregates $A_1$, $A_2$, and $A_3$. Any two of them can be paired together, leaving the third to connect directly with the terminal.

Dantzig and Ramser introduce an elegant visual tool: place the conflicting aggregates at the vertices of a triangle, with the terminal $A_0$ inside. Label each edge with its route distance. The minimum-cost pairing is immediately visible.

Figure 7 The Triangle Trick

The triangle diagram from Figure 2 of the original paper. Drag $A_0$ around to see distances change. Toggle between the three possible pairings to find the minimum.

Section 3.7 How Close to Optimal?

The algorithm's solution covers 294 distance units. The believed true optimal is 290 units — a difference of just 1.4%. Not bad for 1959.

The algorithm's routes are $(P_1 P_2 P_3 P_4)$, $(P_7 P_{12} P_{11} P_9)$, $(P_6 P_{10} P_8)$, and $P_5$ alone. The believed optimal swaps $P_9$ and $P_{10}$ between the second and third routes: $(P_7 P_{12} P_{11} P_{10})$, $(P_6 P_8 P_9)$.

Honest About Limitations

Dantzig and Ramser are forthright: their method "does not guarantee that the absolute optimum solution is obtained." But they conjecture — correctly, as later research showed — that the gap shrinks as the number of stations grows. The LP relaxation provides a lower bound, bounding the error.

Figure 8 Algorithm vs. Optimal — Side by Side

Compare the algorithm's solution (294 units) with the believed optimal (290 units). The overlay view highlights the segments that differ between the two solutions.

Sections 4–6 Extensions

With the core algorithm in hand, Dantzig and Ramser sketch two natural generalizations that bring the model closer to reality.

4 Multiple Products

When a truck must deliver $n$ different products to each station, the key question is whether products are interchangeable in the carrier. If a truck has moveable partitions (or the products are of equal density), only the total demand $Q_i = \sum_k q_{i,k}$ matters. The same algorithm applies unchanged.

5 Mixed Fleet

When trucks have different capacities $C_1, C_2, \ldots, C_m$, the problem becomes one of minimizing total cost rather than total mileage — unused capacity has a price. Dantzig and Ramser suggest solving for the largest truck capacity $C_m$ and then assigning trucks post-hoc based on each route's total demand.

6 Relaxed Delivery

What if you don't have to satisfy demand exactly? Allowing a percentage of over- or underdelivery opens new pairings and reduces total mileage. The ultimate version: deliver proactively so that "no station ever runs dry." This anticipatory approach — requiring demand forecasting — would later become a rich field of its own.