Fleet Dispatching (mTSP)

The multi-vehicle routing problem (VRP) extends the traveling salesman problem to a fleet: several vehicles start from a depot and must jointly visit all customers at minimum total cost. It is one of the most economically important NP-hard problems.

How it works

Classical constructive methods include the Clarke-Wright savings algorithm, which starts with one route per customer and merges routes in order of the distance saved, and cluster-first route-second approaches that group customers geographically before solving a TSP per cluster. Improvement phases apply 2-opt and or-opt moves within and between routes, and metaheuristics such as tabu search and large neighborhood search close most of the remaining gap to optimal.

Applications

VRP plans parcel delivery for postal and courier fleets, school bus routes, field service technician schedules, and waste collection circuits. Commercial routing engines solve VRP variants millions of times daily, making it a core skill for logistics and operations research engineers.