CN113390414A - 一种军用油料投送路径规划方法 - Google Patents

Abstract

本发明的一个实施例公开了一种军用油料投送路径规划方法，该方法包括：S10：根据实际地图情况，计算起始点与终点之间最短投送路径；S20：规划基于最短投送路径的油料调拨顺序。该方法具有动态避障搜索功能，并且通过重构不同代价的权重系数，可按需动态调整算法的搜索方向，在提高搜索效率的基础上，可以拓展搜索方向，避免陷入局部最优解。

Description

一种军用油料投送路径规划方法

技术领域

本发明涉及路径规划领域。更具体地，涉及一种军用油料投送路径规划方法。

背景技术

我国幅员辽阔，战地配置位置不同且分布不均匀，道路网络庞大，道路情况复杂等问题增加了油料投送路径规划的难度。为多配送点投送油料时，调拨顺序和路径规划依赖人工经验并按人工安排的方式进行，没有高级指挥控制系统的参与，导致油资无法按要求时限及时送达。目前我国对军用油料配送问题上没有提供系统的解决方案，多数聚焦于解决单配送点的两点最短路径规划问题。

发明内容

有鉴于此，本发明第一个实施例提供一种军用油料投送路径规划方法，包括：

S10：根据实际地图情况，计算起始点与终点之间最短投送路径；

S20：规划基于最短投送路径的油料调拨顺序。

在一个具体实施例中，所述S10包括：

S101：构建计算两点间最短路径数学模型；

S103：构建代价函数；

S105：利用所述数学模型和代价函数计算最短投送路径。

在一个具体实施例中，所述S101包括：

包含有n个节点的地图，其道路分布图记为G¹＝(V¹,A¹)，其中，V¹为节点集，记为V¹＝{v¹ ₁＝(x¹ ₁,y¹ ₁),...,v¹ _n＝(x¹ _n,y¹ _n)}其中(x¹ _i,y¹ _i)表示顶点i的坐标，两个需求点分别记为v¹ _start和v¹ _end，A¹表示边集，顶点j和顶点k之间的距离记为

最短路径记为点集P¹＝{p¹ ₁,p¹ ₂,...,p¹ _l}(0<l≤n)，油料投送最短路径优化目标函数为：

为A¹内所有边定义二进制变量O_ij

构建约束条件，以使保证规划路径不经过特殊路段

在一个具体实施例中，所述S103包括：

构建包含当前状态到故障路段的代价的代价函数，

f(n)＝α×g(n)+β×h(n)+γ×y(n)

其中，g(n)表示起始状态v¹ _start到当前状态v¹ _n的代价，h(n)表示当前状态v¹ _n至结束状态v¹ _end的代价，y(n)表示当前状态v¹ _n至所有故障路段v¹ _i(0<i≤l)的代价；α,β,γ分别为g(n),h(n),y(n)的权重系数，且α+β+γ＝1。

在一个具体实施例中，所述S105包括：

S1051：设置代价函数影响因子初始值α,β,γ；

S1053:生成P¹'，其中P¹'包含的元素为与当前道路节点联通且O_ij为1的所有节点；

S1055：根据判断依据判断是否代价不平衡，若不平衡则重新设置价函数影响因子α,β,γ的值，否则进行S1057，判断依据为：判断代价函数是否满足下列公式，若满足则代价平衡，反之则不平衡

S1057：计算集合P¹'中每个元素的代价值，从P¹'中选择代价值最小的节点v¹ ₂，更新路径访问顺序P¹＝{v¹ _start,v¹ ₂}；

S1059：重复进行S1053-1057，直至访问到v¹ _end为止。

在一个具体实施例中，所述S20包括：

S201：构建调拨顺序规划的目标函数，包括：

将m个点的网络分布图记为G²＝(V²,A²)，其中，m个点包括m-1个需求点和1个配送站，V²为需求点集，记为V²＝{v² ₁＝(x² ₁,y² ₁),...,v² _m＝(x² _m,y² _m)}，调度顺序表示为P²＝{p² ₁,p² ₂,...,p² _m}，根据S105中计算出每两点的最短距离D_ij ¹，然后调拨顺序规划的目标函数为

