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

Achim Hildenbrandt ()
Additional contact information
Achim Hildenbrandt: Ruprecht Karls Universitat Heidelberg

EURO Journal on Computational Optimization, 2019, vol. 7, issue 3, No 1, 209-242

Abstract: Abstract 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: Traveling salesman problem; Linear ordering problem; Polyhedra theory; Branch-and-cut; 90C10; 90C35; 90C57; 05C38; 05C20 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s13675-019-00111-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:eurjco:v:7:y:2019:i:3:d:10.1007_s13675-019-00111-x

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/13675

DOI: 10.1007/s13675-019-00111-x

Access Statistics for this article

EURO Journal on Computational Optimization is currently edited by Martine C. Labbé

More articles in EURO Journal on Computational Optimization from Springer, EURO - The Association of European Operational Research Societies
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().