规避超载超限货车的导航系统路径规划方法研究

Research on Path Planning Methods for Navigation Systems to Avoid Overloaded and Overweight Trucks

摘要: 受到部分交通设施限载和限高的影响，货车司机需要合理的导航路径规划，该路径规划既要满足全路径交通设施限载和限高，又要实现运行的最小成本，目前缺乏高效的算法流程，因此本文对基础路网进行拓扑，提出了将道路上的货车限制信息相匹配，形成面向货车的约束路网，考虑道路约束信息对路径规划的相互关系，通过计算通行成本，标记合适道路，构建面向超载超限货车的导航系统路径规划方法。最后本文以浙江大学紫金港校区区域为例，构建了与地图相匹配的路径规划算法，展示了货车路径规划工作原理的工作逻辑。

Abstract: Affected by some traffic facilities with load and height restrictions, truck drivers need reasonable navigation path planning, which should satisfy the full path traffic facilities with load and height restrictions, and also realize the minimum cost of operation, so this paper topologizes the basic road network, proposes to match the truck restriction information on the road to form a truck-oriented constrained road network, and considers the interrelationship of road constraint information on path planning. By calculating the access cost and marking the suitable roads, the path planning method of the navigation system for overloaded and overloaded trucks is constructed. Finally, this paper takes the Zijingang campus area of Zhejiang University as an example, constructs the path planning algorithm matching with the map, and shows the working logic of the working principle of truck path planning.

1. 引言

近年来，我国的货运行业得到了极大的发展，但货运车辆违法行为屡禁不止，尤其是超载和超限现象频繁出现，对社会经济造成了不同程度损失并且对人民生命安全带来了未知隐患[1]。如2019年江苏省无锡市发生的桥面垮塌事件就是由于货运车辆超载所致。超载超限现象的成因一方面源于货运行业生态的混乱导致了恶性竞争，另一方面恶性竞争导致运费压低，司机为了获得更大的利润而选择违法运输。

目前，国内外对于超载超限问题的研究较为广泛。许多学者从交通安全角度探讨了超载和超限的危害。根据刘宁的研究，公路超限超载问题不仅影响交通安全，还对基础设施造成严重损害，甚至引发交通事故[2]。黄文元等指出，超载运输对公路设施的破坏呈几何级数增长，且76%的交通事故与超限超载行为相关[3]。不少学者研究发现，车辆严重超载会导致路面结构的早期疲劳破坏，缩短道路使用寿命，引发交通事故和环境污染等问题[4] [5]，强调了制定针对性治理措施的重要性。

在治理超载问题的过程中，导航系统逐渐成为提升超载治理和路径规划的重要工具。在很早之前，国外的有关产业就已经开始了卫星定位系统与导航系统的有机结合。国外如日本的VICS系统以及欧洲和美国的动态交通信息收集与传播系统，已在道路交通信息管理方面取得了较大的成就，为货运安全提供了有力支持[6] [7]。在国内，自上世纪90年代以来，许多科研机构就逐渐开始在导航技术、数字地图和路径规划领域进行探索。但货车行驶路径的规划不仅要考虑车辆本身的属性，还需结合道路的限高限重等限制信息。根据超载超限货车的自身特性，以及道路的特征，货车的路径规划需要解决以下问题：

(1) 货车约束路网的建立。我国的实际道路信息包括限制信息和禁止信息，其中限制信息包括限高和限重，禁止信息则是该道路是否允许该车辆通行[8]。将这些限制信息考虑在内，并与基础路网进行有机的结合，可以为货车提供更加合理的最优路径选择。

(2) 最优路径的选择规划方法。货车最优路径的规划需要考虑到的因素包括限制信息和禁止信息，这是普通的车载导航系统的路线规划算法所不具备的[9]。

综上所述，车载导航已经逐渐普及，但针对货运导航系统将超载超限考虑在内的路径规划方法和模型还需进一步完善，以此为货运司机提供帮助。本文根据超载超限货车的自身特性，以及道路的特征，建立货车约束路网，给出最优路径的选择规划模型和算法。

2. 货车约束路网

2.1. 货车约束数据定义

