Benchmark for Euclidean Single-Depot Bounded Multiple Travelling Salesman Problem instances

This repository introduces 168 novel instances (file: instances-168.csv) designed for solving the Euclidean Single-Depot Bounded Multiple Traveling Salesman Problem (Bounded MTSP). These instances are adapted from the TSP library, with city '1' designated as the depot, and the remaining 'n-1' cities representing destinations to be visited by 'k' salesmen. To define the tour constraints, we establish 'm_{min}' (minimum) and 'm_{max}' (maximum) values, informed by real-world surveys reflecting client visits ranging from 15 to 60. Our repository provides three sets of 'm_{min}' and 'm_{max}' pairs: 30, 50; 24, 40; and 18, 30. Additionally, the value for 'k' is calculated using the formula:

⎡ 1.3 x n ⎤
k( n , m_{max} ) = ⎜ ⎼⎼⎼⎼⎼⎼⎼ ⎥
⎜ m_{max} ⎥

In addition to the 168 new instances, we have included 6 instances proposed by (Junjie & Dingwei, 2006) (file instances-6.csv) and 16 instances proposed by (Necula et al. 2015) (instances-16.csv), raising the total to 190 instances. For each instance, we provide the best solution delivered by our 3-phase algorithm (folders: solutions-22 and solutions-163) and its corresponding solution graph (folder: graphs), along with a table detailing the minimum, average and maximum costs, the run number in which the best cost was obtained and the time elapsed to obtain that best cost, as well as the average processing time, the best cost and the lower bound achieved by the CPLEX solver (IBM, 2024), as well as the elapsed processing time, limited to 2 hours (file: results.xlsx).

These instances serve as valuable benchmarks for researchers exploring MTSP variants.

R. Necula, M. Breaban, and M. Raschip,
"Performance evaluation of ant colony systems for the single-depot multiple traveling salesman problem",
In International Conference on Hybrid Artificial Intelligence Systems, Springer, Cham. pp. 257--268, 2015.
Available: \url{https://doi.org/10.1007/978-3-319-19644-2\_22}

P. Junjie and W. Dingwei,
"An ant colony optimization algorithm for multiple travelling salesman problem",
In First International Conference on Innovative Computing, Information and Control-Volume I (ICICIC'06),
Vol. 1, pp. 210--213, IEEE, 2006
Available: \url{https://doi.org/10.1109/ICICIC.2006.40}

V. H. Pacheco-Valencia, N. Vakhania and J. A. Hernández-Aguilar,
"An Algorithm to Solve the Euclidean Single-Depot Bounded Multiple Traveling Salesman Problem",
In 2023 IEEE World Conference on Applied Intelligence and Computing (AIC), Sonbhadra, India, 2023, pp. 7-12,
Available: https://doi.org/10.1109/AIC57670.2023.10263920.

IBM,
"IBM Ilog CPLEX optimization studio versión 22.1.1",
Available at https://www.ibm.com/academic/home,
Last accessed 15 march 2024.

TSPLIB
Available: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/
Last consulted 30 sep 2023

本仓库引入了168个全新的实例（文件：instances-168.csv），旨在解决欧几里得单仓库有界多旅行商问题（Bounded MTSP）。这些实例源自TSP库，其中城市编号'1'被指定为仓库，其余的'n-1'个城市代表由'k'位旅行商访问的目的地。为了定义旅行路线约束，我们设定了'm_{min}'（最小值）和'm_{max}'（最大值），这些值基于反映客户访问次数从15到60的实地调查。我们的仓库提供了三组'm_{min}'和'm_{max}'的配对值：30, 50；24, 40；以及18, 30。此外，'k'的值通过以下公式计算得出：

⎡ 1.3 x n ⎤
k( n , m_{max} ) = ⎜ ⎼⎼⎼⎼⎼⎼⎼ ⎥
⎜ m_{max} ⎥

除了168个新实例外，我们还包含了由（Junjie & Dingwei，2006）提出的6个实例（文件：instances-6.csv）和由（Necula等，2015）提出的16个实例（instances-16.csv），使得总数达到190个实例。对于每个实例，我们提供了由我们的三阶段算法得出的最佳解决方案（文件夹：solutions-22和solutions-163）及其相应的解决方案图（文件夹：graphs），以及一个表格，详细说明了最小值、平均值和最大成本，最佳成本所在的运行次数，以及获得该最佳成本所需的时间，还包括平均处理时间、最佳成本和由CPLEX求解器（IBM，2024）实现的下界，以及限于2小时内的处理时间（文件：results.xlsx）。

这些实例作为研究人员探索MTSP变体的宝贵基准。

R. Necula, M. Breaban, 和 M. Raschip，
“蚁群系统在单仓库多旅行商问题性能评估”，
国际混合人工智能系统会议，Springer，Cham. 第257-268页，2015。
可访问：url{https://doi.org/10.1007/978-3-319-19644-2_22}

P. Junjie 和 W. Dingwei，
“一种用于多旅行商问题的蚁群优化算法”，
在首届国际创新计算、信息和控制会议-第I卷（ICICIC'06），
第1卷，第210-213页，IEEE，2006
可访问：url{https://doi.org/10.1109/ICICIC.2006.40}

V. H. Pacheco-Valencia, N. Vakhania 和 J. A. Hernández-Aguilar，
“解决欧几里得单仓库有界多旅行商问题的算法”，
2023 IEEE世界应用智能和计算会议（AIC），印度Sonbhadra，2023，第7-12页，
可访问：https://doi.org/10.1109/AIC57670.2023.10263920。

IBM，
“ILOG CPLEX优化工作室版本22.1.1”，
可在https://www.ibm.com/academic/home获取，
最后访问日期：2024年3月15日。

TSPLIB
可访问：http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/
最后咨询日期：2023年9月30日。