An efficient exact approach for the constrained shortest path tour problem. (2nd January 2020)

• Record Type: Journal Article
• Authors: Ferone, Daniele; Festa, Paola; Guerriero, Francesca
• Is Part Of: Optimization methods and software. Volume 35:Number 1(2020)
• Page Start: 1
• Page End: 20
• Publication Date: 2020-01-02
• Subjects: Shortest path problems -- shortest path tour problem -- capacity constraints -- branch & bound; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2018.1548015
• Languages: English
• ISSNs: 1055-6788

Abstract

ABSTRACT: Given a directed graph with non-negative arc lengths, the Constrained Shortest Path Tour Problem ( C S P T P ) 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 C S P T P 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.