1. Portfolio
  2. Problem Families
  3. Routing

Routing Problems

Optimal Paths Through Complex Networks

From the classical Traveling Salesman Problem to time-windowed vehicle routing, this family addresses the fundamental challenge of finding minimum-cost traversals across graphs and networks. These NP-hard problems underpin modern logistics, transportation, and supply chain optimization.

8
Problems
498
Tests
48
Algorithms
19
Variants

Quick Navigation

TSP CVRP VRPTW Variants Exact Methods Hierarchy References

Traveling Salesman Problem

TSP / ATSP — NP-hard (Karp, 1972)
92 tests 8 Python files 10 test classes

Given n cities and pairwise distances, find the shortest Hamiltonian cycle visiting each city exactly once and returning to the start. The symmetric variant (TSP) uses undirected distances; the asymmetric variant (ATSP) uses directed distances where d(i,j) ≠ d(j,i). One of the most studied combinatorial optimization problems, serving as the benchmark for algorithm development since the 1950s.

Logistics Circuit Board Drilling DNA Sequencing Telescope Scheduling Warehouse Picking Ride-Sharing Routing

Mathematical Formulation

Dantzig-Fulkerson-Johnson Formulation min ∑i ∑j≠i dij · xij
s.t. ∑j≠i xij = 1   ∀ i ∈ V  /* leave each city once */
     ∑i≠j xij = 1   ∀ j ∈ V  /* enter each city once */
     ∑i∈S ∑j∈S xij ≤ |S| - 1   ∀ S ⊂ V, 2 ≤ |S| ≤ n-1  /* subtour elimination */
     xij ∈ {0, 1}

Directed arc formulation (covers both symmetric TSP and ATSP). For symmetric TSP, add xij = xji or use undirected edge variables with degree-2 constraints.

Algorithm Comparison
Algorithm Type Complexity Reference Notes
Held-Karp DP Exact O(2n · n²) Held & Karp (1962) Subset DP (bitmask), optimal for n ≤ 23
Branch & Bound Exact Exponential Held & Karp (1970) 1-tree lower bound, NN warm-start
Nearest Neighbor Heuristic O(n²) Rosenkrantz et al. (1977) Greedy construction, multi-start variant
Cheapest Insertion Heuristic O(n³) Rosenkrantz et al. (1977) 2-approx. for metric TSP (triangle inequality required)
Christofides’ Algorithm Heuristic O(n³) Christofides (1976) 3/2-approx. for metric TSP; MST + min-weight perfect matching
Farthest Insertion Heuristic O(n³) Rosenkrantz et al. (1977) Builds tour from farthest cities first
Nearest Insertion Heuristic O(n³) Rosenkrantz et al. (1977) Insert nearest unvisited city
Greedy (Nearest Edge) Heuristic O(n² log n) — Edge-based greedy construction
Lin-Kernighan Local Search O(n2.2) empirical Lin & Kernighan (1973) Variable-depth k-opt; gold-standard practical TSP heuristic
2-opt / Or-opt / VND Local Search O(n²) per iter Croes (1958); Lin (1965); Or (1976) Segment reversal, segment relocation, VND
Simulated Annealing Metaheuristic O(n² · T) Kirkpatrick et al. (1983) 2-opt moves, auto-calibrated temperature
Genetic Algorithm Metaheuristic O(pop · n · gen) Davis (1985) OX crossover, swap mutation, optional 2-opt LS
Benchmark Instances
Instance Cities Optimal Type
small4 4 Known Verification instance
small5 5 Known Verification instance
gr17 17 2016 TSPLIB symmetric

Standard benchmarks: TSPLIB (Reinelt, 1991) is the definitive benchmark library with symmetric and asymmetric instances from 14 to 85,900 cities. The gr17 instance above is from TSPLIB.

Key Concepts
Metric vs General TSP

Metric TSP satisfies the triangle inequality (dik ≤ dij + djk). Approximation guarantees (Christofides 3/2, insertion 2×) hold only for metric instances.

1-Tree Lower Bound

A minimum spanning tree on n−1 nodes plus two cheapest edges to the excluded node. Strengthened by Lagrangian relaxation (Held & Karp, 1970).

Concorde Solver

Branch-and-cut solver (Applegate et al., 2006) that has solved TSPLIB instances with 85,900 cities to proven optimality. The gold standard for exact TSP.

View Source

Try It Yourself

