Logistics & Transportation
Routing · Hub Design · Fleet · Dispatch
Logistics is arguably the most studied domain in operations research. The Travelling Salesman Problem has driven combinatorial optimisation since the 1930s, and the Vehicle Routing Problem introduced by Dantzig & Ramser in 1959 remains a cornerstone of applied OR — three problems that illustrate how mathematical models transform everyday delivery, warehousing, and field-service operations.
The Capacitated Vehicle Routing Problem (CVRP) was introduced by Dantzig & Ramser (1959) in the context of gasoline delivery. Each vehicle departs from a depot, visits a subset of customers whose total demand does not exceed vehicle capacity, and returns. The goal is to minimise total route distance. Clarke & Wright (1964) proposed a savings heuristic that remains a practical baseline — it starts with one route per customer and iteratively merges routes when the savings from combining them exceed the extra cost.
Problem type: Capacitated Vehicle Routing (CVRP). Assign customers to vehicle routes and sequence visits within each route to minimise total travel distance, subject to vehicle capacity constraints. All routes begin and end at the depot.
s.t. Σj x_ij = 1 ∀ customer i // each visited once
Σi∈S d_i ≤ Q ∀ route S // capacity
x_ij ∈ {0,1} // binary edge selection
// subtour elimination via MTZ or cut callbacks
CVRP Solver
- Dantzig, G. & Ramser, J. (1959). The truck dispatching problem. Management Science, 6(1), 80-91. Published
- Clarke, G. & Wright, J. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 568-581. Published
- UPS ORION (On-Road Integrated Optimization & Navigation). Deployed across 55,000+ routes, saving 100 million miles per year. Operational
The 1D Bin Packing Problem asks: given items of various sizes and bins of uniform capacity, pack all items using the fewest bins. Garey, Graham & Ullman (1972) showed that First Fit Decreasing (FFD) — sorting items large-to-small then placing each in the first bin that fits — uses at most (11/9)OPT + 6/9 bins. Johnson (1974) tightened bounds and showed FFD performs within 22% of optimal in the worst case. In warehouse operations, this maps directly to packing orders into shipping cartons, palletising goods, or loading truck compartments.
Problem type: 1D Bin Packing (NP-hard). Assign items with known sizes to unit-capacity bins, minimising the number of bins used, subject to the constraint that total size in each bin does not exceed capacity.
s.t. Σj x_ij = 1 ∀ item i // each item assigned once
Σi s_i · x_ij ≤ C · y_j ∀ bin j // capacity
x_ij, y_j ∈ {0,1}
Bin Packing Solver
- Garey, M., Graham, R. & Ullman, J. (1972). Worst-case analysis of memory allocation algorithms. Proceedings of the 4th ACM Symposium on Theory of Computing, 143-150. Published
- Johnson, D. (1974). Fast algorithms for bin packing. Journal of Computer and System Sciences, 8(3), 272-314. Published
The Vehicle Routing Problem with Time Windows (VRPTW) adds appointment constraints to the standard VRP: each customer must be served within a specified time interval. Solomon (1987) introduced benchmark instances that remain standard today. In technician dispatch, skill requirements add another dimension — a repair job may require a specific certification. Cordeau, Laporte, Pasin & Ropke (2005) showed that metaheuristics for the VRPTW with heterogeneous skills can reduce fleet costs by 15-25% over manual scheduling.
Problem type: VRPTW with skill constraints. Assign service calls to technicians and sequence visits so that each call is served within its time window by a technician with the required skill, minimising total travel time and tardiness.
s.t. a_i ≤ start_i ≤ b_i ∀ call i // time window
skill(tech_k) ⊇ req(call_i) // skill match
start_j ≥ start_i + service_i + travel_ij // sequencing
Σk x_ik = 1 ∀ call i // each call assigned once
Technician Dispatch Solver
- Solomon, M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35(2), 254-265. Published
- Cordeau, J.-F., Laporte, G., Pasin, F. & Ropke, S. (2010). Scheduling technicians and tasks in a telecommunications company. Journal of Scheduling, 13, 393-409. Published
All Logistics & Transport Applications
Browse the complete collection