10.6084/M9.FIGSHARE.7599194.V1
Ferone, Daniele
Daniele
Ferone
Festa, Paola
Paola
Festa
Guerriero, Francesca
Francesca
Guerriero
An efficient exact approach for the constrained shortest path tour problem
Taylor & Francis
2019
Dataset
Biophysics
Cell Biology
Molecular Biology
Neuroscience
Physiology
FOS: Biological sciences
FOS: Biological sciences
Pharmacology
Immunology
FOS: Clinical medicine
FOS: Clinical medicine
19999 Mathematical Sciences not elsewhere classified
FOS: Mathematics
FOS: Mathematics
Developmental Biology
Science Policy
60506 Virology
2019-01-17
2020-03-11
2019
10.1080/10556788.2018.1548015
10.6084/m9.figshare.7599194
238494 Bytes
Creative Commons Attribution 4.0 International
Given a directed graph with non-negative arc lengths, the Constrained Shortest Path Tour Problem (CSPTP) is aimed at finding a shortest path from a single-origin to a single-destination, such that a sequence of disjoint and possibly different-sized node subsets are crossed in a given fixed order. Moreover, the optimal path must not include repeated arcs. In this paper, for the CSPTP we propose a new mathematical model and a new efficient Branch & Bound method. Extensive computational experiments have been carried out on a significant set of test problems in order to evaluate empirically the performance of the proposed approach.