.png){kind=icon}
.png){kind=icon}
Return
The constrained shortest path tour problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2016.04.002.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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. (C) 2016 Elsevier Ltd. All rights reserved.
Keywords:
Shortest path problems
Network flow problems
Combinatorial optimization
Branch & Bound
GRASP
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W