将需求点v² _i访问次数定义为

约束条件为0<i≤m,N_i＝1以使得调度方案中每个需求点访问且仅访问一次；

S202:用基因和染色体表示调度顺序，并生成初始可行解；

S203：建立适应度函数，并计算所有可行解的适应性大小；

S205：确定需要保留的染色体、交叉后形成的染色体和变异后的形成的染色体；

S207：更新种群，直至满足迭代条件；

S209：将节点序号按照节点权重降序排列，即可得到调拨顺序序列。

在一个具体实施例中，所述S202包括：

节点总数目为m，每代的染色体总数目为GEN，则染色体i表示为 chromoⁱ＝{a₁ ⁱ,a₂ ⁱ,...,a_m ⁱ}，其中基因值0<a_k ⁱ<1表示节点k的权重，基因值大，则优先访问该节点；

节点序号按照染色体上基因值降序排列，得到初始可行解。

在一个具体实施例中，所述适用度函数为

其中，D_i ²为调拨顺序的行进路程，用于决定染色体i的优良程度。

在一个具体实施例中，所述S205包括：

需要保留的染色体、交叉后形成的染色体和变异后的形成的染色体构成比例分别为t₁,t₂,t₃，三个参数满足如下条件：

t₁+t₂+t₃＝1

若染色体i的适应度为f(x_i)，则该个体被选中的概率为：

该染色体的累积概率为：

在[0,1]区间内随机生成随机数r₁，保留满足式Q(x_k-1)≤r₁<Q(x_k)的第k条染色体；

两个染色体经过交叉操作可以形成两个新的染色体，随机设置交叉点 r₂∈N*,1≤r₂≤m。随机产生[0,1]区间内随机生成随机数r₃，比较r₃与交叉概率P_m，若r₃>P_m，则两染色体相互交叉，反之则不进行操作，交叉操作即两条染色体交叉点后的基因相互交换，形成两个新的染色体。

在一个具体实施例中，所述S205还包括：

随机设置交叉点r₄∈N*,1≤r₄≤m，随机产生[0,1]区间内的随机数r₅，比较r₅与交叉概率P_c，若r₅>P_c，则进行变异操作，即将该基因位的基因值换为[0,1]区间内的随机数r₆，反之则不进行变异。

本发明的有益效果如下：

本发明解决了复杂网络条件下的多配送点油料投送的路径规划问题，通过引入权重系数，使该方法具有动态避障搜索功能，并且通过重构不同代价的权重系数，可按需动态调整搜索方向，在提高搜索效率的基础上，拓展搜索方向，避免算法陷入局部最优解。再计算出配送点到所有供给点及供给点之间的两点间最短路径后，再使用基于优先值的遗传算法计算基于总投送路径最短的油料投送调拨顺序问题，更节省时间。

附图说明

为了更清楚地说明本发明实施例中的技术方案，下面将对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1示出本发明的一个实施例的军用油料投送路径规划方法系统架构示意图。

图2示出能实现本发明的一个实施例的军用油料投送路径规划方法流程图。

具体实施方式

为使本发明的、技术方案和优点更加清楚，下面将结合附图对本发明实施方式作进一步地详细描述。

如图1所示，为能实现本发明的一个实施例的军用油料投送路径规划方法系统架构，系统架构可以包括地图数据集合101和服务器103。其中地图数据集合101包括多个包含多个节点的道路分布图，并将已经规划好投送路线的道路分布图和未规划好路线的道路分布图分别存放，服务器103为提供各种服务的服务器，例如为计算追踪目标量测值提供支持的后台服务器等。

需要指出的是，地图数据集合101可以存储在其他装置上也可以存储在网络上，或者也可以直接存储在服务器103中，本申请对此不作限定。

如图2所示，一种军用油料投送路径规划方法，包括：

S10：根据实际地图情况，计算起始点与终点之间最短投送路径；

S101：构建计算两点间最短路径数学模型；

