MATLAB路径规划实战：最短路径与TSP求解算法详解

简介：本资源是一套面向MATLAB初学者与优化算法实践者的旅行商问题（TSP）求解实战方案，聚焦31座城市的最短路径规划这一经典组合优化任务，适用于物流调度、智能交通、运筹学课程设计及算法竞赛备赛等场景。压缩包共16个文件，含14个核心MATLAB脚本（.m）与2个城市坐标文本（.txt），总大小仅8KB；其中包含禁忌搜索、遗传算法两大主流启发式求解框架，涵盖距离计算、种群操作、目标函数、路径可视化等完整模块，代码结构清晰、注释充分，便于理解算法逻辑与调试改进。已有483人学习下载，读者可直接运行获得最优/近优路径结果，并基于现有框架快速替换城市数据、调整参数或对比不同算法性能，是掌握TSP建模与MATLAB实现的高性价比入门实践材料。 做路径规划的工程实现，选型通常有三种路线：Python生态（networkx、OSMnx）、C++（常用于车规级部署）、MATLAB。我这次选MATLAB，核心原因有几个：

第一，矩阵运算是MATLAB的看家本领。路径规划里最基础的距离矩阵计算，在MATLAB里就是一条pdist2的事，Python还得numpy加循环；第二，调试体验好，变量工作区直接看结构，数据集小的时候可以逐步检查每个中间量；第三，可视化零成本，plot、scatter、imagesc一套下来，路径结果长什么样一目了然。对于算法研究和课程项目来说，这个性价比很高。

但其实我也踩过坑。如果你准备拿MATLAB做路径规划，要先把预期放对：MATLAB适合做算法的验证和原型，不适合做最终的产品部署。真正上车的路径规划器还是要用C++或者优化过的Python版本重写。所以这个项目的定位是“快速验证算法思路”，不是“给生产环境交付代码”。

1.2 算法选型：最短路径和TSP分别怎么解

标题里的关键词很清楚：旅行商问题和最短路径。这两个问题看着相似，实际是完全不同的复杂度层级。

最短路径问题（Single-Source Shortest Path）在非负权图上，经典解法是Dijkstra，复杂度O(n²)或者用堆优化到O((n+m)logn)；如果需要所有节点对之间的最短路径，Floyd-Warshall更省事，三重循环搞定。这类问题的特征是：给定起点和终点，找一条总和最小的路径。

旅行商问题（TSP）则是另一回事：给定n个节点，要找一条经过所有节点且只经过一次、最后回到起点的最短环路。这是一个NP-hard问题，城市数量一多，穷举不可能。求解思路分两派：精确算法（动态规划、分支定界）和近似/启发式算法（遗传算法、蚁群算法、模拟退火）。

我这次两边都做了。在这个项目里，最短路径用Dijkstra和Floyd-Warshall，TSP用动态规划（小规模）和遗传算法（大规模）。这两套方案的适用边界差异很大，搞清楚边界比背代码重要得多。

1.3 项目模块划分

我整个工具集按数据层、算法层、展示层三层来组织，后面加代码的时候也好维护：

• 数据层：负责生成地图、导入节点坐标、计算距离矩阵。提供两种数据入口：随机生成示范数据和外部导入的实际坐标数据（支持经纬度、平面坐标）。
• 算法层：最短路径模块（Dijkstra、Floyd-Warshall）、TSP求解模块（状态压缩DP、遗传算法）。
• 展示层：主界面可视化、路径渲染、迭代收敛曲线。

这套划分看起来简单，但实际用了之后会发现，调试算法的时候不用去翻数据代码，换数据的时候也不需要动算法，非常省心。

2. 核心算法原理与MATLAB实现要点

2.1 最短路径：Dijkstra的分步实现

Dijkstra算法的核心思想是贪心加松弛。贪心体现在每次都从未处理的节点里找当前距离最短的那个，然后尝试用它去更新相邻节点的距离。因为边权非负，所以一旦某个节点被弹出，它的最短距离就不会再被后续节点更新了。

