How Our VRP Solver Finds Optimal Delivery Routes

Route optimization might sound simple — just find the shortest path through a list of stops. In reality, the Vehicle Routing Problem (VRP) is one of the most studied problems in operations research, and solving it efficiently for real-world logistics requires serious engineering.

The Problem

Given a set of delivery stops, a fleet of vehicles (each with capacity limits), and constraints like delivery time windows and driver breaks, find the assignment of stops to vehicles and the sequence of stops for each vehicle that minimizes total cost (distance, time, or a combination).

This is an NP-hard problem, meaning there's no known algorithm that can guarantee the optimal solution in reasonable time for large instances. A fleet of 5 vehicles serving 50 stops has more possible route combinations than atoms in the universe.

Our Approach

QDS Routes uses a production-grade optimization engine that combines several techniques:

• Construction heuristics: The solver first builds an initial feasible solution using greedy algorithms that respect all constraints.
• Local search: The initial solution is then improved through neighborhood search operations — swapping stops between routes, reordering sequences, and moving stops to different vehicles.
• Metaheuristics: Advanced strategies like guided local search help escape local optima and explore the solution space more broadly.

Real Road Distances

A critical differentiator is how we calculate distances between stops. Many optimization tools use straight-line (Euclidean) distance, which can be wildly inaccurate — a river, highway, or one-way street system can make the actual driving distance 2-3x the straight-line distance.

QDS Routes uses self-hosted routing infrastructure that calculates actual driving distances and durations based on real road networks. This infrastructure runs on our own dedicated servers with no third-party API dependency, meaning no rate limits, no per-call costs, and consistent performance regardless of query volume.

Constraints We Handle

The solver supports a comprehensive set of real-world constraints:

• Time windows: Each stop can have a delivery window (e.g., "between 9am and 12pm"). The solver ensures vehicles arrive within the specified window.
• Vehicle capacity: Weight, volume, and item count limits are respected across all stops assigned to each vehicle.
• Lunch breaks: Mandatory rest periods are inserted into routes at appropriate times, complying with labor regulations.
• Service time: The time required at each stop (calculated from demand volume) is factored into route timing.
• Multiple depots: Vehicles can start and end at different locations.

Performance

For typical workloads (10-200 stops, 2-20 vehicles), the solver returns optimized routes in under 30 seconds. Larger instances may take longer but always produce a feasible solution within the configured time limit, with quality improving as more time is allowed.