一种基于帝国主义竞争算法的车辆路径规划方法

摘要

本发明公开的一种基于帝国主义竞争算法的车辆路径规划方法，包括步骤：S1、建立区域环境交通图、S2、建立初始帝国、S3、帝国内的同化操作、S4、帝国内的革命操作、S5、帝国内的增强操作、S6、帝国间的竞争操作、S7、迭代判断。本发明通过帝国主义竞争算法自动计算出满足全局优化、计算时间、解的质量、收敛速度等综合要求的一个最优行驶路线，省去了驾驶员或调度员自己规划路线的精力消耗，与原来的非最优路径相比，优化减少的部分能直接节省车辆运行时间成本和燃油成本，提升单车的物流配送效率和服务质量，降低物流企业的运营成本。

说明书

技术领域

本发明属于交通物流的路径规划领域，特别涉及一种基于帝国主义竞争算法的车辆路径规划方法。

背景技术

随着互联网信息技术的浪潮，电子商务、全球定位系统、智能交通系统、地理信息系统和全球移动通讯系统等工具的技术愈加成熟，促进了物流业的迅速发展。物流配送是物流行业的一个关键环节，配送车辆多数时间是消耗在城市穿梭中的。配送路径的优化能直接降低配送过程中的人力和时间成本，显著提升物流企业的运输效率和服务质量。所以，车辆路径规划主要解决的问题是：如何以顾客配送需求为输入，在行驶距离或消耗时间最少的优化目标下，为配送车辆提供最合理的行驶路线。

由于车辆路径规划是强NP难题(未被证明是否存在多项式算法能够解决的问题)，面对城市内几千个配送点，直接对大规模配送点进行多车路径规划很难在可行时间内得到结果，且可行解一般精度不高。考虑到实用性，对大规模多车路径规划的一般做法是，根据城市街道布局对配送网络分区，将问题转化为小规模区域的单车路径规划。

经过区域划分，小规模区域的配送点一般少则几十，多则上百。为了解决单车路径规划问题，一般有精确算法、传统启发式算法和元启发式算法三类方法。精确算法如分支界定法、动态规划法、最小K树法、列生成法等，无法避开指数爆炸问题，通常适用于非常小规模的路径规划问题，在实际中相对难以应用。构建型法、扫除算法、局部搜索算法、节约算法等传统启发式算法通过某种直观判断或试探，能在可接受时间内求得问题的次优解，这类方法近20年来得到了很好的发展，但缺乏统一、完整的理论体系。随着计算机运算能力的增长，遗传算法、粒子群算法、蚁群算法、萤火虫算法、花瓣算法等元启发算法逐渐成为路径规划的主流方法，这类算法内嵌了不同的技术和概念来规避局部最优，包括随机、进化、记忆存储、引导等。尽管目前可选方法众多，但仍然没有一个公认完美的算法能解决路径规划的NP问题。不同的路径规划方法均会表现出下述问题的一个或多个：适用性差、陷入局部最优、过多的无效计算、收敛速度慢、解的质量不高、稳定性不好等问题。因此对于路径规划方法的研究一般旨在改善已有算法的缺陷，或提出综合表现力更好的算法。

发明内容

本发明的目的在于提供一种基于帝国主义竞争算法的车辆路径规划方法，可直接应用于解决物流行业中，解决货物配送时多配送点的单车路径规划问题。

为了实现上述目的，本发明采用如下技术方案：

一种基于帝国主义竞争算法的车辆路径规划方法，包括以下步骤：

S1、建立区域环境交通图，结合区域环境交通图给出物流中心和配送点的点集、弧集，以及给出物流中心及各配送点相互间的距离值；所述点集指物流中心和配送点在区域环境交通图上的位置点集合，弧集指物流中心与配送点之间的道路集合；

S2、建立初始帝国，通过乱序算法并依据步骤S1的点集与弧集随机生成N个路径，计算各路径的总距离，定义N个国家，通过路径总距离与国家权力的关系式来评估各国家的国家权力，接着按照国家权力排序并将所有国家分成殖民国家和殖民地，生成权力最大的N_imp个殖民国家，即N_imp个帝国和N_col＝N-N_imp个殖民地，分别存储殖民国家和殖民地的权力表；

S3、帝国内的同化操作：殖民国家以自身路径为基准，依据一定同化率随机地替换和改变殖民地路径中的部分点集；

S4、帝国内的革命操作：殖民地随机改变自身路径的部分地点位置，变化方式为节点的0-1交换和1-1交换，并重新评估殖民国家和殖民地的权力，若后者力大于前者，则取代前者形成新的帝国；

