Optimization Online


A Semidefinite Opimization Approach to the Target Visitation Problem

Philipp Hungerlaender (philipp.hungerlaender***at***aau.at)

Abstract: We propose an exact algorithm for the Target Visitation Problem (TVP). The (TVP) is a composition of the Linear Ordering Problem and the Traveling Salesman Problem. It has several military and non-military applications, where two important, often competing factors are the overall distance traveled (e.g. by an unmanned aerial vehicle) and the visiting sequence of the various targets or points of interest. Hence our algorithm can be used to find the optimal visiting sequence of various pre-determined targets. First we show that the (TVP) is a special Quadratic Position Problem. Building on this finding we propose an exact semidefinite optimization approach to tackle the (TVP) and finally demonstrate its efficiency on a variety of benchmark instances with up to 50 targets.

Keywords: Target Visitation Problem; Linear Ordering Problem; Traveling Salesman Problem; Semidefinite Programming; Global Optimization

Category 1: Applications -- OR and Management Sciences (Production and Logistics )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Opimization Letters, 9(8):1703-1727, 2015.

Download: [PDF]

Entry Submitted: 01/14/2015
Entry Accepted: 01/14/2015
Entry Last Modified: 12/14/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society