一种港区集卡群体路径优化方法及计算机可读介质

1.本发明涉及智能交通中的交通路径规划技术领域，尤其是涉及一种港区集卡群体路径优化方法及计算机可读介质。


背景技术：

2.迪杰斯特拉算法是由荷兰计算机科学家e.w.dijkstra提出的图论中求最短路径的常用算法，是目前对于求解最短路问题最完备、最广泛的算法。但当使用迪杰斯特拉算法对港区集卡行驶路径进行规划时，只考虑最短路径问题而不考虑港区实时路况产生的影响，可能导致大量车辆同时选择同一条最短路径，从而造成拥堵现象，降低港区道路利用率和集卡运输效率。且传统迪杰斯特拉算法在搜索方向上也具有盲目性，搜索范围较大，搜索效率较低，算法缺乏实时性，不具备动态搜索功能。


技术实现要素：

3.为了解决上述问题，本发明提出了一种港区集卡群体路径优化方法及计算机可读介质。
4.本发明方法的技术方案为一种港区集卡群体路径优化方法，具体包括以下步骤：
5.步骤1：结合港区路网的地图分布信息，获取港区路网的每个交叉口及两交叉口之间的路段，定义路段的加权长度，以构建港区路网模型，并获取港区路网的车流量信息；
6.步骤2：获取待决策集卡行驶路径的起始结点和目标结点，以及各路段的加权长度；
7.步骤3：基于待决策集卡行驶路径的起始结点和目标结点，以及各路段的加权长度，采用改进迪杰斯特拉算法获得最优路径。
8.作为优选，步骤1所述构建港区路网模型，具体如下：
9.将港区路网的每个交叉路口定义为港区路网模型的每个结点，两交叉口之间的路段定义为港区路网模型的两结点之间的路段连接状态，两交叉口之间的路段的加权长度定义为港区路网模型的两相连结点之间的路段权重；
10.所述港区路网模型表示为：
11.r＝(v,e,w)
12.v＝{node1,node2,..,noden}
13.e＝{e
x,y
|x∈[1,n]，y∈[1,n]，x≠y}
[0014]
w＝{w
x,y
|x∈[1,n]，y∈[1,n]，x≠y}
[0015]
其中，r表示港区路网模型；v为港区路网模型的结点集合，node
x
为港区路网模型的第x个结点，n为港区路网模型的结点总数；e为港区路网模型的两结点之间的路段连接状态集合，e
x,y
表示港区路网模型的第x个结点与第y个结点之间的路段连接状态，若e
x,y
＝1则港区路网模型的第x个结点与第y个结点之间存在路段，若e
x,y
＝0则不存在；w为港区路网模型的两相连结点之间的路段权重集合，w
x,y
表示港区路网模型的第x个结点与第y个结点之
间的路段权重，若e
x,y
＝0则w
x,y
不存在；
[0016]
所述路段的加权长度是综合考虑路段的实际长度、路段车流量、路段拥堵程度计算求解所得到的长度；
[0017]
步骤1所述获取港区路网的车流量信息，具体如下：
[0018]
通过港区道路管理中心获取港区各路段的车流量数据信息；
[0019]
作为优选，步骤2中基于集卡运输作业任务信息获取待决策集卡行驶路径的起始结点和目标结点；
[0020]
步骤2所述获取各路段的加权长度，具体包括以下步骤：
[0021]
步骤2.1：获取路段k的实际长度lk，其中，1≤k≤s，s为港区路段总数；
[0022]
步骤2.2：获取路段k在通畅状态下集卡通过路段k所需时间tk：
[0023][0024][0025]
其中，t
free,k
表示路段k的自由流行驶时间；vk表示路段k的自由流速度；qk表示路段k的道路车流量；fk表示路段k的通行能力；α为比例参数，β为指数参数，tk表示集卡通过路段k所需时间；
[0026]
步骤2.3：获取路段k在拥堵状态下路段k的拥堵惩罚值ωk：
[0027]
将路段k等距划分成i个子路段，选取拥堵程度最高的子路段的车辆密度作为路段k的拥堵惩罚值ωk；
[0028]
步骤2.4：以路段的实际长度l、路段通畅状态下集卡通过路段所需时间t和路段拥堵状态下路段拥堵惩罚值ω为列，第k条路段的实际长度lk、第k路段通畅状态下集卡通过路段所需时间tk和第k路段拥堵状态下路段拥堵惩罚值ωk为行，其中，1≤k≤s，s为港区路段总数；建立决策矩阵a：
[0029][0030]
对决策矩阵中每个元素依次进行归一化处理，得到决策矩阵中每个元素归一化后的属性值：
[0031][0032]
其中，r
i,j
决策矩阵a中第i行第j列的元素归一化后的属性值，a
i,j
为决策矩阵a中第i行第j列的元素，为第j列中a
i,j
的最小值，为第j列中a
i,j
的最大值，1≤i≤s，1≤j≤3，i、j均为整数；
[0033]
步骤2.5：根据路段的实际长度l、路段通畅状态下集卡通过路段所需时间t和路段
拥堵状态下路段拥堵惩罚值ω三属性，通过德尔菲法，选取专业决策人员成立评价小组，依据(1,9)九标度法，构建判断矩阵，从而获取路段的实际长度l、路段通畅状态下集卡通过路段所需时间t和路段拥堵状态下路段拥堵惩罚值ω路段路段实际长度属性、集卡通过路段所需时间属性、路段拥堵惩罚值属性对应的权重，分别为u1,u2,u3；
[0034]
步骤2.6：由属性权重和属性值，计算各路段的加权长度：
[0035]
wk＝u1r
k,1
+u2r
k,2
+u3r
k,3
[0036]
其中，wk为第k路段的加权长度，u1,u2,u3∈(0,1)，r
k,1
为第k路段的归一化后的路段实际长度属性值,r
k,2
为第k路段的归一化后的路段通畅状态下集卡通过路段所需时间属性值,r
k,3
为第k路段的归一化后的路段拥堵状态下路段拥堵惩罚值属性值；
[0037]
作为优选，步骤3采用改进迪杰斯特拉算法获得最优路径，具体包括以下步骤：
[0038]
步骤3.1：将港区路网结点进行分类，按照算法的搜索方向，分为正向搜索中遍历结点集合d1和反向搜索中遍历结点集合d2；按照算法的搜索范围，分为在扇形搜索范围内结点集合h和不在扇形搜索范围内结点集合q；在算法计算时，扇形搜索范围内的结点分为临时结点集合r和动态结点集合u；
[0039]
步骤3.2：初始化改进迪杰斯特拉算法中的各个参数，将港区路网路段的加权长度w作为改进迪杰斯特拉算法的权重；获取待决策集卡路径的起始结点m和目标结点d，设初始化时u＝{m,d}，化时u＝{m,d}，为空集；判断港区路网模型中遍历结点是否在扇形搜索范围内，若在加入集合h，否则加入集合q；
[0040]
步骤3.3：在集合h中找出与起始结点m、目标结点d有直接边相连的结点将其加入集合r，并从集合h中删除；
[0041]
步骤3.4：在集合r中找出到起始结点m或目标结点d改进算法权重w最小的结点c，将结点c加入集合h并将其从集合r中删除；
[0042]
步骤3.5：找出与结点c直接相连且不在集合h中的结点，将其加入集合r后并将其从集合h中删除；
[0043]
步骤3.6：在集合r中找出到结点c改进算法权重w最小的结点，将其加入集合h并从集合r中删除；
[0044]
步骤3.7：判断d1、d2的交集，若则停止搜索算法结束并输出最优路径；否则执行新一轮双向搜索，直到符合终止条件为止。
[0045]
上述技术方案的有益效果是：本发明对算法的搜索方式和权重进行改进，使算法具有实时性和动态搜索功能，且考虑到实时路况对路径决策产生的影响，提高了算法的搜索效率，可为集卡提供更优的路径决策方案。
[0046]
本发明还提供了一种计算机可读介质，所述计算机可读介质存储电子设备执行的计算机程序，当所述计算机程序在电子设备上运行时，执行所述港区集卡群体路径优化方法的步骤。
[0047]
与现有技术相比，本发明的有益效果是：
[0048]
本发明为了解决传统迪杰斯特拉算法在规划港区集卡行驶路径时只考虑最短路径，忽略港区路况如道路车流量、拥挤程度对路径规划带来的影响，且算法搜索范围大、搜索效率低、缺乏实时性，而提出一种改进的可用于港区集卡群体最优路径决策的迪杰斯特
拉算法。从迪杰斯特拉算法的搜索方式和权重入手，利用双向扇形动态搜索和路段的加权长度改进迪杰斯特拉算法，为集卡提供更优的路径决策方案，提高集卡运输效率和港区道路利用率。
附图说明
[0049]
图1：本发明实施例的方法流程图；
[0050]
图2：本发明实施例的求解方法流程图。
具体实施方式
[0051]
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0052]
下面结合图1-2介绍本发明的具体实施方式为一种港区集卡群体路径优化方法，具体如下：
[0053]
本发明实施例的方法流程如图1所示，包括以下步骤：
[0054]
步骤1：结合港区路网的地图分布信息，获取港区路网的每个交叉口及两交叉口之间的路段，定义路段的加权长度，以构建港区路网模型，并获取港区路网的车流量信息；
[0055]
步骤1所述构建港区路网模型，具体如下：
[0056]
将港区路网的每个交叉路口定义为港区路网模型的每个结点，两交叉口之间的路段定义为港区路网模型的两结点之间的路段连接状态，两交叉口之间的路段的加权长度定义为港区路网模型的两相连结点之间的路段权重；
[0057]
所述港区路网模型表示为：
[0058]
r＝(v,e,w)
[0059]
v＝{node1,node2,..,noden}
[0060]
e＝{e
x,y
|x∈[1,n]，y∈[1,n]，x≠y}
[0061]
w＝{w
x,y
|x∈[1,n]，y∈[1,n]，x≠y}
[0062]
其中，r表示港区路网模型；v为港区路网模型的结点集合，node
x
为港区路网模型的第x个结点，n为港区路网模型的结点总数；e为港区路网模型的两结点之间的路段连接状态集合，e
x,y
表示港区路网模型的第x个结点与第y个结点之间的路段连接状态，若e
x,y
＝1则港区路网模型的第x个结点与第y个结点之间存在路段，若e
x,y
＝0则不存在；w为港区路网模型的两相连结点之间的路段权重集合，w
x,y
表示港区路网模型的第x个结点与第y个结点之间的路段权重，若e
x,y
＝0则w
x,y
不存在；
[0063]
所述路段的加权长度是综合考虑路段的实际长度、路段车流量、路段拥堵程度计算求解所得到的长度；
[0064]
步骤1所述获取港区路网的车流量信息，具体如下：
[0065]
通过港区道路管理中心获取港区各路段的车流量数据信息；
[0066]
步骤2：获取待决策集卡行驶路径的起始结点和目标结点，以及各路段的加权长度；
[0067]
步骤2中基于集卡运输作业任务信息获取待决策集卡行驶路径的起始结点和目标结点；
[0068]
步骤2所述获取各路段的加权长度，具体包括以下步骤：
[0069]
步骤2.1：获取路段k的实际长度lk，其中，1≤k≤s，s为港区路段总数；
[0070]
步骤2.2：获取路段k在通畅状态下集卡通过路段k所需时间tk：
[0071][0072][0073]
其中，t
free,k
表示路段k的自由流行驶时间；vk表示路段k的自由流速度；qk表示路段k的道路车流量；fk表示路段k的通行能力；α为比例参数，β为指数参数，tk表示集卡通过路段k所需时间；
[0074]
步骤2.3：获取路段k在拥堵状态下路段k的拥堵惩罚值ωk：
[0075]
将路段k等距划分成i个子路段，选取拥堵程度最高的子路段的车辆密度作为路段k的拥堵惩罚值ωk；
[0076]
步骤2.4：以路段的实际长度l、路段通畅状态下集卡通过路段所需时间t和路段拥堵状态下路段拥堵惩罚值ω为列，第k条路段的实际长度lk、第k路段通畅状态下集卡通过路段所需时间tk和第k路段拥堵状态下路段拥堵惩罚值ωk为行，其中，1≤k≤s，s为港区路段总数；建立决策矩阵a：
[0077][0078]
对决策矩阵中每个元素依次进行归一化处理，得到决策矩阵中每个元素归一化后的属性值：
[0079][0080]
其中，r
i,j
决策矩阵a中第i行第j列的元素归一化后的属性值，a
i,j
为决策矩阵a中第i行第j列的元素，为第j列中a
i,j
的最小值，为第j列中a
i,j
的最大值，1≤i≤s，1≤j≤3，i、j均为整数；
[0081]
步骤2.5：根据路段的实际长度l、路段通畅状态下集卡通过路段所需时间t和路段拥堵状态下路段拥堵惩罚值ω三属性，通过德尔菲法，选取专业决策人员成立评价小组，依据(1,9)九标度法，构建判断矩阵，从而获取路段的实际长度l、路段通畅状态下集卡通过路段所需时间t和路段拥堵状态下路段拥堵惩罚值ω路段路段实际长度属性、集卡通过路段所需时间属性、路段拥堵惩罚值属性对应的权重，分别为u1,u2,u3；
[0082]
步骤2.6：由属性权重和属性值，计算各路段的加权长度：
[0083]
wk＝u1r
k,1
+u2r
k,2
+u3r
k,3
[0084]
其中，wk为第k路段的加权长度，u1,u2,u3∈(0,1)，r
k,1
为第k路段的归一化后的路段实际长度属性值,r
k,2
为第k路段的归一化后的路段通畅状态下集卡通过路段所需时间属性值,r
k,3
为第k路段的归一化后的路段拥堵状态下路段拥堵惩罚值属性值；
[0085]
步骤3：基于待决策集卡行驶路径的起始结点和目标结点，以及各路段的加权长度，采用改进迪杰斯特拉算法获得最优路径；
[0086]
如图2所示，所述基于待决策集卡行驶路径的起始结点和目标结点，以及各路段的加权长度，采用改进迪杰斯特拉算法获得最优路径，具体包括以下步骤：
[0087]
步骤3.1：将港区路网结点进行分类，按照算法的搜索方向，分为正向搜索中遍历结点集合d1和反向搜索中遍历结点集合d2；按照算法的搜索范围，分为在扇形搜索范围内结点集合h和不在扇形搜索范围内结点集合q；在算法计算时，扇形搜索范围内的结点分为临时结点集合r和动态结点集合u；
[0088]
步骤3.2：初始化改进迪杰斯特拉算法中的各个参数，将港区路网路段的加权长度w作为改进迪杰斯特拉算法的权重；获取待决策集卡路径的起始结点m和目标结点d，设初始化时u＝{m,d}，化时u＝{m,d}，为空集；判断港区路网模型中遍历结点是否在扇形搜索范围内，若在加入集合h，否则加入集合q；
[0089]
步骤3.3：在集合h中找出与起始结点m、目标结点d有直接边相连的结点将其加入集合r，并从集合h中删除；
[0090]
步骤3.4：在集合r中找出到起始结点m或目标结点d改进算法权重w最小的结点c，将结点c加入集合h并将其从集合r中删除；
[0091]
步骤3.5：找出与结点c直接相连且不在集合h中的结点，将其加入集合r后并将其从集合h中删除；
[0092]
步骤3.6：在集合r中找出到结点c改进算法权重w最小的结点，将其加入集合h并从集合r中删除；
[0093]
步骤3.7：判断d1、d2的交集，若则停止搜索算法结束并输出最优路径；否则执行新一轮双向搜索，直到符合终止条件为止。
[0094]
本发明的具体实施例还提供了一种计算机可读介质。
[0095]
所述计算机可读介质为服务器工作站；
[0096]
所述服务器工作站存储电子设备执行的计算机程序，当所述计算机程序在电子设备上运行时，使得所述电子设备执行本发明实施例的港区集卡群体路径优化方法的步骤。
[0097]
应当理解的是，本说明书未详细阐述的部分均属于现有技术。
[0098]
应当理解的是，上述针对较佳实施例的描述较为详细，并不能因此而认为是对本发明专利保护范围的限制，本领域的普通技术人员在本发明的启示下，在不脱离本发明权利要求所保护的范围情况下，还可以做出替换或变形，均落入本发明的保护范围之内，本发明的请求保护范围应以所附权利要求为准。

