Shortest Paths and Vehicle Routing

Bjørn Petersen

    Research output: Book/ReportPh.D. thesis

    1666 Downloads (Pure)


    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


    • 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


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

    Cite this