S5、帝国内的增强操作：根据殖民国家权力表，对权力最小的殖民国家进行增强，增强方式为：随机移除该殖民国家路径中部分点集，再将移除的点集随机重排并依次插入剩余地点中所以可能的位置，接着重新评估殖民国家增强前后的权力，保留权力大的殖民国家；

S6、帝国间的竞争操作：以帝国为单位，计算帝国内殖民国家和所有殖民地的标准化加权权力和，通过评估所有帝国权力，将最弱帝国的最弱殖民地分配给最强帝国，此外，当某个帝国内没有任何殖民地时视为帝国消失，则该帝国的殖民国家也被分配给最强帝国作为殖民地；

S7、迭代判断：判断是否一个帝国是否到达预设迭代次数，若是则停止运算，输出权力最大殖民国家的路径作为最优解，若否，则返回S3。

所述步骤S1具体包括：首先给出物流中心和配送点的点集，定义G＝(V,E,D)为需要货物配送的区域环境交通图，其中V＝{1,2,…,M}为物流中心和要经过的配送点的集合，即点集，设V₁为物流中心，E＝{(i,j)|(i,j∈V),i≠j}为物流中心与各配送点之间的道路集合，即弧集，距离矩阵D＝[d_ij]_M×M中每一个元素表示物流中心或配送点”i与物流中心或配送点j的距离，且有d_ij＞0,d_ii＝+∞,i,j∈V。

所述步骤S2具体包括：

S21、初始化路径和距离：构建初始路径解，即对除V₁以外的点集{V₂,V₃,…,V_M}进行N次乱序排列，生成N条不同路径L＝{L₁,L₂,…,L_N}及其路径总距离dist＝{dist₁,dist₂,…,dist_N}，其中所有路径的初始点均为物流中心V₁，则一条车辆配送路径的总距离为

S22、初始化国家和权力：定义N个国家C＝{C₁,C₂,…,C_N}及其国家权力c＝{c₁,c₂,…,c_N}，并将路径总距离dist与国家权力c建立相关性其中c_n、dist_n分别表示第n个国家的权力和对应的路径总距离，初始化当前迭代次数iter＝1和预设迭代次数iter_final；

S23、殖民国家的殖民地分配：按照国家权力从大到小对所有国家进行排序，取权力最大的N_imp个国家作为殖民国家，它们的权力定义为c_imp_i,i＝1,2,…,N_imp，剩余N_col＝N-N_imp个作为殖民地，它们权力定义为c_col_j,j＝1,2,…,N_col；然后对殖民国家权力标准化有接着根据分配公式N_imp_i＝round{p_imp_i·N_col}将所有殖民地分配给殖民国家，第n个殖民国家可分得N_imp_i个殖民地，且满足其中round表示取整函数，至此，结束N_imp个帝国的初始化过程。

所述步骤S3具体包括：

S31、初始化同化率：生成M个[0,1]间的随机数，M个随机数对应殖民国家路径解中的M个序号；定义同化率ρ，取值范围为0＜ρ＜1；

S32、路径解的局部同化：随机数小于等于ρ的序号处视作同化地点，同化方式为殖民国家在这些序号处的地点编号直接作为同化后殖民地在相同序号处的地点编号；

S33、路径解的局部保持：对于随机数大于ρ的序号，若殖民地在这些序号处的地点编号未在局部同化时出现过，则视作被保持，保持方式为殖民地在这些序号处的地点编号直接作为保持后殖民地在相同序号处的地点编号；

S34、路径解的局部重排：对于随机数大于ρ的序号，若殖民地在这些序号处的地点编号已在局部同化时出现过，则视作被重排，重排方式为将殖民国家在这些序号处的地点编号，一一插入局部保持后殖民地路径的任意位置，并取最小增加距离的位置；

S35替换：将局部重排后殖民地替换原有殖民地。

所述步骤S4包括如下具体步骤：

S41、0-1交换：在殖民地路径中随机选择一个除初始地点以外的地点，将该点依次插入其他位置，并取最小增加距离的位置，若有更优解，替换原解，若无，则保留原解；

S42、1-1交换：殖民地路径中随机选择一个除初始地点以外的地点，与其他位置依次交换，并取最小增加距离的位置；若有更优解，替换原解，若无，则保留原解；

S43、评估和革命：对所有殖民地进行0-1和1-1交换后，评估帝国内的殖民国家和殖民地权力并进行排序，若殖民地的最高权力大于殖民国家，则该殖民地和殖民国家交换身份。

所述步骤S5包括如下具体步骤：

