A Branch-and-Cut Algorithm for Elementary Shortest Path Problem with Resource Constraints

Mads Kehlet Jepsen; Bjørn Petersen; Simon Spoorendonk

A Branch-and-Cut Algorithm for Elementary Shortest Path Problem with Resource Constraints

Mads Kehlet Jepsen
, Bjørn Petersen
, Simon Spoorendonk

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

Abstract

The elementary shortest path with resource constraints are commonly solved with dynamic programming algorithms. We present a branch-and-cut algorithm for the undirected version. Two types of resources are discussed: A capacity and a fixed charge resource. The former is the subproblem of the capacitated vehicle routing problem and the latter is for the split delivery version.

Original language	English
Publication date	2010
Publication status	Published - 2010
Event	Optimization Days 2010 - Montréal, Canada Duration: 10 May 2010 → 12 May 2010 http://w1.cirrelt.ca/jopt2010/en/

Conference

Conference	Optimization Days 2010
Country/Territory	Canada
City	Montréal
Period	10/05/2010 → 12/05/2010
Internet address	http://w1.cirrelt.ca/jopt2010/en/

OpenUrl availability

Check availability in DTU Findit

Cite this

@conference{de544ba6c88e403d9a9041ce6f1e6014,

title = "A Branch-and-Cut Algorithm for Elementary Shortest Path Problem with Resource Constraints",

abstract = "The elementary shortest path with resource constraints are commonly solved with dynamic programming algorithms. We present a branch-and-cut algorithm for the undirected version. Two types of resources are discussed: A capacity and a fixed charge resource. The former is the subproblem of the capacitated vehicle routing problem and the latter is for the split delivery version.",

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

year = "2010",

language = "English",

note = "Optimization Days 2010 ; Conference date: 10-05-2010 Through 12-05-2010",

url = "http://w1.cirrelt.ca/jopt2010/en/",

}

TY - ABST

T1 - A Branch-and-Cut Algorithm for Elementary Shortest Path Problem with Resource Constraints

AU - Jepsen, Mads Kehlet

AU - Petersen, Bjørn

AU - Spoorendonk, Simon

PY - 2010

Y1 - 2010

N2 - The elementary shortest path with resource constraints are commonly solved with dynamic programming algorithms. We present a branch-and-cut algorithm for the undirected version. Two types of resources are discussed: A capacity and a fixed charge resource. The former is the subproblem of the capacitated vehicle routing problem and the latter is for the split delivery version.

AB - The elementary shortest path with resource constraints are commonly solved with dynamic programming algorithms. We present a branch-and-cut algorithm for the undirected version. Two types of resources are discussed: A capacity and a fixed charge resource. The former is the subproblem of the capacitated vehicle routing problem and the latter is for the split delivery version.

M3 - Conference abstract for conference

T2 - Optimization Days 2010

Y2 - 10 May 2010 through 12 May 2010

ER -

A Branch-and-Cut Algorithm for Elementary Shortest Path Problem with Resource Constraints

Abstract

Conference

OpenUrl availability

Fingerprint

Cite this