(classic problem)
Definition: Find an optimal route of one or more vehicles through a graph.
Also known as VRP.
Generalization (I am a kind of ...)
optimization problem.
Specialization (... is a kind of me.)
traveling salesman.
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.
Author: PEB
Description of related problems and links to research groups and papers.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified Fri Dec 17 12:28:59 2004.
HTML page formatted Wed Oct 26 09:48:20 2005.
Cite this as:
Paul E. Black, "vehicle routing problem", from
Dictionary of Algorithms and Data
Structures, Paul E. Black, ed.,
NIST.
http://www.nist.gov/dads/HTML/vehicleRouting.html
