EURO Journal on Computational Optimization (Sep 2019)

A branch-and-cut algorithm for the target visitation problem

  • Achim Hildenbrandt

Journal volume & issue
Vol. 7, no. 3
pp. 209 – 242

Abstract

Read online

In this paper, we consider the target visitation problem (TVP) which arises in the context of disaster treatment. Mathematically speaking, the problem is concerned with finding a route to visit a set of targets starting from and returning to some base. In addition to the distance travelled, a tour is evaluated by taking also preferences into account which address the sequence in which the targets are visited. The problem thus is a combination of two well-known combinatorial optimization problems: the traveling salesman and the linear ordering problem. In this paper, we point out some polyhedral properties, develop a branch-and-cut algorithm for solving the TVP to optimality and present some computational results.

Keywords