An integer linear programming model for the constrained shortest path tour problem

Let D = (V, A) be a directed graph with set of vertices V and set of arcs A, and let each arc (i, j) ∈ A, with i, j ∈ V, be associated with a non-negative cost. The constrained shortest path tour problem (CSPTP) is NP-Hard and consists in finding a shortest path between two distinct vertices s ∈ V a...

Full description

Saved in:
Bibliographic Details
Published in:Electronic notes in discrete mathematics 2018-08, Vol.69, p.141-148
Main Authors: de Andrade, Rafael Castro, Saraiva, Rommel Dias
Format: Article
Language:English
Subjects:
Combinatorial optimization
Constrained shortest path tour problem
Integer linear programming
Network flow problems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let D = (V, A) be a directed graph with set of vertices V and set of arcs A, and let each arc (i, j) ∈ A, with i, j ∈ V, be associated with a non-negative cost. The constrained shortest path tour problem (CSPTP) is NP-Hard and consists in finding a shortest path between two distinct vertices s ∈ V and t ∈ V such that the path does not include repeated arcs and must visit a sequence of vertex disjoint subsets T1, …, TN in this order. In this work, we formulate the CSPTP as an integer linear programming (ILP) model and present valid inequalities for the problem. Computational experiments performed on benchmark data sets from the literature show that our ILP model consistently outperforms existing exact algorithms for the CSPTP and finds optimal solutions for most instances.
ISSN:1571-0653
1571-0653
DOI:10.1016/j.endm.2018.07.019