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:  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:  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

## 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:   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:   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--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_ir_", 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:  --

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:   --