S51、m-m交换：根据殖民国家权力表，将权力最小的殖民国家作为增强对象，从殖民国家路径中随机移除m个地点，再将这m个地点按顺序依次插入剩余M-m个地点中所有可能的位置，每次插入取最小增加距离的位置，直至m个地点插入完毕；

S52、评估和增强：对m-m交换前后的殖民国家路径解进行评估，若有更优解，替换原解，视为帝国增强成功，若无，则保留原解。

所述S6中包括如下具体步骤：

S61、计算帝国权力：在N_imp个帝国中，第i个帝国由1个殖民国家和N_imp_i个殖民地组成，第i个帝国的权力T_i由殖民国家权力c_imp_i和殖民地权力c_col_j加权组成，计算如下：

接着对N_imp个帝国权力进行标准化有：

且满足因此有帝国权力向量

S62、殖民地吞并：定义与Tp相同维的随机向量其元素均服从均匀分布Rp_i～U(0,(1+N_imp_i)/N)，并定义概率向量：

Dp＝Tp-Rp＝{Dp₁,Dp₂,…,Dp_imp}

＝{Tp₁-Rp₁,Tp₂-Rp₂,…,Tp_imp-Rp_imp}

接着找到max{Dp}和min{Dp}所对应的最强和最弱帝国，并找到最弱帝国中权力最小殖民地min{c_col₁,c_col₂,…}，将其分配给最强帝国，更新最强和最弱帝国的殖民地数量。

S63、帝国吞并：判断是否存在无殖民地的帝国，若是，则该帝国的殖民国家分配给最强帝国当殖民地，帝国和殖民国家数量均为N_imp＝N_imp-1。

所述S7中具体内容如下：

判断当前帝国数量是否为一或者迭代次数是否大于等于iter_final，若是，则停止运算，输出权力最大殖民国家的路径作为最优解，若否，则返回S3，iter＝iter+1。

采用上述方案后，本发明有益效果是：本发明通过帝国主义竞争算法自动计算出满足全局优化、计算时间、解的质量、收敛速度等综合要求的一个最优行驶路线，省去了驾驶员或调度员自己规划路线的精力消耗，与原来的非最优路径相比，优化减少的部分能直接节省车辆运行时间成本和燃油成本，提升单车的物流配送效率和服务质量，降低物流企业的运营成本。另外，本发明首先将帝国主义竞争算法应用于车辆路径规划领域，为该领域提供了一个基于社会启发群智能算法的新切入点和新思路。

下面结合附图对本发明做进一步的说明。

附图说明

图1是本发明基于帝国主义竞争算法车辆路径规划方法的流程图；

图2是步骤S2建立初始帝国的原理图；

图3是步骤S3帝国内部同化操作的原理图；

图4是步骤S4帝国内部革命操作的原理图；

图5是步骤S5帝国内部增强操作的原理图；

图6是步骤S6帝国之间竞争操作的原理图。

具体实施方式

结合图1说明本具体实施方式，本发明实施例揭示的一种基于帝国主义竞争算法的车辆路径规划方法，是按以下步骤进行的：

S1、建立区域环境交通图，结合区域环境交通图给出物流中心和配送点的点集、弧集，以及给出物流中心及各配送点相互间的距离值；所述点集指物流中心和配送点在区域环境交通图上的位置点集合，弧集指物流中心与配送点之间的道路集合；具体是：

首先给出物流中心和配送点的点集，定义G＝(V,E,D)为需要货物配送的区域环境交通图，其中V＝{1,2,…,M}为物流中心和要经过的配送点的集合，即点集，设V₁为物流中心，E＝{(i,j)|(i,j∈V),i≠j}为物流中心与各配送点之间的道路集合，即弧集，距离矩阵D＝[d_ij]_M×M中每一个元素表示配送点或物流中心i与配送点或物流中心j的距离，且有d_ij＞0,d_ii＝+∞,i,j∈V。

S2、建立初始帝国，通过乱序算法并依据步骤S1的点集与弧集随机生成N个路径，计算各路径的总距离，定义N个国家，通过路径总距离与国家权力的关系式来给各国家分配国家权力，接着按照国家权力排序并将所有国家分成殖民国家和殖民地，生成权力最大的N_imp个殖民国家，即N_imp个帝国和N_col＝N-N_imp个殖民地，分别存储殖民国家和殖民地的权力表；

参见图2，根据历史社会事实，一个完整的帝国由一个殖民国家和若干个殖民地组成。此外，路径规划大体上包括构建初始路径解、路径优化两大步，因此实施帝国主义竞争算法时，应先建立初始帝国，分为下述三步进行：

