In this paper, we study the constrained shortest path tour problem. Given a directed graph with non-negative arc lengths, the aim is to find a single-origin single-destination shortest path, which needs to cross a sequence of node subsets that are given in a fixed order. The subsets are disjoint and may be of different size. In addition, it is required that the path does not include repeated arcs. Theoretical properties of the problem are studied, proving that it belongs to the complexity class NP-complete. To exactly solve it, a Branch & Bound method is proposed. Given the problem hardness, a Greedy Randomized Adaptive Search Procedure is also developed to find near-optimal solutions for medium to large scale instances. Extensive computational experiments, on a significant set of test problems, are carried out in order to empirically evaluate the performance of the proposed approaches. The computational results show that the Greedy Randomized Adaptive Search Procedure is effective in finding optimal or near optimal solutions in very limited computational time.

Ferone, D., Festa, P., Guerriero, F., Laganà, D. (2016). The constrained shortest path tour problem. COMPUTERS & OPERATIONS RESEARCH, 74, 64-77 [10.1016/j.cor.2016.04.002].

The constrained shortest path tour problem

Ferone, D;
2016

Abstract

In this paper, we study the constrained shortest path tour problem. Given a directed graph with non-negative arc lengths, the aim is to find a single-origin single-destination shortest path, which needs to cross a sequence of node subsets that are given in a fixed order. The subsets are disjoint and may be of different size. In addition, it is required that the path does not include repeated arcs. Theoretical properties of the problem are studied, proving that it belongs to the complexity class NP-complete. To exactly solve it, a Branch & Bound method is proposed. Given the problem hardness, a Greedy Randomized Adaptive Search Procedure is also developed to find near-optimal solutions for medium to large scale instances. Extensive computational experiments, on a significant set of test problems, are carried out in order to empirically evaluate the performance of the proposed approaches. The computational results show that the Greedy Randomized Adaptive Search Procedure is effective in finding optimal or near optimal solutions in very limited computational time.
Articolo in rivista - Articolo scientifico
Branch & Bound; Combinatorial optimization; GRASP; Network flow problems; Shortest path problems;
Branch & Bound; Combinatorial optimization; GRASP; Network flow problems; Shortest path problems; Computer Science (all); Modeling and Simulation; Management Science and Operations Research
English
2016
74
64
77
none
Ferone, D., Festa, P., Guerriero, F., Laganà, D. (2016). The constrained shortest path tour problem. COMPUTERS & OPERATIONS RESEARCH, 74, 64-77 [10.1016/j.cor.2016.04.002].
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/10281/219755
Citazioni
  • Scopus 34
  • ???jsp.display-item.citation.isi??? 30
Social impact