4. 路径规划基础：图论基础

OHT（空中穿梭车）在洁净室天花板轨道网络中运行，其路径规划与调度本质上是一个图论问题。将物理轨道网络抽象为数学模型，是后续所有优化算法（Dijkstra、A*、遗传算法等）的基石。本节将系统讲解图论的核心概念，并直接映射到OHT轨道网络的实际场景中。

4.1 图的基本构成：节点、边、权重

一个图 G = (V, E) 由两个核心集合组成：

• 节点集合 V (Vertex Set)： 代表网络中的“位置点”。在OHT网络中，节点可以是：
  • 轨道交叉口（Junction）
  • 设备装载口（Load Port）
  • 存储货架（Stocker）的出入端口
  • 轨道端点或变轨点
• 边集合 E (Edge Set)： 代表连接两个节点的“路径段”。在OHT网络中，边对应：
  • 一段直线轨道
  • 一段弯道
  • 一段道岔（Switch）
• 权重 (Weight)： 附加在边上，表示通过该路径段的“代价”。常见权重定义：
  • 距离权重： 轨道段的物理长度（米）。
  • 时间权重： OHT通过该段所需的平均时间（秒），包含加减速。
  • 动态权重： 实时拥堵系数（0.0 ~ 1.0），用于动态路径规划。

4.2 有向图与无向图

根据边是否具有方向性，图分为两种基本类型，它们在OHT网络建模中各有应用场景。

4.2.1 无向图 (Undirected Graph)

边没有方向，表示双向通行。在OHT网络中，标准的直线轨道段通常建模为无向边，因为OHT可以在两个方向上自由行驶。

• 特点： 边 (u, v) 等价于 (v, u)。
• 适用场景： 车间内主干道、非单向循环的轨道段。

4.2.2 有向图 (Directed Graph / Digraph)

边具有方向，用箭头表示，只能单向通行。在OHT网络中，单向环线、道岔的特定通过方向、以及避让段必须建模为有向边。

• 特点： 边 <u, v> 与 <v, u> 是两条不同的边，权重可以不同。
• 适用场景： 单向循环轨道、道岔的强制方向、特定区域的单向交通管制。

4.3 OHT轨道网络的图模型构建

下面通过一个具体的SVG图，展示一个典型的OHT轨道网络如何被抽象为有向图与无向图的混合模型。

4.4 图论在OHT路径规划中的核心作用

将物理网络抽象为图模型后，OHT路径规划问题就转化为标准的图搜索问题。以下是图论在其中的具体应用流程：

1. 建模阶段： 将工厂CAD图纸或轨道布局转化为图数据结构（邻接矩阵或邻接表）。
2. 权重赋值： 根据实时传感器数据（OHT位置、速度、拥堵情况）动态更新边权重。
3. 路径搜索： 使用Dijkstra、A*等算法在图上搜索从起点节点到终点节点的最短/最优路径。
4. 路径执行： 将算法输出的节点序列（路径）下发给OHT的PLC，OHT沿轨道行驶。
5. 动态重规划： 当检测到前方节点拥堵或边权重突变时，在剩余图上重新搜索路径。

4.5 图论基础总结