Competing for the most profitable tour: The orienteering interdiction game
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914857482190848 |
|---|---|
| author | Álvarez-Miranda, Eduardo Sinnl, Markus Tanınmış, Kübra |
| author_facet | Álvarez-Miranda, Eduardo Sinnl, Markus Tanınmış, Kübra |
| contents | The orienteering problem is a well-studied and fundamental problem in transportation science. In the problem, we are given a graph with prizes on the nodes and lengths on the edges, together with a budget on the overall tour length. The goal is to find a tour that respects the length budget and maximizes the collected prizes. In this work, we introduce the orienteering interdiction game, in which a competitor (the leader) tries to minimize the total prize that the follower can collect within a feasible tour. To this end, the leader interdicts some of the nodes so that the follower cannot collect their prizes. The resulting interdiction game is formulated as a bilevel optimization problem, and a single-level reformulation is obtained based on interdiction cuts. A branch-and-cut algorithm with several enhancements, including the use of a solution pool, a cut pool and a heuristic method for the follower's problem, is proposed. In addition to this exact approach, a genetic algorithm is developed to obtain high-quality solutions in a short computing time. In a computational study based on instances from the literature for the orienteering problem, the usefulness of the proposed algorithmic components is assessed, and the branch-and-cut and genetic algorithms are compared in terms of solution time and quality. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_02959 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Competing for the most profitable tour: The orienteering interdiction game Álvarez-Miranda, Eduardo Sinnl, Markus Tanınmış, Kübra Optimization and Control Discrete Mathematics 90B06, 90C10, 90C57 The orienteering problem is a well-studied and fundamental problem in transportation science. In the problem, we are given a graph with prizes on the nodes and lengths on the edges, together with a budget on the overall tour length. The goal is to find a tour that respects the length budget and maximizes the collected prizes. In this work, we introduce the orienteering interdiction game, in which a competitor (the leader) tries to minimize the total prize that the follower can collect within a feasible tour. To this end, the leader interdicts some of the nodes so that the follower cannot collect their prizes. The resulting interdiction game is formulated as a bilevel optimization problem, and a single-level reformulation is obtained based on interdiction cuts. A branch-and-cut algorithm with several enhancements, including the use of a solution pool, a cut pool and a heuristic method for the follower's problem, is proposed. In addition to this exact approach, a genetic algorithm is developed to obtain high-quality solutions in a short computing time. In a computational study based on instances from the literature for the orienteering problem, the usefulness of the proposed algorithmic components is assessed, and the branch-and-cut and genetic algorithms are compared in terms of solution time and quality. |
| title | Competing for the most profitable tour: The orienteering interdiction game |
| topic | Optimization and Control Discrete Mathematics 90B06, 90C10, 90C57 |
| url | https://arxiv.org/abs/2407.02959 |