简介基于时间窗规划与Dijkstra的AGV调度算法MATLAB实现源码附带全部数据面向智能仓储、柔性产线等场景的AGV多车路径规划与冲突消解。代码已通过运行测试可直接使用适合自动化、计算机、电子信息等专业学生用于课程设计、毕业设计或项目初期验证也为算法初学者提供完整可复现的参考工程。压缩包共17个文件主体为15个.m脚本按功能可拆分为时间窗生成与检测、Dijkstra最短路径搜索、调度路径规划、地图初始化及路径绘制等模块另有1个README说明文档和1个许可证文件包体仅17KB结构精简便于阅读和二次改造。目前已有477人学习使用配套数据与源码一并提供。读者可获得一套可直接跑通的AGV调度工程既能观察时间窗策略与Dijkstra算法如何结合解决节点冲突也能基于现有函数扩展更多车辆、随机任务或动态障碍进一步深化对调度算法的理解这一工程既适合教学演示也可为实际AGV系统原型验证提供参考帮助使用者快速掌握时间窗约束建模与图搜索算法落地的关键流程。1. AGV调度为什么绕不开Dijkstra和时间窗自动化仓库里十几台AGV小车在巷道间来回跑单看每一台车的路径都是最短的但放到同一张地图上同时跑就会在交叉路口互相顶死。原因在于路径只解决了空间维度没有解决时间维度。Dijkstra先把单台AGV在栅格地图上的最短路径算出来时间窗再给路径上每个节点标注“哪台车在什么时间段占用该节点”后到的车等在窗口外从机制上避免碰撞。这套MATLAB实现把地图初始化、Dijkstra搜索、时间窗生成、冲突检测拆成了独立文件MapInit、G2D负责地图dijkstraR、GetPath负责寻路Get_TimerWindow、Detection_TW负责时间窗模块边界清晰适合做调度课设、毕设也适合只想快速验证调度算法的工程师。真正理解和改造这套代码关键在弄清两个模块之间怎么衔接。2. 栅格地图初始化与Dijkstra全局路径规划实现这一章先把地图数据结构和单机路径规划走通。后面时间窗阶段的所有计算都依赖本章生成的路径节点序列所以地图建模的细节会直接影响调度质量。2.1 栅格地图的数据结构MapInit.m与G2D.mMapInit.m生成一个0/1矩阵0表示可通行栅格1表示障碍物。G2D.m负责把栅格序列号转成二维坐标。这里放在一起讲是因为邻接矩阵建图、路径回溯、可视化绘图都要反复用到这两个文件。% MapInit.m 核心逻辑 function map MapInit(rows, cols, obstacles) map zeros(rows, cols); % 0可通行, 1障碍 for k 1:size(obstacles, 1) map(obstacles(k,1), obstacles(k,2)) 1; end end % G2D.m 栅格序号转行列坐标 function [x, y] G2D(idx, rows, cols) y ceil(idx / rows); % 列号 x mod(idx - 1, rows) 1; % 行号 end逻辑说明MapInit里obstacles是障碍物坐标列表每一行是一个障碍栅格的行列位置。G2D中的idx如果从1开始编号那么当rows12、idx13时会得到x1、y2也就是第二列第一行的栅格这里x对应行、y对应列。绘图时注意axis equal和axis off通常要一起设置否则栅格地图会被拉伸变形。2.2 Dijkstra邻接矩阵实现dijkstraR.mDijkstra在这里的输入不是地图本身而是由地图转换出的邻接矩阵A。A(i,j)存储节点i到节点j的移动代价为0表示不可达。四邻域移动时代价通常取1如果允许斜向移动对角线的代价取sqrt(2)但很多AGV的物理转向机构不支持斜走所以工程里一般先关掉对角。function [dist, parent] dijkstraR(A, start_node) % A: n*n邻接矩阵, A(i,j)0时表示i到j不可达 % start_node: 起点栅格编号 n size(A, 1); visited false(n, 1); dist inf(n, 1); parent zeros(n, 1); dist(start_node) 0; for iter 1:n % 从未访问节点中找dist最小的 min_dist inf; u 0; for i 1:n if ~visited(i) dist(i) min_dist min_dist dist(i); u i; end end if u 0 break; end visited(u) true; % 松弛邻接节点 for v 1:n if A(u, v) 0 dist(u) A(u, v) dist(v) dist(v) dist(u) A(u, v); parent(v) u; end end end end逻辑说明外层循环控制访问次数最多n次内层第一个循环选取未访问且dist最小的节点u标记为已访问第二个循环遍历所有邻接节点v如果通过u到达v的累计代价比当前dist(v)小就更新dist(v)并记录前驱parent(v)。整个算法跑完后dist中存的是起点到各节点的最短代价parent存的是路径回溯用的前驱节点。这个写法的时间复杂度是O(n²)在100×100以内的栅格地图上就是毫秒级。如果地图规模上万节点可以换成最小堆维护候选集但对AGV调度这个场景来说数组实现足够而且调试时单步看dist和visited的变化非常直观。2.3 路径回溯GetPath.m与A*协议的互换性Dijkstra算完之后parent只是前驱关系需要从目标节点反向回溯出一条完整的节点序列这是GetPath.m做的工作。function path GetPath(parent, start_node, target_node) path target_node; cur target_node; while cur ~ start_node cur parent(cur); path [cur, path]; end end逻辑说明cur从目标节点出发不断取parent(cur)向前推进直到回到起点。这里有一个典型的边界问题如果地图不连通parent链会在起点之前的0处中断所以外部调用前应先检查dist(target_node)是否为inf避免陷入死循环。参数方面start_node和target_node都必须使用和邻接矩阵一致的行号编号。很多AGV调度系统的演示代码默认用A做全局路径搜索因为A用启发式函数加速了搜索过程。这套代码选Dijkstra的意义在于在时间窗调度框架里路径搜索只是冷启动阶段的一次性操作每台车只需要在任务开始时算一次比重很小Dijkstra少了启发式函数的设计和调参可解释性更强出问题容易定位。若后续想替换成A*只需要让A*返回同样格式的parent数组即可。模块函数职责关键输出MapInit.m初始化栅格地图0/1矩阵G2D.m栅格序号与坐标互转x, yBuildAdjacency地图转邻接矩阵A矩阵dijkstraR.m最短路径搜索dist, parentGetPath.m前驱数组回溯路径栅格节点序列3. 时间窗生成、冲突检测与等待策略的MATLAB实现Dijkstra给出的是空间上的路径多台AGV共享同一张地图时节点被谁在什么时间占用必须单独表示。这一章是整套代码的核心时间窗生成和冲突检测两个函数决定了调度质量的上限。3.1 为什么只有路径还不够时间窗的语义一条路径本质上是一个节点数组比如[12, 22, 32, 42]每个节点就是地图上的一个栅格位置。单台AGV走这条路时没有任何问题两台以上AGV同时运行时可能在交叉节点同时到达。时间窗给每个节点附加两个数字enter_time和leave_time表示这台AGV预计从什么时刻进入节点、什么时刻离开节点。在时间窗模型里节点是排他性资源同一时刻只能被一台AGV占用。这条语义是整个冲突检测的基础。注意这里的“占用”不只是车的物理长度还包括转向时间、避让时间等安全余量所以leave_time和enter_time的差一般大于纯行驶时间。3.2 Get_TimerWindow.m从路径生成时间窗function tw Get_TimerWindow(path, v, t_safe) % path: 栅格节点序列例如 [12, 22, 32, 42] % v: AGV行驶速度格/秒 % t_safe: 节点占用的安全余量秒 m length(path); tw(m) struct(node, int16(0), enter, 0, leave, 0); for i 1:m tw(i).node path(i); if i 1 tw(i).enter 0; tw(i).leave 0; else td 1.0 / v; % 边行驶时间 tw(i).enter tw(i-1).leave td; tw(i).leave tw(i).enter t_safe; end end end逻辑说明第一个节点是出发点时间窗置零从第二个节点开始进入时间等于上一节点的离开时间加行驶时间离开时间等于进入时间加t_safe。这里假设每个栅格边长度相等所以行驶时间是固定的1/v。实际项目中如果地图栅格有物理尺寸比如每格0.5米那么行驶时间是0.5/v秒直接用1.0/v会带来整体时间轴缩放的问题。参数物理含义参考值调节影响vAGV行驶速度0.5~1.0格/秒速度越快时间窗越窄吞吐量高但冲突概率上升t_safe节点安全余量2~3秒越大越安全但总完成时间明显拉长path长度路径总步数地图规模决定越长占用资源越多可考虑只对交叉节点建窗提示t_safe不是AGV通过一个栅格的时间而是通过后到下一台车允许进入的最小间隔。调参时先固定v只调t_safe效果最容易判断。3.3 冲突判定Detection_TW.m时间窗表建好之后需要一个函数把所有AGV的时间窗两两比较判断是否重叠。这个函数的效率和准确性直接决定planningPath能否跑通。function [flag, conflict_msg] Detection_TW(tw_all) % tw_all: 所有AGV时间窗的结构体元胞数组 % flag1表示存在冲突, flag0表示无冲突 flag 0; conflict_msg ; na length(tw_all); for i 1:na for j i1:na for p 1:length(tw_all{i}) for q 1:length(tw_all{j}) if tw_all{i}(p).node tw_all{j}(q).node ai tw_all{i}(p).enter; al tw_all{i}(p).leave; bi tw_all{j}(q).enter; bl tw_all{j}(q).leave; if ~(al bi || bl ai) flag 1; conflict_msg sprintf(AGV%d与AGV%d在节点%d冲突, ... i, j, tw_all{i}(p).node); return; end end end end end end end逻辑说明四层循环分别遍历AGV对、节点对、时间窗对。两个时间窗不重叠的条件是“前一个的离开时间小于等于后一个的进入时间”或者“反过来也成立”用!(al bi || bl ai)排除这两个“相离”情况后剩下的就是真正重叠。conflict_msg返回具体冲突节点编号这在多车排错时非常有用。工程里可以在比较时加一个很小的delta_time容差比如al bi 0.01避免浮点运算导致时间窗边缘误判。另一个注意点是这里只检测了节点占用冲突没有检测同一条边上的相向冲突即两台车在相邻节点之间迎面相遇的情况。如果项目里AGV在通道中不允许对向相会需要额外在Detection_TW中补充边占用检测逻辑。3.4 等待策略与空闲窗口OPW.m的作用检测到冲突后有多种处理策略低优先级等待、重新规划路径、原地绕行。这套代码中planningPath走的是“等待”路线本质上是把后插入的AGV时间窗整体向未来平移。具体到实现细节就是OPW.m做的事情——在当前节点的时间窗表中找到一个空闲区间插入。function [insert_time, ok] OPW(node_win_table, t_req, t_hold) % node_win_table: 该节点已预约的时间区间m*2矩阵每行是[start, end] % t_req: 请求进入时间 % t_hold: 需要占用的时间长度 ins t_req; for k 1:size(node_win_table, 1) if ins node_win_table(k,1) ins node_win_table(k,2) ins node_win_table(k,2); % 推到占用区间结束之后 end end % 检查推到之后是否与后续区间再次重叠 insert_time ins; ok true; end逻辑说明ins从期望进入时间开始依次扫描每个已占用区间如果落在某个区间内部就直接跳到该区间的结束时刻循环结束后ins就是可插入的时刻。严格来说这个贪心逻辑对连续多个重叠区间需要再扫第二轮因为推到区间末端后可能紧接着又撞上下一段占用。完整做法是把node_win_table按start排序后用while循环反复扫描直到不再重叠。这里保留的是代码里常见的基本形态便于理解后再加固。4. 多AGV调度主流程从预规划到动态避让的代码串联前两章分别解决了“怎么走”和“怎么占时间”这一章把两者串起来。打开test.m沿调用链看整套调度的顺序是初始化地图为每台AGV算Dijkstra路径按优先级把路径转成时间窗并做冲突检测冲突时触发等待最后绘图验证。4.1 Preplanned_Path.m批量预规划多AGV场景下不需要像单机那样一次只算一条路径。Preplanned_Path.m接收所有AGV的起点和目标点循环调用dijkstraR和GetPath返回一个路径元胞数组。function path_list Preplanned_Path(start_list, target_list, A) % start_list: 每台AGV的起点节点编号 % target_list: 每台AGV的目标点节点编号 % A: 邻接矩阵 n_agv length(start_list); path_list cell(n_agv, 1); for k 1:n_agv [dist, parent] dijkstraR(A, start_list(k)); if isinf(dist(target_list(k))) error(AGV%d: 起点与目标点不连通请检查地图障碍物, k); end path_list{k} GetPath(parent, start_list(k), target_list(k)); end end逻辑说明这个循环的先后顺序没有业务含义它只负责生成每台车的静态最短路径不涉及优先级。真正决定通行次序的是planningPath。注意这里提前检查了isinf(dist(target_list(k)))这是一个非常必要的保护性代码否则GetPath会进入死循环。4.2 planningPath.m按优先级插入时间窗并处理冲突planningPath.m是调度主逻辑。它先按priority排序优先级高的AGV先插入时间窗优先级低的排在后面后面的车发现冲突时就等待。function [tw_all, path_list] planningPath(start_list, target_list, A, v, t_safe, priority) [~, order] sort(priority); path_list Preplanned_Path(start_list, target_list, A); tw_all cell(length(order), 1); for idx 1:length(order) k order(idx); % 当前处理的AGV编号 tw Get_TimerWindow(path_list{k}, v, t_safe); tw_all{k} tw; if idx 1 [flag, ~] Detection_TW(tw_all(1:idx)); while flag % 整体后移当前AGV的时间窗 for p 2:length(tw) tw(p).enter tw(p-1).leave 1.0 / v; tw(p).leave tw(p).enter t_safe; end tw_all{k} tw; [flag, ~] Detection_TW(tw_all(1:idx)); end end end end逻辑说明外层循环按优先级从高到低插入AGV。每次插入新AGV后用Detection_TW检查已经插入的前idx台车的全部时间窗冲突时把当前AGV时间窗整体向后平移一个固定步长再次检测直到无冲突。这里的“整体后移”是一种简化策略它假设当前AGV在所有冲突节点之前减速等待然后整条链路后移代价是可能引入多余的等待时间。常见的优化做法是记录每个冲突节点需要的等待时长插入到对应窗口前后续窗口按累计延迟重新计算。提示这个while循环需要设置最大迭代次数比如50次并在超过后抛出提示。否则在极端拥堵地图上可能陷入长时间循环让人误以为程序卡死。实际项目中可以打印当前AGV编号和第几次迭代便于观察收敛情况。4.3 test.m从初始化到出图的完整验证链test.m是整个工程的主入口跑通它就能看到地图上的路径和每台车的时间窗图。下面是一个自定义地图和AGV配置的示例骨架。% test.m 示例 rows 12; cols 14; obstacles [3 5; 3 6; 3 7; 8 10; 8 11; 8 12]; map MapInit(rows, cols, obstacles); A BuildAdjacency(map, rows, cols); % 四邻域邻接矩阵 % 定义三台AGV的起终点和优先级 start_list [f2c(2, 3, rows), f2c(9, 10, rows), f2c(5, 3, rows)]; target_list [f2c(10, 8, rows), f2c(2, 12, rows), f2c(11, 11, rows)]; priority [1, 2, 3]; v 0.8; % 格/秒 t_safe 2.0; % 秒 [tw_all, path_list] planningPath(start_list, target_list, A, v, t_safe, priority); plotMap_Path(map, path_list); % 地图与路径可视化 plotTW(tw_all); % 时间窗图横轴时间纵轴AGV/节点逻辑说明f2c是行列坐标转节点编号的辅助函数与G2D.m互逆。BuildAdjacency需要自己补全逻辑是遍历每个栅格判断上下左右四个相邻栅格是否为障碍把可通行的边写入A代价为1。plotTW会把所有AGV的时间窗画在时间轴上每台车一行横轴是时间能直观看到哪台车在哪段等待。调用顺序函数作用产出1MapInit.m初始化栅格地图0/1矩阵2BuildAdjacency地图转邻接矩阵A矩阵3Preplanned_Path.m批量Dijkstra寻路路径元胞数组4Get_TimerWindow.m单AGV时间窗tw结构体5Detection_TW.m多AGV冲突检测flag消息6planningPath.m调度主循环全部时间窗7plotMap_Path.m / plotTW.m可视化路径图/时间窗图4.4 动态避让场景的处理方式planningPath是离线预调度逻辑实际AGV运行中会出现偏离计划的情况比如某台车因为装载超时延误了几秒此时预先算好的时间窗就不准了。常见做法是把planningPath放进一个周期循环中重新执行每次用AGV实时位置作为新起点对尚未执行的时间窗做局部重规划。在这套代码里这意味着复用Detection_TW和OPW对受影响的AGV重新生成时间窗即可不需要修改Dijkstra路径部分。5. 参数调优、可视化验证与MATLAB排错技巧最后说一些把这套代码从“能跑”调到“跑得稳”的实用经验集中在参数调整和排错两个方向。5.1 三个关键参数的调优顺序先固定v再调t_safe最后动priority。v直接放大或缩小整个时间轴会让所有等待现象同步变化不利于定位单个问题。先用较小的v把调度逻辑跑通确认无冲突后逐渐提速。t_safe从2.0秒起步如果plotTW.m中等待窗口明显偏多把t_safe降到1.5再对比总完成时间。priority的分配原则是优先级越高的车在某个节点上的等待越少越好所以把环节最长的AGV设为最高优先级往往能缩短整体任务时间。这里可以简单算一下如果AGV1跑60步AGV2跑30步按AGV1优先调度后AGV2平均每次冲突等待2秒总共多等约4秒反过来则AGV1可能多等8秒以上明显不划算。5.2 运行时常见问题对照现象可能原因检查位置dijkstraR返回dist为inf地图被障碍割裂起点终点不连通检查obstacles坐标用imagesc画map确认GetPath陷入死循环parent链中断或成环在while循环加迭代上限检查起点编号一致性Detection_TW始终报冲突t_safe过大导致时间窗过宽调小t_safe重新plotTW观察路径有斜穿墙角邻接矩阵开了对角但没做障碍角检查BuildAdjacency中对角移动需检查两个相邻正边plotTW图上一片空白tw结构体字段名与plot函数不匹配使用fieldnames(tw)确认字段为node/enter/leave关于MATLAB版本这套代码核心都是数组操作和structR2018b及之后版本都能直接运行不需要额外工具箱。打开工程后先用test.m跑通链路再逐个文件单步调试是熟悉这套体系最快的方式。5.3 最后验证路径是否正确把test.m中的priority改成[1, 2, 3]和[3, 2, 1]各跑一次对比plotTW.m中同一节点被占用的时间段变化。AGV3从最优先变为最低优先时它在交叉节点的窗口应该整体右移、等待区间变多同时前两台车的窗口几乎不变。如果这个特征出现了说明时间窗插入与冲突检测逻辑工作正常。修改t_safe从2.0到1.5时间窗图的总跨度应明显缩短。跑完这两组对照再回到代码里确认Detection_TW返回的第一个冲突消息对应的是哪辆车核对plotTW中哪个窗口发生了重叠整个调度链路就算验证清楚了。本文还有配套的精品资源点击获取