S21、初始化路径和距离：构建初始路径解，即对除V₁以外的点集{V₂,V₃,…,V_M}进行N次乱序排列，生成N条不同路径L＝{L₁,L₂,…,L_N}及其路径总距离dist＝{dist₁,dist₂,…,dist_N}，其中所有路径的初始点均为物流中心V₁，则一条车辆配送路径的总距离为路径规划的目标是使总距离最小，有：

s.t.

对任意V的真子集S

约束1和2表示对任意一条弧而言，仅有一条边进和一条边出，约束3用于避免产生含有子回路的路径解，约束4中|S|为集合S中含图G的地点个数，约束5表示弧E_(i,j)被作为车辆最优路径。

S22、初始化国家和权力：定义N个国家C＝{C₁,C₂,…,C_N}及其国家权力c＝{c₁,c₂,…,c_N}，并将路径总距离dist与国家权力c建立相关性其中c_n、dist_n分别表示第n个国家的权力和对应的路径总距离，初始化当前迭代次数iter＝1和预设迭代次数iter_final；

S23、殖民国家的殖民地分配：按照国家权力从大到小对所有国家进行排序，取权力最大的N_imp个国家作为殖民国家，它们的权力定义为c_imp_i,i＝1,2,…,N_imp，剩余N_col＝N-N_imp个作为殖民地，它们权力定义为c_col_j,j＝1,2,…,N_col；为了后续计算的准确性和便利性，对殖民国家权力标准化有接着根据分配公式N_imp_i＝round{p_imp_i·N_col}将所有殖民地分配给殖民国家，第n个殖民国家可分得N_imp_i个殖民地，且满足其中round表示取整函数，至此，结束N_imp个帝国的初始化过程。

S3、帝国内的同化操作：殖民国家以自身路径为基准，依据一定同化率随机地替换和改变殖民地路径中的部分点集；

参见图3，帝国同化是帝国主义竞争算法在优化过程中的局部收敛步骤，表现在殖民国家以自身路径解为基准，同化其下属殖民地的路径解，并引导解的优化方向，使分散的解收敛至较优解周围，帝国同化过程分为下述五步进行：

S31、初始化同化率：生成M个[0,1]间的随机数，M个随机数对应殖民国家路径解中的M个序号；定义同化率ρ，为防止前期收敛过快，同化率ρ不宜过大，取值范围为0＜ρ＜1；

S32、路径解的局部同化：随机数小于等于ρ的序号处视作同化地点，同化方式为殖民国家在这些序号处的地点编号直接作为同化后殖民地在相同序号处的地点编号；以表1为例，给出殖民国家和殖民地的路径。取同化率ρ＝0.5，在殖民国家路径中，假设序号②④⑥⑦⑩处的随机数小于等于ρ，它们的地点编号会用于同化，将这些序号处的地点编号3、7、9、2、5直接作为局部同化后殖民地在相同序号处的地点编号。

表1路径解的局部优化

S33、路径解的局部保持：对于随机数大于ρ的序号，若殖民地在这些序号处的地点编号未在局部同化时出现过，则视作被保持，保持方式为殖民地在这些序号处的地点编号直接作为保持后殖民地在相同序号处的地点编号；以表2为例，殖民国家路径中，序号③⑤⑧⑨处的随机数大于ρ，其中在殖民地路径中只有序号③⑤⑧中的地点编号8、10、6未在上一步结果中(局部同化后殖民地)出现，则局部保持后的殖民地更新序号③⑤⑧处的地点编号8、10、6。

表2路径解的局部保持

S34、路径解的局部重排：对于随机数大于ρ的序号，若殖民地在这些序号处的地点编号已在局部同化时出现过，则视作被重排，重排方式为将殖民国家在这些序号处的地点编号，一一插入局部保持后殖民地路径的任意位置，并取最小增加距离的位置；以表3为例，殖民国家路径中，随机数大于ρ的序号为③⑤⑧⑨，其中序号③⑤⑧的地点编号已在上一步进行局部保持，剩下序号⑨处的地点编号4未处理，此时将4一一插入上一步结果中(局部保持后殖民地)，假设插入序号③处能使路径总距离最小，则可得到最终路径1、3、4、8、7、10、9、2、6、5。

表3路径解的局部重排

S35替换：将局部重排后殖民地替换原有殖民地。

S4、帝国内的革命操作：殖民地随机改变自身路径的部分地点位置，变化方式为节点的0-1交换和1-1交换，并重新评估殖民国家和殖民地的权力，若后者力大于前者，则取代前者形成新的帝国；

