Website of MSTSP

Multi-Solution Traveling Salesman Problem (MSTSP)


Abstract

Problems with multiple optimal solutions widely exist in the real world. In some applications, it is required to locate multiple optima. However, most studies are dedicated to the continuous multi-solution optimization, while few works contribute to the discrete multi-solution optimization. To promote the multi-solution research in the discrete area, we specify on Traveling Salesman Problem (TSP) and design a benchmark suite of TSP variant with multiple equally optimal solutions, namely MSTSP. To solve MSTSPs, we propose two algorithms: neighborhood-based genetic algorithm (NGA) and niching memetic algorithm (NMA). The experimental results validate the effectiveness of these two algorithms. Below you can find more details of our works. This page provides the data files of MSTSP benchmark and the source codes of NGA and NMA.

MSTSP Benchmark

Multi-solution Traveling Salesman Problem (MSTSP) is essentially a TSP, but the one with multiple optimal solutions. This benchmark includes 25 MSTSPs. The number of cities ranges from 9 to 66, and the number of optimal solutions ranges from 4 to 196. The algorithm adopted to tackle MSTSPs terminates when the maximum fitness evaluations (MaxFEs) are exhausted. To be specific, the MaxFEs are set as 6.00E+04 for MSTSP1-MSTSP12 and 1.20E+06 for MSTSP13-MSTSP25. Finally, the algorithm is required to provide a solution set. These candidate solutions are further evaluated with two indicators, i.e., $F_{\beta}$ and Diversity Indicator (DI). $F_{\beta}$ measures the solution quality, and DI measures the solution diversity.

Three categories of MSTSPs

Simple MSTSP

MSTSP4

MSTSP4(simple4_11)

Geometry MSTSP

MSTSP7

MSTSP7(geometry1_10)

MSTSP7

MSTSP12(geometry6_15)

Composite MSTSP

MSTSP24

MSTSP24(composite12_60)

subtours of MSTSP24

Avaible source

TSPLIB-ms

Apart from the above MSTSP benchmark, an MSTSP optimizer can be further evaluated by the well-known TSPLIB. Many instances in TSPLIB possess multi-solution characteristics, but the previous studies using this test suite consider one global optimum only. We defined a subset of TSPLIB, named TSPLIB-ms, which contains eight instances with multiple good solutions: eil51, berlin52, st70, pr76, kroA100, lin105. The developers of MSTSP solvers are also suggested to test their algorithms on the TSPLIB-ms and provide the final solution set with superior and diverse solutions. To be specific, the provided solutions should meet the following two requirements. (1) The length is shorter than a certain threshold length: (1 + σ) × (the optimal tour length provided by the TSPLIB), where σ is set to 0.1. (2) The sharing distance (a similarity measure) between any two solutions should be smaller than λ x (the number of cities in this instance), where λ is set to 0.8. As an example, the representative solutions obtained by NMA on the st70 and eil51 are shown below.
multi-solution of st70
The multi-solution of st70
multi-solution of eil51
The multi-solution of eil51

Data file of the TSPLIB-ms

Demo Works on MSTSP

1. Neighborhood-Based Genetic Algorithm (NGA)

T. Huang, Y. Gong and J. Zhang, “Seeking Multiple Solutions of Combinatorial optimization Problems: A Proof of Principle Study,” 2018 IEEE Symposium Series on Computational Intelligence (SSCI), Bangalore, India, 2018, pp. 1212-1218.
To promote the multi-solution research in the discrete area, we design a benchmark test suite for multi-solution traveling salesman problems and propose two evaluation indicators. Further, in order to solve the problems, the genetic algorithm is incorporated with a niching technique defined in the discrete space, namely NGA. Experimental results demonstrate that the proposed algorithm outperforms the compared algorithm concerning the quality and diversity of obtained solutions.

The results in terms of $F_\beta$ and DI obtained by NGA on MSTSPs.

MSTSP MSTSP1 MSTSP2 MSTSP3 MSTSP4 MSTSP5
$F_\beta$ 0.973 0.959 0.935 0.932 0.846
DI 0.980 0.972 0.957 0.947 0.916
MSTSP MSTSP6 MSTSP7 MSTSP8 MSTSP9 MSTSP10
$F_\beta$ 0.877 0.769 0.578 0.974 0.969
DI 0.943 0.869 0.838 0.975 0.969
MSTSP MSTSP11 MSTSP12 MSTSP13 MSTSP14 MSTSP15
$F_\beta$ 0.949 0.331 0.096 0.172 0.416
DI 0.963 0.809 0.792 0.844 0.847
MSTSP MSTSP16 MSTSP17 MSTSP18 MSTSP19 MSTSP20
$F_\beta$ 0.054 0.044 0.031 0.007 0.000
DI 0.783 0.803 0.704 0.699 0.671
MSTSP MSTSP21 MSTSP22 MSTSP23 MSTSP24 MSTSP25
$F_\beta$ 0.000 0.000 0.000 0.000 0.000
DI 0.628 0.409 0.344 0.319 0.270

NGA Source Code (C++)

2. Niching Memetic Algorithm (NMA)

T. Huang, Y. Gong, S. Kwong, H. Wang and J. Zhang, “A Niching Memetic Algorithm for Multi-Solution Traveling Salesman Problem,” IEEE Transactions on Evolutionary Computation. DOI: 10.1109/TEVC.2019.2936440.
This paper proposes a niching memetic algorithm (NMA). The proposed algorithm is characterized by a niche preservation technique to enable the parallel search of multiple optimal solutions; an adaptive neighborhood strategy to balance the exploration and exploitation; a critical edge-aware method to provide effective guidance to the reproduction; and a selective local search strategy to improve the search efficiency. The experimental results show that our algorithm outperforms other compared algorithms. Furthermore, the proposed algorithm is adopted to tackle problems from the well-known TSPLIB library to obtain a set of distinct but good solutions.

The results in terms of $F_\beta$ and DI obtained by NMA on MSTSPs.

MSTSP MSTSP1 MSTSP2 MSTSP3 MSTSP4 MSTSP5
$F_\beta$ 1.000 1.000 1.000 1.000 1.000
DI 1.000 1.000 1.000 1.000 1.000
MSTSP MSTSP6 MSTSP7 MSTSP8 MSTSP9 MSTSP10
$F_\beta$ 1.000 0.923 0.772 1.000 1.000
DI 1.000 0.945 0.898 1.000 1.000
MSTSP MSTSP11 MSTSP12 MSTSP13 MSTSP14 MSTSP15
$F_\beta$ 1.000 0.535 0.611 0.883 0.732
DI 1.000 0.871 0.922 0.981 0.932
MSTSP MSTSP16 MSTSP17 MSTSP18 MSTSP19 MSTSP20
$F_\beta$ 0.554 0.605 0.571 0.168 0.165
DI 0.926 0.944 0.932 0.865 0.865
MSTSP MSTSP21 MSTSP22 MSTSP23 MSTSP24 MSTSP25
$F_\beta$ 0.023 0.013 0.016 0.010 0.002
DI 0.834 0.816 0.829 0.811 0.747

The number of satisfactory solutions obtained by NMA on TSPLIB_ms.

TSPLIB_ms eil51 berlin52 st70
No. Solution 5.84 4.54 6.00
TSPLIB_ms pr76 kroA100 lin105
No. Solution 5.12 5.36 4.54

NMA Source Code (C++)


Contact

The School of Computer Science and Engineering, South China University of Technology, Guangzhou 510006, China.

Email: cshting [AT] mail.scut.edu.cn