MATLAB里用一个数组dist存源点到各节点的当前最短距离，一个逻辑数组visited标记已确定节点，再用一个prev数组记录前驱节点，方便回溯路径。代码实现时我踩过一个坑：MATLAB的下标从1开始，所以所有节点的索引都要统一从1编号，否则回溯路径的时候很容易出边界错误。

核心代码我给一个通用版本：

function [path, dist] = dijkstra(adj, startNode, targetNode) n = size(adj, 1); dist = inf(1, n); prev = zeros(1, n); visited = false(1, n); dist(startNode) = 0; for iter = 1:n % 选择未访问节点中距离最小的 u = -1; minDist = inf; for i = 1:n if ~visited(i) && dist(i) < minDist minDist = dist(i); u = i; end end if u == -1 || u == targetNode break; end visited(u) = true; % 松弛相邻节点 neighbors = find(adj(u, :) > 0); for v = neighbors if ~visited(v) && dist(u) + adj(u, v) < dist(v) dist(v) = dist(u) + adj(u, v); prev(v) = u; end end end % 回溯还原路径 path = []; if isinf(dist(targetNode)) return; end cur = targetNode; while cur ~= startNode path = [cur, path]; cur = prev(cur); if cur == 0 error('路径回溯失败：节点不可达'); end end path = [startNode, path]; end

这段代码里有个关键细节：path = [cur, path]的拼接方式。如果写成path = [path, cur]，回溯出来就是反的，后面还要再翻转一次。虽然不影响正确性，但在工程习惯上，从终点往前回溯时用头插法更直观。

2.2 TSP精确求解：状态压缩DP

TSP的精确解法里，最容易理解且代码量短的是状态压缩动态规划。状态定义是：dp[mask][i]表示已经访问过的城市集合为mask（用二进制位表示），当前停留城市为i时，走过的最小总距离。

转移方程很直接：从当前状态往任意未访问城市j走，更新dp[mask | (1<<j)][j]。

function [bestPath, minCost] = tsp_dp(distMat) n = size(distMat, 1); totalStates = 2^n; dp = inf(n, totalStates); parent = zeros(n, totalStates); dp(1, 1) = 0; for mask = 1:totalStates-1 for last = 1:n if isinf(dp(last, mask)) continue; end for nxt = 1:n if bitand(mask, 2^(nxt-1)) == 0 newMask = bitor(mask, 2^(nxt-1)); newCost = dp(last, mask) + distMat(last, nxt); if newCost < dp(nxt, newMask) dp(nxt, newMask) = newCost; parent(nxt, newMask) = last; end end end end end fullMask = totalStates - 1; minCost = inf; lastCity = -1; for i = 2:n total = dp(i, fullMask) + distMat(i, 1); if total < minCost minCost = total; lastCity = i; end end % 回溯路径 bestPath = []; mask = fullMask; cur = lastCity; while cur > 0 bestPath = [cur, bestPath]; prevCity = parent(cur, mask); mask = bitand(mask, ~2^(cur-1)); cur = prevCity; end bestPath = [1, bestPath]; end

注意两点。第一，DP数组大小是n × 2^n，当n=20时已经要八百万个浮点数，内存开始吃紧；超过25基本就跑不动了。这是状态压缩DP的物理上限，所以它只能作为小规模TSP的精确基准。第二，MATLAB里位运算的写法是bitand、bitor，不能用Python的&、|，很多人刚迁移过来会在这上面卡一下。

2.3 TSP启发式求解：遗传算法

城市数量超过30，状态压缩DP就无法接受了。这时候工程上常用的做法是启发式算法。我选了遗传算法，因为它思想简单、调参直观，而且特别适合这种排列编码的问题。

遗传算法求解TSP有几个关键点：

编码方式直接用城市的排列顺序作为染色体。比如[5 3 1 2 4]表示从5出发依次经过3、1、2、4再回到5的路线。适应度函数取总距离的倒数，距离越小适应度越高。

选择采用锦标赛选择（tournament），避免所有个体快速趋同。交叉算子这里要特别注意：普通的单点交叉会产生重复城市，生成不合法路径。必须用顺序交叉（Order Crossover）或者部分映射交叉（PMX）。我实现里用了顺序交叉：

