简介：面向毕业设计、课程设计与项目开发场景，这份基于JS的百度地图旅行路径规划算法资源，提供了完整可运行的源码、项目文档、算法流程解析与功能介绍。算法以最小生成树为基础，先用克鲁斯卡尔构造带权无向图的最小生成树，再通过贪心策略删除节点度大于二的边，将局部最优逐步转化为全局最优，并利用匹配算法处理一度点，从而解决每个景点只访问一次且总路径最短的旅行规划问题，也适用于理解经典旅行商问题的变体。压缩包共三十四个文件，包含十一份超文本页面、七份脚本、九份可扩展标记配置，以及样式表、标记文档和项目配置，整体仅有八十八KB，目录结构清晰，便于按模块阅读与二次开发。目前已有一百四十人浏览学习，源码经过严格测试，可直接作为毕业设计、课程设计的参考实现，或在此基础上扩展新的路径规划功能。
1. 多点排序才是“百度地图旅行路径规划”真正要解决的问题
普通导航只解决“从 A 到 B”，但毕业设计里最常见的场景是“一天跑 6 个客户、逛 4 个景点、送 8 件货”。人脑按直觉排序时很容易被“当前最近”误导，实际路网距离、红绿灯和单行道会让最终路径多出 20% 甚至更多的里程。基于 javaScript 实现的百度地图旅行路径规划算法，就是把“给定起点和多个目的地，找到一条尽量短的访问顺序”这件事拆成地图展示、距离矩阵计算、最近邻构造和 2-opt 优化四个可独立测试的模块。整套源码和项目文档同时面向毕业设计、课程设计和二次开发，既能直接演示算法效果，也可以换成自己的数据集跑实验。
2. 旅行路径规划问题建模与百度地图 API 选型
写代码之前先把问题变成数学对象。给定 n 个地点，任意两地之间都有“驾车距离”和“驾车耗时”，这就构成一张带权完全图。现实路网里有单行道、高架入口限制，所以 A→B 的距离未必等于 B→A，建议一开始就按有向图处理，避免后期返工。
const travelState = { points: [], // 地点数组，元素是 { name, lng, lat } distMatrix: [], // n x n 驾车距离矩阵，distMatrix[i][j] 表示 i 到 j timeMatrix: [], // n x n 驾车耗时矩阵，单位秒 bestOrder: [] // 最终访问顺序，存储的是 points 的下标 };这个对象就是整个旅行路径规划算法的全局状态。把地图覆盖物、算法计算和矩阵缓存都收敛到它上面，可以避免页面里堆满全局变量。调试时只需在控制台打印travelState就能看清每一步的输入输出。
2.1 从“旅行安排”到“TSP 完全图”的抽象过程
旅行路径规划算法本质上是 TSP（旅行商问题）的一个变体：从一个固定起点出发，访问所有地点后不需要返回起点，求最短路径。因为不需要回到起点，所以它比标准 TSP 稍微简单，但仍属于 NP-Hard 问题，没有办法保证多项式时间内找到全局最优解。
我一般会在文档里这样写输入输出：
- 输入：
travelState.points，至少包含经纬度和名称。 - 输出：
travelState.bestOrder，例如[0, 3, 1, 2]表示从第 0 号点出发，先后访问 3、1、2 号点。 - 权重：优先使用驾车距离，因为用户对“公里数”更敏感；如果要做时间窗约束，再用
timeMatrix作为第二权重。
边权重不对称这一点容易被忽略。如果直接按对称矩阵优化，算法结果可能在实际路网上变成“无法左转”的假路径。所以我在代码里保留isDirected的判断，构造矩阵时默认把distMatrix[i][j]和distMatrix[j][i]分开请求。
2.2 百度地图 JavaScript API 与 Web 服务距离矩阵的选型对比
百度地图相关能力并不只有一种取法。做毕业设计前先列一张对比表，可以省下大量重写时间。
| 方案 | 数据来源 | 请求方式 | 优点 | 局限 |
|---|---|---|---|---|
BMapGL.DrivingRoute | 浏览器端 JavaScript API | 每次计算一对点 | 直接在地图上看到轨迹，无需后端 | 循环请求多，耗时久，配额消耗快 |
| Web 服务距离矩阵 | 百度地图 Web 服务 API | 后端或代理请求 | 一次请求可算多对点，适合矩阵构建 | 浏览器直接 fetch 有跨域限制，需要代理 |
| 静态图 + 手工数据 | 无实时请求 | 无 | 算法调试最稳定 | 无法体现“真实道路距离” |
对于纯 javaScript 前端项目，我最常用BMapGL.DrivingRoute循环求距离。它返回的结果里直接包含距离和耗时，还能顺便拿到路线几何数据，适合在地图上展示。虽然请求量为 n×(n−1) 次，但 10 个点以内的毕业设计场景完全撑得住。
如果导师允许加一个 Node 代理，我会优先换 Web 服务距离矩阵。前端只发一个经纬度数组，后端拼参数、做缓存、控制并发，前端代码会简单很多。这套设计写进项目文档里，也能体现你对前后端职责划分的思考。
2.3 地图、数据、算法、视图四层模块划分
源码结构直接决定项目文档好不好写。常见做法是分成四个模块：
- 地图模块：负责初始化
BMapGL.Map，添加 Marker 和 Label。 - 数据模块：负责把
points变成distMatrix，包括异步调度、错误重试和缓存。 - 算法模块：只接受矩阵，不碰 DOM，返回访问顺序。
- 视图模块：把最终顺序画成 Polyline，更新面板上的里程信息。
算法模块与地图模块解耦后，可以直接在 Node 环境里用假矩阵做单元测试，也可以把同一套 TSP 算法复用到打车聚合、快递配送等场景。课程设计答辩时，这一条“可测试性”往往是加分项。
3. HBuilderX 初始化工程并实现旅行路径规划算法源码
现在进入可运行的前端实现。下面的步骤以百度地图 GL 版 JavaScript API 为例，开发工具用 HBuilderX。HBuilderX 里创建一个普通 Web 项目，配置好 html、css、javascript 后，内置浏览器和控制台可以直接调试，比手动开本地服务器省事。
3.1 最小 HTML 工程和百度地图脚本加载
<!DOCTYPE html> <html lang="zh-CN"> <head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>百度地图旅行路径规划</title> <style> body, html { margin: 0; height: 100%; } #map { width: 100%; height: 100%; } </style> </head> <body> <div id="map"></div> <script type="text/javascript" src="https://api.map.baidu.com/api?type=webgl&v=1.0&ak=你的密钥"></script> <script src="algorithm.js"></script> <script src="main.js"></script> </body> </html>这段 html 里最关键的是type=webgl参数，它让百度地图加载 GL 版命名空间BMapGL。如果换用旧版 v3.0，命名空间就变成BMap，下面代码里的BMapGL.Map要同步替换。ak参数必须在百度地图控制台申请，并且要配置域名白名单，否则本地打开页面会报“校验失败”。
3.2 初始化地图和添加 POI 地点的 JavaScript 函数
const map = new BMapGL.Map('map'); map.centerAndZoom(new BMapGL.Point(116.404, 39.915), 12); map.enableScrollWheelZoom(true); function addPoint(name, lng, lat) { const point = new BMapGL.Point(lng, lat); const marker = new BMapGL.Marker(point); const label = new BMapGL.Label(name, { position: point, offset: new BMapGL.Size(-12, -28) }); map.addOverlay(marker); map.addOverlay(label); travelState.points.push({ name, lng, lat }); }centerAndZoom的第一个参数是地图中心点，第二个是缩放级别。城市级用例设置 12，如果是整个区县可以放宽到 10。Label的 offset 需要根据文字宽度微调，避免压住 Marker。这里所有地点都直接使用百度坐标 BD-09，不要混用其他坐标系，否则后面绘制路线时会出现几十米的偏移。
3.3 用 Promise 封装驾车距离获取并构建距离矩阵
BMapGL.DrivingRoute的回调风格和现代 JavaScript 不太合拍。我习惯用 JavaScript 函数把它包成 Promise，再用async/await串行构建矩阵。串行虽然慢一点，但不容易触发百度地图配额限制。
function getDrivingSegment(fromIdx, toIdx) { return new Promise((resolve, reject) => { const start = travelState.points[fromIdx]; const end = travelState.points[toIdx]; const driving = new BMapGL.DrivingRoute(map, { onSearchComplete(results) { if (driving.getStatus() === BMAP_STATUS_SUCCESS) { const route = results.getPlan(0).getRoute(0); resolve({ distance: route.getDistance(), duration: route.getDuration() }); } else { reject(new Error(`路线规划失败，状态码 ${driving.getStatus()}`)); } } }); driving.search(new BMapGL.Point(start.lng, start.lat), new BMapGL.Point(end.lng, end.lat)); }); } async function buildDistanceMatrix() { const n = travelState.points.length; for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { if (i === j) continue; try { const res = await getDrivingSegment(i, j); travelState.distMatrix[i][j] = res.distance; travelState.timeMatrix[i][j] = res.duration; } catch (e) { console.error(`计算 ${i} -> ${j} 失败`, e); } } } }这里需要注意getRoute(0)读取的是第一条子路线。某些跨城路线会返回多条 plan，默认取第一条即可；如果追求更严格的结果，可以对所有 plan 做getDistance()求最小值。代码里的travelState.distMatrix[i][j]是方向性的，i 到 j 和 j 到 i 各算一次，因此矩阵构建的时间复杂度是 O(n²) 次网络请求，而不是 O(n)。
3.4 最近邻 + 2-opt 优化算法源码
矩阵建好后，算法部分就是纯 javaScript 计算。先用最近邻构造初始解，再用 2-opt 局部优化。最近邻的时间复杂度是 O(n²)，2-opt 在 50 个点以内表现稳定。
const MAX_ITER = 100; const EPSILON = 0.001; function pathDistance(order) { let total = 0; for (let i = 0; i < order.length - 1; i++) { const dist = travelState.distMatrix[order[i]][order[i + 1]]; total += dist || 0; } return total; } function nearestNeighbor() { const n = travelState.points.length; const visited = new Array(n).fill(false); const order = [0]; visited[0] = true; for (let k = 1; k < n; k++) { const current = order[order.length - 1]; let nearest = -1; let nearestDist = Infinity; for (let i = 0; i < n; i++) { const dist = travelState.distMatrix[current][i]; if (!visited[i] && dist != null && dist < nearestDist) { nearestDist = dist; nearest = i; } } order.push(nearest); visited[nearest] = true; } return order; } function twoOpt(order) { let best = order.slice(); let improved = true; let iter = 0; while (improved && iter < MAX_ITER) { improved = false; iter++; for (let i = 1; i < best.length - 1; i++) { for (let j = i + 1; j < best.length; j++) { const candidate = best .slice(0, i) .concat(best.slice(i, j + 1).reverse()) .concat(best.slice(j + 1)); if (pathDistance(candidate) < pathDistance(best) - EPSILON) { best = candidate; improved = true; } } } } return best; } const nnOrder = nearestNeighbor(); const finalOrder = twoOpt(nnOrder); console.log('最近邻里程', pathDistance(nnOrder)); console.log('优化后里程', pathDistance(finalOrder));这段算法源码有几个关键点。i从 1 开始，是为了固定起点下标 0 不被反转队列带走。pathDistance只计算访问顺序相邻节点间的距离，不闭合回路，因为旅行路径规划通常不需要回到起点。如果需求变成“送完货还要回仓库”，只需要在路径末尾补一个起点下标再参与计算即可。EPSILON用来过滤浮点数抖动导致的无效优化。
这里的参数可以按数据规模微调：
| 参数 | 建议值 | 说明 |
|---|---|---|
MAX_ITER | 100 | 节点数超过 30 时可调到 500 |
EPSILON | 0.001 | 小于该差值视为无改进 |
| 起点固定 | 0 | 用travelState.points[0]作为出发点 |
| 矩阵方向 | 有向 | 保留 A→B 和 B→A 两个距离 |
3.5 把优化后的访问顺序绘制成百度地图路线
算法返回的finalOrder是一组下标，比如[0, 3, 1, 2]。要把它变成可视化结果，需要把这些下标映射回坐标点，再添加 Polyline 覆盖物。
function drawOptimizedRoute(order) { map.clearOverlays(); const routePoints = order.map(idx => { const p = travelState.points[idx]; return new BMapGL.Point(p.lng, p.lat); }); const polyline = new BMapGL.Polyline(routePoints, { strokeColor: '#1677ff', strokeWeight: 6, strokeOpacity: 0.8 }); map.addOverlay(polyline); travelState.points.forEach((p, idx) => { const marker = new BMapGL.Marker(new BMapGL.Point(p.lng, p.lat)); map.addOverlay(marker); }); map.setViewport(routePoints); }clearOverlays()会一次性清掉地图上的全部覆盖物，所以要把 Marker 重新添加回来。setViewport的作用是自动调整视野，让所有路线点完整出现在地图可视区内。对于课程设计演示来说，这一步做完就已经具备完整的“输入地点 → 自动排序 → 绘制路线”链路。
4. 算法流程解析与项目文档落盘技巧
毕业设计答辩不会只看能跑的界面，更看重项目文档里能不能把算法流程讲清楚。这一章把“从坐标到路线”的完整流程拆开，并给出可以直接写进文档的结构化内容。
4.1 从输入到路线的五个阶段数据流
旅行路径规划算法的核心流程可以概括为五个阶段：
- 录入 POI 地点，得到一组带经纬度的坐标点。
- 调用百度地图
DrivingRoute构建有向距离矩阵。 - 用最近邻算法从起点开始构造初始访问顺序。
- 对初始顺序做 2-opt 局部优化，直到没有明显改进。
- 将最终下标数组映射为地图 Polyline 并展示。
如果要在论文或课程设计文档里画流程图，直接用以下伪代码代替手画图：
输入：points, distMatrix 输出：order order = nearestNeighbor(points) repeat: improved = false for i = 1 to order.length - 2: for j = i + 1 to order.length - 1: candidate = reverseSegment(order, i, j) if distance(candidate) < distance(order) - EPSILON: order = candidate improved = true until improved == false or iteration >= MAX_ITER这个流程解析的重点是“起点固定”和“路径不闭合”。很多学生作业直接套用标准 TSP 的 2-opt，默认回路闭合，结果在旅行场景里总会多绕一段回头路。我在文档里会特别标注这一区别，因为答辩时老师经常追问。
4.2 项目文档里的算法对比表和模块设计
写项目文档时，不要只贴代码，要放一张实验结果对比表。我可以给一个模板，用你实际跑出的数据替换“示例值”即可：
| 场景 | 节点数 | 最近邻总里程 | 最近邻 + 2-opt 总里程 | 提升比例 |
|---|---|---|---|---|
| 示例数据 | 8 | 42.5 km | 36.8 km | 13.4% |
| 示例数据 | 15 | 109.7 km | 88.2 km | 19.6% |
这类表格同时出现在“算法流程解析”和“测试分析”两章中，会显得数据链完整。 除了结果表，还建议给每个核心 JavaScript 函数写一段模块说明：
buildDistanceMatrix：负责网络请求，返回 Promise，失败时打印日志但不中断。nearestNeighbor：纯函数，输入矩阵，输出初始顺序。twoOpt：纯函数，输入初始顺序，输出优化后的顺序。drawOptimizedRoute：只做视图渲染，不参与算法计算。
把函数职责写清楚后，答辩老师问“如果地点增加 10 倍怎么办”，你就能顺势引出复杂度分析。最近邻是 O(n²)，2-opt 每轮最坏执行 O(n³) 的距离计算。这也是为什么下一章要把算法放进 Web Worker 处理的原因。
4.3 常见运行时报错、状态码与百度地图 API 调试
百度地图相关的 JavaScript 运行时报错，大多数不是算法问题，而是 API 使用姿势问题。
| 报错现象 | 可能原因 | 处理方式 |
|---|---|---|
BMapGL is not defined | API 脚本未加载，密钥错误或网络不通 | 在控制台 Network 面板查看 api 请求 |
NETWORK_ERROR | 域名白名单没有配置 | 百度地图控制台里添加运行域名 |
| 请求频繁被拒绝 | 并发请求太多触发配额限制 | 串行构建矩阵或加请求队列 |
| 路线坐标发生偏移 | 传入的是 GCJ-02 或 WGS-84 坐标 | 统一转换为百度 BD-09 坐标 |
我在buildDistanceMatrix中会把错误打印到控制台而不是抛出后中断，这样即使个别路段失败，其他点的矩阵数据仍然可用。如果某个distMatrix[i][j]缺失，路径规划算法会跳过该边，最终结果可能退化为不可达顺序，所以文档中也建议加入矩阵完整性校验，例如判断travelState.distMatrix.length === n * n。
5. 20 个点之后的旅行路径规划算法验证与性能提升
当地点数量达到 20 以上，最近邻加上 2-opt 依然能跑，但页面可能会因为频繁计算距离而卡顿。这一章给出最实用的两个优化手段。
5.1 固定起点矩阵验证算法结果是否稳定
旅行路径规划算法是确定性的，因为最近邻和 2-opt 都不包含随机数。我第一次跑完总会用下面的代码确认优化是否真实有效：
const nnOrder = nearestNeighbor(); const optOrder = twoOpt(nnOrder); const before = pathDistance(nnOrder); const after = pathDistance(optOrder); console.log(`优化提升 ${((before - after) / before * 100).toFixed(1)}%`);多跑几组随机坐标后，如果提升比例忽高忽低，属于正常现象，因为最近邻的初始解质量依赖点的分布。如果出现负提升，说明twoOpt里的反转逻辑改变了起点位置，检查 i 是否从 1 开始即可。
5.2 把 2-opt 计算放进 Web Worker，避免 UI 卡死
主线程里执行两层循环会影响地图拖动。常见做法是新建tsp-worker.js，把算法从渲染层剥离。
const worker = new Worker('tsp-worker.js'); worker.postMessage({ distMatrix: travelState.distMatrix, currentOrder: nnOrder }); worker.onmessage = (e) => { drawOptimizedRoute(e.data.order); };在tsp-worker.js中复制pathDistance和twoOpt，并把onmessage作为入口：
self.onmessage = (e) => { const { distMatrix, currentOrder } = e.data; const result = twoOptWithMatrix(currentOrder, distMatrix); self.postMessage({ order: result }); };Worker 没有 DOM 访问权限，所以里面不能调用BMapGL，只能做矩阵运算。我把地图相关代码全部留在主线程，这个分层已经足够覆盖绝大多数课程设计和毕业设计场景。
5.3 把“不返回起点”的闭合判定写成配置项
最后留一个值得雕琢的小细节：在很多外卖聚合、巡检路线项目中，“是否返回起点”是一个动态配置，而不是写死的逻辑。在算法模块里增加一个returnToStart参数，路径距离计算时在前端闭合即可。
function pathDistance(order, returnToStart = false) { let total = 0; for (let i = 0; i < order.length - 1; i++) { total += travelState.distMatrix[order[i]][order[i + 1]]; } if (returnToStart) { total += travelState.distMatrix[order[order.length - 1]][order[0]]; } return total; }这样一个函数就能兼容“旅行”和“巡店”两种语义。把returnToStart写进项目文档，相当于给算法流程解析增加了一个可扩展点，后续无论接入到达时间窗还是多车辆约束，矩阵缓存和 Worker 分层都能继续复用。
本文还有配套的精品资源，点击获取