货车约束数据主要有限高数据，限重数据，禁止数据三种。其中限高数据和限重数据为限制数据，若货车无法满足某路段的限制数据，那么该货车就无法通过此路段；禁止为禁止数据，说明货车无法通过此路段或者货车通过产生违章受到处罚。定义通行货车的自身属性为H(h_i, w_i)，其中h_i是通行货车高度数据，w_i是通行货车载重数据。定义相关路段的自身属性为L(r_i, d_i)。其中ri为相关路段的限制数据，r_i = (lo, la, s, ag, l)，lo为相关路段的经度数据，la为相关路段的维度数据，s为相关路段具体的限制数据，ag为相关路段限制数据的角度数据，l为相关路段约束数据类型；d_i为相关路段的禁止数据，d_i = (x_n, m_n)，其中x_n为相关路段的线状禁止数据，m_n为相关路段的面状禁止数据。

2.2. 基础路网与约束数据的录入

2.2.1. 限制数据的匹配录入

对于限制数据，采用点匹配的方法，完成限制数据在基础路网上的录入。首先通过确定约束点位置，来绘制约束框，框选受限制数据影响的相关路段。设约束点坐标为P(x₀, y₀)，相关距离为d，约束框的范围坐标为$\text{J}\left(\text{p},\text{d}\right)\left\{\left(\text{x},\text{y}\right)|{\text{x}}_0-\text{d}<\text{x}<{\text{x}}_0+\text{d},{\text{y}}_0-\text{d}<\text{y}<{\text{y}}_0+\text{d}\right\}$ 。只要路段上的任意一点处于约束框内，则该路段就被视为约束数据的相关路段，如图1所示。约束数据的相关路段的综合为Sx，即约束数据的相关路段上必定存在一点${\text{p}}_{\text{i}}\left({\text{x}}_{\text{i}},{\text{y}}_{\text{i}}\right)$ 满足${\text{p}}_{\text{i}}|\left({\text{x}}_1<{\text{x}}_{\text{i}}<{\text{x}}_2,{\text{y}}_1<{\text{y}}_{\text{i}}<{\text{y}}_2\right)$ ，其中x₁、x₂、y₁、y₂表是约束框的边界坐标，x₁和y₁构成的是约束框的左下角坐标，x₂和y₂构成的是约束框的右上角坐标。随后过约束点P向各个限制数据相关路段做垂线，计算约束点P到各个限制数据相关路段Sx的相邻点p_m，p_m即为过约束点向相关路段做垂线的垂足，约束点P到相邻点p_m的相对距离即为最短距离d₀。由于限制数据相关路段为带有方向的路段，可以计算其方向偏差角a = ap − as，其中ap为约束点P的角度，as为限制数据相关路段的角度，当方向偏差角的角度绝对值|a| < 15时，限制数据与相关路段录入成功，即可以筛选掉角度不合适的路段，保证限制数据录入的准确性。

Figure 1. Matched input of constrained data

图1. 约束数据的匹配录入

2.2.2. 禁止数据的匹配录入

对于禁止数据，可以采用禁止面数据和禁止线数据两种录入方式进行数据录入，其中禁止线数据录入可以选择与限制数据录入相同的点匹配的方法，即通过约束点坐标确定约束框的范围坐标，再通过约束框，框选出相关路段，如图2所示。禁止面录入方法则是将指定的面内所有相关路段设置为禁止。首先要计算禁止面m的外接框(x₁, x₂, y₁, y₂)，其中x₁、x₂、y₁、y₂表示约束框的边界坐标，x₁和y₁构成的是约束框的左下角坐标，x₂和y₂构成的是约束框的右上角坐标，x_i (x₁ < x_i < x₂)指的是外接框内的所有横坐标，y_i (y₁ < y_i < y₂)指的是外接框内的所有总坐标。通过外接框来框选禁止数据相关路段，如果路段的首端位置坐标和末端位置坐标均处于禁止面内，那么该路段为禁止数据相关路段，该路段禁止通行，从而完成禁止路段在地图数据中的录入。

Figure 2. Prohibits the Entry of Matched Data

图2. 禁止数据的匹配录入

2.2.3. 高层路网约束数据的匹配录入

在完成了底层路网中限制性数据和禁止性数据的录入之后，对高层路网的相应路段进行底层路网数据的映射。

若高层路网的某一路段在对应的底层路网中存在任意一段带有禁止性数据的路段，则将该高层路网路段标记为禁止路段。

对于高层路网路段，若其在底层路网中有对应的限制性数据路段，则高层路网路段同样继承限制性数据。此外，高层路网路段的限制性数据取自所有对应底层路网路段限制性数据的最小值。这种取值方法旨在为高层路网提供更为严格的限制性数据，以适应可能的最小限制条件。

3. 货车引导数据生成

3.1. 最优路径的标记

