A branch-and-cut algorithm for the target visitation problem
Tóm tắt
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.
Tài liệu tham khảo
Applegate DL, Bixby RE, Chvátal V, Cook WJ (2006) The traveling salesman problem. Princeton series in applied mathematics. Princeton Univ. Press, Princeton
Arulselvan A, Commander C, Pardalos P (2008) A hybrid genetic algorithm for the target visitation problem. Technical report, University of Florida
Christof T, Loebel A (2009) PORTA: polyhedron representation transformation algorithm, version 1.4. http://comopt.ifi.uni-heidelberg.de/software/PORTA/index.html. Accessed 1 Feb 2019
Grötschel M, Jünger M, Reinelt G (1985) Facets of the linear ordering polytope. Math Program 33:43–60
Grundel D, Jeffcoat D (2004) Formulation and solution of the target visitation problem. In: Proceedings of the AIAA 1st intelligent systems technical conference
Heismann O, Hildenbrandt A, Silvestri F, Reinelt G, Borndörfer R (2013) HUHFA: a framework for facet classification. Tech. Rep. 13-45, Zuse Institue Berlin
Hildenbrandt A (2015) The target visitation problem. PhD thesis
Hildenbrandt A (2018) Traveling salesman problems with additional ordering constraints. Oper Res Proc 2017:221–227
Hildenbrandt A, Reinelt G (2015) Inter programming models for the target visitation problem. Informatica 39(3):257–260
Hungerländer P (2015) A semidefinite optimization approach to the target visitation problem. Optim Lett 9(8):1703–1727
Lörwald S (2014) Exact solving methods for the target visitation problem. Diploma thesis
Queyranne M, Wang Y (1993) Hamiltonian path and symmetric travelling salesman polytopes. Math Program 58:89–110
Rafael M, Reinelt G (2011) The linear ordering problem: exact and heuristic methods in combinatorial optimization. Springer, Berlin
Reinelt G (1985) The linear ordering problem: algorithms and applications. Heldermann, Berlin
Ziegler GM (1995) Lectures on polytopes. Springer, Berlin