Vehicle routing step by step
About this app
One depot, 16 customers, four vans with 40 crates each: the Clarke–Wright savings algorithm turns out-and-back trips into four routes, rejected pairs light up with their reason, then 2-opt shortens every route. Load bars per van, the falling total distance and the sweep method for comparison.
The idea
In the vehicle routing problem (VRP), vehicles with a limited capacity Q serve several customers from one depot, and the total distance should be as short as possible. The Clarke-Wright savings algorithm starts with out-and-back trips depot → customer → depot. For every pair of customers it computes the saving s_ij = d_0i + d_0j − d_ij, the distance saved when one vehicle visits i and j in a row. Pairs are processed in descending order: two routes are joined if i and j each sit at a route end and the combined load does not exceed Q. The result is a heuristic, not a guaranteed optimum.
What you see
One depot, 16 customers with their demand, and four vehicles carrying 40 crates each. The app runs in phases: out-and-back trips, savings for all 120 customer pairs, merging by Clarke-Wright, then 2-opt on each route. Every rejected merge lights up in red with its reason, such as “capacity” or “not a route end”. Load bars show how full each vehicle is, and a curve tracks the falling total distance. For comparison you can switch to the sweep method, where a ray turns around the depot and assigns customers to vehicles by angle.
Things to try
Step through the savings list with Next or let it play; the arrow keys move back and forth. Hover over a row in the list and the map shows the triangle depot–i–j that the saving comes from. Notice that not every large saving gets used. At the end, compare the two methods: in this example sweep with 2-opt reaches 97.53 km, savings with 2-opt 91.21 km. Coordinates and demands form a fixed, made-up instance.
Frequently asked questions
- How does the Clarke-Wright savings algorithm work?
- Each customer first gets its own out-and-back route from the depot. For every pair the saving s_ij = d_0i + d_0j − d_ij is computed, and the list is sorted in descending order. Going down the list, two routes are joined via the edge i–j whenever both customers are at the end of their route and the vehicle capacity is not exceeded.
- What is the difference between the savings and the sweep method?
- The savings method merges routes by the largest distance saving. The sweep method rotates a ray around the depot, orders customers by angle and fills vehicles in that order until capacity is reached, so it splits the area into sectors. Which one gives shorter routes depends on where the customers are.
- What does 2-opt do in vehicle routing?
- 2-opt improves a single route. It removes two edges, reverses the segment between them and reconnects it with two new edges whenever that makes the route shorter. This repeats until no reversal helps any more, which also removes crossings from the route.
- Can I enter my own customers or demands in the app?
- No, the app uses a fixed instance of 16 customers, four vehicles and a capacity of 40 crates. The data panel lists all coordinates and demands, so every step and intermediate result can be checked by hand.
Subject: Operations research
More from Operations research
- Big M: Nebenbedingungen an- und ausschalten
- Dijkstra's algorithm
- Ganzzahlig ist anders: LP gegen IP
- Konvexe Mengen, Hülle und Ecken
- Linear problems made visual
- Nebenbedingungen verschärfen (Tightening)
- Simplex in space
- Simplex algorithm
A VisuApp by heyprof: interactive, free in your browser, no sign-up. What is a VisuApp? · All apps