Shortest Paths and Vehicle Routing

Bjørn Petersen

Shortest Paths and Vehicle Routing

Bjørn Petersen

Research output: Book/Report › Ph.D. thesis

1666 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 language	English

Place of Publication	Kgs. Lyngby
Publisher	DTU Management
Number of pages	232
Publication status	Published - Jan 2011

Series	PhD thesis
Number	9.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

Access to Document

BjørnPetersen PhD thesis 2011Final published version, 3.02 MB

OpenUrl availability

Full text

Ikke-robust dekomponering og løsning af hårde korteste-vej problemer
Petersen, B., Pisinger, D., Irnich, S., Salani, M. & Larsen, J.
Technical University of Denmark
01/03/2009 → 02/02/2011
Project: PhD

Cite this

@phdthesis{dd816da964fe4d0bae30eb7f8e9db934,

title = "Shortest Paths and Vehicle Routing",

abstract = "This thesis presents how to parallelize a shortest path labeling algorithm. It is shown how to handle Chv{\'a}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.",

keywords = "Chv{\'a}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",

author = "Bj{\o}rn Petersen",

year = "2011",

month = jan,

language = "English",

series = "PhD thesis",

number = "9.2011",

publisher = "DTU Management",

}

TY - BOOK

T1 - Shortest Paths and Vehicle Routing

AU - Petersen, Bjørn

PY - 2011/1

Y1 - 2011/1

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

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

KW - Chvátal-Gomory rank-1 cuts

KW - Vehicle Routing Problems

KW - Branch-and-Cut

KW - Elementary Shortest Path Problems with Resource Constrains

KW - Branch-Price-and-Cut

KW - Dantzig-Wolfe decomposition

M3 - Ph.D. thesis

T3 - PhD thesis

BT - Shortest Paths and Vehicle Routing

PB - DTU Management

CY - Kgs. Lyngby

ER -

Shortest Paths and Vehicle Routing

Abstract

Keywords

Access to Document

OpenUrl availability

Fingerprint

Projects

Ikke-robust dekomponering og løsning af hårde korteste-vej problemer

Cite this