Travelling salesman with a directional constraint

Question

I am trying to order an array of 3D coordinates by their order along a path. A sample:

points = np.array([[ 0.81127451,  0.22794118,  0.52009804],                    [ 0.62986425,  0.4546003 ,  0.12971342],                    [ 0.50666667,  0.41137255,  0.65215686],                    [ 0.79526144,  0.58186275,  0.04738562],                    [ 0.55163399,  0.49803922,  0.24117647],                    [ 0.47385621,  0.64084967,  0.10653595]]) 

The points are in random order, but there is always a single path through them. I am finding the path with an adapted travelling salesman problem (TSP) soution, using the LKH solver (Helsgaun 2009). It involves two modifications:

• Add a point at or near the origin. This finds the best starting point in every instance I've tackled so far. This was my idea, I have no other basis for it.
• Add a point at a distance of zero from every point. This makes the solver find a route to the other end of the path. This idea was from this SO question.

Note that the TSP does not involve position, only the distances between nodes. So the solver does 'know' (or care) that I'm working in 3D. I just make a distance matrix like so:

import numpy as np from scipy.spatial.distance import pdist, squareform  # Add a point near the origin. points = np.vstack([[[0.25, 0, 0.5]], points]) dists = squareform(pdist(points, 'euclidean'))  # Normalize to int16s because the solver likes it. d = 32767 * dists / np.sqrt(3) d = d.astype(np.int16)  # Add a point that is zero units from every other point. row, col = d.shape d = np.insert(d, row, 0, axis=0) d = np.insert(d, col, 0, axis=1) 

I pass this to my fork of pytsp, which passes it to the LKH solver. And everything is fine... except when the path crosses itself. TSP solutions cannot have closed loops, so I always get the open loop shown on the right here:

Note that this is an analogous 2D version of my situation. Note also that the points are imperfectly aligned, even along the 'straight' bits.

So my question is: how can I help the solver preserve the direction of the path whenever possible? I've got two ill-formed ideas, but so far been unable to implement anything:

• Use another metric instead of L2. But I don't think this can work, because at a given junction, there's nothing inherently different about the 'wrong' point. Its wrongness depends on the previous point. And we don't know yet which is the previous point (that's what we're trying to figure out). So I think this is no good.
• Evaluate the local colinearity of every set of three points (e.g. using the determinant of every triple). Modulate the local '3D slope' (not sure what I mean) by this colinearity coefficient. Give every point another dimension expressing this local alignment. Now the norm will reflect local alignment and (hopefully) roughly colinear things will join up.

I have put these files on Dropbox:

• Raw data NumPy file
• Ordered data NumPy file

Thank you for reading; any ideas appreciated.

Reference

K. Helsgaun, General k-opt submoves for the Lin-Kernighan TSP heuristic. Mathematical Programming Computation, 2009, doi: 10.1007/s12532-009-0004-6.

Answer 1

Judging by the documentation on pytsp, the distance matrix doesn't have to be symmetric. This means that you could modify the L2 norm to incorporate information on a preferred direction into that matrix. Say you have a preferred direction for some pairs of points (i,j), then for each of these point you could divide dists[i,j] by (1+a) and multiply dists[j,i] by (1+a) to make that direction more favourable. This means that if your algorithm is sure to find the global optimum, you can force it to satisfy your preferred direction by taking a is sufficiently large.

Also, I'm not sure it's impossible to have closed loops in a solution where the distance matrix is taken from 3D data. It seems to me that the 'no closed loops' is a result (of the triangle inequality) specific to 2D.