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