REAL

Solving resource constrained shortest path problems with LP-based methods

Horváth, Markó and Kis, Tamás (2016) Solving resource constrained shortest path problems with LP-based methods. Computers & Operations Research, 73. pp. 150-164. ISSN 0305-0548

[img]
Preview
Text
rcspp.pdf

Download (408kB) | Preview
[img]
Preview
Text
rcspp_rev2.pdf

Download (437kB) | Preview

Abstract

In the resource constrained shortest path problem (RCSPP) there is a directed graph along with a source node and a destination node, and each arc has a cost and a vector of weights specifying its requirements from a set of resource types with finite capacities. A minimum cost source–destination directed path is sought such that the total consumption of the arcs from each resource type does not exceed the capacity of the resource. In this paper we investigate LP-based branch-and-bound methods and introduce new cutting planes, separation procedures, variable fixing, and primal heuristic methods for solving RCSPP to optimality. We provide detailed computational experiments, and a comparison to other methods in the literature.

Item Type: Article
Subjects: Q Science / természettudomány > QA Mathematics / matematika
Depositing User: Dr. Tamás Kis
Date Deposited: 09 Sep 2015 10:04
Last Modified: 20 May 2016 11:23
URI: http://real.mtak.hu/id/eprint/26108

Actions (login required)

Edit Item Edit Item