技术特征：
1.一种港区集卡群体路径优化方法，其特征在于，包括以下步骤：步骤1：结合港区路网的地图分布信息，获取港区路网的每个交叉口及两交叉口之间的路段，定义路段的加权长度，以构建港区路网模型，并获取港区路网的车流量信息；步骤2：获取待决策集卡行驶路径的起始结点和目标结点，以及各路段的加权长度；步骤3：基于待决策集卡行驶路径的起始结点和目标结点，以及各路段的加权长度，采用改进迪杰斯特拉算法获得最优路径。2.根据权利要求1所述的港区集卡群体路径优化方法，其特征在于：步骤1所述构建港区路网模型，具体如下：将港区路网的每个交叉路口定义为港区路网模型的每个结点，两交叉口之间的路段定义为港区路网模型的两结点之间的路段连接状态，两交叉口之间的路段的加权长度定义为港区路网模型的两相连结点之间的路段权重；所述港区路网模型表示为：r＝(v,e,w)v＝{node1,node2,..,node
n
}e＝{e
x,y
|x∈[1,n]，y∈[1,n]，x≠y}w＝{w
x,y
|x∈[1,n]，y∈[1,n]，x≠y}其中，r表示港区路网模型；v为港区路网模型的结点集合，node
x
为港区路网模型的第x个结点，n为港区路网模型的结点总数；e为港区路网模型的两结点之间的路段连接状态集合，e
x,y
表示港区路网模型的第x个结点与第y个结点之间的路段连接状态，若e
x,y
＝1则港区路网模型的第x个结点与第y个结点之间存在路段，若e
x,y
＝0则不存在；w为港区路网模型的两相连结点之间的路段权重集合，w
x,y
表示港区路网模型的第x个结点与第y个结点之间的路段权重，若e
x,y
＝0则w
x,y
不存在；所述路段的加权长度是综合考虑路段的实际长度、路段车流量、路段拥堵程度计算求解所得到的长度；步骤1所述获取港区路网的车流量信息，具体如下：通过港区道路管理中心获取港区各路段的车流量数据信息。3.根据权利要求2所述的港区集卡群体路径优化方法，其特征在于：步骤2所述获取待决策集卡行驶路径的起始结点和目标结点为：基于集卡运输作业任务信息获取待决策集卡行驶路径的起始结点和目标结点。4.根据权利要求3所述的港区集卡群体路径优化方法，其特征在于：步骤2所述获取各路段的加权长度，具体步骤如下：步骤2.1：获取路段k的实际长度l
k
，其中，1≤k≤s，s为港区路段总数；步骤2.2：获取路段k在通畅状态下集卡通过路段k所需时间t
k
：：其中，t
free,k
表示路段k的自由流行驶时间；v
k
表示路段k的自由流速度；q
k
表示路段k的道路车流量；f
k
表示路段k的通行能力；α为比例参数，β为指数参数，t
k
表示集卡通过路段k所
需时间；步骤2.3：获取路段k在拥堵状态下路段k的拥堵惩罚值ω
k
：将路段k等距划分成i个子路段，选取拥堵程度最高的子路段的车辆密度作为路段k的拥堵惩罚值ω
k
；步骤2.4：以路段的实际长度l、路段通畅状态下集卡通过路段所需时间t和路段拥堵状态下路段拥堵惩罚值ω为列，第k条路段的实际长度l
k
、第k路段通畅状态下集卡通过路段所需时间t
k
和第k路段拥堵状态下路段拥堵惩罚值ω
k
为行，其中，1≤k≤s，s为港区路段总数；建立决策矩阵a：对决策矩阵中每个元素依次进行归一化处理，得到决策矩阵中每个元素归一化后的属性值：其中，r
i,j
决策矩阵a中第i行第j列的元素归一化后的属性值，a
i,j
为决策矩阵a中第i行第j列的元素，为第j列中a
i,j
的最小值，为第j列中a
i,j
的最大值，1≤i≤s，1≤j≤3，i、j均为整数；步骤2.5：根据路段的实际长度l、路段通畅状态下集卡通过路段所需时间t和路段拥堵状态下路段拥堵惩罚值ω三属性，通过德尔菲法，选取专业决策人员成立评价小组，依据(1,9)九标度法，构建判断矩阵，从而获取路段的实际长度l、路段通畅状态下集卡通过路段所需时间t和路段拥堵状态下路段拥堵惩罚值ω路段路段实际长度属性、集卡通过路段所需时间属性、路段拥堵惩罚值属性对应的权重，分别为u1,u2,u3；步骤2.6：由属性权重和属性值，计算各路段的加权长度：w
k
＝u1r
k,1
+u2r
k,2
+u3r
k,3
其中，w
k
为第k路段的加权长度，u1,u2,u3∈(0,1)，r
k,1
为第k路段的归一化后的路段实际长度属性值,r
k,2
为第k路段的归一化后的路段通畅状态下集卡通过路段所需时间属性值,r
k,3
为第k路段的归一化后的路段拥堵状态下路段拥堵惩罚值属性值。5.根据权利要求4所述的港区集卡群体路径优化方法，其特征在于：步骤3所述采用改进迪杰斯特拉算法获得最优路径，具体包括以下步骤：步骤3.1：将港区路网结点进行分类，按照算法的搜索方向，分为正向搜索中遍历结点集合d1和反向搜索中遍历结点集合d2；按照算法的搜索范围，分为在扇形搜索范围内结点集合h和不在扇形搜索范围内结点集合q；在算法计算时，扇形搜索范围内的结点分为临时结点集合r和动态结点集合u；
步骤3.2：初始化改进迪杰斯特拉算法中的各个参数，将港区路网路段的加权长度w作为改进迪杰斯特拉算法的权重；获取待决策集卡路径的起始结点m和目标结点d，设初始化时u＝{m,d}，为空集；判断港区路网模型中遍历结点是否在扇形搜索范围内，若在加入集合h，否则加入集合q；步骤3.3：在集合h中找出与起始结点m、目标结点d有直接边相连的结点将其加入集合r，并从集合h中删除；步骤3.4：在集合r中找出到起始结点m或目标结点d改进算法权重w最小的结点c，将结点c加入集合h并将其从集合r中删除；步骤3.5：找出与结点c直接相连且不在集合h中的结点，将其加入集合r后并将其从集合h中删除；步骤3.6：在集合r中找出到结点c改进算法权重w最小的结点，将其加入集合h并从集合r中删除；步骤3.7：判断d1、d2的交集，若则停止搜索算法结束并输出最优路径；否则执行新一轮双向搜索，直到符合终止条件为止。6.一种计算机可读介质，其特征在于，其存储电子设备执行的计算机程序，当所述计算机程序在电子设备上运行时，使得所述电子设备执行如权利要求1-5任一项所述方法的步骤。

技术总结
本发明公开了一种港区集卡群体路径优化方法及计算机可读介质。本发明构建港区路网模型并获取港区路网的车流量信息；获取待决策集卡行驶路径的起始结点、目标结点和路段的加权长度；基于待决策集卡行驶路径的起始结点、目标结点和路段的加权长度，采用改进迪杰斯特拉算法获得最优路径；所述改进迪杰斯特拉算法，是对迪杰斯特拉算法的搜索方式和权重进行改进；改进后的搜索方式为：双向扇形动态搜索；改进后的权重为：路段的加权长度。通过利用算法的搜索方式和权重改进迪杰斯特拉算法，可使算法具有实时性，且考虑实时路况对集卡行驶路径决策的影响，可为集卡提供更优的路径决策方案，提高集卡运输效率和港区作业水平。提高集卡运输效率和港区作业水平。提高集卡运输效率和港区作业水平。


技术研发人员：刘永悦 严新平 贺宜
受保护的技术使用者：武汉理工大学
技术研发日：2023.04.27
技术公布日：2023/8/9