包含n个节点的道路分布图记为G¹＝(V¹,A¹)，节点集记为 V¹＝{v¹ ₁＝(x¹ ₁,y¹ ₁),...,v¹ _n＝(x¹ _n,y¹ _n)}，其中(x¹ _i,y¹ _i)表示顶点i的坐标，两个需求点分别记为v¹ _start和v¹ _end，A¹表示边集。顶点j和顶点k之间的距离记为

最短路径记为点集P¹＝{p¹ ₁,p¹ ₂,...,p¹ _l}(0<l≤n)，油料投送最短路径优化目标函数为：

在实际军用油料投送过程中存在道路堵塞、桥梁损毁、敌方干扰等问题。在此类情况下，相关路段禁止访问，为A¹内所有边定义二进制变量O_ij，若O_ij为 1，则该路径可以通行，若O_ij为0，则该路径不可以通行。

保证规划路径不经过特殊路段需满足如下约束条件：

S103：构建代价函数；

构建初始代价函数为f(n)＝g(n)+h(n)，f(n)表示从初始状态经由状态n的实际代价，g(n)是在状态空间中从初始状态到状态n的实际代价，h(n)是从状态n到目标状态的估计代价。为解决实际投送过程避免通过禁止访问路段，在初始代价函数中增加当前状态到故障路段的代价，且三种代价加入权重系数，通过调节权重系数大小改变解空间优先搜索方向，最终得到包含当前状态到故障路段的代价的代价函数，

f(n)＝α×g(n)+β×h(n)+γ×y(n)

其中，g(n)表示起始状态v¹ _start到当前状态v¹ _n的代价，h(n)表示当前状态v¹ _n至结束状态v¹ _end的代价，y(n)表示当前状态v¹ _n至所有故障路段v¹ _i(0<i≤l)的代价；α,β,γ分别为g(n),h(n),y(n)的权重系数，且α+β+γ＝1。

通过引入y(n)代价因子，使得该方法在搜索最优路径的过程中，具有动态避开障碍功能。代价函数由3个因子组成，若某个因素的代价值过小/过大，会导致代价函数不平衡，则会向该方向持续搜索，陷入局部最优解。本发明提出通过动态规划α,β,γ值的大小，调整算法的搜索方向，扩大搜索范围，避免局部最优解的产生。

S105：利用所述数学模型和代价函数计算最短投送路径。

S1051：设置代价函数影响因子初始值α,β,γ；

S1053:生成P¹'，其中P¹'包含的元素为与当前道路节点联通且O_ij为1的所有节点；

S1055：根据判断依据判断是否代价不平衡，若不平衡则重新设置价函数影响因子α,β,γ的值，否则进行S1057，判断依据为：判断代价函数是否满足下列公式，若满足则代价平衡，反之则不平衡

S1057：计算集合P¹'中每个元素的代价值，从P¹'中选择代价值最小的节点v¹ ₂，更新路径访问顺序P¹＝{v¹ _start,v¹ ₂}；

S1059：重复进行S1053-1057，直至访问到v¹ _end为止。

S20：规划基于最短投送路径的油料调拨顺序。

S201：构建调拨顺序规划的目标函数

两点间最短投送路线规划完成后，需以总路径最短为目标进行需求点调拨顺序规划。将包括m个点的网络分布图记为G²＝(V²,A²)，其中，m个点包括m-1 个需求点和1个配送站，V²为需求点集，记为V²＝{v² ₁＝(x² ₁,y² ₁),...,v² _m＝(x² _m,y² _m)}，调度顺序表示为P²＝{p² ₁,p² ₂,...,p² _m}，则调拨顺序规划的目标函数为

其中，D_ij ¹为S105中计算的每两点的最短距离，

将需求点v² _i访问次数定义为

约束条件为0<i≤m,N_i＝1，以使得调度方案中每个需求点访问且仅访问一次，

S202:用基因和染色体表示调度顺序，并生成初始可行解；

生成调拨顺序调度问题的可行解并用基因和染色体表示的过程称为染色体编码。节点总数目为m，每代的染色体总数目为GEN，则染色体i表示为 chromoⁱ＝{a₁ ⁱ,a₂ ⁱ,...,a_m ⁱ}，其中基因值0<a_k ⁱ<1表示节点k的权重，基因值大，则优先访问该节点

将节点序号按照染色体上基因值即某节点权重降序排列，即可得到调拨顺序序列；

S203：建立适应度函数，并计算所有可行解的适应性大小；

个体的优良程度可由适应度函数计算得出，适应度越高的个体保留概率更大，其基因能够在种群中不断遗传.染色体i优良程度由该种调拨顺序的行进路程D_i ²决定，适应度函数f(x)为：

S205：确定需要保留的染色体、交叉后形成的染色体和变异后的形成的染色体；

根据遗传学进行计算方法是一种模仿自然界生物进化理论提出的全局搜索计算方法。优化问题的每一个可行解对应于一条染色体，通过交叉、变异、选择等操作保留适应度高的个体并生成新的种群，通过不断的迭代向优化问题的最优解靠近。新种群染色体由交叉、变异、选择构成的比例分别为t₁,t₂,t₃，三个参数满足如下条件：

t₁+t₂+t₃＝1

个体保留与否由轮赌法确定，若染色体i的适应度为f(x_i)，则该个体被选中的概率为：

该染色体的累积概率为：

在[0,1]区间内随机生成随机数r₁，保留满足式Q(x_k-1)≤r₁<Q(x_k)的第k条染色体；

采用单点交叉算子，两个染色体经过交叉操作可以形成两个新的染色体。随机设置交叉点r₂∈N*,1≤r₂≤m。随机产生[0,1]区间内随机生成随机数r₃，比较r₃与交叉概率P_m，若r₃>P_m，则两染色体相互交叉，反之则不进行操作。交叉操作即两条染色体交叉点后的基因相互交换，形成两个新的染色体；

随机设置交叉点r₄∈N*,1≤r₄≤m，随机产生[0,1]区间内的随机数r₅，比较r₅与交叉概率P_c，若r₅>P_c，则进行变异操作，即将该基因位的基因值换为[0,1]区间内的随机数r₆，反之则不进行变异。

S207：更新种群为选择保留的染色体、交叉后的染色体、变异后的染色体，直至满足迭代条件；

S209：将节点序号按照节点权重降序排列，即可得到调拨顺序序列。

显然，本发明的上述实施例仅仅是为清楚地说明本发明所作的举例，而并非是对本发明的实施方式的限定，对于所属领域的普通技术人员来说，在上述说明的基础上还可以做出其它不同形式的变化或变动，这里无法对所有的实施方式予以穷举，凡是属于本发明的技术方案所引伸出的显而易见的变化或变动仍处于本发明的保护范围之列。

Claims (10)

1.一种军用油料投送路径规划方法，其特征在于，包括：

S10：根据实际地图情况，计算起始点与终点之间最短投送路径；

S20：规划基于最短投送路径的油料调拨顺序。

2.根据权利要求1所述的方法，其特征在于，所述S10包括：

S101：构建计算两点间最短路径数学模型；

S103：构建代价函数；

S105：利用所述数学模型和代价函数计算最短投送路径。

3.根据权利要求1所述的方法，其特征在于，所述S101包括：

包含有n个节点的地图，其道路分布图记为G¹＝(V¹,A¹)，其中，V¹为节点集，记为V¹＝{v¹ ₁＝(x¹ ₁,y¹ ₁),...,v¹ _n＝(x¹ _n,y¹ _n)}其中(x¹ _i,y¹ _i)表示顶点i的坐标，两个需求点分别记为v¹ _start和v¹ _end，A¹表示边集，顶点j和顶点k之间的距离记为

最短路径记为点集P¹＝{p¹ ₁,p¹ ₂,...,p¹ _l}(0＜l≤n)，油料投送最短路径优化目标函数为：

为A¹内所有边定义二进制变量O_ij

构建约束条件，以使保证规划路径不经过特殊路段

4.根据权利要求3所述的方法，其特征在于，所述S103包括：

构建包含当前状态到故障路段的代价的代价函数，

f(n)＝α×g(n)+β×h(n)+γ×y(n)