function [child] = orderCrossover(parent1, parent2) n = length(parent1); pos1 = randi(n - 1); pos2 = randi([pos1 + 1, n]); child = zeros(1, n); child(pos1:pos2) = parent1(pos1:pos2); cursor = 1; for i = 1:n if cursor == pos1 cursor = pos2 + 1; end if cursor > n break; end gene = parent2(i); if ~ismember(gene, child) child(cursor) = gene; cursor = cursor + 1; end end end

变异算子我用的是随机交换两个位置。变异概率不能太大，我实验下来0.05到0.1之间效果比较好，太大容易破坏已经收敛的好解。

function [bestPath, bestCost, costHistory] = ga_tsp(cityPos, popSize, maxGen) n = size(cityPos, 1); distMat = pdist2(cityPos, cityPos); pop = zeros(popSize, n); for i = 1:popSize pop(i, :) = randperm(n); end bestCost = inf; bestPath = []; costHistory = zeros(1, maxGen); for gen = 1:maxGen costs = zeros(1, popSize); for k = 1:popSize costs(k) = tspCost(pop(k, :), distMat); end [genBestCost, idx] = min(costs); if genBestCost < bestCost bestCost = genBestCost; bestPath = pop(idx, :); end costHistory(gen) = bestCost; newPop = zeros(popSize, n); [~, eliteIdx] = min(costs); newPop(1, :) = pop(eliteIdx, :); for k = 2:2:popSize p1 = tournamentSelect(pop, costs); p2 = tournamentSelect(pop, costs); [c1, c2] = orderCrossover(p1, p2); if rand() < 0.08 c1 = swapMutate(c1); end if rand() < 0.08 c2 = swapMutate(c2); end newPop(k, :) = c1; if k + 1 <= popSize newPop(k + 1, :) = c2; end end pop = newPop; end end

3. 实操过程：从数据准备到仿真运行

3.1 数据准备

我建议先测试随机数据来验证算法，通过之后再换真实数据。随机城市坐标生成用：

numCities = 50; cityPos = 100 * rand(numCities, 2); distMat = pdist2(cityPos, cityPos);

注意pdist2默认算的是欧氏距离，如果你的场景是经纬度坐标，必须自己写球面距离函数。这个细节在后面“常见问题”里我再细讲。50个城市用遗传算法跑，种群规模200、迭代500代，结果通常很快收敛到比较稳定的路线。

3.2 距离矩阵的两种构建方式

距离矩阵是整个项目的地基，它的正确性直接决定后面所有算法的结果。模型里的distMat(i,j)表示节点i到节点j的代价，无向图的距离矩阵必须是对称的，即distMat(i,j) == distMat(j,i)。

用坐标直接算距离的方法是：

n = size(cityPos, 1); distMat = zeros(n, n); for i = 1:n for j = 1:n distMat(i, j) = sqrt((cityPos(i,1) - cityPos(j,1))^2 + ... (cityPos(i,2) - cityPos(j,2))^2); end end

虽然循环看起来笨，但对理解距离矩阵的含义有帮助。实际项目可以用pdist2直接替代。注意，如果你从别的地方拿到一个距离矩阵，一定要先验证对称性和对角线元素是否为零，这两个检查能帮你挡掉很多数据错误。

3.3 主流程串联

一个完整的范例流程是这样的：

% 1. 生成或导入数据 cityPos = load('cities.mat'); % 或随机生成 distMat = pdist2(cityPos, cityPos); % 2. 运行遗传算法求解TSP [bestPath, bestCost, history] = ga_tsp(cityPos, 200, 500); % 3. 可视化结果 figure; plot(cityPos(:,1), cityPos(:,2), 'bo', 'MarkerSize', 8); hold on; routeX = cityPos(bestPath, 1); routeY = cityPos(bestPath, 2); routeX(end+1) = routeX(1); routeY(end+1) = routeY(1); plot(routeX, routeY, 'r-', 'LineWidth', 1.5); title(sprintf('TSP最优路径，总距离: %.2f', bestCost));

