输电线路货运路径规划算法∗

秦 剑 张飞凯 刘中书 刘 晨

（1.中国电力科学研究院有限公司 北京 100055）（2.国网陕西省电力公司建设分公司 西安 710065）

1 引言

一般情况下储存或加工输电线路施工物料的物料站位于交通便利、便于物料装卸的交通要道，而待建的铁塔则多处于偏僻的山区，远离已有公路，仅依靠公路运输无法将物料从物料站运送到远离公路的在建铁塔。针对公路运输的短板，可在路边和铁塔附近分别设置上料点和下料点，在上下料点间架设临时货运索道，实现物料转运。该方法是当下实现输电线路施工物料运输的主流方法。

由于公路交通网的特性和山区地形的复杂性，将输电线路施工物料从物料站运输到铁塔位置有多个可供选择的公路运输路径和索道架设方案。但如何根据三维地理信息数据、公路信息和铁塔与物料站位置搜索出这些备选路径和方案，并通过对比研究筛选出最佳的公路运输和索道运输路径一直是困扰工程人员的难题。

针对公路交通的路径规划算法较为成熟，大量学者采用改进的蚁群算法［1］、遗传网络神经算法［2］、蒙特卡洛模拟和遗传算法［3］、改进的Floyd 算法［4］、Dijkstra 或优化的Dijkstra 算法［5～8］、A*或改进的A*算法［8～12］对公路交通的路径规划问题进行了研究。然而，针对索道运输的路径规划算法研究鲜少有人涉足。因此，工程中只能进行人工路径规划，路径的优劣在很大程度上依赖技术人员的经验，且规划过程中需多次前往现场进行勘测，耗费大量的时间和人力。在进行公路运输和索道运输协同路径规划时，需充分考虑地理信息对物料运输的科学性和经济性的影响，依赖技术人员的经验进行人工路径规划的方式很难选出最优化的路径，会在很大程度上影响施工物料运输的效率与成本。

在输电线路施工领域，亟需一种新的路径规划算法，以运输效率和成本为约束条件，根据地理信息数据自动化协同规划公路运输和索道运输路径，从而降低物料运输路径规划的时间消耗，减小工程人员户外勘测等工作强度，响应现代化线路施工对货物运输的降本增效要求。

2 路径规划主要流程

2.1 输电线路施工物料运输路径规划问题

图1 所示的是一个输电线路施工物料运输路径规划问题的示意图，物料站位于市郊的交通干道附近，施工现场的铁塔位于远离城市的山区，且铁塔与最近的公路还有一段距离。因此需要借助倾斜摄影等技术对实际地理信息数据进行采集和处理。

图1 物料站与铁塔位置示意图

2.2 输电线路施工物料运输路径规划流程

受地理信息的影响和索道架设条件的限制，以部分公路沿线附近的点为上料点可能无法架设合理的索道实现物料的运输。因此，在进行路径规划时，需要先进行索道运输的路径规划工作，确定备选的索道架设方案及上料点位置，再进行公路路径规划工作，最终通过对比筛选，规划出最佳物料运输路径。

在索道运输路径规划时，为保证索道负载运行过程中货物不与地面发生接触，应先搜索出所有满足架设要求的空载索道路径，确定索道路径的架设参数，在此基础上计算货物运动轨迹，通过优化支架优化筛选出负载索道运输路径。

因此提出输电线路施工物料运输路径规划流程，如图2所示，该流程的主要步骤如下所示。

图2 输电线路施工物料运输路径规划流程

1）搜索空载索道运输路径：在索道规划区域选出上/下料点，得到备选索道运输路径与对应的地形剖面；然后模拟空载条件下的索道承载索并采用干涉点搜索法确定支架位置；最后根据架设要求挑选空载索道路径。

2）优化负载索道运输路径：遍历所有空载索道路径，采用工作索结构耦合方法计算货物运动轨迹，对空载条件下索道支架进行优化。

3）搜索公路运输路径：根据公路信息数据、物料站位置和所有筛选出的负载索道路径的上料点位置，规划出从物料站到索道上料点的最佳公路运输路径并计算各路径的公路运输成本。

4）计算物料运输成本并输出最佳路径：以运输效率和成本为条件，选出最佳运输路径组合。

