Shortest Paths and Vehicle Routing

Bjørn Petersen

    Research output: Book/ReportPh.D. thesisResearch

    887 Downloads (Pure)

    Abstract

    This thesis presents how to parallelize a shortest path labeling algorithm. It is shown how to handle Chvátal-Gomory rank-1 cuts in a column generation context. A Branch-and-Cut algorithm is given for the Elementary Shortest Paths Problem with Capacity Constraint. A reformulation of the Vehicle Routing Problem based on partial paths is presented. Finally, a practical application of finding shortest paths in the telecommunication industry is shown.
    Original languageEnglish
    Place of PublicationKgs. Lyngby
    PublisherDTU Management
    Number of pages232
    Publication statusPublished - Jan 2011
    SeriesPhD thesis
    Number9.2011

    Keywords

    • Chvátal-Gomory rank-1 cuts
    • Vehicle Routing Problems
    • Branch-and-Cut
    • Elementary Shortest Path Problems with Resource Constrains
    • Branch-Price-and-Cut
    • Dantzig-Wolfe decomposition

    Fingerprint Dive into the research topics of 'Shortest Paths and Vehicle Routing'. Together they form a unique fingerprint.

    Cite this