其中，g(n)表示起始状态v¹ _start到当前状态v¹ _n的代价，h(n)表示当前状态v¹ _n至结束状态v¹ _end的代价，y(n)表示当前状态v¹ _n至所有故障路段v¹ _i(0＜i≤l)的代价；α,β,γ分别为g(n),h(n),y(n)的权重系数，且α+β+γ＝1。

5.根据权利要求1所述的方法，其特征在于，所述S105包括：

S1051：设置代价函数影响因子初始值α,β,γ；

S1053:生成P¹'，其中P¹'包含的元素为与当前道路节点联通且O_ij为1的所有节点；

S1055：根据判断依据判断是否代价不平衡，若不平衡则重新设置价函数影响因子α,β,γ的值，否则进行S1057，判断依据为：判断代价函数是否满足下列公式，若满足则代价平衡，反之则不平衡

S1057：计算集合P¹'中每个元素的代价值，从P¹'中选择代价值最小的节点v¹ ₂，更新路径访问顺序P¹＝{v¹ _start,v¹ ₂}；

S1059：重复进行S1053-1057，直至访问到v¹ _end为止。

6.根据权利要求1所述的方法，其特征在于，所述S20包括：

S201：构建调拨顺序规划的目标函数，包括：

将m个点的网络分布图记为G²＝(V²,A²)，其中，m个点包括m-1个需求点和1个配送站，V²为需求点集，记为V²＝{v² ₁＝(x² ₁,y² ₁),...,v² _m＝(x² _m,y² _m)}，调度顺序表示为P²＝{p² ₁,p² ₂,...,p² _m}，根据S105中计算出每两点的最短距离D_ij ¹，然后调拨顺序规划的目标函数为

将需求点v² _i访问次数定义为

约束条件为0＜i≤m,N_i＝1以使得调度方案中每个需求点访问且仅访问一次；

S202:用基因和染色体表示调度顺序，并生成初始可行解；

S203：建立适应度函数，并计算所有可行解的适应性大小；

S205：确定需要保留的染色体、交叉后形成的染色体和变异后的形成的染色体；

S207：更新种群，直至满足迭代条件；

S209：将节点序号按照节点权重降序排列，即可得到调拨顺序序列。

7.根据权利要求6所述的方法，其特征在于，所述S202包括：

节点总数目为m，每代的染色体总数目为GEN，则染色体i表示为chromoⁱ＝{a₁ ⁱ,a₂ ⁱ,...,a_m ⁱ}，其中基因值0＜a_k ⁱ＜1表示节点k的权重，基因值大，则优先访问该节点；

节点序号按照染色体上基因值降序排列，得到初始可行解。

8.根据权利要求1所述的方法，其特征在于，所述适用度函数为

其中，D_i ²为调拨顺序的行进路程，用于决定染色体i的优良程度。

9.根据权利要求1所述的方法，其特征在于，所述S205包括：

需要保留的染色体、交叉后形成的染色体和变异后的形成的染色体构成比例分别为t₁,t₂,t₃，三个参数满足如下条件：

t₁+t₂+t₃＝1

若染色体i的适应度为f(x_i)，则该个体被选中的概率为：

该染色体的累积概率为：

在[0,1]区间内随机生成随机数r₁，保留满足式Q(x_k-1)≤r₁＜Q(x_k)的第k条染色体；

两个染色体经过交叉操作可以形成两个新的染色体，随机设置交叉点r₂∈N*,1≤r₂≤m。随机产生[0,1]区间内随机生成随机数r₃，比较r₃与交叉概率P_m，若r₃＞P_m，则两染色体相互交叉，反之则不进行操作，交叉操作即两条染色体交叉点后的基因相互交换，形成两个新的染色体。

10.根据权利要求1所述的方法，其特征在于，所述S205还包括：

随机设置交叉点r₄∈N*,1≤r₄≤m，随机产生[0,1]区间内的随机数r₅，比较r₅与交叉概率P_c，若r₅＞P_c，则进行变异操作，即将该基因位的基因值换为[0,1]区间内的随机数r₆，反之则不进行变异。

Images