König, Barbara:
Heuristiken zur Ein-Depot-Tourenplanung
München, 1995
1995Buch
Informatik
Titel:
Heuristiken zur Ein-Depot-Tourenplanung
Autor*in:
König, BarbaraUDE
GND
1050396502
LSF ID
15982
ORCID
0000-0002-4193-2889ORCID iD
Sonstiges
der Hochschule zugeordnete*r Autor*in
Erscheinungsort:
München
Erscheinungsjahr:
1995
Umfang:
120
Notiz:
München, Techn. Univ., Dipl.-Arbeit, 1995

Abstract:

The Vehicle Routing Problem (VRP) is a generalization of the Traveling Salesman Problem (TSP). An amount of goods is assigned to every node of a graph and they are to be collected by vehicles restricted in their capacity and time and brought to a depot. The aim is to minimize the overall costs. The decision problem for vehicle routing is NP-complete, which means that there probably is no polynomial-time algorithm for VRP and we are forced to resort to heuristics. Several heuristics are introduced, including Sweep, several variants of the Savings-procedure, a giant tour algorithm and a $k$-opt algorithm for the improvement of existing tours. The heuristics are tested on graphs representing real-world road networks and are compared in their results and their computational complexity. Technische Universität München (in German)