一种两阶段多车场危化品车辆路径规划方法

1.本发明涉及一种危化品风险管理领域，尤其涉及一种两阶段多车场危化品车辆路径规划方法。


背景技术：

2.工业快速发展至今，危化品已成为农业、工业、国防和生产生活中不可或缺的重要物质。但危化品运输是一中低几率、高后果的危险事项，严重情况下会对人类生命财产和生态环境产生重大危害。传统危化品运输路径规划方法普遍采用单个配送中心运输，即单车场运输的方式进行，在运输与距离和运输成本上具有很强的局限性。因此，在实际物流配送中，考虑多车场运输是必要的。此外，在更加高效、低成本地将货物运送到顾客手中的同时，还需要考虑如何将运输风险最低化。
3.例如，一种在中国专利文献上公开的“二型模糊环境下的危化品车辆路径规划方法”，其公告号cn110533238a，包括在传统运输风险模型的基础上引入了二型模糊变量，根据置信度方法构建了机会约束模型以及其对应的等价确定型。针对模型特性，设计了一种模拟退火算法。提出的saa以一定的概率来接受一个比当前解要差的解,因此有可能会跳出这个局部的最优解,达到全局的最优解。此方案能够解决危化品单车场运输的最优路径选择，与本方案的目的有相似点，但采用的技术手段不同，且无法实现多车场运送路径的最优选择。


技术实现要素：

