Pruning and packing the cost matrix

A distance matrix can become the expensive part of a delivery batch before the route solver does any useful work. The usual implementation builds a list of driver and order nodes, asks Google Maps for every origin-destination pair, and only then tells the solver which arcs are illegal.

That is wasteful in a multi-service fleet. Drivers may be enrolled in different services, vehicle capacity can rule out assignments, and pickup-delivery state rules can make whole classes of transitions impossible. Those pairs do not need a travel-time measurement.

I was working on a vehicle-routing engine for a delivery company that wanted to move from single-pickup, single-delivery routes to multi-pickup, multi-delivery routes. Driver availability was unpredictable because drivers were independent or freelance, so the routing engine had to share capacity across food, grocery, and package services.

That made routing a constrained allocation problem as well as a shortest-path problem. The engine had to decide which work could share a route, which drivers were eligible, and which transitions were legal before it could ask for travel costs.

The useful framing is:

Do not fetch a complete matrix and then tell the solver which arcs are illegal. Build the legal arc set first, then pay for measurements only on that set.

That enrolment information is part of the routing constraints, so it can also reduce the distance-matrix problem.

The process has two stages:

prune the directed graph until it contains only useful candidate arcs;
pack those arcs into as few valid Distance Matrix API requests as possible.

The second stage is where Google OR-Tools becomes useful.

The complete matrix is the wrong starting point

Suppose a batch contains:

$D$ drivers;
$O$ orders;
one pickup and one delivery node for each order;
a starting node for each driver.

A rough node count is $D + 2O$ . A complete directed matrix therefore has approximately:

(D + 2O)^2

entries before removing self-transitions.

That estimate is already pessimistic for the routing model. The solver has precedence, capacity, service, and assignment constraints. The graph is directed, and many pairs are structurally impossible.

For example, these requests do not provide useful information under the model:

order A pickup $→$ order A delivery, when that transition is represented by an internal route-state transition rather than a road leg;
a driver's starting node $→$ an order delivery, when every route must begin with a pickup;
a driver starting node $→$ a node belonging to a service in which that driver is not enrolled;
a driver starting node $→$ a pickup node belonging to an order that exceeds the driver's vehicle capacity;
any transition that violates a hard service, precedence, or route-state rule.

The exact exclusions depend on how the solver represents a route. The principle is stable: the cost provider should understand enough of the solver's legality rules to avoid measuring arcs that the solver cannot select.

This is a directed graph problem. It is not enough to say that two nodes are both present in the batch. We need to know whether the ordered pair $(i,j)$ can occur in a legal route.

Step 1: sparsify the cost graph

I represent the requestable part of the matrix as a set of directed arcs:

E = \{(o_i, d_j) \mid legal(o_i, d_j)\}

Each arc needs metadata as well as its endpoints. In a delivery system, that can include:

the origin node type;
the destination node type;
the order and service associated with each node;
which driver or driver group can reach the origin;
whether the transition is compatible with pickup-before-delivery;
whether a solver constraint will ever inspect the resulting cost.

The filter should happen before any API batching. Otherwise a later batching step may accidentally reintroduce impossible pairs by putting two large node lists into one rectangular request.

A simple version looks like this:

codepython

def requestable(origin, destination, driver):
    if origin == destination:
        return False

    if origin.is_pickup and destination.is_delivery:
        if same_order_transition_is_internal(origin, destination):
            return False

    if origin.is_driver_start and destination.is_delivery:
        return False

    if destination.service not in driver.enrolled_services:
        return False

    return solver_allows(origin, destination, driver)

The final predicate is deliberately abstract. The important design choice is that this filter is derived from the same rules that define legal solver arcs. If the API layer has a second, slightly different understanding of legality, the matrix will be either wasteful or incomplete.

Sparsification also changes what “matrix” means. Internally, the result may be a sparse map keyed by $(origin, destination)$ , with missing entries treated as unavailable rather than as zero or infinity by accident.

