1. 项目缘起从“纸上谈兵”到“动手算路”最近在做一个关于物流路径优化的内部项目核心算法绕不开经典的旅行商问题。为了测试算法在不同数据规模下的表现我需要一个覆盖全国主要城市的、坐标精确的数据集。网上能找到的要么是几个城市的简单示例要么是动辄几百个城市的国际数据集就是没有一份刚好覆盖中国所有省级行政中心包括港澳台的、同时包含经纬度和平面坐标的TSP标准数据。这让我意识到很多朋友在入门运筹学、路径规划或者GIS开发时可能都卡在了“找数据”这一步。没有一份好数据再精妙的算法也像是无米之炊。所以我决定自己动手整理一份“中国34个城市TSP数据集”。这份数据不仅包含了34个城市的名称更重要的是我提供了两套坐标系统一套是大家熟悉的WGS84经纬度用于地图显示和球面距离计算另一套是经过高斯-克吕格投影转换后的平面直角坐标用于大多数需要欧氏距离的经典TSP算法。这样一来无论是做算法演示、课程作业还是进行严肃的学术研究你都可以直接“开箱即用”。下面我就把数据整理的过程、背后的原理、以及使用时的关键注意事项毫无保留地分享出来。2. 数据核心34个城市与两套坐标系统的详解这份数据集的核心价值在于其完整性和实用性。我选取了中国大陆31个省、自治区、直辖市的省会首府城市加上香港、澳门两个特别行政区以及台湾地区的台北市共计34个关键节点。这基本上构成了一个覆盖全国版图的、具有代表性的路径网络。2.1 城市名单与数据来源确认首先明确城市列表是基础。我参考了国家权威的地理信息资料确保行政级别和名称的准确性。列表如下按拼音排序 北京、上海、天津、重庆、哈尔滨、长春、沈阳、呼和浩特、石家庄、太原、济南、郑州、西安、兰州、西宁、银川、乌鲁木齐、合肥、南京、杭州、长沙、南昌、武汉、成都、贵阳、昆明、南宁、拉萨、海口、广州、福州、台北、香港、澳门。注意城市坐标的获取必须使用可靠来源。我采用的是通过专业GIS平台从权威底图数据中提取的市政府或城市中心点的坐标而非简单从某些地图API获取这能最大程度保证坐标的代表性和一致性避免因选取“火车站”、“机场”等特定地标带来的位置偏差。2.2 经纬度坐标WGS84的全球通用语言我们最常接触的经纬度是基于WGS84坐标系。这份数据中每个城市都有一对(经度, 纬度)值例如北京的坐标大约是(116.4074, 39.9042)。这里的经度范围大约在东经73°到东经135°之间纬度范围大约在北纬18°到北纬53°之间。为什么必须用WGS84因为它是GPS的全球标准也是绝大多数在线地图如谷歌地图、高德地图、百度地图使用的坐标系统。当你需要将TSP的求解结果可视化到网页地图或移动端App上时WGS84经纬度是唯一不需要额外转换、可直接使用的格式。计算两个经纬度点之间的实际距离需要使用球面三角公式如Haversine公式而不是简单的欧氏距离。2.3 平面坐标为经典TSP算法准备的“舞台”绝大多数教科书和开源算法库如Concorde, LKH中的TSP算法都默认输入点是二维平面上的点并计算它们之间的欧氏距离。直接将经纬度当作平面坐标使用在中小范围内误差尚可接受但在中国这么大的跨度下会引入巨大的形变导致距离计算完全失真。因此我必须将经纬度坐标投影到平面上。我选择了高斯-克吕格投影3度带。这是一种保角投影能保证在小范围内角度和形状不变形非常适合东西跨度大的中国地区。我使用专业工具如ArcGIS Pro或开源的PROJ库将所有城市的WGS84经纬度统一投影到了CGCS2000坐标系下的3度带中央经线根据城市位置选择例如东部地区常用120°E。转换后每个城市会得到一对(X, Y)的平面直角坐标单位是米。这个转换过程解决了什么它把地球曲面上的点“熨平”到了一个二维平面上。转换后的坐标其X值代表东西方向东为正Y值代表南北方向北为正。此时城市A(X1, Y1)和城市B(X2, Y2)之间的直线距离sqrt((X1-X2)^2 (Y1-Y2)^2)就可以近似代表它们在地球表面的实际最短路径距离在投影带内精度很高。你的TSP算法现在可以直接处理这些(X, Y)点了。3. 坐标转换实操从原理到工具的完整链路你可能好奇这个从经纬度到平面坐标的“魔法”是怎么实现的。这里我抛开复杂的数学公式用“拍扁橘子皮”的类比来解释并给出两种可实操的方法。3.1 投影转换的核心思想与参数选择想象地球是一个橘子经纬度网格画在橘子皮上。你要把这块橘子皮完整地铺平在桌子上且尽量保持上面每个小区域的形状不变。高斯-克吕格投影就是这样一种“剥皮铺平”的方法。它把地球按经度分成一个个窄条带例如3度一个带每个带单独投影。关键参数决策投影类型选择“横轴墨卡托投影”Transverse Mercator这是高斯-克吕格投影的数学基础。中央经线我选择3度分带。对于中国大部分地区常用的中央经线有75°, 78°, ... , 132°, 135°等。为了平衡变形我为不同区域的城市选择了合适的带。例如东部沿海城市如上海、杭州使用120°E作为中央经线。坐标系目标平面坐标系我选用CGCS2000。它是中国最新的国家大地坐标系与WGS84在厘米级精度上非常接近更适合国内应用。EPSG:4524、EPSG:4525等就是CGCS2000的3度带投影编码。提示如果你使用ArcGIS Pro在“投影”工具中选择“WGS 1984”作为输入地理坐标系输出坐标系选择“CGCS 2000 3 Degree GK”开头的相应带号如“CGCS2000_3_Degree_GK_Zone_40”。如果使用代码PROJ库的转换字符串类似projtmerc lat_00 lon_0120 k1 x_0500000 y_00 ellpsGRS80 unitsm no_defs。3.2 使用PythonPyProj进行批量转换对于开发者或研究人员用代码批量处理是最佳选择。以下是使用pyproj库的示例代码片段from pyproj import Transformer import pandas as pd # 定义转换器从WGS84经纬度 转 CGCS2000 3度带(120E中央经线) # 注意这里是一个示例实际应根据城市经度选择不同中央经线的转换器 transformer Transformer.from_crs(EPSG:4326, EPSG:4525, always_xyTrue) # EPSG:4525 是 CGCS2000 / 3-degree Gauss-Kruger zone 40 (120E) # 假设有一个包含lon(经度), lat(纬度)的DataFramedf_cities df_cities pd.read_csv(cities_wgs84.csv) # 进行坐标转换 df_cities[x], df_cities[y] transformer.transform(df_cities[lon].values, df_cities[lat].values) # 保存结果 df_cities.to_csv(cities_plane_coords.csv, indexFalse)这段代码的要点解析EPSG:4326是WGS84经纬度坐标系的通用编码。EPSG:4525是其中一个CGCS2000 3度带投影的编码。你必须根据城市所在的经度范围选择正确的目标投影带EPSG代码否则转换后的坐标会完全错误。例如乌鲁木齐大约在东经87度可能属于“Zone 29”中央经线87°E其EPSG代码可能是EPSG:4522。always_xyTrue确保输入输出顺序是(经度, 纬度) 和 (X, Y)。转换后的X、Y单位是米数值通常会很大X值通常为几十万到几百万Y值为几百万。3.3 常见陷阱“传递的经纬度不合法”错误分析在转换或使用坐标时你可能会遇到“传递的经纬度不合法”这类错误。这通常不是数据本身的问题而是处理逻辑的bug顺序混淆最常见的错误是把纬度和经度的顺序搞反了。大部分GIS库和函数约定俗成的顺序是(longitude, latitude)即(经度, 纬度)。如果你传成了(lat, lon)就会报错。格式错误输入了字符串而非数字或者字符串中包含非数字字符如中文括号、度分秒符号° 。值域超限经度应在[-180, 180]纬度应在[-90, 90]。如果你不小心把投影后的平面坐标单位米数值很大当作经纬度传进去必然报错。坐标系不匹配你的转换器Transformer定义的源坐标系或目标坐标系与你数据的实际坐标系不符。排查步骤首先打印出出错的那个坐标对检查是否为数字、顺序是否正确、值是否在合理范围内。然后核对转换器初始化时使用的EPSG代码是否与数据匹配。4. 数据应用在TSP求解与可视化中的实战有了这份包含两套坐标的数据我们就可以真正开始“玩转”TSP了。下面我以Python环境为例展示从加载数据、计算距离矩阵到求解和可视化的完整流程。4.1 构建距离矩阵球面距离 vs 平面距离TSP问题的输入通常是一个距离矩阵D其中D[i][j]表示从城市i到城市j的距离。我们应该用哪套坐标来计算这个矩阵呢这取决于你的应用场景。场景一追求计算速度与算法兼容性使用平面坐标如果你的目标是快速测试启发式算法如遗传算法、模拟退火或调用某些只接受欧氏距离TSP的经典库那么请使用平面坐标(x, y)。import numpy as np from scipy.spatial import distance_matrix # 假设df_plane包含x, y列 points df_plane[[x, y]].to_numpy() # 计算欧氏距离矩阵 dist_matrix_euclidean distance_matrix(points, points)场景二需要真实地理距离使用经纬度如果你关心的是车辆实际行驶的公里数或者用于真实的物流规划那么应该基于WGS84经纬度计算球面大圆距离。from math import radians, sin, cos, sqrt, atan2 def haversine_distance(lon1, lat1, lon2, lat2): # 将十进制度数转化为弧度 lon1, lat1, lon2, lat2 map(radians, [lon1, lat1, lon2, lat2]) # haversine公式 dlon lon2 - lon1 dlat lat2 - lat1 a sin(dlat/2)**2 cos(lat1) * cos(lat2) * sin(dlon/2)**2 c 2 * atan2(sqrt(a), sqrt(1-a)) r 6371000 # 地球平均半径单位米 return c * r / 1000 # 返回公里数 # 计算球面距离矩阵 n len(df_wgs84) dist_matrix_spherical np.zeros((n, n)) for i in range(n): for j in range(n): if i ! j: dist_matrix_spherical[i][j] haversine_distance( df_wgs84.iloc[i][lon], df_wgs84.iloc[i][lat], df_wgs84.iloc[j][lon], df_wgs84.iloc[j][lat] )注意球面距离矩阵通常不是完全对称的由于地球非完美球体及计算精度且计算量比欧氏距离大得多。对于34个城市双重循环计算是可以接受的。4.2 调用求解器与获取路径有了距离矩阵就可以求解了。这里展示用python-tsp库和简单的模拟退火算法import tsplib95 import numpy as np from python_tsp.heuristics import solve_tsp_simulated_annealing # 假设我们使用欧氏距离矩阵 distance_matrix dist_matrix_euclidean # 调用模拟退火算法求解 permutation, distance solve_tsp_simulated_annealing(distance_matrix) print(f找到的路径顺序城市索引: {permutation}) print(f路径总长度: {distance:.2f} 米)permutation是一个列表例如[0, 12, 5, ..., 1]表示从索引0的城市出发依次访问索引12、5...的城市最后返回索引1的城市如果起点固定。你需要将这个索引映射回具体的城市名称。4.3 结果可视化静态地图与交互式地图可视化是检验结果合理性的关键一步。方法一使用Matplotlib绘制静态路径图基于平面坐标import matplotlib.pyplot as plt # 获取按最优路径顺序排列的坐标 optimal_order permutation x_ordered points[optimal_order, 0] y_ordered points[optimal_order, 1] plt.figure(figsize(12, 10)) plt.scatter(points[:, 0], points[:, 1], cred, s50, labelCities) plt.plot(x_ordered, y_ordered, b-, linewidth1, alpha0.7, labelOptimal Route) # 闭合路径 plt.plot([x_ordered[-1], x_ordered[0]], [y_ordered[-1], y_ordered[0]], b-, linewidth1, alpha0.7) for i, (x, y) in enumerate(points): plt.text(x, y, df_plane.iloc[i][city_name], fontsize8, haright) plt.xlabel(X Coordinate (m)) plt.ylabel(Y Coordinate (m)) plt.title(TSP Optimal Route - Plane Coordinates) plt.legend() plt.grid(True, alpha0.3) plt.axis(equal) # 保证x,y轴比例相同图形不变形 plt.show()方法二使用Folium绘制交互式地图基于经纬度这能更直观地展示真实地理路径。import folium # 以北京为中心创建地图 m folium.Map(location[39.9042, 116.4074], zoom_start4) # 将所有城市点添加到地图 for idx, row in df_wgs84.iterrows(): folium.CircleMarker( location[row[lat], row[lon]], radius5, popuprow[city_name], colorblue, fillTrue ).add_to(m) # 根据最优路径索引获取经纬度序列 optimal_path_coords [] for idx in permutation: optimal_path_coords.append([df_wgs84.iloc[idx][lat], df_wgs84.iloc[idx][lon]]) # 闭合路径 optimal_path_coords.append(optimal_path_coords[0]) # 将路径画到地图上 folium.PolyLine(optimal_path_coords, colorred, weight2.5, opacity0.8).add_to(m) # 保存为HTML文件 m.save(tsp_solution_china.html)打开生成的HTML文件你就能看到一个可缩放、可拖动的全国地图上面用红线清晰地标出了TSP算法找到的“最优”环游路径。这种可视化方式极具冲击力能立刻让你感受到算法的效果。5. 进阶探讨数据局限性与算法优化方向虽然这份数据集已经足够应对大多数教学和初步研究场景但如果你想将其用于更接近真实世界的项目有几个关键点必须考虑。5.1 本数据集的假设与局限性“点”城市的假设数据将每个城市抽象为一个点通常是行政中心。现实中物流配送有具体的仓库、门店地址旅行也有具体的景点或酒店。城市内部的路径被忽略了。直线距离 vs 实际路网距离无论是球面距离还是平面欧氏距离计算的都是“直线距离”或“大圆距离”。实际车辆行驶必须遵循公路、铁路网络实际距离会远大于直线距离且受地形、交通规则影响。直线距离通常作为实际距离的下界用于快速评估和算法初筛。对称性假设经典TSP假设从A到B的距离等于从B到A。在现实中由于单行道、上下坡、风向等因素这可能不成立此时问题变为非对称TSP。静态性假设数据是静态的。真实交通中存在拥堵、天气、临时交通管制等动态因素会影响旅行时间成本。5.2 从“学术TSP”到“现实VRP”的跨越真实的物流问题很少是单纯的TSP更多的是车辆路径问题VRP或其变种。你可以基于这份数据尝试更复杂的建模加入容量限制每个城市有货物需求车辆有载重上限。加入时间窗每个城市要求在特定时间段内被访问。多车场、多车辆货物从多个仓库发出由多辆车完成配送。考虑实际路网这是最大的挑战。你需要接入高德、百度等地图API获取城市间实际的行车距离和时间来构建成本矩阵。这能瞬间将问题真实度提升一个量级。API返回的通常是基于当前交通状况的驾驶距离和时间比直线距离可靠得多。5.3 算法选择的经验之谈对于34个城市规模的对称TSP精确算法如动态规划、分支定界已经非常吃力。在实际操作中我通常这样选择快速验证与基线使用最近邻法或插入法快速得到一个可行解。这个解的质量可能一般但计算极快可以作为后续优化算法的起点或者作为一个性能基线。质量与速度的平衡模拟退火和遗传算法是首选。它们实现相对简单调参空间大通常能在合理时间内得到质量非常不错的解。我的经验是对于34个点模拟退火在几分钟内就能稳定找到一个与最优解差距在5%以内的解。追求最高质量可以尝试使用专业的TSP求解器如Concorde目前公认最快的精确求解器之一但对于34个点可能杀鸡用牛刀或者LKH算法一种非常高效的k-opt局部搜索启发式算法在很多问题上能找到最优解。这些工具通常需要编译或者有复杂的接口但性能卓越。利用对称性如果你的问题是对称的且距离矩阵满足三角不等式可以尝试Christofides算法。这是一个近似算法能保证解的长度不超过最优解的1.5倍对于理论分析很有价值。我个人在项目初期喜欢用模拟退火快速出一个“能用”的解用于演示和初步评估。当需要交付一个高质量方案时会花更多时间调优遗传算法的参数或者封装调用LKH算法。6. 数据获取与扩展建议最后谈谈这份数据本身。我整理的数据集将以CSV和JSON两种格式提供包含城市名、拼音、所属省份、WGS84经纬度、CGCS2000平面坐标等字段。数据字段示例city_name,province,longitude,latitude,x_coord,y_coord 北京市,北京市,116.4074,39.9042,441880.23,4427945.67 上海市,上海市,121.4737,31.2304,570123.45,3467890.12 ...如何扩展这份数据集增加城市你可以很容易地通过同样的方法加入更多地级市甚至县级市构建更大规模的测试集。附加属性为每个城市增加“人口”、“GDP”、“需求权重”等属性将TSP扩展为带权重的路径问题。生成标准TSPLIB格式TSPLIB是TSP问题的标准数据格式。你可以将平面坐标和距离矩阵写入.tsp文件这样就能被几乎所有TSP研究软件和库直接读取。创建基准答案对于34个城市的欧氏距离TSP你可以用长时间运行的精确求解器或多次运行高级启发式算法尝试找到一个目前已知的“最优”或“近似最优”解及其路径长度作为后来者验证算法的基准。这份数据集是我在实际工作中“磨刀”的产物。它解决了我当时“找数据难”的痛点也希望它能成为你进入路径优化世界的一块有用的垫脚石。在实际使用中最深的体会是清晰地区分“理论距离”和“现实成本”并根据你的目标选择合适的坐标系统和距离度量方式这比选择哪个算法更重要。很多时候问题建模的方向对了哪怕用一个简单的启发式算法也能得到有实际价值的结果。