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

EURO Journal on Computational Optimization

Achim Hildenbrandt¹ 

[1] Ruprecht Karls Universitat Heidelberg, INF 205, 69120, Heidelberg, Germany.;

关键词: 90C10;    90C35;    90C57;    05C38;    05C20;   

DOI  :  

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown