Skip to main content

Downloads


Contents:

               1. Algorithms
                              1.1 - TSP algorithms
                              1.2 - Sparse TSP algorithms

               2. Benchmark sets for TSP and its variations
                              2.1 - TSP and HCP benchmark sets
                              2.2 - CGTSP benchmark sets
                              2.3 - TDTSP benchmark set


1. Algorithms
                        
1.1 - TSP algorithms

TSP Solver
Description
LKH
A relatively recent implementation of the famous Lin-Kernighan heuristic known for its success of at discovering the best known solutions for many benchmark examples including the World TSP challenge. It holds a number of records for TSP.



Relevant Article:
[1] Helsgaun, K. (2000). An effective implementation of the Lin–Kernighan traveling salesman heuristic. European Journal of Operational Research, 126(1), 106-130.
Concorde
Arguably the most well-known exact TSP solver. Even though Concorde’s worst-case complexity is combinatorial, in practice, the solution often solutions are obtained within polynomial time bounds because it uses clever linear programming techniques to obtain and verify an optimal solution.

Relevant Book:

[2] Applegate, D. L., Bixby, R. E., Chvatal, V., & Cook, W. J. (2006). The traveling salesman problem: a computational study. Princeton university press.



1.2 - Sparse TSP algorithms



STSP Solver
Description
Download
sLKH
A relatively recent implementation of the famous Lin-Kernighan heuristic known for its success of at discovering the best known solutions for many benchmark examples including the World TSP challenge. It holds a number of records for TSP.

Relevant Article: 
[1] Helsgaun, K. (2000). An effective implementation of the Lin–Kernighan traveling salesman heuristic. European Journal of Operational Research, 126(1), 106-130.

Referencing Note: this solver is a slight third-party modification of LKH algorithm. If you intend to use this work please reference Helsgaun’s article above.







Concorde-SLH hybrid
The Concorde-SLH hybrid algorithm is the proof of concept hybrid algorithm based on Chapter 4 of the doctoral thesis of Pouya Baniasadi. Two parallel runs are dynamically integrated to find the lower bound and upper bound for the graph. For
the lower bound we have used the implementation of Concorde 03.12.192. The support graph is then created from the solution of the LP problem and passed on to SLH HCP solver to solve. One unit of improvement on the lower bound is set to be the trigger for updating the support graph. The upper bound value and the best tour is either updated by SLH or by in-build features of Concorde. When an upper bound matches a lower bound, the tour is returned as the optimal tour.

Relevant articles: 
[2] W. J. (2006). The traveling salesman problem: a computational study. Princeton university press.
[3] Baniasadi, P., Ejov, V., Filar, J. A., Haythorpe, M., & Rossomakhine, S. (2014). Deterministic “Snakes and Ladders” Heuristic for the Hamiltonian cycle problem. Mathematical Programming Computation, 6(1), 55-75.

Referencing Note: this solver is a combination of two solvers SLH and Concorde. If you use this code, please add references to both relevant articles. Concorde and SLH are both freely available for academic research. For non-academic use please email authors of each algorithm separately.






sLKH-SLH
This program is a combination of sLKH and SLH2 implemented for both Windows and Linux. For difficult instances where finding a tour in the sparse graph is difficult, or for instances where sLKH is unable to reduce the number of gaps to their minimal, the SLH algorithm is activated. After SLH concludes its process, LKH is re-activated on the best tour obtained by SLH
to find a local minimum

Relevant articles: 
[1] Helsgaun, K. (2000). An effective implementation of the Lin–Kernighan traveling salesman heuristic. European Journal of Operational Research, 126(1), 106-130.
[3] Baniasadi, P., Ejov, V., Filar, J. A., Haythorpe, M., & Rossomakhine, S. (2014). Deterministic “Snakes and Ladders” Heuristic for the Hamiltonian cycle problem. Mathematical Programming Computation, 6(1), 55-75.

Referencing Note: this solver is a combination of two solvers LKH and LKH. To refer to using this code in an article, please add a reference to both relevant articles. LKHand SLH is both freely available for academic research. For non-academic use please email authors of each algorithm separately.

Integrated in the sTSP platform
sTSP platform
A unified platform is implemented which unifies the input and the output format of sparse instances for multiple sparse TSP algorithms. The solver may be chosen from sLKH, sLKH-SLH, Concorde-SLH Hybrid or Condorde algorithm. Furthermore, an independent randomized test may be paralleled under this platform.




2. Benchmark sets for TSP and its variations