The API limits make each request a small rectangle

The Distance Matrix API returns a Cartesian product of origins and destinations. If a request contains $m$ origins and $n$ destinations, it contains $m \times n$ elements.

For the API configuration I was targeting, one request had to obey:

m \leq 25,\qquad n \leq 25,\qquad m n \leq 100

The last constraint is usually the one that surprises people. Two lists of 25 are individually valid but produce 625 elements, so they cannot be sent together.

Each request is therefore a rectangle with:

a maximum height of 25 origins;
a maximum width of 25 destinations;
an area of at most 100 elements.

The API does not accept an arbitrary list of directed edges. It accepts a rectangle, and that rectangle may contain pairs we did not want. That is why pruning and packing have to be designed together.

If every origin could use every destination, ordinary chunking would be enough. For a sparse graph, it is wasteful: a rectangle can include many cells outside $E$ . The packer should therefore group nodes that share useful arcs, or at least measure the tradeoff between a larger rectangle and its extra cells.

Step 2: pack the sparse arcs

The first useful abstraction is a bin:

codetext

bin:
  origins      <= 25
  destinations <= 25
  origins * destinations <= 100

A bin becomes one API request. The objective is to cover all required arcs with as few bins as possible, subject to the rectangle limits and any policy about extra cells.

This is related to two-dimensional bin packing, but the source data is sparse and directed. A node can occur in several bins, and two arcs with the same origin do not necessarily share a destination group. In practice, I found it more useful to think in terms of nested packing:

group compatible destinations into small destination bins;
group origins around those destination bins while respecting the area limit;
emit the resulting origin/destination rectangles as requests.

The nesting is helpful because the product constraint couples the two dimensions. A destination group of 20 leaves room for only five origins if the request must stay below 100 elements. A destination group of four can be paired with 25 origins.

An exact model is not always worth its own complexity. For small batches, a deterministic greedy packer is easier to operate and may be good enough. The solver becomes useful when request count, element waste, or quota pressure is large enough to justify comparing candidate packings against that baseline.

A simplified packing loop might look like this:

codepython

for destination_bin in pack_destinations(required_arcs):
    remaining_origins = origins_for(destination_bin)

    while remaining_origins:
        max_origins = min(
            25,
            100 // len(destination_bin),
        )
        origin_bin = take_compatible_origins(
            remaining_origins,
            max_origins,
        )
        emit_request(origin_bin, destination_bin)
        remove(remaining_origins, origin_bin)

This is not the whole optimiser. It shows the shape of the constraint: the maximum number of origins depends on the destination-bin size.

A more complete OR-Tools model can make each candidate placement a binary decision. Let $x_{r,b}$ indicate that required arc $r$ is covered by request bin $b$ , and let $y_b$ indicate that bin $b$ is used. The basic coverage constraint is:

\sum_b x_{r,b} \geq 1

For each bin, the origin and destination counts and their product must satisfy the API limits. The objective can minimise the number of non-empty bins:

\min \sum_b y_b

and each placement must use an active bin:

x_{r,b} \leq y_b

The candidate bins still need origin and destination membership variables, plus constraints that enforce the side and area limits. The equations above describe the coverage shape rather than a complete implementation.

There are several ways to encode the product constraint in OR-Tools. One practical approach is to generate only feasible $(m,n)$ shapes, where $m \leq 25$ , $n \leq 25$ , and $mn \leq 100$ , then let the solver choose among those shapes. Another is to model the two counts and constrain the allowed combinations. The important part is to keep the API rule visible in the model instead of hoping a post-processing step catches an oversized rectangle.

What does “optimal” mean here?

Minimising request count is the obvious objective, but it is not always the complete one.

A rectangle can cover many required arcs while also asking for cells that will never be used. Those extra elements may still consume quota, increase response size, or make debugging harder. A useful objective can therefore combine:

