- What vehicle routing and the traveling salesman problem are
- Visual map of routing
- Example data: a depot and 5 customers
- Nearest neighbor: building the route
- 2-opt improvement: swapping two legs
- From the traveling salesman to vehicle routing
- Where routing fits in operations
- Common mistakes and limitations
- Frequently asked questions
What vehicle routing and the traveling salesman problem are
Vehicle routing decides the order in which a vehicle visits a set of stops so that distance or time is as low as possible. When one vehicle must visit every stop and return to the start, it is the traveling salesman problem (TSP).
With several vehicles, load capacity and delivery time windows, the problem becomes the vehicle routing problem (VRP). It is daily work for anyone who ships finished goods, collects parts from suppliers or feeds the line with a milk run.
The TSP is hard because the number of routes explodes. With 5 customers there are 5! = 120 possible sequences; with 10 customers, 10! = 3,628,800. That is why practice relies on heuristics: simple rules that give a good route in seconds, without guaranteeing the best one.
Visual map of routing
The map summarizes this article's example: the route built by nearest neighbor and its 2-opt improvement.
Example data: a depot and 5 customers
Fictional example, only to illustrate the calculation. Depot D sits at the origin and each grid unit equals 1 km. Coordinates (x, y): D (0, 0), F (1, 3), A (2, 6), B (5, 1), C (6, 5) and E (9, 2).
d = √[(x₂ − x₁)² + (y₂ − y₁)²]
Example: from D to F, d = √(1² + 3²) = √10 = 3.16 km. The table lists every distance between the points, in km.
| D | F | A | B | C | E | |
|---|---|---|---|---|---|---|
| D | – | 3.16 | 6.32 | 5.10 | 7.81 | 9.22 |
| F | 3.16 | – | 3.16 | 4.47 | 5.39 | 8.06 |
| A | 6.32 | 3.16 | – | 5.83 | 4.12 | 8.06 |
| B | 5.10 | 4.47 | 5.83 | – | 4.12 | 4.12 |
| C | 7.81 | 5.39 | 4.12 | 4.12 | – | 4.24 |
| E | 9.22 | 8.06 | 8.06 | 4.12 | 4.24 | – |
In real operations, replace straight-line distance with a road distance or travel-time matrix. The heuristics work the same way.
Nearest neighbor: building the route
This is the simplest heuristic. Start at the depot and, at each step, go to the closest customer not yet visited. When all are visited, return to the depot.
- From D, the closest is F (3.16 km), versus A (6.32), B (5.10), C (7.81) and E (9.22).
- From F, the closest is A (3.16 km).
- From A, the closest is C (4.12 km).
- From C, B (4.12 km) is shorter than E (4.24 km), so go to B.
- From B, only E remains (4.12 km).
- From E, return to D (9.22 km).
| Step | From | To | Distance (km) |
|---|---|---|---|
| 1 | D | F | 3.16 |
| 2 | F | A | 3.16 |
| 3 | A | C | 4.12 |
| 4 | C | B | 4.12 |
| 5 | B | E | 4.12 |
| 6 | E | D | 9.22 |
| Total | 27.91 |
The route D–F–A–C–B–E–D adds up to 27.91 km. Note the typical flaw of the method: in the last steps only distant customers are left, and the E–D return of 9.22 km alone makes up a third of the route.
2-opt improvement: swapping two legs
2-opt starts from a finished route and tests replacing two legs (edges) with two others, reversing the segment between them. If the total drops, it keeps the swap and repeats until no swap helps.
gain = (edge 1 + edge 2) removed − (edge 3 + edge 4) added
In route D–F–A–C–B–E–D, remove C–B and E–D. Reconnect C to E and B to D, reversing the B–E segment. The sequence becomes D–F–A–C–E–B–D.
| Route | Sequence | Edges swapped | Total (km) |
|---|---|---|---|
| Before (nearest neighbor) | D–F–A–C–B–E–D | C–B (4.12) + E–D (9.22) = 13.34 | 27.91 |
| After (2-opt) | D–F–A–C–E–B–D | C–E (4.24) + B–D (5.10) = 9.34 | 23.91 |
The gain is 13.34 − 9.34 = 4.00 km, a 14.3% reduction (from 27.91 to 23.91 km). After testing all remaining swaps, none improves the route further. I checked the result by listing all 120 sequences: 23.91 km is indeed the shortest distance for this example. 2-opt does not always reach the optimum, but it usually gets close.
From the traveling salesman to vehicle routing
The TSP assumes one vehicle with no load limit. Real plants and distribution networks add constraints:
- Capacity: the vehicle cannot carry all orders at once, so customers must be split into several routes.
- Time windows: the customer only receives between 8 and 11 a.m., for example.
- Mixed fleet: vehicles of different sizes and costs.
- Service time: unloading, checking and the driver's maximum shift.
- Pickup and delivery: stops that receive goods and stops that ship them.
A classic method to split customers into routes is the Clarke and Wright savings algorithm (1964), which merges routes when that reduces total distance. Larger problems or those with many constraints call for integer linear programming models or routing software.
Where routing fits in operations
- External milk run: collecting from several suppliers on one trip, as in replenishment logistics.
- Distribution: deliveries to customers, where freight is a relevant part of production cost; see also cross docking.
- Warehouse: the order of visiting locations in picking is a small TSP.
- Maintenance and inspection: technician rounds across several machines.
- Supply chain: the route is one piece of the supply chain that sets lead time and logistics cost.
Common mistakes and limitations
- Assuming nearest neighbor is optimal. It is only a starting point; in the example it came out 17% above the best (27.91 versus 23.91 km).
- Using straight lines instead of the road network. Rivers, railways and one-way streets change the ideal order.
- Ignoring time. The shortest distance is not always the shortest time; traffic and time windows matter.
- Forgetting constraints. Capacity, receiving hours and driver shift must be set before comparing routes.
- Not validating with the driver. Drivers know blocked streets, docks and queues that a map does not show.
- Calculating only once. When orders change, the route changes; recalculate each delivery cycle.
Frequently asked questions
What is the traveling salesman problem?
It is the problem of finding the shortest route that visits each point on a list once and returns to the starting point.
What is vehicle routing?
It is defining the routes of a fleet to serve customers, respecting capacity and time windows at minimum distance or time.
How does nearest neighbor work?
Start at the depot and, at each step, go to the closest unvisited customer until all are visited, then return to the start.
What is 2-opt?
It is an improvement that replaces two edges of the route with two others, reversing the segment between them, when this lowers total distance.
Does nearest neighbor give the best route?
Not guaranteed. In the example it gave 27.91 km and 2-opt reached 23.91 km, the minimum verified among the 120 sequences.
How many routes exist with 10 customers?
10! = 3,628,800 sequences from one depot, which is why heuristics are used instead of testing them all.
Sources
- APPLEGATE, D. L. et al. The Traveling Salesman Problem: A Computational Study. Princeton University Press, 2006.
- TOTH, P.; VIGO, D. (eds.). The Vehicle Routing Problem. SIAM, 2002.
- CROES, G. A. A method for solving traveling-salesman problems. Operations Research, v. 6, 1958.
- CLARKE, G.; WRIGHT, J. W. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, v. 12, 1964.
- BALLOU, R. H. Business Logistics/Supply Chain Management. Pearson.
Keep studying: trusted sources and links
- INFORMS: What is Operations Research?
- INFORMS: Institute for Operations Research and the Management Sciences
Save this address: Manufatura Enxuta is your school for lean manufacturing. Come back whenever you need to study, with a complete article, a visual map and trusted sources. Follow one of the learning paths or check the A–Z glossary.
Want a quick reference guide for the factory floor?
Download the free Pocket Guide e-book with the Lean tools summarized on one page each.
Download the e-book
About the author
Lean Manufacturing & Behavioral Management Specialist
Over 20 years in the automotive and metalworking industries (GM and Dana), Lean Manufacturing practitioner since 2006. SENAI instructor and mentor in Brazil’s Brasil Mais Produtivo program, delivering consulting, training and audits for 50+ companies, combining quality, productivity and people development.