首先对最优路径进行标记。设存在一端点为a和b的路径设为s，采用蛛网分块方法以及Dijkstra的路径规划方法[10]，若路径s构成端点至任一蛛网块W_i的最优路径，则该路径s将被授予蛛网块W_i的最优标记。在此基础上总结出一个规律，任意蛛网块W_i的边界上的端点一定位于其他蛛网块的端点到W_i的最优路径上。基于此，只需得到蛛网块W_i与相关路段的最优标记。设v_i为蛛网块W_i的边界端点，如果路段的通行代价(a, v_i) − 路段通行代价(b, v_i) = 路段通行代价(a, b)，即可认为该路段的最优路径标记为真。

3.2. 最优路径的拓展

在将路段的最优路径标记推广到所有蛛网块的过程中，本文采用双向拓展的方法，即正向拓展和反向拓展相结合的方法。假设某蛛网块的边界节点v_i的数量为n，确认所有为真的最优路线标记，总共需要进行2*n次拓展。若地图中的总蛛网块的数量为w，总共要进行2*n*w次拓展来确认所有为真的最优路线标记。最优路线标记由正向最优路线标记和反向最优路线标记组成，在蛛网块路网中以蛛网块为基本单位进行最优路线标记的收纳。

如此，货车引导数据以及生成，为之后最优路径规划奠定了基础。

4. 面向约束地图的路径规划

4.1. 起止点录入

起点和终点是路径规划最根本的两个约束点，只有将终点和起点与上文所述的约束地图有机结合在一起，才可以进行相应的路径规划操作。起点和终点在地图上的录入有不同的方法和不同的结果。本文以通行代价作为考量来阐述起点与终点的录入。面向约束地图的路径规划首先需要通过起止点录入的方法把起止点录入到相关的路段或者端点上，并且计算经过所有出口需要的代价。

4.1.1. 起点录入的三种情况

起点录入会产生三种结果：一、起点录入到地图中的单向路段，二、起点录入到地图中的双向路段，三、录入到地图中的端点位置。当起点录入到地图中的单向路段时候，将单向路段设为s₁，如果存在起点设为s，起点到路段出口的长度设为d，录入点设为m，路段的端点设置为a、b，路段的出口设为C₁、C₂、C₃，该起点的通行代价 = 通行代价(d) + 通行代价(b, C_i)。当起点录入到地图中的双向路段时候，将双向路段设为s₂，若存在起点设为s，起点到路段两个端点的长度分别设为该起点到一端出口的通行代d₁和d₂，录入点设为m，路段的端点设为a、b，路段的出口设为Ca₁、Ca₂、Ca₃和Cb₁、Cb₂、Cb₃，该起点到一端出口的通行代价 = 通行代价(d₁) + 通行代价(a, Ca_i)，或者该起点到另一端出口的通行代价 = 通行代价(d₂) + 通行代价(b, Cb_i)。当起点录入到路口时，若存在起点设为s和路段所有的出口C₁、C₂、C₃，该起点到三个路段出口的通行代价全部为0。

4.1.2. 终点录入的三种情况

终点录入同样会产生三种结果：一、终点录入到地图中的单向路段，二、终点录入到地图中的双向路段，三、终点录入到地图中的端点位置。当终点录入到地图中的单向路段时候，将单向路段设为s₁，如果存在终点设为s，路段的出口到终点的长度设为d，录入点设为m，路段的端点设置为a、b，路段的出口设为C₁、C₂、C₃，该终点的通行代价 = 通行代价(d)。当终点录入到地图中的双向路段时候，将双向路段设为s2，若存在起点设为s，终点到路段的两个端点的长度为d₁、d₂，录入点设为m，路段的端点设为a、b，路段的出口设为Ca₁、Ca₂、Ca₃和Cb₁、Cb₂、Cb₃，该终点到一端出口的通行代价 = 通行代价(d₁))或者通行代价 = 通行代价(d₂)。当终点录入到路口时，若存在终点设为s和路段所有的出口C₁、C₂、C₃，该终点到三个路段出口的通行代价为0。

4.2. 货车最优路径的生成

4.2.1. 路线回溯

最优路径的识别涉及从众多潜在路径中筛选出成本最低的解决方案。路线回溯的过程首先从所有通往目的地的路径中确定那些具有最小通行成本的候选路径。随后，通过分析各个节点之间的前驱-后继关系，按照路径的实际走向，逐步回溯至起点，以确定构成最优路径的各个节点。最终，将这些节点顺序连接，构建出一条连贯且成本效益最高的路径，如图3所示。

Figure 3. Backtracking diagram

图3. 路线回溯示意图

4.2.2. 路线校正

