In the m-Peripatetic Salesman Problem (m-PSP) the aim is to determine m edge disjoint Hamiltonian cycles of minimum total cost on a graph. This presentation introduces new valid inequalities, polyhedral results and an improved 2-index branch-and-cut algorithm for the m-PSP. Tests performed on randomly generated and TSPLIB Euclidean instances indicate that this algorithm can solve instances with more than double size of what was previously achievable.

We present formulations for the Precedence Constrained Assymetric Travelling Salesman (PCATS) problem obtained by relating formulations of the ATS problem with formulations of the so-called linear ordering problem. We introduce several exponential sized sets of cut-like inequalities to link formulation of these two problems. From a practical point of view, we discuss polynomial routines to separate these inequalities and give preliminary results evaluating the strength of our formulations.

It is well known that the TSP remains NP-hard even when the underlying graph is planar. However, there are indications that the planar TSP is in some sense 'easier' than the TSP on general graphs: i) a sub-exponential time exact algorithmis known for the planar TSP (Deinecko et al.), whereas for the general TSP none is known; ii) a polynomial-time approximation scheme (PTAS) is known for the planar TSP (Arora et al.), whereas none exists for the general TSP unless P=NP; iii) there exists an efficient separation algorithm for the so-called 'domino-parity' inequalities, which only works when the point to be separated induces a planar graph (Letchford). In this talk, we continue to examine the separation question. We show that the separation problem for the subtour elimination, 2-matching and simple domino-parity constraints can be solved much more quickly in the planar case than in the case of general graphs. We also present a small number of graphs for which the subtour elimination and domino-parity inequalities are insufficient to describe the (graphical) TSP polyhedron, and conjecture that these are the excluded minors for this property.