The Vehicle Routing Problem (VRP) is classified as NP-hard — meaning no computer on earth can guarantee finding the perfect solution for a large delivery network in a reasonable timeframe. For a business running 50 stops across Sydney, the number of possible route sequences exceeds the number of atoms in the observable universe. Yet every morning, delivery managers somehow need to produce efficient routes before drivers clock on. The gap between mathematical perfection and operational reality is exactly where route optimization algorithms live — and understanding how they work helps you choose software that actually delivers.
What is the Vehicle Routing Problem
The Vehicle Routing Problem is a mathematical framework first formally described by George Dantzig and John Ramser in 1959. At its core, VRP asks: given a set of customers with known locations and a fleet of vehicles at one or more depots, what is the most cost-efficient set of routes that services all customers?
The "pure" VRP assumes unlimited vehicle capacity and no time constraints — which bears almost no resemblance to real delivery operations. That is why researchers have developed dozens of VRP variants that model real-world constraints:
- CVRP (Capacitated VRP): each vehicle has a weight or volume limit
- VRPTW (VRP with Time Windows): customers must be served within a specific time range
- MDVRP (Multi-Depot VRP): vehicles can depart from multiple depots
- VRPPD (VRP with Pickups and Deliveries): vehicles collect items as well as deliver them
- OVRP (Open VRP): vehicles do not need to return to the depot
Most commercial route planning software is solving one or more of these variants simultaneously. When a planner at a Melbourne florist maps 35 morning deliveries across Carlton, Fitzroy, and Collingwood with a 4-hour time window for each stop, the software is solving a CVRP+VRPTW problem — factoring vehicle load, delivery windows, and real road distances all at once.
Understanding what route optimization is helps frame why solving VRP matters: the difference between a good solution and a poor one can be tens of thousands of dollars per year in wasted fuel and overtime.
Common Route Optimization Algorithms
No single algorithm solves every routing problem optimally. Modern route optimization tools layer multiple approaches, using fast heuristics to build an initial solution and more sophisticated metaheuristics to improve it. Here is how the main approaches work:
Nearest Neighbour Heuristic
The simplest constructive algorithm. Starting from the depot, the algorithm repeatedly adds the closest unvisited stop until all stops are assigned. It is fast, intuitive, and produces a reasonable starting solution — but it tends to create inefficient "back-tracking" routes because it makes greedy local decisions without a global view.
A nearest-neighbour route for 20 Sydney stops might be 15% longer than optimal. That translates to roughly 45 extra kilometres per day, or around $27 in fuel at current Sydney diesel prices — over $9,000 per year for a single driver.
Clarke-Wright Savings Algorithm
Developed by G. Clarke and J.W. Wright in 1964 and still used in commercial software today. The savings algorithm starts with the worst-case scenario: every stop has its own dedicated vehicle making a round trip. It then calculates the "savings" achieved by merging two routes into one. The merge with the greatest saving is applied first, and the process repeats until no beneficial merges remain.
This is particularly effective for hub-and-spoke delivery networks common in Australian courier operations. A Brisbane logistics firm running 8 drivers from a Rocklea depot will often see route costs drop 20–30% compared to naive individual routing when savings-based construction is applied.
2-Opt and 3-Opt Local Search
Once an initial route is built, local search algorithms improve it by swapping segments. The 2-opt algorithm takes two edges in a route and reverses the path between them, checking if the resulting route is shorter. The process repeats until no improving swap exists — this is called a "locally optimal" 2-opt solution.
Three-opt extends the same idea to three edge swaps, finding improvements 2-opt misses. These algorithms are computationally inexpensive and highly effective for single-vehicle routes. Most routing software runs 2-opt as a standard post-processing step.
Genetic Algorithms
Genetic algorithms (GAs) mimic natural selection. A population of random routes is generated. Routes are evaluated on total distance, fuel cost, or time. The best routes are "bred" together — mixing segments from each parent solution — and random mutations are introduced. Over thousands of generations, the population converges toward near-optimal solutions.
GAs excel at VRP problems with complex, interacting constraints where local search gets stuck. They are computationally expensive but parallelise well on modern hardware. Route optimization platforms that advertise "AI-powered" routing often use genetic or evolutionary algorithms under the hood.
Simulated Annealing
Inspired by the metallurgical process of slowly cooling metal to reduce defects. The algorithm accepts worse solutions with a probability that decreases over time (the "temperature"). This escape from local optima allows simulated annealing to find solutions that pure greedy improvement would miss.
A simulated annealing solver run on a 100-stop Melbourne delivery problem will typically find solutions within 2–5% of theoretical optimum in under 30 seconds — practical for real-time route planning.
Ant Colony Optimisation (ACO)
ACO models the pheromone-trail behaviour of ant colonies. Artificial "ants" traverse the route network, depositing virtual pheromone on edges they travel. Shorter, faster paths accumulate more pheromone and attract future ants. Over many iterations, the strongest paths emerge as the optimised route.
ACO is particularly effective for dynamic routing problems where conditions change in real time — for example, a courier network where new delivery requests arrive throughout the day.
Algorithm Comparison Table
| Algorithm | Speed | Solution Quality | Best For | Limitation |
|---|---|---|---|---|
| Nearest Neighbour | Very fast | Fair (within 20–25% of optimal) | Quick initial solutions | Greedy, misses global improvements |
| Clarke-Wright Savings | Fast | Good (within 10–15% of optimal) | Multi-vehicle fleet routing | Less effective with tight time windows |
| 2-Opt / 3-Opt | Fast | Good (within 5–10% of optimal) | Improving existing routes | Can get stuck in local optima |
| Genetic Algorithm | Slow | Excellent (within 1–5% of optimal) | Complex, constrained VRP | Requires significant compute |
| Simulated Annealing | Medium | Very good (within 2–5% of optimal) | Escaping local optima | Requires tuning of cooling schedule |
| Ant Colony Optimisation | Medium | Very good (within 2–5% of optimal) | Dynamic, real-time routing | Complex to implement correctly |
| Hybrid (commercial tools) | Fast-Medium | Near-optimal | Production delivery software | Varies by vendor |
Most commercial route optimization tools — including RouteMate — use hybrid approaches: fast constructive heuristics build an initial solution, then metaheuristics like simulated annealing or genetic improvement refine it. This balances solution quality with the practical need to generate routes in seconds, not hours.
Constraints in Routing
The mathematical difficulty of VRP explodes as real-world constraints are added. Understanding the main constraint types helps delivery managers configure their routing software accurately — garbage in, garbage out applies to algorithms just as much as spreadsheets.
Time Windows
A time window constraint requires a stop to be served between a customer-specified earliest and latest time. Hard time windows fail the route if violated; soft time windows allow late arrivals but add a penalty cost.
For a Perth medical supply company serving aged care facilities, hard time windows are non-negotiable — medication deliveries must arrive before nursing shifts change. An algorithm that ignores time windows might produce a shorter route that is operationally useless.
Time windows interact in complex ways: serving stop A before stop B might be required to avoid backtracking, but stop A has an afternoon window and stop B a morning window. The algorithm must find a feasible sequencing or flag that no feasible solution exists.
Vehicle Capacity
Capacity constraints are either weight-based (a van rated to 1,200 kg) or volume-based (3.5 cubic metres of cargo space), or both. When a route's cumulative load exceeds the vehicle limit, the algorithm must split the work across multiple vehicles or routes.
A Sydney florist delivering 60 orders on Valentine's Day with two vans each rated at 400 arrangements must have capacity constraints set correctly — otherwise the algorithm may attempt to load 500 arrangements into a single van.
Driver Hours and Break Rules
Under Australia's Heavy Vehicle National Law (HVNL), commercial drivers must take mandatory rest breaks. A long-haul driver cannot continuously operate for more than 5.5 hours without a 15-minute break. Route algorithms that model driver fatigue rules prevent compliance violations and also prevent the planning of routes that look good on paper but are legally unworkable.
For metro delivery fleets in Sydney, Melbourne, and Brisbane not subject to HVNL, the relevant constraint is typically a shift-end deadline. Routes that would require a driver to work more than 8 hours trigger an automatic warning in properly configured routing software.
Skill-Based and Vehicle-Type Constraints
Some deliveries require specific vehicles (refrigerated van, caged truck) or driver certifications (dangerous goods licence, forklift ticket). Modern routing algorithms allow stop-level attributes that match stops to eligible vehicles and drivers. An Adelaide wine distributor delivering temperature-sensitive stock to restaurants needs the algorithm to assign those stops exclusively to refrigerated vehicles.
AI in Route Optimization
The term "AI" is used loosely in logistics software marketing, but genuinely new AI techniques are improving route optimization in measurable ways.
Machine Learning for Travel Time Prediction
Classical routing algorithms use static speed estimates on road segments — often based on posted speed limits or historical averages. Machine learning models trained on years of GPS probe data can predict travel times at specific times of day on specific days of the week with significantly higher accuracy.
Google's routing engine uses this approach, and dedicated logistics platforms are building proprietary ML models on fleet GPS data. A Melbourne courier network that knows, from 18 months of GPS history, that the Eastern Freeway runs at 35 km/h rather than 60 km/h between 4:00–5:30 pm on Fridays will build routes that arrive when promised — not when a spreadsheet predicted.
Reinforcement Learning for Dynamic Routing
Reinforcement learning (RL) agents learn routing policies through millions of simulated delivery episodes. Rather than solving each routing problem from scratch, an RL-trained agent can instantly respond to new orders, cancellations, and traffic disruptions by applying a learned policy.
This approach is particularly powerful for same-day delivery networks where the stop list changes constantly. Brisbane-based courier businesses handling on-demand deliveries are early adopters of RL-powered dynamic dispatch, where the algorithm continuously re-optimises routes as new jobs arrive throughout the day.
Neural Combinatorial Optimisation
A research frontier where deep learning models learn to solve combinatorial optimisation problems directly. Models like the Attention Model and Pointer Network can produce near-optimal VRP solutions faster than classical metaheuristics for medium-sized problems. These approaches are not yet mainstream in commercial software but represent the direction the field is heading.
The practical upshot: the best route optimization platforms today are not just running a single algorithm but orchestrating multiple ML and operations research techniques together. For a business comparing tools, the relevant question is not "which algorithm does it use?" but "how close to optimal are the routes it produces, and how fast?"
For a deeper look at the practical benefits this delivers, see the benefits of route optimization for delivery. And to understand how modern planning tools compare to each other, the ultimate guide to route optimization covers the full landscape.
FAQ
Q: Can route optimization algorithms find the mathematically perfect solution?
For large problems (over 20–30 stops with multiple constraints), guaranteed optimal solutions are computationally infeasible. Commercial tools find near-optimal solutions — typically within 1–5% of theoretical optimum — in seconds. The practical cost difference between "near-optimal" and "theoretically perfect" is negligible compared to the gap between optimized and manually planned routes.
Q: How does adding time windows affect route quality?
Time windows significantly increase problem complexity and can force longer routes when tight windows cluster in geographically inconvenient patterns. Good routing software will flag when time window constraints make a problem infeasible, rather than silently producing a route that violates them.
Q: Does road network data quality affect algorithm output?
Significantly. An algorithm is only as good as the road speed and distance data it consumes. Tools that rely on real-time traffic-adjusted travel times — like RouteMate, which uses Google Routes API data — produce more accurate ETAs and tighter routes than tools using static road data.
Q: How long does it take to compute an optimized route?
For typical delivery operations (10–200 stops, 1–20 vehicles), modern hybrid algorithms produce high-quality solutions in 1–30 seconds. Very large problems (500+ stops, complex constraints) may take a few minutes. Real-time dynamic re-routing for on-demand delivery networks requires sub-second response and typically uses approximation algorithms or pre-trained ML models.
Start Optimizing Your Routes Today
RouteMate applies multi-algorithm optimization to your deliveries — handling time windows, vehicle capacity, and driver hours without manual configuration. Import your stops, set your constraints, and get optimized routes in seconds.