3 索道运输路径搜索

图3展示了规划索道运输路径的主要步骤。

3.1 筛选备选上/下料点

在路径自动规划时，需要先在公路和铁塔附近分别选出备选上料点和备选下料点。

为便于货物运输且又不影响道路交通与铁塔施工，上/下料点与道路/铁塔距离不能太远和太近，将与公路或铁塔的距离为10m～20m 之间的点选出，作为上/下料点的备选点。

在地面平整度方面，通过计算备选点及其周边区域的最大梯度smax和梯度的均方根w筛除地形不平缓的备选上/下料点。区域梯度的均方根的表达式如式（1）所示：

式中：Ω 为备选区域；AΩ为Ω 面积；s(x,y)为(x,y)处梯度。

当w>0.5 或smax>1 时，地面平整度不满足要求，需要删除对应的备选上/下料点。

3.2 获得索道地形剖面

根据备选上/下料点位置，在三维高程上双线性插值获取索道地形剖面。

三维高程（地理信息）为(xj,yk,gjk)，j=1,2,…,nx，k=1,2,…,ny，xj为水平面x轴坐标、yk为水平面y轴坐标，gjk为高程坐标，nx为x轴采样点数量，ny为y轴采样点数量。

如图4（a）所示，将上料点和下料点间连线在水平面的投影，将投影线段均分n份，投影线段各点的水平面坐标分别为(xi,yi)，i=1,2,…,n+1。其中：

图4 地形剖面获取示意图

式中：x1，xn+1分别为上料点、下料点的水平面x轴坐标；y1，yn+1为上、下料点的水平面y轴坐标。

当连线投影点坐标满足xj

建立局部坐标系ouz，u坐标轴方向由上料点投影指向下料点投影，z坐标轴方向向上。投影线段各点的水平面坐标(xi,yi)在坐标系ouz下的坐标为ui。其中：

根据二维地形下插值点(ui,gi)，可拟合得到剖面地形曲线的vg(u)，如图4（b）所示。

式中：φi(u)为拟合曲线的基函数；ci为拟合曲线的拟合系数。

在地形剖面上，只有满足式（6）的水平坐标的集合（即地形剖面上凸点的集合）才适合选做索道支架的架设点。

3.3 搜索索道支架位置

多跨索道的支架将承载索分割为若干索段，不考虑索段间的相互影响，可将每个索段近似为如式（7）所示的抛物线：

式中：vc(u,l,C)为u 处的抛物线高度；l为抛物线起点和终点的水平距离（跨距）；C为抛物线起点和终点的高差；f为跨中垂度，取为0.05。

然后根据索道路径的二维地形剖面和中间支架选取原则，提出干涉点搜索法，为备选上/下料点组合出的备选索道路径设置中间支架。

首先在上料点和下料点分别设置一个支架，上料点处的支架编号为1，下料点支架编号为2。

然后，执行下列程序即可自动计算中间支架坐标(uα,vg(uα))，在此下标α表示支架编号。

其中k表示中间支架的循环更新次数；m为支架数量；p(u)表示承载索与地面高度差随u变化的函数；up为承载索与地面最大干涉位置的水平坐标。

完成索道中间支架自动设置之后，判断索道合理性，即判断是否满足总长度小于3000m、相邻支架跨距大于20m且小于400m、总支架数量不大于9个、弦倾角小于45°等架设条件。

4 索道运输路径优化

4.1 货物运动轨迹计算

使用索道进行物料运输时，在货物载荷的作用下，空载时不与地面接触的承载索可能会与地面接触，且货物所在位置始终是承载索最容易与地面接触的位置。

求解负载索道的载荷位置时，需考虑不同跨间的承载索之间以及承载索与牵引索之间的相互作用。

因此，定义所有支架和载荷为节点，节点间的索段为仅受自重作用的悬链线段，其表达式为［13］

式中：L为悬链线起点和终点的水平距离；h为悬链线起点和终点的高差；H为悬链线水平张力；q为悬链线的线密度；s为悬链线未受张力时的长度；EA0为悬链线的弹性模量与截面积之积；VA为悬链线左端外力的垂直分量；TA为悬链线左端外力的切向分量；TB为悬链线右端外力的切向分量。

