Heuristiken zur Ein-Depot-Tourenplanung


Barbara König. Heuristiken zur Ein-Depot-Tourenplanung. Master's thesis, Technische Universität München, 1995. (in German).


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 -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.

Suggested BibTeX entry:

    author = {Barbara K{\"o}nig},
    note = {(in German)},
    school = {Technische Universit{\"a}t M{\"u}nchen},
    title = {Heuristiken zur {E}in-{D}epot-{T}ourenplanung},
    year = {1995}

GZipped PostScript (212 kB)PDF (456 kB)
© University of Duisburg-Essen, Theoretical Computer Science group