2.1. TSP and HCP Benchmark sets



STSP Solver
Description
Download
Difficult HCP instances
Difficult instances of HCP in .hcp format. Please read the article for more information about each graph in the benchmark set. 

Relevant Article: 
[4] Baniasadi, P., Ejov, V., Haythorpe, M., & Rossomakhine, S. (2018). A new benchmark set for Traveling salesman problem and Hamiltonian cycle problem. arXiv preprint arXiv:1806.09285.



Simulated TSP overlap graphs
These instances are simulated instances based on the DNA-assembly problem. The graph is not a direct conversion of DNA-assembly graph, but rather, the structure of the overlap graph is simulated. TSP overlap graphs are generated directly for n = 25k, 50k, 100k, 250k, 500k, reads of size 1000 bases. For solving these instances, the TSP solver must enforce the following condition on TSP:

edge (2k-1, 2k) is a forced edge for k = 1, ... , n.

These graphs are in .whcp format (weighted HCP format).


Relevant Article: 
[5] Baniasadi, P. (2019), Algorithms for Solving Variations of the Traveling Salesman Problem (Doctoral Dissertation). Flinders University.









2.2. CGTSP Benchmark sets



STSP Solver
Description
Download
Random CGTSP instances
The instances of the benchmark set consist of randomly generated vertices in a 1000 × 1000 2D Euclidean space. We use the generic name “rnd<NC>-<NS>-<NV >n", where NC is the number of clusters, NS is the number of subclusters in each cluster, and NV is the number of vertices in each cluster. For each size, we have generated problems with high, low or even numbers for NC, NS and NV relative to one another to extract the differences that arise from various combinations. 

Relevant Article: 
--



CGTSP Instances inspired by ASRS
A number of item locations are generated in a warehouse that is assumed to be square. Each item may be associated with multiple item locations. A robot collects the items in the warehouse is given a list of orders and due to stacking restrictions, it must finish collecting one order, before moving on to the next order. Finally, the robot should deliver the collected items to a specific point (the initial point) in the warehouse. This problem may be modelled as a CGTSP and this benchmark set is a collection of CGTSP instances associated with this problem.


Consider a warehouse where the stored items are in thetwo categories of high-demand and low-demand items, consisting of 20% and 80% of total items respectively. We randomly generate orders for which we presume that there is a 80% chance that a randomly selected item in an order is marked as a high-demand item. Furthermore, there are 400 possible storage locations in the warehouse, and each item may be stored at multiple locations. The ASRS test instances are labeled as “ASRS_i<A>r<L>_<I><type>", where A is the total number of available items in the warehouse, L is the number of locations where each item is stored, and I is the total number of items in all orders. It is clear that the size of the problem is n = L×I. The type of the instance determined whether the locations of all items is randomly selected in the warehouse (type = rnd), or if there is at least one location for all high-demand items near the I/O conveyor (type = alt). 


Relevant Article: 
--





CGTSP Instances inspired by Drone delivery systems
We have used GTSPLIB instances to generate CGTSP instances corresponding to the drone-assisted parcel delivery service (PDS) and compare the impact of the different number of drones. In the GTSPLIB library the nodes of the selected TSPLIB test instances are divided into regions (clusters of close-by nodes) by a simple clustering procedure that clusters nodes that are close to each other. If the size of any particular cluster is larger than the number of drones plus one, we further subdivide the cluster into subclusters where the truck only visits one of the nodes from each subcluster, and the drones visit the rest of the nodes. We assume that loaded drones and empty drones are 50% and 100% faster than the truck respectively. We also presume that one unit of distance traveled by truck corresponds to one unit of time. As a measure of improvements made by adding the drones, we compare the time values to the case where the drones are not employed. It is interesting to note that if we employ zero drones, the problem is equivalent to a CTSP. Furthermore, if there are enough drones in each step to cover an entire cluster, then the problem reduces to a GTSP.


Relevant Article: 
--


zip file





2.3. TDTSP randomly generated benchmark set



STSP Solver
Description
Download
Random TDTSP instances
The TDTSP instances are generated as follows. For each t = 1, 2, …, n, a symmetric matrix of size n is generated that contains random weights of up to 100 and the i, j entries are the d(t, i, j) distances of TDTSP. The instances are then converted to a TSP by the conversion described in Section 4.3. Then, the asymmetric TSP instances are transformed to symmetric TSP instances by a simple conversion that doubles the sizes of the graph.

Relevant Article: 
[5] --