参见图4，帝国革命是帝国主义竞争算法在优化过程中的局部搜索步骤，表现在殖民地随机改变自身路径的部分地点位置，尝试找到总距离更短的路径解，在帝国内的同化操作后，所有殖民地的解会逐渐趋于殖民国家的解，因此帝国革命能增加殖民地解的多样性，防止局部收敛过快。另外，殖民地的解围绕在殖民国家的解附近，因此是一类局部搜索。帝国革命过程分为下述三步进行：

S41、0-1交换：在殖民地路径中随机选择一个除初始地点以外的地点，将该点依次插入其他位置，并取最小增加距离的位置，若有更优解，替换原解，若无，则保留原解；

S42、1-1交换：殖民地路径中随机选择一个除初始地点以外的地点，与其他位置依次交换，并取最小增加距离的位置；若有更优解，替换原解，若无，则保留原解；

S43、评估和革命：对所有殖民地进行0-1和1-1交换后，评估帝国内的殖民国家和殖民地权力并进行排序，若殖民地的最高权力大于殖民国家，则该殖民地和殖民国家交换身份。

S5、帝国内的增强操作：根据殖民国家权力表，对权力最小的殖民国家进行增强，增强方式为：随机移除该殖民国家路径中部分点集，再将移除的点集随机重排并依次插入剩余地点中所以可能的位置，接着重新评估殖民国家增强前后的权力，保留权力大的殖民国家；

参见图5，帝国增强是帝国主义竞争算法在优化过程中的全局搜索步骤，表现在对于权力最弱的殖民国家，随机改变其自身路径的部分地点位置，尝试找到总距离更短的路径解。帝国革命是局部搜索，帝国增强为全局搜索，需要有更强的改变力度，包括下述两步：

S51、m-m交换：根据殖民国家权力表，将权力最小的殖民国家作为增强对象，从殖民国家路径中随机移除m个地点，再将这m个地点按顺序依次插入剩余M-m个地点中所有可能的位置，每次插入取最小增加距离的位置，直至m个地点插入完毕；

S52、评估和增强：对m-m交换前后的殖民国家路径解进行评估，若有更优解，替换原解，视为帝国增强成功，若无，则保留原解。

S6、帝国间的竞争操作：以帝国为单位，计算帝国内殖民国家和所有殖民地的标准化加权权力和，通过评估所有帝国权力，将最弱帝国的最弱殖民地分配给最强帝国，此外，当某个帝国内没有任何殖民地时视为帝国消失，则该帝国的殖民国家也被分配给最强帝国作为殖民地；

参见图6，帝国竞争是帝国主义竞争算法在优化过程中的全局收敛步骤，表现在最强帝国逐渐吸收最弱帝国的殖民地，使多个小帝国逐渐兼并成一个大帝国，以此完成多个路径解到一个全局最优解的收敛过程。帝国竞争操作包括三步：

S61、计算帝国权力：在N_imp个帝国中，第i个帝国由1个殖民国家和N_imp_i个殖民地组成，第i个帝国的权力T_i由殖民国家权力c_imp_i和殖民地权力c_col_j加权组成，计算如下：

接着对N_imp个帝国权力进行标准化有：

且满足因此有帝国权力向量

S62、殖民地吞并：定义与Tp相同维的随机向量其元素均服从均匀分布Rp_i～U(0,(1+N_imp_i)/N)，并定义概率向量：

Dp＝Tp-Rp＝{Dp₁,Dp₂,…,Dp_imp}

＝{Tp₁-Rp₁,Tp₂-Rp₂,…,Tp_imp-Rp_imp}

接着找到max{Dp}和min{Dp}所对应的最强和最弱帝国，并找到最弱帝国中权力最小殖民地min{c_col₁,c_col₂,…}，将其分配给最强帝国，更新最强和最弱帝国的殖民地数量。

S63、帝国吞并：判断是否存在无殖民地的帝国，若是，则该帝国的殖民国家分配给最强帝国当殖民地，帝国和殖民国家数量均为N_imp＝N_imp-1。

S7、迭代判断：判断是否一个帝国是否到达预设迭代次数，若是则停止运算，输出权力最大殖民国家的路径作为最优解，若否，则返回S3。

S7具体是：判断当前帝国数量是否为一或者迭代次数是否大于等于iter_final，若是，则停止运算，输出权力最大殖民国家的路径作为最优解，若否，则返回S3，iter＝iter+1。

上述说明示出并描述了本发明的优选实施例，应当理解本发明并非局限于本文所披露的形式，不应看作是对其他实施例的排除，而可用于各种其他组合、修改和环境，并能够在本文发明构想范围内，通过上述教导或相关领域的技术或知识进行改动。而本领域人员所进行的改动和变化不脱离本发明的精神和范围，则都应在本发明所附权利要求的保护范围内。