Instance
8
City Map & Tour
Generate cities and solve to see the tour.
Algorithms
Nearest Neighbor (H) Greedy Edge (H) Cheapest Insert (H) 2-Opt (LS) Sim. Annealing (M) Held-Karp DP (E)
Results
Algorithm Distance Time Gap
No results yet
Click "Random" to generate cities, then "Solve" to compare algorithms.
Need to Solve Larger Instances?

This demo handles up to 15 cities for educational purposes. For real-world instances, custom solutions, or research collaboration:

 Get in Touch  LinkedIn

Capacitated Vehicle Routing Problem

CVRP — NP-hard (generalizes TSP + Bin Packing)
88 tests 5 Python files 8 test classes

Given n customers with demands, a depot, and a fleet of identical vehicles with capacity Q, find a set of routes (depot → customers → depot) that minimize total travel distance while visiting each customer exactly once and respecting vehicle capacity. CVRP simultaneously addresses the clustering of customers into feasible routes and the sequencing of customers within each route.

Last-Mile Delivery Waste Collection Fuel Distribution Cold Chain Logistics Field Service

Mathematical Formulation

Two-Index Vehicle Flow Formulation min ∑i ∑j dij · xij
s.t. ∑j≠i xij = 1   ∀ i ∈ V \ {0}  /* leave each customer once */
     ∑i≠j xij = 1   ∀ j ∈ V \ {0}  /* enter each customer once */
     ∑j x0j = K  /* K vehicles leave depot */
     ∑i xi0 = K  /* K vehicles return to depot */
     ∑i∈S ∑j∉S xij ≥ ⌈∑i∈S qi / Q⌉   ∀ S ⊆ V \ {0}  /* capacity cuts */
     xij ∈ {0, 1}

K = number of vehicles (given constant or upper bound). qi = demand of customer i, Q = vehicle capacity.

Algorithm Comparison
Algorithm Type Complexity Reference Notes
Clarke-Wright Savings Heuristic O(n² log n) Clarke & Wright (1964) Merge route pairs by largest savings s(i,j) = d(0,i) + d(0,j) - d(i,j)
Sweep Algorithm Heuristic O(n log n) Gillett & Miller (1974) Angular sweep from depot, multi-start variant
Simulated Annealing Metaheuristic O(n² · T) Osman (1993) Relocate, swap, 2-opt* inter-route neighborhoods
Genetic Algorithm Metaheuristic O(pop · n · gen) Prins (2004) Giant-tour encoding, OX crossover, split decoder
ALNS Metaheuristic O(n² · T) Ropke & Pisinger (2006) Adaptive Large Neighborhood Search; destroy-repair with operator selection
Key Concepts
Savings Criterion

s(i,j) = d(0,i) + d(0,j) - d(i,j) measures the distance saved by serving customers i and j on the same route instead of separate trips.

Giant-Tour Encoding

A single permutation of all customers is split into capacity-feasible routes via optimal splitting (Prins, 2004), enabling standard TSP operators.

Standard benchmarks: Classic Augerat A/B/P sets (1995) and the modern Uchoa set (2017, up to 1,000 customers) are available at CVRPLIB. Exact state-of-the-art uses branch-and-cut-and-price (Pecin et al., 2017).

View Source

Try It Yourself

Instance
6 50
Route Map
Generate customers and solve to see routes.
Algorithms
Clarke-Wright (H) Sweep (H) Nearest Neighbor (H)
Results
AlgorithmDistanceVehiclesTime
No results yet
Click "Random" to generate customers, then "Solve".
Need to Solve Larger Instances?

This demo handles up to 12 customers. For real-world routing with hundreds of stops:

 Get in Touch  LinkedIn

Vehicle Routing with Time Windows

VRPTW — Strongly NP-hard (generalizes CVRP)
82 tests 4 Python files 8 test classes

Extends the CVRP with time window constraints [ei, li] for each customer. Vehicles must arrive at customer i no later than li; if arriving before ei, they must wait. Each customer requires si service time. The depot has a planning horizon [E0, L0]. The interplay between capacity constraints and time feasibility makes VRPTW significantly harder than CVRP.

E-Commerce Delivery Home Healthcare School Bus Routing Meal Delivery Bank Courier Services Drone Delivery Last-Mile Logistics

Mathematical Formulation

