Solving multi-depot closed-path multiple traveling salesman problem using k-means++ hierarchical clustering and neural combinatorial networks.

1. import argparse
2. import os
3. import math
4. import numpy as np
6. import time
7. from tqdm import tqdm
8. from clustering import k_means_plusplus_clustering_sklearn,clusterRefinement
9. from neural_end2end_solver import end2end_solver,make_opts
10. from common import HyperparametersConfig, TSP_tour_distance, loadDataFormTSPLibFile
11. from end2end_model.kool2019.utils import load_model
12. from merge_sub_tours import merge
14. def KHC_NCN_MDCP_MTSP(mdcp_mtsp,salesman_m,ideal_cluster_size,alpha,model, random_seed=1234):
15. # load config parameters
16. config=HyperparametersConfig("config.ini")
18. opts=make_opts()
20. # clusters <- k-means++(mdcp_mtsp, salesman_m)
21. clusters=k_means_plusplus_clustering_sklearn(mdcp_mtsp, salesman_m, max_iterations=config.max_clustering_iter, n_jobs=config.n_jobs, random_seed=random_seed)
22. clusters=clusterRefinement(clusters,True)
24. cluster_data_list=[]
25. for c in clusters:
26. cluster_data_list.append(np.copy(c["points"]))
28. allTours=[]
30. for tsp in tqdm(cluster_data_list):
31. if tsp.shape[0]<=standard_cluster_size*(1+alpha):
32. result_dict=end2end_solver(tsp,model,opts,normalize=True)
33. allTours.append(result_dict["sorted_tsp_data"])
34. else:
35. k=math.floor(tsp.shape[0]/standard_cluster_size)
36. if tsp.shape[0]-k*standard_cluster_size>standard_cluster_size*alpha:
37. k=k+1
39. sub_clusters=k_means_plusplus_clustering_sklearn(tsp, k, config.max_clustering_iter, config.n_jobs)
40. sub_clusters=clusterRefinement(sub_clusters,False)
42. # solve each cluster with end2end Model and merge the results
43. subTours=[]
44. for sub_cluster in sub_clusters:
45. tmp_tsp_data=np.array(sub_cluster['points'])
46. sub_tour_result_dict=end2end_solver(tmp_tsp_data,model,opts,normalize=True)
47. sub_tour_result_dict["center"]=sub_cluster['centroid']
48. subTours.append(sub_tour_result_dict)
49. # merge the results
50. merged_tour=merge(subTours)
51. allTours.append(merged_tour)
53. return allTours
55. def solve_one_MTSP_with_different_K(data_file,model_path,standard_cluster_size,m_list,alpha,log_tag, random_seed=1234):
56. m_list=[m_list[0]] + m_list
58. ## load model
59. end2end_model, _ = load_model(model_path)
61. different_m_results=[]
62. different_m_time_consumed_list=[]
64. _,mdcp_mtsp_data=loadDataFormTSPLibFile(data_file)
65. mdcp_mtsp=np.array(mdcp_mtsp_data)
67. for m in tqdm(m_list):
68. time_start=int(round(time.time()*1000))
70. fixed_m_allTours=KHC_NCN_MDCP_MTSP(mdcp_mtsp,salesman_m=m,ideal_cluster_size=standard_cluster_size,alpha=alpha,model=end2end_model, random_seed=random_seed)
72. total_distance=0
73. for r in fixed_m_allTours:
74. total_distance+=TSP_tour_distance(r)
75. different_m_results.append(total_distance)
77. end_time=int(round(time.time()*1000))
78. time_consumed=end_time-time_start
80. print("----------cluster sizes: m={}---------------".format(m))
81. for r in fixed_m_allTours:
82. print("cluster size:{}".format(len(r)))
83. print("----------end cluster sizes---------------")
84. print("total distance: {}".format(total_distance))
85. print("time consumed: {} ms".format(time_consumed))
87. different_m_time_consumed_list.append(time_consumed)
89. return different_m_results[1:], different_m_time_consumed_list[1:]
94. if __name__ == "__main__":
95. config=HyperparametersConfig("config.ini")
97. model_path=config.model
98. standard_cluster_size=config.standard_cluster_size
99. alpha=config.scaling_factor
101. parser = argparse.ArgumentParser(
102. description="Run MTSP experiment with user-provided data_file and k_list."
103. )
104. parser.add_argument(
105. "--data_file", "-d", required=True, type=str,
106. help="Path to the TSP/MTSP data file, e.g., data/eil76.tsp"
107. )
108. parser.add_argument(
109. "--k_list", "-k", required=True, nargs='+',type=int,
110. help="List of cluster sizes, e.g. -k 2 3 4 5"
111. )
112. parser.add_argument(
113. "--random_seed", "-r", required=False,type=int,
114. help="RandomSeed, e.g. 1234; default: None, meaning random"
115. )
117. args = parser.parse_args()
119. data_file = args.data_file
120. if not os.path.exists(data_file):
121. raise FileNotFoundError(f"Data file not found: {data_file}")
123. k_list = args.k_list
125. print("data_file:", data_file)
126. print("k_list:", k_list)
128. if args.random_seed is not None:
129. random_seed=args.random_seed
130. print("random_seed:", random_seed)
131. else:
132. print("random_seed: default, using system time.")
133. random_seed=int(time.time())
135. pure_data_file_name=data_file.split("/")[-1].split(".")[0]
137. k_list_str="_".join([str(k) for k in k_list])
139. timestamp=time.strftime("%Y%m%d%H%M%S", time.localtime())
140. log_tag="{}_TSP{}Model_m_{}_{}".format(pure_data_file_name, standard_cluster_size, k_list_str, timestamp)
142. if not os.path.exists(data_file):
143. raise FileNotFoundError(f"Data file not found: {data_file}")
145. different_m_results, different_m_time_consumed_list=solve_one_MTSP_with_different_K(data_file,model_path,standard_cluster_size,k_list,alpha,log_tag, random_seed=random_seed)
147. result_file_name="{}.txt".format(log_tag)
148. log_dir="logs"
149. if not os.path.exists(log_dir):
150. os.makedirs(log_dir)
151. with open(os.path.join(log_dir, result_file_name), "w") as f:
152. for m, total_distance, time_consumed in zip(k_list, different_m_results, different_m_time_consumed_list):
153. f.write("m={}; total_distance={}; time_consumed={} ms\n".format(m, total_distance, time_consumed))
155. # print results
156. print("-------------------Results-------------------")
157. for m, total_distance, time_consumed in zip(k_list, different_m_results, different_m_time_consumed_list):
158. print("m={}; total_distance={}; time_consumed={} ms".format(m, total_distance, time_consumed))

solving_MTSP_one_instance.py at commit 310a9cc, no license · at the source