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.
|Place of Publication||Kgs. Lyngby|
|Number of pages||232|
|Publication status||Published - Jan 2011|
- Chvátal-Gomory rank-1 cuts
- Vehicle Routing Problems
- Elementary Shortest Path Problems with Resource Constrains
- Dantzig-Wolfe decomposition