根据式（8）可由s、H和VA计算得到L、h、TA等参数。因此，每个索段的悬链线有且仅有3个未知量。

设索道的索段数为N，整条索道的承载索和牵引索共由2N个索段组成，即共有6N个未知量。由文献［14］可建立6N个工作索结构耦合方程，通过求解该非线性方程组即可得到所有索段的悬链线参数。

通过计算载荷在索道各跨间行进过程中的位置，即可得到货物的运动轨迹曲线vr(u)。

4.2 索道运输路径优化流程

对空载索道运输路径进行负载优化是不断在货物运动轨迹与地形的最大干涉位置处添加新的支架的过程，可通过与空载时的支架设置程序类似过程实现。只需将程序中承载索与地面高度差函数p(u)替换为货物运动轨迹与地面的高度差函数q(u)，即

5 公路运输路径规划

5.1 主要流程

在确定索道运输路径后，根据公路信息数据、物料站位置和索道运输的上料点位置，可规划出从物料站到上料点的最佳公路运输路径。

使用A*算法进行路径规划，主要流程如图5所示，主要包括以下步骤：

1）公路骨架提取：对公路的栅格地图进行处理，提取公路的骨架（中心线）［15］，以减少后续路径规划的计算量；

2）公路路径起点和终点搜索：在公路上分别选取距离物料站和上料点最近的点，作为公路运输路径的起点和终点；

3）基于A*算法进行路径规划：计算启发函数和估价函数，引导整个路径搜索过程，快速找到从起点出发到达终点的最小通行成本和其所对应的最佳路径。

4）判断是否已经遍历所有索道路径：若是，完成公路运输路径搜索；若否，选择下一条索道路径的上料点并返回第2）步。

5.2 基于A*算法的公路运输路径规划

A*算法输入的公路信息数据为栅格地图，每个栅格对应地图上的一个采样点，栅格的取值表示该采样点的状态，当取值为1 时，表示该采样点是公路上的点，当取值为0 时，表示该采样点不是公路上的采样点。

借助通行成本估价函数f(n)引导整个路径搜索过程，快速找到从起点出发到达终点的最小通行成本和其所对应的最佳路径。f(n)可表示为

式中：g(n)为起点到栅格n的实际通行成本，可根据已经搜索的路径进行实际计算；h(n) 为栅格n到终点的通行成本估算值，即为启发函数。

由于公路上的栅格与其周边的八个栅格都是连通的，本文选用式（11）所示的切比雪夫距离［16］作为A*算法的启发函数。

式中：xn和yn分别为栅格n的x和y坐标值；xd和yd分别为终点d的x和y坐标值。

6 算例

针对图1 所示的典型输电线路施工物料运输问题，使用本文所提出的路径规划方法对其进行公路运输与索道运输的协同路径规划，筛选出如图6所示的最佳运输路径。

图6 图1的算例的路径规划结果

针对多个货运路径规划问题进行求解，得到的路径规划结果如表1 所示，平均每个模型约搜索出48 条空载索道路径和6 条满足索道架设要求的负载索道路径以及对应的公路运输路径，平均耗时64.3min。

表1 货运路径规划问题计算结果

与传统依靠人工的路径规划相比，该方法可以快速地遍历所有可选的物料运输路径，并能够选出最优结果，显著提高了路径规划的效率与效果。

7 结语

本文提出了一种输电线路物料运输路径规划算法，结合索道路径搜索及优化、公路运输路径规划等方法，以运输效率和成本为约束条件，根据地理信息数据自动化协同规划联合运输路径。

在货运索道方面，以三维地理信息数据为基础，提出承载索、货物与地面接触的判断方法、索道路径中间支架设置的干涉点搜索方法，给出了具体算法。结合地形剖面和支架点选取原则，实现了索道路径和支架的自动筛选。

在公路运输方面，以公路的栅格地图为基础，进行公路骨架提取、路径起点与终点搜索，最终基于A*算法实现了公路运输路径规划。

与人工方法相比，该方法更加经济高效，能够降低物料运输路径规划的时间消耗，减小工程人员户外勘测等工作强度，响应现代化线路施工对货物运输的降本增效要求。