Routing and sequencing
The problem is NP-hard. The answer still has to arrive before the truck does.
Quincus solves the pickup and delivery problem with time windows, multi-depot and heterogeneous fleet variants, and stochastic travel times. Exactly where exactness pays, heuristically where it does not, and always with a bound that tells the operator how much room is left.
Solve a route
The problem class
Four variants, one formulation.
Pickup and delivery with time windows.
Precedence, capacity, and time window constraints solved jointly rather than sequentially.
Multi-depot and heterogeneous fleet.
Vehicles with different capacities, costs, and eligibility routed across many depots simultaneously.
Stochastic travel times and demand.
Distributions on lane duration and demand quantity carried through to feasibility and cost.
The method
How the solve is structured.
Omega is the set of all feasible routes, which is exponentially large, so it is never enumerated. It is generated on demand.
The restricted master problem yields duals pi. The pricing subproblem, an elementary shortest path problem with resource constraints, searches for a route with negative reduced cost using a labeling algorithm with dominance pruning. When none exists, the linear relaxation is solved and the bound is exact.
Demand xi is a random variable, not a number on a manifest. Routes are admitted only if they respect capacity with confidence one minus alpha, which is set per customer rather than per solver.
Solver engineering
Choosing the method is the easy part.
The formulations above are standard and published. What is not published is knowing which one to reach for on a given instance, and what to do when the clock runs out before the proof does.
Instance shape drives decomposition.
Column generation dominates when routes are long and the customer count per route is modest. Compact formulations win on dense short-haul instances where the pricing subproblem stops paying for itself. Choosing wrong costs an order of magnitude, and the choice is made per instance rather than per customer.
Exact where it pays.
Exactness earns its cost when a decision is expensive to reverse or has to be defended: network design, capacity commitment, contractual service guarantees. On a dispatch that will be re-optimized within the hour, a strong heuristic carrying a measured gap is the better engineering answer.
Anytime by construction.
Every solver returns its best feasible solution with a bound at whatever moment it is interrupted. Optimality accrues with time. It is not a precondition for returning an answer.
An illustrative selection map by instance shape, not a fixed rule. The boundaries move with fleet, service policy, and horizon.
What this changes
What an operator actually gets.
A plan you can defend, because the gap is published alongside it.
Re-optimization in minutes rather than overnight batches.
Time windows treated as constraints rather than aspirations.
Where it runs
Sectors that lean on this capability.
If your network makes decisions under uncertainty, we should talk.
We work with a small number of operators at a time. Tell us what your network is optimizing for.
Start a conversation