可视化是路径规划项目里非常直观的验证手段。我第一次跑通的时候，把50个城市的TSP结果渲染出来，中间路线交叉很少，能明显看到遗传算法在迭代200代左右就基本进入稳定阶段。这个收敛曲线也是后面调参的重要依据。

3.4 结果验证与收敛性观察

我建议多做一步验证：小规模问题用DP的精确解和遗传算法结果对比，误差控制在5%以内算正常。比如10个城市，DP跑出的最优距离是1200，遗传算法跑到1250左右，这时候你心里就有底了。我用30个城市测试过，遗传算法多次运行的最优结果和DP精确解误差在3%左右，效果可以接受。

跑遗传算法的时候，把costHistory画出来，你会看到一条典型的收敛曲线——前期断崖式下降，中后期缓慢波动。如果曲线在很早期就变成一条水平线，说明种群已经早熟了，这时候要回头检查变异率和种群多样性，而不是盲目加大迭代次数。我曾在一个60城市的案例里把迭代次数从500加到2000，结果最优距离几乎没变，纯粹浪费时间。后来把变异率从0.05调到0.1，效果立竿见影。

3.5 用App Designer封装演示界面

如果你的项目要给别人演示，或者做课设答辩，建议用MATLAB App Designer包一个简单界面。左边放地图坐标轴，右边放参数输入框（城市数量、种群规模、迭代代数）和两个按钮：“生成数据”和“开始求解”。代码层面把算法封装成独立函数，界面的回调函数只负责传参和接收结果。

这里有个小技巧：在按钮回调里加drawnow来强制刷新绘图，否则长时间循环会让界面卡住。虽然App Designer本身有事件队列，但遗传算法这种重度循环很容易把界面线程占满，加一个drawnow limitrate可以保证界面在求解过程中仍然能拖动、能看到中间结果。

4. 常见问题与排查技巧实录

4.1 坐标数据导致距离矩阵失真

这个坑很隐蔽。如果数据里经度是113.5、纬度是35.2这种数值，直接用欧氏距离计算，出来的距离值完全是失真的。因为角度不是线性距离单位。解决方式有两个：一是如果规划范围不大，可以先用墨卡托投影转到平面坐标；二是直接用球面距离公式。我推荐在GPS/北斗场景下，直接把球面距离封装成一个函数，避免用错了还得回头排查。

function d = haversineKm(lat1, lon1, lat2, lon2) R = 6371; dLat = deg2rad(lat2 - lat1); dLon = deg2rad(lon2 - lon1); a = sin(dLat/2)^2 + cos(deg2rad(lat1)) * cos(deg2rad(lat2)) * sin(dLon/2)^2; c = 2 * atan2(sqrt(a), sqrt(1-a)); d = R * c; end

4.2 遗传算法不收敛或者早熟

遗传算法最常遇到两个问题：一是迭代很多代最优值纹丝不动，二是收敛到一个明显交叉很多的路线。这两个问题大概率出在参数上。我建议先用小规模数据测试，观察每一代的最优值和平均值变化。如果最优值一直不变但平均值还在下降，说明种群多样性还可以，多给点迭代代数可能继续提升；如果平均值也不动了，说明早熟，需要提高变异概率或者增大种群规模。

另外，交叉算子很关键。有一次我图省事直接用了均匀交叉，结果生成的路线里大量重复城市，适应度计算直接出错。排查了半天才发现是交叉方式不合法。如果你自己写交叉算子，一定先验证子代是否包含所有城市恰好一次。

4.3 MATLAB运行性能和并行计算

TSP的遗传算法里，最耗时的部分是适应度计算。城市多的时候，每一代都要算几百个个体的路径总距离。建议提前把距离矩阵算好，适应度函数直接查矩阵，不要现场算坐标距离。

如果装了并行工具箱，把代际循环改成parfor有奇效。需要注意parfor是按逻辑处理器分配任务，不是按物理内核，线程数设置别太离谱。有一次我为了跑快一点设成parpool(16)，结果笔记本直接风扇狂转，后面改回物理内核数才稳定。另外提醒一点：如果你在虚拟机里跑MATLAB，大型计算会明显变慢，因为虚拟机的浮点性能和内存访问效率都打了折扣。

