.png){kind=icon}
.png){kind=icon}
Return
The probabilistic orienteering problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2016.12.025.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The probabilistic orienteering problem (POP) is defined on a directed graph where a cost is associated with each arc and a prize is associated with each node. Moreover, each node will be available for visit only with a certain probability. A server starts from a fixed origin, has a given budget to visit a subset of nodes, and ends at a fixed destination. In a first stage, a node subset has to be selected and a corresponding a priori path has to be determined such that the server can visit all nodes in the subset and reach the destination without exceeding the budget. The list of available nodes in the subset is then revealed. In a second stage, the server follows the a priori path by skipping the absent nodes. The POP consists in determining a first-stage solution that maximizes the expected profit of the second-stage path, where the expected profit is the difference between the expected total prize arid the expected total cost. We discuss the relevance of the problem and formulate it as a linear integer stochaStic problem. We develop a branch-and-cut approach for the POP and several matheuristic methods, corresponding to different strategies to reduce the search space of the exact method. Extensive computational tests on instances with up to 100 nodes show the effectiveness of the exact method and the efficiency of the matheuristics in finding high quality solutions in a few minutes. Moreover, we provide an extended analysis on a subset of instances to show the value of explicitly modeling the stochastic information in the problem formulation. (C) 2016 Elsevier Ltd. All rights reserved.
Keywords:
Stochastic routing
Orienteering problem
Probabilistic TSP
L-shaped method
Matheuristics
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