Partial Path Column Generation for the ESPPRC

Mads Kehlet Jepsen; Bjørn Petersen

Partial Path Column Generation for the ESPPRC

Mads Kehlet Jepsen (Invited author), Bjørn Petersen (Invited author)

Research output: Contribution to conference › Conference abstract for conference › Research

Abstract

This talk introduces a decomposition of the Elementary Shortest Path Problem with Resource Constraints(ESPPRC), where the path is combined by smaller sub paths. We show computational result by comparing different approaches for the decomposition and compare the best of these with existing algorithms. We show that the algorithm for many instances outperforms a bidirectional labeling algorithm.

Original language	English
Publication date	2009
Publication status	Published - 2009
Event	20th International Symposium of Mathematical Programming - Chicago, IL, United States Duration: 23 Aug 2009 → 28 Aug 2009 Conference number: 20 http://ismp2009.eecs.northwestern.edu/

Conference

Conference	20th International Symposium of Mathematical Programming
Number	20
Country/Territory	United States
City	Chicago, IL
Period	23/08/2009 → 28/08/2009
Internet address	http://ismp2009.eecs.northwestern.edu/

Access to Document

http://ismp2009.eecs.northwestern.edu/printfiles/ScheduleFriday.pdf

OpenUrl availability

Full text

Cite this

@conference{f02c964bc062458aada6d6bfe9af4648,

title = "Partial Path Column Generation for the ESPPRC",

abstract = "This talk introduces a decomposition of the Elementary Shortest Path Problem with Resource Constraints(ESPPRC), where the path is combined by smaller sub paths. We show computational result by comparing different approaches for the decomposition and compare the best of these with existing algorithms. We show that the algorithm for many instances outperforms a bidirectional labeling algorithm.",

author = "Jepsen, {Mads Kehlet} and Bj{\o}rn Petersen",

year = "2009",

language = "English",

note = "20th International Symposium of Mathematical Programming, 2009 ISMP ; Conference date: 23-08-2009 Through 28-08-2009",

url = "http://ismp2009.eecs.northwestern.edu/",

}

TY - ABST

T1 - Partial Path Column Generation for the ESPPRC

AU - Jepsen, Mads Kehlet

AU - Petersen, Bjørn

N1 - Conference code: 20

PY - 2009

Y1 - 2009

N2 - This talk introduces a decomposition of the Elementary Shortest Path Problem with Resource Constraints(ESPPRC), where the path is combined by smaller sub paths. We show computational result by comparing different approaches for the decomposition and compare the best of these with existing algorithms. We show that the algorithm for many instances outperforms a bidirectional labeling algorithm.

AB - This talk introduces a decomposition of the Elementary Shortest Path Problem with Resource Constraints(ESPPRC), where the path is combined by smaller sub paths. We show computational result by comparing different approaches for the decomposition and compare the best of these with existing algorithms. We show that the algorithm for many instances outperforms a bidirectional labeling algorithm.

M3 - Conference abstract for conference

T2 - 20th International Symposium of Mathematical Programming

Y2 - 23 August 2009 through 28 August 2009

ER -