CN108038576A - 基于改进Dijkstra算法的物流配送路径选择方法及系统 - Google Patents

Abstract

本发明公开了一种基于改进Dijkstra算法的物流配送路径选择方法及系统，先获取货物配送起始位置与终点位置间的路径模型，该路径模型包含各个节点之间的各个选择因素的权值，选择因素包括物件配送紧急程度、道路拥挤度及路径距离，然后计算上述路径模型各个节点之间的综合权值，再以综合权值替换Dijkstra算法中对应的路径距离的权值来进行改进Dijkstra算法的运算，选择出一条总的综合权值最小的路径。本发明对多项影响路径规划的选择因素进行了综合考虑，能够得到更加符合实际物流配送的个性化需求的综合最优路径。

Description

基于改进Dijkstra算法的物流配送路径选择方法及系统

技术领域

本发明涉及导航领域，尤其涉及导航过程中路径的选择方面，更具体地说，涉及一种基于改进Dijkstra算法的物流配送路径选择方法及系统。

背景技术

Dijkstra算法性能稳定并且能很好地适应网络拓扑变化，是路径规划的经典算法。Dijkstra算法思想是：设G＝(V,E)是一个带权有向图，把图中各顶点的集合V分成两组，第一组为已求出最短路径的顶点集合(用S表示，初始时S中只有一个源点，以后每求得一条最短路径，就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了)，第二组为其余未确定最短路径的顶点集合(用U表示)，按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

Dijkstra算法步骤：

a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U＝{其余顶点}，若v与U中顶点u有边，则<u,v>正常有权值，若u不是v的出边邻接点，则<u,v>权值为∞。

b.从U中选取一个距离v最小的顶点k，把k，加入S中(该选定的距离就是v到k的最短路径长度)。

c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。

d.重复步骤b和c直到所有顶点都包含在S中。

上述的Dijkstra算法可以得到从起始点到终点的最短路径，但是在实际的物流配送导航路径规划问题中，由于物流配送的复杂性和多样性，实际的物流配送路径选择也呈现个性化和多样化，如路径最短成本也不一定最低，因此对物流配送路径的选择不仅仅以路径距离作为唯一标准，还需要考虑影响路径选择的其他因素，仅仅考虑路径距离不能满足物流配送的路径选择需求。

发明内容

本发明要解决的技术问题在于，针对现有技术的采用Dijkstra算法进行路径选择的方案不能很好的满足物流配送中路径选择的需求的技术缺陷，提供一种基于改进Dijkstra算法的物流配送路径选择方法及系统。

本发明解决其技术问题，所采用的技术方案是构造一种基于改进Dijkstra算法的物流配送路径选择方法，包含下述步骤：

S1、获取货物配送起始位置与终点位置间的路径模型，该路径模型包含将岔路口作为节点的节点之间的各个选择因素的权值，选择因素包括物件配送紧急程度、道路拥挤度、路径距离；

S2、计算所述路径模型各个节点之间的综合权值，其中任意节点p与q之间的综合权值通过下述公式计算所得：

f＝ω₁×f₁+ω₂×f₂+…+ω_n×f_n，

式中，f表示综合权值，n表示选择因素的总个数，f₁、f₂、…及f_n分别为节点p与节点q之间的各个因素的权值，ω₁、ω₂、…及ω_n分别为f₁、f₂、…及f_n对应的权重；

S3、以综合权值替换Dijkstra算法中对应的路径距离的权值来进行改进Dijkstra算法的运算，选择出一条总的综合权值最小的路径。

在本发明的物流配送路径选择方法中，第k个选择因素的归一化后的权重通过下述方法得到：

获取各个选择因素的1～9级判断矩阵标准度S_k，k＝1、2、…、n；

对各个选择因素分别进行如下处理：分别求出第k个选择因素分别相对于所有的选择因素的矩阵标准度的值，然后将该选择因素所有的矩阵标准度的值相乘后求n次方根；

然后将各个选择因素的n次方根进行归一化，归一化的结果即为归一化后的权重。

在本发明的物流配送路径选择方法中，还包括下述步骤：

在利用1～9级判断矩阵标准度进行处理之前，响应用户的设置，更新各个选择因素的优先级。

在本发明的物流配送路径选择方法中，物件配送紧急程度的权重为ω₁＝0.6370，道路拥挤度的权重为ω₂＝0.2583，路径距离的权重为ω₃＝0.1047。