VRPTW 3-Index Formulation with Time Variables min ∑k ∑i ∑j dij · xijk
s.t. ∑k ∑j xijk = 1   ∀ i ∈ V \ {0}  /* visit each customer once */
     ∑i xihk - ∑j xhjk = 0   ∀ h ∈ V \ {0}, ∀ k  /* flow conservation */
     ∑j x0jk = 1   ∀ k  /* each vehicle leaves depot */
     ∑i xi0k = 1   ∀ k  /* each vehicle returns to depot */
     ∑i qi · ∑j xijk ≤ Q   ∀ k  /* vehicle capacity */
     wik + si + tij - M(1 - xijk) ≤ wjk   ∀ i,j,k  /* time consistency */
     ei ≤ wik ≤ li   ∀ i, k  /* time windows */
     xijk ∈ {0, 1}

Variables: xijk = 1 if vehicle k travels arc (i,j); wik = service start time of customer i on vehicle k. Parameters: si = service time; tij = travel time (tij = dij/speed, or tij = dij when unit speed); M = large constant (tight: M = li + si + tij - ej). This is a teaching formulation; exact VRPTW solvers typically use set-partitioning / branch-and-price.

Algorithm Comparison
Algorithm Type Complexity Reference Notes
Solomon I1 Insertion Heuristic O(n² K) Solomon (1987) Composite insertion criterion: distance + urgency
Nearest Neighbor TW Heuristic O(n²) Solomon (1987) Greedy nearest feasible customer with TW checks
Simulated Annealing Metaheuristic O(n² · T) Cordeau et al. (2001) Relocate/swap with time window feasibility checks
Genetic Algorithm Metaheuristic O(pop · n · gen) Potvin & Bengio (1996) Giant-tour encoding, TW-aware split decoder
ALNS Metaheuristic O(n² · T) Ropke & Pisinger (2006) Adaptive destroy-repair; dominant modern VRPTW metaheuristic
Benchmark Instances
Instance Customers Type Description
solomon_c101_mini 8 Clustered Subset of Solomon C101 benchmark, clustered customers
tight_tw5 5 Narrow TW Tight time windows forcing specific sequencing

Solomon (1987) benchmark classes: C (clustered), R (random), RC (mixed) with 25–100 customers. Extended by Gehring & Homberger (1999) to 200–1,000 customers. Exact methods use branch-and-price (Desrochers et al., 1992).

Key Concepts
Time Windows

Interval [ei, li] during which service can begin. Early arrival causes waiting; late arrival is infeasible.

Solomon I1 Criterion

Combines geographic proximity with temporal urgency to select the best insertion position for unrouted customers.

TW-Aware Split

Extends the Prins split procedure to enforce time window feasibility when partitioning the giant tour into vehicle routes.

View Source

Try It Yourself — VRPTW demo

Instance
6
Click Random or 6-Customer Example to generate customers with time windows, demands, and service times.
Route Map
Route Timeline
Algorithms
Results
AlgorithmDistanceVehiclesFeasibleTime
Awaiting instance generation.
Time Window Feasibility

A route is feasible if every customer is reached before its late window li. Early arrivals cause waiting (shown in the timeline). The timeline shows each vehicle’s schedule: travel (dark), waiting (striped), and service (solid) segments.

Full Source

Problem Variants

Extensions and specializations of the core routing problems implemented in this repository

Asymmetric TSP

ATSP — d(i,j) ≠ d(j,i)

Directed distances break symmetry, making the problem materially harder — Christofides’ 3/2-approximation does not apply. Applications include one-way streets, flight routing, and task sequencing with direction-dependent setup times.

Flight Routing One-Way Networks

Multi-Depot VRP

MDVRP — multiple depot locations

Vehicles are stationed at multiple depots. Each customer is assigned to a depot and served by that depot’s fleet. Combines facility assignment with vehicle routing.

Distribution Networks Urban Logistics
Pickup & Delivery
PDPTW — paired pickup-delivery with TW

Each request has a pickup and delivery location with precedence constraint (pickup before delivery) on the same vehicle. Adds pairing and precedence to VRPTW constraints.

Ride-Hailing Dial-a-Ride
Open VRP
OVRP — no return to depot

Vehicles end their routes at the last customer instead of returning to the depot. Models contractor-based deliveries where drivers go home after their last stop.

Contract Delivery
Electric VRP
EVRP — battery + recharging stations

Vehicles have limited battery range and may need to detour to recharging stations. Adds energy consumption modeling and recharge scheduling to CVRP.

Green Logistics Sustainability
Split Delivery VRP
SDVRP — demand > vehicle capacity allowed

