Definition: Find an optimal route of one or more vehicles through a graph.
Also known as VRP.
Generalization (I am a kind of ...)
Specialization (... is a kind of me.)
See also Hamiltonian cycle, Chinese postman problem.
Note: The vehicles may be school buses, garbage trucks, delivery vans, etc. The optimal may be fastest routes, least variation (all get nearly equal assignments), least "cost" (big cost for going through Mayor's neighborhood, small cost for taking freeway), etc.
With one vehicle, this is the traveling salesman problem.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 10 September 2012.
HTML page formatted Fri Feb 23 10:06:08 2018.
Cite this as:
Paul E. Black, "vehicle routing problem", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 10 September 2012. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/vehicleRouting.html