1178. Neighbourhood-constrained Bilevel Shortest Path Problem
Invited abstract in session MB-55: Network Optimization 2, stream Network Optimization.
Monday, 10:30-12:00Room: Liberty 1.09
Authors (first author is the speaker)
| 1. | Szymon Wróbel
|
| Department of Fundamentals of Computer Science, Wrocław University of Science and Technology | |
| 2. | Adam Kasperski
|
| Wroclaw University of Science and Technology, Faculty of Management | |
| 3. | Pawel Zielinski
|
| Department of Fundamentals of Computer Science, Wroclaw University of Science and Technology |
Abstract
The Shortest Path problem has been extensively studied in the deterministic setting, where the arc weights are precisely known and all variables are controlled by a single decision-maker. Although in many cases it may be a sufficient model, the input data may be subject to uncertainty or not be fully controlled by the decision maker. One of the approaches that can be used in such scenario is bilevel optimisation, which is a framework in which the problem is divided into two hierarchically dependent subproblems: the leader and the follower.
Although bilevel versions of the Shortest Path problem have been explored in the literature, they have primarily focused on adversarial settings (network interdiction) or cooperative settings (leader and follower build a single path). The Neighbourhood-constrained Bilevel Shortest Path problem introduces a new bilevel version of the Shortest Path problem, in which the decisions available to the follower are restricted to a neighbourhood of the path selected by the leader.
Our main contribution is the formulation of the problem, its relations to other optimisation problems, and preliminary complexity results.
Keywords
- Mathematical Programming
- Graphs and Networks
Status: accepted
Back to the list of papers