Concorde is a cut and branch based exact TSP solver. In other words, the solution from Concorde is the best optimal solution among all feasible one.
However, due to license constraint (see the last license issue section for details), I have to look into an alternative heuristic (approximation) approach later.
1. Download Concorde source code from here.
2. Download a binary LP solver from here and deploy the header and static library into ./QS64_linux or ./QS64_darwin sub folder under Concorde source code depending on your platform.
3. Build with the following script:
if [ "$1" == "linux" ]; then echo "Build for Linux 64" make clean ./configure --with-qsopt=$PWD/QS64_linux make -j 16 elif [ "$1" == "darwin" ]; then echo "Build for Mac OS X 64" make clean ./configure --with-qsopt=$PWD/QS64_darwin --host=intel-x86-linux make -j 16 else echo "Unkown parameters!" echo "./build-64.sh [linux|darwin]" fi
4. If you resolve all other dependencies in your build platform and build it successfully, Concorde binary will reside in ./TSP folder.
Given entry points and exit points of each part in the layer from output text file, we can use asymmetric traveling salesman problem (ATSP) solver to find out the optimal traveling order of the parts such that air time travel distance is minimal.
If you already build and \play with Concorde, you will find that Concorde seem to only solve TSP, where there is one and only one weighted edge between two vertexes. I have to say Concorde is great except its poor documentation. For last 10 years, its developer's guide is still under construction. You can hardly find a user guide to tell you how to provide input and interpret output.
In any rate, Concorde is free. So stop complaining and poke around this.
After reading its test code, it mentioned TSPLIB, which is TSP solver benchmark data. Google TSPLIB and you will find its data format. I shared the data format specs in the file section. There are two ways to define edge weight in TSP:
1. Define vertex coordinate -- Vertex_Index X_coordinate Y_coordinate.
2. Define edge weight matrix. If the matrix is not symmetric, you turn Concorde from solving TSP into ATSP
See TSPLIB tsp input data here.
So I manually write a trivial case to do a PoC. See the diagram below generated by dot file and the in and out of Concorde.
TSPLIB format input:
Ricky@imac:~/repo/concorde/SAMPLES$ cat 4point.tsp NAME: demo TYPE: TSP COMMENT: 4 vertexes asymmetric problem DIMENSION: 4 EDGE_WEIGHT_TYPE: EXPLICIT EDGE_WEIGHT_FORMAT: FULL_MATRIX EDGE_WEIGHT_SECTION 9999 11 8 4 10 9999 7 2 6 5 9999 4 6 3 9 9999 EOF
Ricky@imac:~/repo/concorde/TSP$ ./concorde ../SAMPLES/4point.tsp ./concorde ../SAMPLES/4point.tsp Host: imac Current process id: 96043 Using random seed 1528799254 Problem Name: demo Problem Type: TSP 4 vertexes asymmetric problem Number of Nodes: 4 Explicit Lengths (CC_MATRIXNORM) Optimal Solution: 21.00 Total Running Time: 0.00 (seconds) Ricky@imac:~/repo/concorde/TSP$ cat 4point.sol 4 0 2 1 3
Concorde deliver the optimal tour 0 => 2 => 1 => 3 => 0 with optimal cost 21.
For our path planning purpose, we don't need a tour that comes back to the original point. One trick I made is to add a facilitated vertex where its in and out edge weight is zero and connect to all other vertexes.
Augmented Concorde Input:
Ricky@imac:~/repo/concorde/SAMPLES$ cat 4point_extended.tsp NAME: demo TYPE: TSP COMMENT: 4 vertexes asymmetric problem DIMENSION: 5 EDGE_WEIGHT_TYPE: EXPLICIT EDGE_WEIGHT_FORMAT: FULL_MATRIX EDGE_WEIGHT_SECTION 9999 11 8 4 0 10 9999 7 2 0 6 5 9999 4 0 6 3 9 9999 0 0 0 0 0 9999 EOF
Augmented Concorde Output:
Ricky@imac:~/repo/concorde/TSP$ ./concorde ../SAMPLES/4point_extended.tsp ./concorde ../SAMPLES/4point_extended.tsp Host: imac Current process id: 97242 Using random seed 1528804704 Problem Name: demo Problem Type: TSP 4 vertexes asymmetric problem Number of Nodes: 5 Explicit Lengths (CC_MATRIXNORM) Optimal Solution: 13.00 Total Running Time: 0.00 (seconds) Ricky@imac:~/repo/concorde/TSP$ cat 4point_extended.sol 5 0 4 2 1 3
By removing the facilitated vertex 4, we got a path 2 => 1 => 3 => 0 with optimal cost 13.
Writing a converter is a piece of cake in Python. We have X and Y coordinate of all entry point and exit point of parts. Compute its Euclidian distance, generate the asymmetric weight matrix and then add a facilitated vertex. Then our converter is done.
I shoot an email to Prof William Cook, who owns Concorde and co-authors the great TSP book, and ask if I can use Concorde under GPL. He suggest to make use of Concorde as my hobby project, instead of GPL. I respect that. After reviewing Concorde source code, you will be amazed how many years of experience and intelligence built in that implementation.
I don't think I have bandwidth or enough intelligence to build a TSP solver from ground up. He pointed me to implement TSP in a simple heuristic approach -- 3-opt (k-opt) approach. I will look into that as I'm writing this log.