number of requests;
total elements requested;
number of extra, non-required cells;
estimated monetary cost;
retry or failure risk for very large requests.

For example:

score = w_r R + w_e Q + w_x X

where $R$ is request count, $Q$ is requested element count, and $X$ is the number of extra cells.

The weights are operational choices. If billing is per element, element count deserves more weight. If the dominant problem is round-trip overhead, request count matters more. If sparsity is high, penalising extra cells prevents the solver from “optimising” by returning a few dense rectangles full of irrelevant pairs.

This is also where the solver model and the API model meet. A cheap matrix is not useful if it omits an arc that a legal route needs. Coverage constraints should be checked before sending requests, and again after responses are assembled.

A small example

Imagine that pruning leaves 240 required arcs. A complete matrix over the same nodes would contain several thousand possible pairs, but only those 240 can reach the routing solver.

A naive edge-by-edge implementation would make 240 API requests. A naive rectangular implementation might use broad origin and destination lists, but exceed the 100-element limit or pay for many forbidden cells.

A packed solution might use shapes such as:

codetext

10 origins x 10 destinations = 100 elements
20 origins x 5 destinations  = 100 elements
25 origins x 4 destinations  = 100 elements

The best shape depends on which origins and destinations share arcs. The arithmetic alone does not decide it. The sparse graph decides whether a rectangle actually covers useful work.

The result is not necessarily 240 elements exactly. Some duplicate or extra cells may be unavoidable if the API's rectangle interface is used. That overhead should be visible in the packing score and in the batch metrics.

The packing stage is part of routing

It is tempting to treat API batching as plumbing around the “real” vehicle-routing problem. In a large batch, that separation breaks down.

The routing model decides which transitions matter. The packing model decides how to measure them within an external interface. A change to one can invalidate assumptions in the other:

adding a new service changes driver eligibility;
allowing a different first stop changes start-node arcs;
changing pickup-delivery state rules changes precedence pruning;
adding a solver penalty for an arc makes that arc worth measuring;
changing API limits changes the feasible bin shapes.

That suggests a useful boundary in the implementation. Keep these parts explicit:

a legality layer that produces requestable directed arcs;
a packing layer that turns arcs into valid request rectangles;
an API client with retries, quotas, and response validation;
a cost store that records which arcs were measured and why others are absent.

The boundary makes failures inspectable. If the solver asks for a missing cost, the question is whether the arc was incorrectly pruned, incorrectly packed, or failed during retrieval.

What I would measure

The optimisation is only useful if its effect can be observed. For each batch, I would record:

total possible directed pairs;
pairs removed by each pruning rule;
required arcs after sparsification;
number of requests;
requested elements;
extra cells inside rectangles;
failed and retried requests;
cache hits;
time spent packing versus waiting for the API.

Those numbers separate two different wins. Sparsification reduces what needs to be measured. Packing reduces the number of calls needed to measure it. A batch can have excellent pruning and poor packing, or the reverse.

Caching belongs here too. A cost already measured for the same origin, destination, travel mode, and relevant options should not be requested again merely because it appears in a new batch. The cache key is part of correctness: changing traffic assumptions, departure time, or routing options can change the meaning of a stored travel time.

The useful model

The main lesson is that a distance matrix is not automatically a dense table. For a constrained routing engine, it is better understood as a demand graph produced by the solver's own legal-move model.

First remove arcs that cannot matter. Then cover the remaining directed arcs with API-compatible rectangles. Google OR-Tools is useful for the second step because the request limits create a small but real combinatorial optimisation problem: choose a set of bins that covers the required work while respecting side lengths, area, and whatever cost you attach to extra cells.

The API is only one constraint in the system. The harder constraint is semantic: the matrix should describe the routes the solver can actually consider. Once that is explicit, reducing distance-matrix cost stops being a matter of splitting lists into chunks and becomes a decision problem with a measurable objective.