A Semidefinite Opimization Approach to the Target Visitation Problem
Philipp Hungerlaender (philipp.hungerlaenderaau.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.
Entry Submitted: 01/14/2015
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|