A customer’s demand may be split across multiple vehicles. Relaxes the single-visit constraint, potentially reducing total distance at the cost of coordination complexity.

Bulk Delivery

References

TSP Foundations

Dantzig, G., Fulkerson, R. & Johnson, S. (1954). Solution of a large-scale traveling-salesman problem. JORS, 2(4).

Held, M. & Karp, R. (1962). A dynamic programming approach to sequencing problems. JSIAM, 10(1).

Held, M. & Karp, R. (1970). The traveling-salesman problem and minimum spanning trees. Operations Research, 18(6).

Christofides, N. (1976). Worst-case analysis of a new heuristic for the travelling salesman problem. Tech. Report 388, CMU.

Lin, S. & Kernighan, B. (1973). An effective heuristic algorithm for the TSP. Operations Research, 21(2).

Croes, G. (1958). A method for solving traveling-salesman problems. Operations Research, 6(6).

Davis, L. (1985). Applying adaptive algorithms to epistatic domains. IJCAI-85.

Reinelt, G. (1991). TSPLIB — A traveling salesman problem library. ORSA J. Computing, 3(4).

Applegate, D. et al. (2006). The Traveling Salesman Problem: A Computational Study. Princeton.

Rosenkrantz, D., Stearns, R. & Lewis, P. (1977). An analysis of several heuristics for the TSP. SIAM J. Computing, 6(3).

VRP & VRPTW

Clarke, G. & Wright, J. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4).

Solomon, M. (1987). Algorithms for the VRPTW. Operations Research, 35(2).

Prins, C. (2004). A simple and effective evolutionary algorithm for the VRP. Computers & OR, 31(12).

Ropke, S. & Pisinger, D. (2006). An adaptive large neighborhood search heuristic for the PDPTW. Transportation Science, 40(4).

Cordeau, J.-F., Laporte, G. & Mercier, A. (2001). A unified tabu search heuristic for VRPs with TW. JORS, 52(8).

Desrochers, M., Desrosiers, J. & Solomon, M. (1992). A new optimization algorithm for the VRPTW. Operations Research, 40(2).

Toth, P. & Vigo, D. (2014). Vehicle Routing: Problems, Methods, and Applications. 2nd ed., SIAM.

Potvin, J.-Y. & Bengio, S. (1996). The vehicle routing problem with time windows — Part II: Genetic search. INFORMS J. Computing, 8(2).

Exact Methods in Practice

How large routing instances are solved to proven optimality

Branch-and-Cut (TSP)

Solves the LP relaxation of the DFJ formulation, identifies violated subtour-elimination constraints (cutting planes), adds them dynamically, and branches on fractional variables. The Concorde solver (Applegate et al., 2006) has solved TSPLIB instances with up to 85,900 cities to proven optimality using this approach.

Key: Padberg & Rinaldi (1991) — polyhedral study of TSP polytope, comb inequalities

Branch-and-Price (CVRP)

Reformulates CVRP as a set-partitioning problem: choose a minimum-cost subset of feasible routes covering all customers. The exponential number of routes is handled by column generation — a pricing subproblem (shortest path with resource constraints) generates promising routes on the fly.

State-of-art: Pecin et al. (2017) — branch-cut-and-price solves instances up to ~300 customers
Branch-and-Price (VRPTW)

Extends the CVRP approach: the pricing subproblem becomes an elementary shortest path with resource constraints (ESPPRC), where time windows add a time resource alongside capacity. Desrochers, Desrosiers & Solomon (1992) established the foundational column-generation framework.

The 3-index formulation (on this page) is for teaching; practical solvers use set partitioning
When to Use What

● Small instances (n ≤ 20–25): Exact methods (Held-Karp DP, B&B) find proven optima. Good for teaching and verification.

● Medium instances (n ≤ 300): Branch-and-cut/price can solve to optimality. Construction + local search for fast approximations.

● Large instances (n > 300): LKH for TSP; ALNS / LNS for VRP/VRPTW. Metaheuristics dominate practical large-scale routing.

Problem Hierarchy

The routing family forms a natural generalization chain (simplified view)

Traveling Salesman Problem
Single vehicle, no side constraints
+ Multiple vehicles + Capacity Q
Capacitated Vehicle Routing
Fleet of vehicles, capacity limits
+ Time windows [ei, li] + Service times
Vehicle Routing with Time Windows
Capacity + temporal constraints
Portfolio
ESC
↑↓ navigate ↵ open
Search across all problems