4.本发明主要解决传统危化品运输路径规划方法局限于单车场运送，且无法权衡运送风险得出最优运送路线的问题；提供一种两阶段多车场危化品车辆路径规划方法，在满足给定的约束条件背景下，充分考虑运输车辆信息、车场信息、运输道路信息、人口分布和危化品信息；根据上述信息建立多车场危化品车辆路径规划模型，并分两个阶段求解模型，从而获得最短运送距离和最优运送路线。
5.本发明的上述技术问题主要是通过下述技术方案得以解决的：本发明包括：获取基础数据，计算运输时的风险值；执行决策变量定义并建立模型约束条件后，得到多车场危化品车辆路径规划模型；设置分解阶段和求解阶段，依次对多车场危化品车辆路径规划模型完成求解。上文提到的基础数据包括：运输车辆信息、车场信息、运输道路信息、人口分布和危化品信息；在考虑基础数据的情况下建立模型和约束条件，在分解阶段利用一种邻近算法将多车场车辆路径问题分解为单个车场车辆路径子问题；在求解阶段利用粒子群算法与3-opt局部算法，共同求解子问题，从而进一步求解总问题；此种方法考虑到多车场运送，能够更加及时地将危化品运送到指定位置，在缩短运送距离的同时，能够提高物流效率，同时将运输风险降到最低。
6.作为优选，所述的风险值的计算公式为：r
ij
＝p
ij
×
cs
ij
，i，j∈n(1)；其中，r
ij
代表车辆从节点i将危化品运输到节点j的运输风险，p
ij
代表车辆在弧arc
ij
∈l上引发危化品事
故的概率，cs
ij
代表弧arc
ij
上的事故后果，其表达式为cs
ij
＝pop
ij
×
πr2；其中pop
ij
为事故点周围环境中的人口密度，r为事故半径，πr2为事故影响面积。此步骤中包含对于风险值的计算，风险值的大小取决于事故发生的概率以及事故后果的影响。
7.作为优选，所述的决策变量定义为：多车场危化品车辆路径规划模型初步建立为：多车场危化品车辆路径规划模型初步建立为：其中，z1代表最小化运输成本的目标函数；z2代表最小化运输风险的目标函数；h
ij
为节点i，j∈n之间的运输距离，r
ij
为车辆从节点i将危化品运输到节点j的运输风险。计算出从某一位置到另一位置的风险值有利于在后续运输过程中规避风险值过大的路径，提高运输的安全性。
8.作为优选，所述的建立模型约束条件包括：作为优选，所述的建立模型约束条件包括：作为优选，所述的建立模型约束条件包括：其中，约束条件(5-1)表示，单个车场服务的各个客户的需求总量之和小于等于其存储量qd；约束条件(5-2)表示，对于单个客户，只能被一个车场服务；约束条件(5-3)、(5-4)和(5-5)表示任一车辆必须从车场出发，运输完成后返回原车场。此步骤为对具体运输环境的设定，对模型设置上述约束条件，能够更加贴合实际的运输情况，便于后续根据模型求解出更加结合实际、更加准确的计算结果。
9.作为优选，所述的分解阶段中，采用一种k近邻聚类算法，将多车场车辆路径问题分解为一系列单车场车辆路径子问题；列出距离矩阵a，设a为p
t
×
p
t
的2维矩阵，矩阵中的每一个元素表示某一车场坐标到某聚类中心的距离，其中d(i，j)为车场坐标i到聚类中心坐标j的欧氏距离；选取a中不同车场和不同客户群中心的pt个元素后相加，共得到pt！种不同的组合及其对应的累加和(s1，s2，
…
，spt！)；得到累加和的最小值smin＝min(s1，s2，...，sl，...，spt！)(7)；获取smin对应组合中每个元素的d(i，j)行、列标号即为车场i所服务的客户群j。采用smin确定车场服务的客户群，能够更加准确直观地判断出距离客户最近的运输车场，有利于整体缩短车辆的运输距离。
10.作为优选，所述的求解阶段中采用一种基于局部搜索的粒子群算法对分解后的子问题求解：s1.初始化处理，包括设置算法所需参数，确定粒子位置数据，保存最优值；s2.计算每条边的路径长度；s3.随机产生初始解，并计算粒子的适应度函数值；s4.保持粒子速度不便，更新粒子位置数据，重新确定粒子位置数据；s5.判断算法是否达到终止条件，否则执行步骤s3，是则执行步骤s6；s6.根据3-opt变换对最优值进行全局搜索，并更新位置数据；s7.计算每个粒子的适应度函数值，并与保存的最优值进行比较，更新最优值并记录路径；s8.判断最优值持续不变的次数是否达到阈值，是则停止循环并输出最优值，否则执行s3。次不中中采用粒子群算法结合3-opt局部搜索算法，能够进一步提高结果的精确性和算法的收敛速度，增强局部的搜索能力。
11.作为优选，所述的s1中参数包括问题规模、粒子数目和最大迭代次数m；s3中初始解包括粒子的初始位置和速度；s1或s4中的粒子位置数据包括粒子的历史最好位置pi和全
局最好位置pg，所述全局最好位置即最优值，其中s1中令n＝1；s5中的中止条件为n》m；s7还包括：若粒子适应度函数值优于保存的最优值，则更新最优值并记录路径再更新全局最好位置pg。
12.本发明的有益效果是：1.本发明的一种两阶段多车场危化品车辆路径规划方法，在传统的车辆路径规划方法的基础上，结合危化品的运输特性和运输中的风险因素，构建了更加贴近实际生活中危化品运输情形的优化后路径规划模型，并且通过将复杂问题分解为子问题，并通过求解子问题进一步推导复杂问题的方式，得到多车场危化品车辆路径规划问题的解，具有实际应用性和进步性；2.本发明的一种两阶段多车场危化品车辆路径规划方法，通过设计混合粒子群算法与3-opt局部搜索算法的结合算法，从而实现对目标模型的开放性、灵活性求解，大大降低了计算复杂度，增加了结果准确性。
附图说明
13.图1是本发明的一种两阶段多车场危化品车辆路径规划方法的求解阶段算法流程图；图2是本发明的一种两阶段多车场危化品车辆路径规划方法的3-opt交换示意图。
具体实施方式
14.下面通过实施例，并结合附图，对本发明的技术方案作进一步具体的说明。
15.实施例：本实施例的一种两阶段多车场危化品车辆路径规划方法，如图1所示，包括以下步骤：步骤1：获取基础数据，包括运输车辆信息、车场信息、运输道路信息、人口分布和危化品信息；计算运输风险值。
16.多车场危化品车辆问题可被描述为：为满足客户需求，从车场运输危化品服务不同客户，给出风险最小的路径规划方案；假定车场和客户的位置和数量已知；同时客户的需求量以及车场的存量已知；车辆必须从车场出发，服务完客户必须回到原车场；总存储量大于总需求量，即每个客户的需求都可被满足；每个客户只能被一个车场提供服务；各车场之间存储量不互相调用。
17.风险值的大小取决于事故发生的概率以及事故后果的影响。则风险值计算公式为：r
ij
＝p
ij
×
cs
ij
，i，j∈n
ꢀꢀꢀ
(1)r
ij
是车辆从节点i将危化品运输到节点j的运输风险，p
ij
是车辆在弧arc
ij
∈l上所引发危化品事故的概率，cs
ij
是弧arc
ij
上的事故后果，cs
ij
＝pop
ij
×
πr2，其中pop
ij
为事故点周围环境中的人口密度，r为事故半径，πr2为事故影响面积。
18.步骤2：构建多车场危化品车辆运输路径规划模型，执行决策变量定义并建立约束条件。
19.多车场危化品车辆路径规划模型如下：
决策变量定义：决策变量定义：决策变量定义：z1是最小化运输成本的目标函数；z2是最小化运输风险的目标函数，h
ij
为节点i，j∈n之间的运输距离，r
ij
是车辆从节点i将危化品运输到节点j的运输风险。
20.模型约束如下：(5-1)(5-2)(5-3)(5-4)(5-5)约束条件(5-1)表示，对于同一车场，它所需服务的各个客户的需求总量之和小于等于其存储量；约束条件(5-2)表示，对于每一个客户，只能被一个车场服务；约束条件(5-3)，(5-4)，(5-5)表示任何一个车辆必须从车场出发，运输完成后回到原车场。
21.步骤3：设置分解阶段和求解阶段，依次对多车场危化品车辆路径规划模型完成求解。
22.分解阶段，采用一种k近邻聚类算法，将多车场车辆路径问题分解为一系列单个车场车辆问题：首先计算车场到聚类中心的距离：列出距离矩阵a，设a为p
t
×
p
t
的2维矩阵，矩阵中的每一个元素表示某一车场坐标到某聚类中心的距离；其中，d(i，j)为车场坐标i到聚类中心坐标j的欧氏距离。
23.选取a中不同车场和不同客户群中心的pt个元素并相加，共有pt！种不同的组合及其对应的累加和(s1，s2，
…
，spt！)，选出其中最小的s
min
所对应的组合中每个元素d(i，j)行、列标号即为车场i所服务的客户群j；其中s
min
＝min(s1，s2，
…
，s
l
，
…
，s
pt！
)；采用s
min
确定车场服务的客户群有利于整体缩短车辆运输距离。
24.求解阶段，提出了一种基于局部搜索的粒子群算法求解分解后的各子问题，进而获得原问题的解；该算法通过在粒子群中加入3-opt局部搜索算法，进一步提高了解的精确性和算法的收敛速度，增强了局部搜索能力。
25.如图1所示算法具体实现步骤如下：step1初始化：设置算法所需的参数，如问题规模、粒子数目、最大迭代次数m、计算粒子的适应度函数值，确定粒子的历史最好位置pi和全局最好位置pg,令n＝1；
step2计算算法必需的数据，即每条边的路径长度；step3随机产生初始解，即粒子的初始位置和速度，并计算粒子的适应度函数；step4粒子速度不变，更新粒子的位置，确定粒子的历史最好位置pi和全局最好位置pg；step5判断算法是否达到终止条件,若n《m，转step3，否则转step6；step6根据3-opt变换对pg进行局部搜索，更新pg；step7计算每个粒子的适应度函数值，并与保存的最优值进行比较，若结果更优，则保留并更新粒子最优值，且记录路径，再更新pg；step8判断最优值持续不变的次数是否达到，若达到，则停止，输出最优解pg,否则转step3。
26.应理解，实施例仅用于说明本发明而不用于限制本发明的范围。此外应理解，在阅读了本发明讲授的内容之后，本领域技术人员可以对本发明作各种改动或修改，这些等价形式同样落于本技术所附权利要求书所限定的范围。

