A branch-and-cut algorithm for the elementary shortest path problem with resource constraints

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

    Research output: Contribution to conferenceConference abstract for conferenceResearchpeer-review

    Abstract

    The elementary shortest path with resource constraints have commonly been solved with dynamic programming algorithms. Assuming an undirected graph, we present a compact formulation of this problem and a branch-and-cut algorithm to solve it. 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 from the split delivery version. Computational results are presented and compared to dynamic programming algorithms.
    Original languageEnglish
    Publication date2010
    Publication statusPublished - 2010
    Event24th European Conference on Operational Research - Lisbon, Portugal
    Duration: 11 Jul 201014 Jul 2010
    Conference number: 24

    Conference

    Conference24th European Conference on Operational Research
    Number24
    Country/TerritoryPortugal
    CityLisbon
    Period11/07/201014/07/2010

    Fingerprint

    Dive into the research topics of 'A branch-and-cut algorithm for the elementary shortest path problem with resource constraints'. Together they form a unique fingerprint.

    Cite this