在本发明的物流配送路径选择方法中，各个选择因素的权重的得到过程中，还包括步骤：通过对归一化后的权重进行一致性来检验计算得到的归一化后的权重是否符合权值类型之间的实际重要性，若是，则将本次计算的权重作为权重的最终值，否则，获取重新选取矩阵标准度的值来计算权重；

进行一致性判断的方法如下：

判断的值是否小于0.1，若是则符合一致性，否则不符合一致性；

其中，R.I.等于平均随机一致性表中n阶矩阵的值，λ_max是判断矩阵的最大特征根，判断矩阵的第i行的第j列的元素为第i个选择因素相对于第j选择因素的矩阵标准度的值，i＝1、2、…、n，j＝1、2、…、n。

根据本发明的另一方面，本发明为解决其技术问题，还提供了一种基于改进Dijkstra算法的物流配送路径选择系统，包含下述模块：

模型获取模块，用于获取货物配送起始位置与终点位置间的路径模型，该路径模型包含将岔路口作为节点的节点之间的各个选择因素的权值，选择因素包括物件配送紧急程度、道路拥挤度、路径距离；

权值计算模块，用于计算所述路径模型各个节点之间的综合权值，其中任意节点p与q之间的综合权值通过下述公式计算所得：

f＝ω₁×f₁+ω₂×f₂+…+ω_n×f_n，

式中，f表示综合权值，n表示选择因素的总个数，f₁、f₂、…及f_n分别为节点p与节点q之间的各个因素的权值，ω₁、ω₂、…及ω_n分别为f₁、f₂、…及f_n对应的权重；

路径选择模块，用于以综合权值替换Dijkstra算法中对应的路径距离的权值来进行改进Dijkstra算法的运算，选择出一条总的综合权值最小的路径。

在本发明的物流配送路径选择系统中，第k个选择因素的归一化后的权重通过下述方法得到：

获取各个选择因素的1～9级判断矩阵标准度S_k，k＝1、2、…、n；

对各个选择因素分别进行如下处理：分别求出第k个选择因素分别相对于所有的选择因素的矩阵标准度的值，然后将该选择因素所有的矩阵标准度的值相乘后求n次方根；然后将各个选择因素的n次方根进行归一化，归一化的结果即为归一化后的权重。

在本发明的物流配送路径选择系统中，还包括下述模块：

优先级更新模块，用于在利用1～9级判断矩阵标准度进行处理之前，响应用户的设置，更新各个选择因素的优先级。

在本发明的物流配送路径选择系统中，物件配送紧急程度的权重为ω₁＝0.6370，道路拥挤度的权重为ω₂＝0.2583，路径距离的权重为ω₃＝0.1047。

在本发明的物流配送路径选择系统中，各个选择因素的权重的得到过程中，利用下述模块实现：

一致性处理模块，用于通过对归一化后的权重进行一致性来检验计算得到的归一化后的权重是否符合权值类型之间的实际重要性，若是，则将本次计算的权重作为权重的最终值，否则，获取重新选取矩阵标准度的值来计算权重；

进行一致性判断的方法如下：

判断的值是否小于0.1，若是则符合一致性，否则不符合一致性；

其中，R.I.等于平均随机一致性表中n阶矩阵的值，λ_max是判断矩阵的最大特征根，判断矩阵的第i行的第j列的元素为第i个选择因素相对于第j选择因素的矩阵标准度的值，i＝1、2、…、n，j＝1、2、…、n。

本发明的基于改进Dijkstra算法的物流配送路径选择方法及系统，先获取货物配送起始位置与终点位置间的路径模型，该路径模型包含各个节点之间的各个选择因素的权值，选择因素包括物件配送紧急程度、道路拥挤度及路径距离，然后计算路径模型各个节点之间的综合权值，再以综合权值替换Dijkstra算法中对应的路径距离的权值来进行改进Dijkstra算法的运算，选择出一条总的综合权值最小的路径。本发明对多项影响路径规划的选择因素进行了综合考虑，能够得到更加符合实际物流配送的个性化需求的综合最优路径。

附图说明

下面将结合附图及实施例对本发明作进一步说明，附图中：

图1是本发明的基于改进Dijkstra算法的物流配送路径选择方法一实施例的流程图；

图2是综合权值的层次结构图；

图3是网络路径拓扑图。

具体实施方式

为了对本发明的技术特征、目的和效果有更加清楚的理解，现对照附图详细说明本发明的具体实施方式。

