What is TSP (Traveling Salesman Problem)?
The Traveling Salesman Problem asks: given a list of locations, what is the shortest possible route that visits each one exactly once and returns to the starting point? [8, 10]
In delivery terms, TSP answers: "What is the best route for a single driver with a fixed list of stops?" TSP is the right framework for solo delivery drivers and single-vehicle route planning apps.
What is VRP (Vehicle Routing Problem)?
VRP extends TSP to multiple vehicles. It asks: given a fleet of vehicles and a pool of delivery stops, how do you assign stops to vehicles and sequence each vehicle's route to minimise total cost? [8, 9, 10]
VRP is fundamentally harder than TSP because it adds a new decision: which stops should each vehicle handle? The algorithm must optimise both assignment and sequencing across the entire fleet simultaneously.
In delivery terms, VRP answers: "How do I divide and sequence deliveries across a team of drivers?"
VRP extensions for real-world operations
Standard VRP makes assumptions that real-world operations often violate. Key extensions: [10]
- CVRP (Capacitated VRP): Each vehicle has a weight or volume limit. Essential for grocery, pharmacy, or multi-piece freight delivery.
- VRPTW (VRP with Time Windows): Each delivery must occur within a specified time range. The most practically important extension for last-mile couriers.
- PDPTW (Pickup and Delivery Problem with Time Windows): Each shipment has a specific pickup and delivery location, both with time windows.
- MDVRP (Multi-Depot VRP): Vehicles start from multiple depots. Critical for regional couriers and 3PLs with multiple hubs.
- VRPB (VRP with Backhauls): Some stops are pickups after deliveries are made. Common in distribution operations.
TSP vs VRP: side-by-side
| Dimension | TSP | VRP |
|---|---|---|
| Number of vehicles | 1 | 2 or more |
| Core question | Best route for one driver? | How to divide and route a fleet? |
| Decision type | Sequencing only | Assignment + sequencing |
| Computational difficulty | Moderate | High (NP-hard; approximations used) [10] |
| Typical use case | Solo driver apps | Dispatch platforms for fleets |
| Extensions available | Limited | CVRP, VRPTW, PDPTW, MDVRP, VRPB |
| Who it's for | Individual drivers | Dispatchers managing teams |
Which one does your operation need?
You need TSP-based tools if: you are the driver, each driver plans their own route independently, or you're using a personal route planner app.
You need VRP-based software if: you have 2 or more drivers sharing a pool of deliveries, a dispatcher assigns stops from a central dashboard, or you're managing a fleet.
You need VRP with extensions if: time windows must be honoured (VRPTW), vehicles have weight or volume limits (CVRP), you operate from multiple terminals (MDVRP), or you handle both pickups and deliveries on the same routes (PDPTW).
How modern delivery software uses these algorithms
No production route optimisation software runs pure TSP or VRP. The actual implementations are approximation algorithms — heuristics and metaheuristics that find near-optimal solutions quickly. [10, 11]
- Clarke-Wright savings algorithm: Builds multi-vehicle routes by merging single-vehicle routes wherever merging saves distance. [9]
- Local search / 2-opt: Iteratively improves existing routes by swapping pairs of stops to reduce total distance.
- Google OR-Tools: An open-source constraint programming library many SaaS platforms use for VRP solving. [11]
What to ask vendors when evaluating routing software
- Does it support time windows? (VRPTW)
- Does it respect vehicle capacity limits? (CVRP)
- Does it handle multiple depots or terminals? (MDVRP)
- Can it configure toll, highway, or ferry avoidance?
- Does it cluster stops sensibly by area or customer?
- Can it re-optimise when orders are added or cancelled mid-day?
Alchemira's Route Builder supports multi-vehicle optimisation with delivery time-window constraints, toll/highway/ferry avoidance, and auto-clustering by terminal, customer, and geography. [1]