在路线回溯阶段完成后，紧接着将执行路线校正处理。为了提升路径优化过程的效率，本文提出了一种方法，旨在校正过程中界定特定的路线矫正范围，并迅速解决存在的相关问题，以实现最优路径的获取。例如，在实际驾驶情境中，驾驶员普遍倾向于避免重复穿越相同路段。为此，本研究提出两种策略以快速确定矫正范围并选择合理路径。

第一种策略为移除冗余路径。以获得的四条路径为例，若路径1实际上包含了路径2、路径3和路径4的路段，那么可以仅保留路径1，而舍弃其他重复的路径。此方法通过消除冗余，有效避免了路径的不必要重复，如图4所示。

第二种策略为筛选热点路径。鉴于热点路径相较于其他路径往往伴随着更高的通行成本，本研究建议选择绕开这些热点路径，实现对热点路径的有效筛选。通过这种方法，可以显著降低潜在的通行成本。

Figure 4. Alignment diagram

图4. 路线校正示意图

4.3. 路径规划成果

本文以浙江大学紫金港校区为研究案例，根据道路数据，以校区地图为约束地图，基于上述理论基础，为货车在浙江大学紫金港校区内行驶提供路线支持。

在算法的初始化阶段，首先输入所驾驶货车的高度和货车的载重，如果货车的高度或者货车的载重超过了约束地图中为校区道路定义的限制数据与禁止数据，则该道路对于货车的通行代价为无穷大，如果货车的高度以及货车的载重均满足约束地图中为校区道路定义的限制数据与禁止数据则货车的通行代价为道路的长度。

在接收到输入的高度和载重之后，开始遍历道路的通行代价，完成限制道路的通行代价的重置工作。之后接收输入的出发地序号和目的地序号，通过路径规划函数找到最优路径，并将算法遍历道路通行代价得到的最优路径结果存放在预备数组中，然后调用算法中定义的显示函数向用户展示预备数组中的最优路径结果，并计算其通行代价之和，从而完成最优路径的展示工作。

以货车从紫金港校区丹青学园行驶至医学院为例，如图5，在高度和载重均为3的条件下，算法给出的最优路径为：丹青学园北大门→图书馆→大食堂→教学楼→医学院。如图6，在高度和载重均为50的条件下算法给出的最优路径为：丹青学园北大门→蓝田学园→海洋大楼→建筑工程学院→大食堂→教学楼→医学院。

在载重和高度不同的情况下，通过对紫金港校区内部基础路网进行拓扑，输入货车限制信息匹配，形成面向货车的约束路网，考虑道路约束信息对路径规划的相互关系，高效计算通行成本，给出了不同的最优路径。

Figure 5. Load and height not exceeded path planning results display

图5. 载重和高度未超限路径规划结果显示

Figure 6. Path planning results of excessive load or height

图6. 载重或高度超限路径规划结果显示

5. 结语

在货运行业的背景下，开发专用的车载导航系统具有重大的实际意义，其中路径规划技术是该系统的核心组成部分。本文通过构建一个针对货运车辆约束的路网模型，生成货车导航所需的引导数据，并在此基础上，发展一种面向约束地图的路径规划模型。本文的主要贡献可以概括为以下几点：

(1) 本文针对面向货车导航系统专属的约束数据进行了定义与相关设计，将货车约束数据区分为限高数据，限重数据，禁止数据三种，并进一步将这些数据归类为限制性数据和禁止性数据。通过对比分析这些数据类型的共同点与差异，在专属约束地图的基础上，提出了一种货车引导数据的生成方法，并进一步发展了一套最优路径的标记策略和路径拓展方法。

(2) 本研究提出了一种面向货车的路径规划方法和模型。该模型首先通过起止点的录入，将这些关键信息定位到相应的路段或节点上，并计算出通过所有可能出口所需的代价。在此基础上，构建了路线回溯和路线校正两种最优路径的处理和优化方法，并比较了两种最优路径展示方法的优劣。最后以浙江大学紫金港校区区域为例，为货车在浙江大学紫金港校区内行驶提供算法支持。

本文针对穷举搜索算法的低效率，提出对基础路网进行拓扑并附上货车限制信息，形成面向货车的约束路网，考虑道路约束信息对路径规划的相互关系，通过计算通行成本，标记合适道路，构建面向超载超限货车的导航系统路径规划高效算法。最后本文以浙江大学紫金港校区区域为例，构建了与地图相匹配的路径规划算法，展示了货车路径规划工作原理的工作逻辑。

基金项目

广西重点研发计划项目(桂科AB24010305)。

NOTES

^*通讯作者。