Given a directed graph with non-negative arc lengths, the Constrained Shortest Path Tour Problem ((Formula presented.)) 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 (Formula presented.) 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.

An efficient exact approach for the constrained shortest path tour problem / Ferone, Daniele; Festa, Paola; Guerriero, Francesca. - In: OPTIMIZATION METHODS & SOFTWARE. - ISSN 1055-6788. - 35:1(2020), pp. 1-20. [10.1080/10556788.2018.1548015]

An efficient exact approach for the constrained shortest path tour problem

Ferone, Daniele;Festa, Paola
;
Guerriero, Francesca
2020

Abstract

Given a directed graph with non-negative arc lengths, the Constrained Shortest Path Tour Problem ((Formula presented.)) 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 (Formula presented.) 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.
2020
An efficient exact approach for the constrained shortest path tour problem / Ferone, Daniele; Festa, Paola; Guerriero, Francesca. - In: OPTIMIZATION METHODS & SOFTWARE. - ISSN 1055-6788. - 35:1(2020), pp. 1-20. [10.1080/10556788.2018.1548015]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11588/729629
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 19
  • ???jsp.display-item.citation.isi??? 14
social impact