Vehicle Routing Solver

Pseudocode

Routing several vehicles from one depot is TSP with an extra decision layer: first partition the customers among vehicles, then sequence each vehicle route.

// Cluster-first, route-second
MultiVehicleRouting(depot, customers, vehicleCount):
    clusters = partition customers into vehicleCount groups
                (by angle around the depot, or by k-means)
    for each cluster:
        route = solveTSP(depot + cluster)

// Then improve across routes:
repeat until no improvement:
    relocate: move one customer to another route
    exchange: swap two customers between routes
    2-opt:    uncross edges within a single route

The two-phase structure matters because the phases pull against each other. A clustering that looks balanced geometrically can produce routes that are individually awkward, and the cross-route improvement moves are what repair that. Skipping the improvement phase typically leaves 10 to 20 percent on the table, which is far more than any gain from a better initial clustering.

Worked example, step by step

Serve four customers from a central depot using two vehicles, and see why the obvious split beats the alternative.

Example graph: Depot at the origin. Customers north at (0,5), south at (0,-5), east at (5,0) and west at (-5,0). Travel cost is straight-line distance, and each vehicle starts and ends at the depot.

1. Split by opposite pairs. Give vehicle 1 the north and south customers, vehicle 2 the east and west ones. Vehicle 1 travels depot to north (5), north to south (10), south to depot (5), totalling 20. Vehicle 2 is identical by symmetry, so the combined cost is 40.
2. Split by adjacent pairs. Give vehicle 1 north and east, vehicle 2 south and west. Vehicle 1 travels depot to north (5), north to east (about 7.07), east to depot (5), totalling about 17.07. Vehicle 2 matches it, giving about 34.14 in total.
3. Compare. The adjacent-pair split saves nearly 6 units, about 15 percent. The reason is that the opposite-pair split forces each vehicle to cross the depot region twice, traversing the long diameter, while the adjacent split keeps each route within one quadrant pair.
4. Why angular clustering finds this. Sweeping by angle around the depot groups geometrically adjacent customers automatically, which is exactly the structure that produces short routes. A clustering that ignores angle, such as splitting on x-coordinate alone, can easily produce the worse pairing.

The better assignment costs about 34.14 against 40, purely from which customers share a vehicle. Sequencing within each route was trivial here since two customers admit only one order, so the entire difference came from the partitioning decision. That is the general lesson of multi-vehicle routing: the assignment usually matters more than the sequencing, which is the opposite of single-vehicle TSP where sequencing is the whole problem.

Complexity, and where it comes from

Time: NP-hard; O(n^2) per improvement pass · Space: O(n + V)

The problem contains TSP as the special case of a single vehicle, so it is NP-hard, and adding the partitioning decision makes it strictly harder in practice: there are Stirling-number-many ways to split n customers among V vehicles before any sequencing is considered. The cluster-first phase costs O(n log n) for an angular sweep or O(n·V·i) for k-means. Each TSP subproblem is solved heuristically, typically nearest neighbour plus 2-opt at O(m squared) per route for m customers. Cross-route improvement examines O(n squared) candidate relocations and exchanges per pass. Exact methods based on branch and price handle roughly 100 customers; heuristics scale to thousands.

When to use Fleet Dispatching (mTSP), and when not to

The vehicle routing family is a set of increasingly constrained variants. Match the model to the real constraints or the solution will be infeasible.

Common pitfalls

• Optimising each route in isolation. Perfect sequencing within a bad partition still gives a bad solution. Cross-route moves that relocate or exchange customers between vehicles are where most of the improvement comes from, and they are frequently omitted.
• Clustering without regard to the depot. Grouping customers by raw proximity to each other, rather than by angle around the depot, produces routes that double back across the depot region. The example above shows the cost of getting this wrong even with four customers.
• Forcing all vehicles to be used. When demand is low, using fewer vehicles is often cheaper once fixed costs are counted. Requiring every vehicle to carry something can make the answer worse than the true optimum.
• Treating it as independent TSPs. Solving V separate TSPs after a fixed partition ignores the interaction entirely. The partition and the sequencing are coupled, which is why the two-phase method iterates rather than running each phase once.
• Using Euclidean distance for road travel. Straight-line distance ignores one-way systems, turn restrictions and actual road topology. Real routing needs a distance matrix built from shortest paths on the road network.

Frequently asked questions

What is the multi-vehicle routing problem?

It asks how to serve a set of customers from a depot using several vehicles, minimising total travel cost, where each vehicle starts and ends at the depot and every customer is visited exactly once. It generalises the travelling salesman problem by adding the decision of which vehicle serves which customers.

How is it different from TSP?

TSP routes a single vehicle through every customer, so the only decision is the order. Multi-vehicle routing adds a partitioning decision: which customers each vehicle serves. That assignment usually has a larger effect on total cost than the sequencing within each route, which reverses the emphasis from TSP.

What is the cluster-first route-second approach?

It splits the problem into two phases. First partition customers into groups, one per vehicle, typically by sweeping angles around the depot or by k-means. Then solve each group as an independent TSP. Cross-route improvement moves that relocate or exchange customers between vehicles are then applied to repair weaknesses in the initial partition.

What is the time complexity of vehicle routing?

It is NP-hard, containing TSP as a special case. Construction heuristics run in O(n squared) or so, and local search passes examining relocations and exchanges cost O(n squared) each. Exact branch-and-price methods handle around 100 customers, while heuristics scale to thousands with solutions typically within a few percent of optimal.

What is the difference between VRP and CVRP?

The capacitated version adds a load limit per vehicle and a demand per customer, so any partition must keep each vehicle within capacity. That turns the assignment phase into a bin-packing problem alongside the routing, and it is the variant that matches most real distribution operations.