作为影响物流配送路径规划的其中三个权值指标：物件配送紧急程度、道路拥挤度、路径距离，下述实施例仅选取这三个作为所有的选择因素，在其他实施例中，除了具有上述三个选择因素外，还可以具有其他选择因素。在用户实际进行选择路径时，根据不同的需求，这三项权值指标的优先级也可能不同，由此规划出的路径也不尽相同。可以通过用户自行设定五项权值的优先级，进而再规划出满足不同用户需求的最优路径，因此可以预先提示用户进行各个影响因素的优先级排序，用户排序后本方法可以对之前的排序进行更新(若之前没有，则直接保存本次排序)。

本发明研究物流配送导航路径规划，以货物配送起始位置与终点位置间岔路口作为节点，旨在找到一条综合多项权值的最佳路径，为用户提供综合最优的配送路径规划服务。结合物流配送的特点确定了影响物流配送路径规划的主要权值类型，接下来需对这几种权值类型进行权值融合得到综合权值，进而利用综合权值进行路径规划得到综合最优路径。如何进行多权值融合确定出综合权值是本发明的重点研究内容。

目标线性加权法是将目标问题转化为多个目标函数，通过建立这若干个目标函数的线性组合，从而把多个目标优化问题变成总体目标优化问题，通过把各个目标函数利用系数加权法进行统一，是求解多目标方法优化问题的一种主要的方法。把多目标规划问题中的P个目标按重要程度赋以适当的权重系数ω_i，ω_i>0，i＝1，2，…，P，且将作为新的目标函数。本发明利用目标线性加权法来进行多权值融合确定综合权值，进而建立改进的物流配送路径规划模型。

参考图1，本实施例的基于改进Dijkstra算法的物流配送路径选择方法包括如下步骤：

S1、获取货物配送起始位置与终点位置间的路径模型，该路径模型包含将岔路口作为节点的节点之间的各个选择因素的权值，选择因素包括物件配送紧急程度、道路拥挤度及路径距离。

S2、设将物件配送紧急度权值记为f₁，道路拥挤度权值记为f₂，路径距离权值记为f₃，综合权值记为F，由于各项权值类型对综合权值的影响程度不同，将各项权值对F的影响度分别记为ω₁、ω₂、ω₃,则综合权值的计算式如下所示：

F＝ω₁*f₁+ω₂*f₂+ω₃*f₃ (1)

其中，ω₁+ω₂+ω₃＝1，接下来便是确定各项权值类型对综合权值的影响度。

在物流配送路径规划的问题中，本专利使用层次分析法AHP(Analytic HierarchyProcess)，首先定性的确定各权值两两之间的重要程度，然后将定性的分析转化为定量的数据计算进而得到具体的各项权值类型对综合权值的影响。使用AHP求解物流配送的路径规划问题中多目标线性加权的各项权值类型对综合权值各影响度的具体步骤如下：

首先，结合目标问题建立综合权值的层次结构图，如图2所示：

然后，要对各项权重之间两两比较从而构建各权值类型的判断矩阵。这里引入判断矩阵标准度，采用T.L.Saaty等人提出的1～9级判断矩阵标准度，如下表所示：

表1 1～9级判断矩阵标准度

根据判断矩阵标准度表，构造各项权值类型的判断矩阵(选取其中一种情况，因为设定的每个权值的优先级不同，最终的综合权值的表达式也不同，因此规划出的路径也不同)，如下表2所示：

表2各权值类型的判断矩阵

从表中可以看出，结合实际情形考虑，本实施例指定了各项权值两两之间的相对重要程度，比如：路径距离权值比道路拥挤度权值和物件紧急度权值对综合权值的影响度要高，道路拥挤度权值比物件紧急度度权值的影响度稍高。

接着，便是要计算得到各项权值类型的影响度，即组合权重系数，得到ω₁、ω₂、ω₃的值。通常组合权重系数可以采用几何平均法(根法)和规范列平均法(和法)来计算，本专利采用是几何平均法进行计算。求组合权重系数的计算步骤如下：

首先计算判断矩阵各行各元素的乘积，得到一个3行一列的矩阵B，如下表3所示：

表3矩阵各行各元素之积

计算上述B矩阵每个元素的3次方根得矩阵C，如下表4所示：

表4列归一化

然后对矩阵C归一化，得到组合权重系数，即各影响度数值：

ω₁＝0.6370，ω₂＝0.2583，ω₃＝0.1047。