技术特征：
1.一种两阶段多车场危化品车辆路径规划方法，其特征在于，包括以下步骤：获取基础数据，计算运输时的风险值；执行决策变量定义并建立模型约束条件后，得到多车场危化品车辆路径规划模型；设置分解阶段和求解阶段，依次对多车场危化品车辆路径规划模型完成求解。2.根据权利要求1所述的一种两阶段多车场危化品车辆路径规划方法，其特征在于，所述风险值的计算公式为：r
ij
＝p
ij
×
cs
ij
,i,j∈n(1)；其中，r
ij
代表车辆从节点i将危化品运输到节点j的运输风险，p
ij
代表车辆在弧arc
ij
∈l上引发危化品事故的概率，cs
ij
代表弧arc
ij
上的事故后果，其表达式为cs
ij
＝pop
ij
×
πr2；其中pop ij
为事故点周围环境中的人口密度，r为事故半径，πr2为事故影响面积。3.根据权利要求2所述的一种两阶段多车场危化品车辆路径规划方法，其特征在于，决策变量定义为：多车场危化品车辆路径规划模型初步建立为：其中，z1代表最小化运输成本的目标函数；z2代表最小化运输风险的目标函数；h
ij
为节点i,j∈n之间的运输距离，r
ij
为车辆从节点i将危化品运输到节点j的运输风险。4.根据权利要求3所述的一种两阶段多车场危化品车辆路径规划方法，其特征在于，建立模型约束条件包括：立模型约束条件包括：立模型约束条件包括：其中，约束条件(5-1)表示，单个车场服务的各个客户的需求总量之和小于等于其存储量q
d
；约束条件(5-2)表示，对于单个客户，只能被一个车场服务；约束条件(5-3)、(5-4)和(5-5)表示任一车辆必须从车场出发，运输完成后返回原车场。5.根据权利要求4所述的一种两阶段多车场危化品车辆路径规划方法，其特征在于，所述分解阶段中，采用一种k近邻聚类算法，将多车场车辆路径问题分解为一系列单车场车辆路径子问题；列出距离矩阵a，设a为p
t
×
p
t
的2维矩阵，矩阵中的每一个元素表示某一车场坐标到某聚类中心的距离，其中d(i，j)为车场坐标i到聚类中心坐标j的欧氏距离；选取a中不同车场和不同客户群中心的pt个元素后相加，共得到pt！种不同的组合及其对应的累加和(s1，s2，
…
，spt！)；得到累加和的最小值smin＝min(s1，s2，
…
，sl，
…
，spt！)(7)；
获取smin对应组合中每个元素的d(i，j)行、列标号即为车场i所服务的客户群j。6.根据权利要求5所述的一种两阶段多车场危化品车辆路径规划方法，其特征在于，所述求解阶段中采用一种基于局部搜索的粒子群算法对分解后的子问题求解；s1.初始化处理，包括设置算法所需参数，确定粒子位置数据，保存最优值；s2.计算每条边的路径长度；s3.随机产生初始解，并计算粒子的适应度函数值；s4.保持粒子速度不便，更新粒子位置数据，重新确定粒子位置数据；s5.判断算法是否达到终止条件，否则执行步骤s3，是则执行步骤s6；s6.根据3-opt变换对最优值进行全局搜索，并更新位置数据；s7.计算每个粒子的适应度函数值，并与保存的最优值进行比较，更新最优值并记录路径；s8.判断最优值持续不变的次数是否达到阈值，是则停止循环并输出最优值，否则执行s3。7.根据权利要求6所述的一种两阶段多车场危化品车辆路径规划方法，其特征在于，s1中所述的参数包括问题规模、粒子数目和最大迭代次数m；s3中所述初始解包括粒子的初始位置和速度；s1或s4中所述的粒子位置数据包括粒子的历史最好位置p
i
和全局最好位置p
g
，所述全局最好位置即最优值，其中s1中令n＝1；s5中所述中止条件为n>m；s7还包括：若粒子适应度函数值优于保存的最优值，则更新最优值并记录路径再更新全局最好位置p
g
。

技术总结
本发明公开了一种两阶段多车场危化品车辆路径规划方法。为了克服解决传统危化品运输路径规划方法局限于单车场运送，且无法权衡运送风险得出最优运送路线的问题，本发明包括获取基础数据，计算运输时的风险值；执行决策变量定义并建立模型约束条件后，得到多车场危化品车辆路径规划模型；设置分解阶段和求解阶段，依次对多车场危化品车辆路径规划模型完成求解。利用一种邻近算法将多车场车辆路径问题分解为单个车场车辆路径子问题；利用粒子群算法与3-opt局部算法共同求解子问题得到最优解；此种方法考虑到多车场运送，能够更加及时地将危化品运送到指定位置，在缩短运送距离的同时，能够提高物流效率，同时将运输风险降到最低。最低。最低。


技术研发人员：郑松 谢云峰 蒋鹏 刘俊 许欢
受保护的技术使用者：杭州电子科技大学
技术研发日：2023.02.27
技术公布日：2023/9/23