Optimization Online


Minimization and Maximization Versions of the Quadratic Traveling Salesman Problem

Oswin Aichholzer (oaich***at***ist.tugraz.at)
Anja Fischer (anja.fischer***at***mathematik.uni-goettingen.de)
Frank Fischer (frank.fischer***at***uni-kassel.de)
J. Fabian Meier (brief***at***fabianmeier.de)
Ulrich Pferschy (pferschy***at***uni-graz.at)
Alexander Pilz (alexander.pilz***at***inf.ethz.ch)
Rostislav Staněk (rostislav.stanek***at***uni-graz.at)

Abstract: The traveling salesman problem (TSP) asks for a shortest tour through all vertices of a graph with respect to the weights of the edges. The symmetric quadratic traveling salesman problem (SQTSP) associates a weight with every three vertices traversed in succession. If these weights correspond to the turning angles of the tour, we speak of the angular-metric traveling salesman problem (Angle TSP). In this paper, we first consider the SQTSP from a computational point of view. In particular, we apply a rather basic algorithmic idea and perform the separation of the classical subtour elimination constraints on integral solutions only. Surprisingly, it turns out that this approach is faster than the standard fractional separation procedure known from the literature. We also test the combination with strengthened subtour elimination constraints for both variants, but these turn out to slow down the computation. Secondly, we provide a completely different, mathematically interesting MILP linearization for the Angle TSP that needs only a linear number of additional variables while the standard linearization requires a cubic one. For medium sized instances of a variant of the Angle TSP this formulation yields reduced running times. However, for larger instances or pure Angle TSP instances the new formulation takes more time to solve than the known standard model. Finally, we introduce MaxSQTSP, the maximization version of the quadratic traveling salesman problem. Here it turns out that using some of the stronger subtour elimination constraints helps. For the special case of the MaxAngle TSP we can observe an interesting geometric property if the number of vertices is odd. We show that the sum of inner turning angles in an optimal solution always equals Pi. This implies that the problem can be solved by the standard ILP model without producing any integral subtours. Moreover, we give a simple constructive polynomial time algorithm to find such an optimal solution. If the number of vertices is even the optimal value lies between 0 and 2*Pi and these two bounds are tight, which can be shown by an analytic solution for a regular n-gon.

Keywords: Traveling Salesman Problem, Subtour Elimination Constraint, Computational Experiments, Turning Angle, Bitangent

Category 1: Combinatorial Optimization

Category 2: Integer Programming

Citation: Preprint 2016-1, Preprint-Serie des Instituts für Numerische und Angewandte Mathematik (Preprint of the Institute for Numerical and Applied Mathematics of the University of Goettingen), March 2016

Download: [PDF]

Entry Submitted: 03/17/2016
Entry Accepted: 03/18/2016
Entry Last Modified: 03/23/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