最后，通过一致性判断来检验计算得到的相对权重系数是否符合权值类型之间的实际重要性，从而检验多权值融合的正确性。引入统一的平均随机一致性表，如下表5所示

表5平均随机一致性表

检验一致性公式为：

其中：

n为参数个数，即各项权值类型个数，R.I.代表平均随机一致性表中n阶矩阵的值，λ_max是判断矩阵的最大特征根。如果C.R.<0.1，本实施例就认为判断矩阵是一致的。由下式

可得λ_max＝3.0385，将λ_max和n带入公式3，可得C.I.＝(3.0385-3)/(3-1)＝0.0192，将C.I.带入公式2，可得到C.R.＝0.0192/0.52＝0.03696<0.1。由此可知，通过以上计算得到的判断矩阵满足一致性，与各项权值之间的实际重要性相符合，验证了其正确性。综上所述，将得到的组合权值系数带入公式1，得到物流配送路径规划模型的综合权值如下式：

F＝0.637*f₁+0.2583*f₂+0.1047*f₃ (5)

S3、以综合权值替换Dijkstra算法中对应的路径距离的权值来进行改进Dijkstra算法的运算，选择出一条总的综合权值最小的路径。

参考图3，从路径网络拓扑图中可以看出，测试的路径网络拓扑图中标注出了路网中的0到9这十个节点，设置路网中的节点0为路径的起始节点，两节点间路段上标注出的三项数值依次分别代表路径距离权值、道路拥挤度权值、物件配送紧急度权值三项权值。

首先利用多层数据字典对上述路径网络拓扑进行相应信息提取和管理，多层数据字典中包含了起始节点信息、目的节点信息和路径距离权值、道路拥挤度权值、物件配送紧急度权值三项权值信息，如下表6所示。

结合得到的路网信息，根据路径规划文档中建立的物流配送路径规划模型，利用多目标线性加权法通过多项权值融合从而计算得到综合权值，然后结合Dijkstra算法进行路径搜索，从而得到考虑了路径距离权值、道路拥挤度权值、物件配送紧急度三项权值类型的综合优化路径。

表6多层数据字典

首先对以上路网信息数据预处理得到路径距离、道路拥挤度、配送紧急度三项权值的多维数组，分别如式6、7、8所示，其中如果两节点不相邻，则其数值定义为无穷大。

将相邻两节点各路段的各项权值代入建立的物流配送路径规划模型的综合权值表达式中：F＝0.637*f₁+0.2583*f₂+0.1047*f₃(公式5)，可得到相邻两节点各路段的综合权值，得到该路径网络拓扑图的综合权值的矩阵形式，如下式9所示：

矩阵式9中的数值代表了物流配送路径规划模型的两节点间路线的综合权值，不相邻节点的综合权值为无穷大。通过以上矩阵式，结合Dijkstra算法得到综合权值最小的路径，即规划出从起始节点到目标节点的综合多项权值类型、更加符合用户个性化需求的综合最优路径。设定0为起始节点，仿真测试结果如表7所示：

表7改进模型测试结果

上面结合附图对本发明的实施例进行了描述，但是本发明并不局限于上述的具体实施方式，上述的具体实施方式仅仅是示意性的，而不是限制性的，本领域的普通技术人员在本发明的启示下，在不脱离本发明宗旨和权利要求所保护的范围情况下，还可做出很多形式，这些均属于本发明的保护之内。

Claims (10)

1.一种基于改进Dijkstra算法的物流配送路径选择方法，其特征在于，包含下述步骤：

S1、获取货物配送起始位置与终点位置间的路径模型，该路径模型包含将岔路口作为节点的节点之间的各个选择因素的权值，选择因素包括物件配送紧急程度、道路拥挤度、路径距离；

S2、计算所述路径模型各个节点之间的综合权值，其中任意节点p与q之间的综合权值通过下述公式计算所得：

f＝ω₁×f₁+ω₂×f₂+…+ω_n×f_n，

式中，f表示综合权值，n表示选择因素的总个数，f₁、f₂、…及f_n分别为节点p与节点q之间的各个因素的权值，ω₁、ω₂、…及ω_n分别为f₁、f₂、…及f_n对应的权重；

S3、以综合权值替换Dijkstra算法中对应的路径距离的权值来进行改进Dijkstra算法的运算，选择出一条总的综合权值最小的路径。

2.根据权利要求1所述的物流配送路径选择方法，其特征在于，第k个选择因素的归一化后的权重通过下述方法得到：

