Competing for the most profitable tour: The orienteering interdiction game
<|reference_start|>Competing for the most profitable tour: The orienteering interdiction game: 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.<|reference_end|>
@article{álvarez-miranda2024competing,
    title={Competing for the most profitable tour: The orienteering interdiction
  game},
    author={Eduardo 'Alvarez-Miranda, Markus Sinnl, K"ubra Tan{i}nm{i}c{s}},
    journal={arXiv preprint arXiv:2407.02959},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.02959},
    primaryClass={math.OC cs.DM}
}