4.4 版本兼容性：工具箱和函数差异

不同MATLAB版本对部分函数的支持有差异。比如pdist2在老版本里需要在Statistics and Machine Learning Toolbox里，新版本基础环境直接可用。我在R2021a和R2022b上都验证过，代码基本通用。如果你用的版本比较老，建议先把pdist2换成自己写的距离函数，省得启动报错。

还有个不太起眼但很常见的问题：randperm在不同版本的随机数生成策略不同，导致同一段代码两次运行结果不一致。如果你需要可复现的实验结果，记得在最前面加一句rng(42)，固定随机种子。这个习惯能省掉很多“为什么这次结果和上次不一样”的疑问。

4.5 典型问题速查表

5. 项目扩展与工程落地思考

5.1 从TSP扩展到动态障碍物场景

TSP解决的是静态路网下的多目标访问顺序问题，但真实场景很少这么理想。比如无人机巡检，目标点之间可能临时出现禁飞区，或者移动的障碍物挡路，这时候需要的是路径重规划。常用的方案有：Dijkstra/A*做局部重规划，或者人工势场算法做动态避障。我的经验是，把“顺序优化”（TSP）和“轨迹生成”（路径规划）分离开，先定访问顺序，再逐段生成可行轨迹，这样逻辑清晰，出了问题也好定位。

5.2 多目标访问顺序的更多变种

实际工程里遇到的往往不是标准TSP，而是它的变种。比如配送车需要在一天内访问若干个客户点，但每个点有时间窗约束（Vehicle Routing Problem with Time Windows）；又比如无人机电量有限，访问完一批点之后必须回充电站，这是带补给点的TSP。这些变种的核心思路仍然是从TSP延伸出来的，区别在于约束条件变多了，优化目标从“距离最短”变成“综合成本最低”。建议先把标准TSP吃透，再往变种上扩展会顺畅很多。

5.3 路径规划结果怎么评估才算合理

做无人车或者机器人路径规划，经常被问到一个问题：这条路径到底好不好？我自己的评估习惯是从四个维度看：

• 最优性：和精确解或者已知最优解的差距。小规模问题可以用DP算精确解，大规模就用多次运行取最佳。
• 计算时效：从输入数据到输出路径的耗时。TSP遗传算法跑几百代可能就要几十秒，实时性要求高的场景必须考虑算法裁剪。
• 路径平滑性：路线是否有大量尖锐转角。对车辆或机器人来说，尖角意味着急刹车和原地转向，实际执行成本很高。
• 结果可复现性：同一输入多次运行，结果波动是否在可接受范围内。

这四个维度不一定同时最优，实际项目里经常要权衡。比如追求计算时效就可能牺牲最优性，追求路径平滑就可能增加总里程。我的建议是：先把四个维度都量化出来，再根据应用场景定权重，不要只看“距离最短”这一个指标。

5.4 把MATLAB代码迁移到实际平台

把MATLAB里的路径规划迁移到真实平台时，要注意传感器坐标系、地图表示、控制执行这几层的对接。MATLAB里跑通的算法只是最顶层决策，实际执行还要考虑运动学约束、障碍物膨胀、实时性要求。我个人的建议是先用MATLAB验证算法正确性，再用ROS或自研框架在C++里实现同一套逻辑，两条线对照测试，能少走很多弯路。

迁移的时候有个比较实用的做法：用MATLAB Coder把已经验证过的函数转成C++代码。但不是所有语法都支持转换，比如动态数组、匿名函数在生成代码时都有限制。准备迁移前先查一下MATLAB Coder的兼容性文档，免得写完了转不了。

最后再分享一个小技巧。我在做路径规划项目的时候，习惯把每个算法的核心函数单独放一个m文件，文件名和函数名保持一致，然后写一个总入口脚本main.m把所有模块串起来。这样不管你是做算法对比、参数调优，还是给别人讲代码，都清晰得多。路径规划这个方向，真正的大坑往往不在算法本身，而在数据、坐标系、边界条件这些不起眼的地方。把这些基础打牢了，后面的路就好走很多。

本文还有配套的精品资源，点击获取