获取各个选择因素的1～9级判断矩阵标准度S_k，k＝1、2、…、n；

对各个选择因素分别进行如下处理：分别求出第k个选择因素分别相对于所有的选择因素的矩阵标准度的值，然后将该选择因素所有的矩阵标准度的值相乘后求n次方根；

然后将各个选择因素的n次方根进行归一化，归一化的结果即为归一化后的权重。

3.根据权利要求2所述的物流配送路径选择方法，其特征在于，还包括下述步骤：

在利用1～9级判断矩阵标准度进行处理之前，响应用户的设置，更新各个选择因素的优先级。

4.根据权利要求2所述的物流配送路径选择方法，其特征在于，物件配送紧急程度的权重为ω₁＝0.6370，道路拥挤度的权重为ω₂＝0.2583，路径距离的权重为ω₃＝0.1047。

5.根据权利要求2所述的物流配送路径选择方法，其特征在于，各个选择因素的权重的得到过程中，还包括步骤：通过对归一化后的权重进行一致性来检验计算得到的归一化后的权重是否符合权值类型之间的实际重要性，若是，则将本次计算的权重作为权重的最终值，否则，获取重新选取矩阵标准度的值来计算权重；

进行一致性判断的方法如下：

判断的值是否小于0.1，若是则符合一致性，否则不符合一致性；

其中，R.I.等于平均随机一致性表中n阶矩阵的值，λ_max是判断矩阵的最大特征根，判断矩阵的第i行的第j列的元素为第i个选择因素相对于第j选择因素的矩阵标准度的值，i＝1、2、…、n，j＝1、2、…、n。

6.一种基于改进Dijkstra算法的物流配送路径选择系统，其特征在于，包含下述模块：

模型获取模块，用于获取货物配送起始位置与终点位置间的路径模型，该路径模型包含将岔路口作为节点的节点之间的各个选择因素的权值，选择因素包括物件配送紧急程度、道路拥挤度、路径距离；

权值计算模块，用于计算所述路径模型各个节点之间的综合权值，其中任意节点p与q之间的综合权值通过下述公式计算所得：

f＝ω₁×f₁+ω₂×f₂+…+ω_n×f_n，

式中，f表示综合权值，n表示选择因素的总个数，f₁、f₂、…及f_n分别为节点p与节点q之间的各个因素的权值，ω₁、ω₂、…及ω_n分别为f₁、f₂、…及f_n对应的权重；

路径选择模块，用于以综合权值替换Dijkstra算法中对应的路径距离的权值来进行改进Dijkstra算法的运算，选择出一条总的综合权值最小的路径。

7.根据权利要求6所述的物流配送路径选择系统，其特征在于，第k个选择因素的归一化后的权重通过下述方法得到：

获取各个选择因素的1～9级判断矩阵标准度S_k，k＝1、2、…、n；

对各个选择因素分别进行如下处理：分别求出第k个选择因素分别相对于所有的选择因素的矩阵标准度的值，然后将该选择因素所有的矩阵标准度的值相乘后求n次方根；

然后将各个选择因素的n次方根进行归一化，归一化的结果即为归一化后的权重。

8.根据权利要求7所述的物流配送路径选择系统，其特征在于，还包括下述模块：

优先级更新模块，用于在利用1～9级判断矩阵标准度进行处理之前，响应用户的设置，更新各个选择因素的优先级。

9.根据权利要求7所述的物流配送路径选择系统，其特征在于，物件配送紧急程度的权重为ω₁＝0.6370，道路拥挤度的权重为ω₂＝0.2583，路径距离的权重为ω₃＝0.1047。

10.根据权利要求7所述的物流配送路径选择系统，其特征在于，各个选择因素的权重的得到过程中，利用下述模块实现：

一致性处理模块，用于通过对归一化后的权重进行一致性来检验计算得到的归一化后的权重是否符合权值类型之间的实际重要性，若是，则将本次计算的权重作为权重的最终值，否则，获取重新选取矩阵标准度的值来计算权重；

进行一致性判断的方法如下：

判断的值是否小于0.1，若是则符合一致性，否则不符合一致性；

其中，R.I.等于平均随机一致性表中n阶矩阵的值，λ_max是判断矩阵的最大特征根，判断矩阵的第i行的第j列的元素为第i个选择因素相对于第j选择因素的矩阵标准度的值，i＝1、2、…、n，j＝1、2、…、n。