本发明涉及图布局设计与规划，尤其涉及一种求解软集群弧路径优化问题的双级混合迭代搜索方法。
背景技术：
1、软集群容量束弧路径问题(soft-clustered capacitated arc routingproblem,softclucarp)是容量约束弧路径问题(capacitated arc routing problem,carp)的变体。它将所需要服务的弧或边划分为集群，并且同一集群的所有需要服务的弧或边必须由同一车辆服务。softclucarp很好地模拟了各种实际应用，如垃圾收集、邮政投递、扫雪、撒盐和输电线路检测等。
2、软集群容量约束弧路径问题定义在一个具有顶点集v和边集e的无向图g＝(v,e)上，其中顶点v0∈v是唯一的仓库点，在仓库点有m辆相同的容量为q的车辆。边集e中的边要么是必需服务的边er，要么是非必需服务的边e\er，必需服务的边至少遍历一次但只服务一次，如果方便，可以遍历非必需服务的边。任何没有服务的遍历都称空转。每条必需服务的边e∈er都有一个非负的需求d(e)≥0，每条边e∈e都有一个非负的服务代价sc(e)≥0和一个非负的空转代价dc(e)≥0。softclucarp不区分服务代价和空转代价，即sc(e)＝dc(e)。所有必需服务的边都被划分为不相交的集群，即er＝∪i∈hci并且其中h是集群的索引集且i,j∈h。每个集群ci都有一个非负的需求di可视为属于ci的所有必需服务的边的需求之和。softclucarp的目标是确定图g上的成本最低的路径集，这样同一集群的所有客户边由同一辆车服务一次，每条路径上客户边的总需求不超过该车辆的容量q。
3、软集群容量约束弧路径问题复杂程度高，求解时间长。一个可行的softclucarp解要求满足以下四个条件：(1)每条路径应在仓库点开始和结束；(2)每个必需服务的边都被服务只被提供一次服务，但是可以经过多次；(3)每辆车所服务的边总需求不得超过其容量q；(4)同一集群的所有客户边必须由同一辆车服务。
4、图1中所示一个软集群容量约束弧路径问题的算例，该算例的图g中包含9个顶点和11条边，其中v0为仓库点。11条边中有8条边为必需服务的边且被分为5个集群，其中e1＝{e1,e2}、e2＝{e3,e4}、e3＝{e5}、e4＝{e6,e7}、e5＝{e8}。相应的softclucarp解由三条路径组成：r1＝{e1(v0,v1),e2(v2,v0)}、r2＝{e5(v5,v7),e4(v4,v3),e3(v3,v0)}和r3＝{e6(v0,v6),e8(v6,v8),e7(v7,v0)}。
5、因此，本发明提出一种求解软集群弧路径优化问题的双级混合迭代搜索方法解决上述问题。
技术实现思路
1、本发明要解决的技术问题是提供一种求解软集群弧路径优化问题的双级混合迭代搜索方法，对软集群容量约束弧路径问题实现高鲁棒性、高质量求解。
2、为解决上述技术问题，本发明的技术方案为：一种求解软集群弧路径优化问题的双级混合迭代搜索方法，其创新点在于：所述双级混合迭代搜索方法将一个软集群带容量约束的弧路径问题的解s表示为两组大小为m的解，即集群层面的解g和客户层面的解r，集群层面的解g表示一组被访问的集群，而客户层面的解r，即边层解，表示服务客户边的顺序，双级混合迭代搜索方法的步骤包括：
3、步骤(1)、通过初始化程序生成一个集群层的初始解g，记录最优解；
4、步骤(2)、使用基于随机排序的变邻域下降操作优化集群层解g；
5、步骤(3)、使用基于下界指导的变邻域下降操作优化边层解r，并更新最优解；
6、步骤(4)、使用相似性驱动的混合扰动帮助算法跳出局部最优；
7、步骤(5)、重复步骤(2)-步骤(4)，直到达到设定的停止条件，得到问题的最优解。
8、进一步地，所述步骤(1)中初始化程序的具体步骤包括：
9、步骤(1.1)、将所有集群根据需求降序排列；
10、步骤(1.2)、根据随机因子在排列中选择一个位置的集群添加到最近的可行车辆中，要求车辆的容量不超过每辆车的最大限容；
11、步骤(1.3)、重复步骤(1.2)直到将所有集群分配给车辆为止，从而得到一个集群层的可行解g，如果没有车辆有足够的容量来装载下一个集群，则使用重新分配算子重新优化当前的集群分配。
12、进一步地，所述步骤(2)中基于随机排序的变邻域下降操作的具体步骤包括：
13、步骤(2.1)、对步骤(1)生成的子代解go使用基于随机顺序的变邻域下降(randomorder-based variable neighborhood descent,ro-vnd)在集群层进行优化，ro-vnd包含四个邻域分别对路径内和路径间的线路进行优化，对路径内线路优化的邻域包括两个经典算子，分别为2-opt算子和or-opt算子，对路径间线路优化的邻域包括两个算子，分别为relocate-sequence算子和swap-sequence算子；
14、步骤(2.2)、在开始时对这四个邻域进行随机排序；
15、步骤(2.3)、选取排序后的第一个邻域对解go进行优化，如果当前邻域找不到改进解就进入下一个邻域，一旦找到了更优解，就更新当前解并回到第一个邻域继续搜索；
16、步骤(2.4)、重复步骤(2.3)，直到所有邻域都被探索完或无法改进当前解。
17、进一步地，所述步骤(3)中基于下界指导的变邻域下降操作的具体步骤包括：
18、步骤(3.1)、通过随机转换算子将优化后的集群层的解go转化为边层的解ro；
19、步骤(3.2)、对步骤(3.1)生成的边层的初始解ro使用基于下界指导的变邻域下降(lower bound-guided variable neighborhood descent,lb-vnd)在边层进行优化，每一个边层的路径都看作乡村邮递员问题(rural postman problem,rpp)，用迭代局部搜索(iterated local search,ils)对rpp进行求解，即ils-rpp；
20、步骤(3.3)、用ils-rpp对转化后的边层的解在路径内进行优化；
21、步骤(3.4)、按序用relocate-sequence和swap-sequence两个邻域对步骤(3.3)得到的解在路径间进行优化；
22、步骤(3.5)、当步骤(3.4)中的邻域对解进行了改进后，再用ils-rpp对新的路径进行优化；
23、步骤(3.6)、通过下界指导机制加速lb-vnd的搜索。
24、进一步地，所述步骤(4)中相似性驱动的混合扰动的具体步骤包括：
25、步骤(4.1)、计算步骤(3)得到的解s′与最优解s*的相似度
26、步骤(4.2)、当时，采用基于骨骼的方向性扰动(backbone-based directed perturbation,bdp)策略；
27、步骤(4.3)、当时，采用基于破坏-修复的随机性扰动(destroy-repair random perturbation,drp)策略。
28、本发明的优点在于：
29、本发明提供的求解软集群容量约束弧路径问题的混合模因搜索方法，除了一般化的初始化程序外，还集成了三个高效的模块：一个基于随机排序的变邻域下降操作以生成高质量的集群层解，一个基于下界指导的变邻域下降操作对集群层解对应边层解进行优化，以及一个使用相似性驱动的混合扰动帮助算法跳出局部最优，具有求解质量高，鲁棒性强，应用范围广等优点。
1.一种求解软集群弧路径优化问题的双级混合迭代搜索方法，其特征在于：所述双级混合迭代搜索方法将一个软集群带容量约束的弧路径问题的解s表示为两组大小为m的解，即集群层面的解g和客户层面的解r，集群层面的解g表示一组被访问的集群，而客户层面的解r，即边层解，表示服务客户边的顺序，双级混合迭代搜索方法的步骤包括：
2.根据权利要求1所述的求解软集群弧路径优化问题的双级混合迭代搜索方法，其特征在于：所述步骤(1)中初始化程序的具体步骤包括：
3.根据权利要求1所述的求解软集群弧路径优化问题的双级混合迭代搜索方法，其特征在于：所述步骤(2)中基于随机排序的变邻域下降操作的具体步骤包括：
4.根据权利要求1所述的求解软集群弧路径优化问题的双级混合迭代搜索方法，其特征在于：所述步骤(3)中基于下界指导的变邻域下降操作的具体步骤包括：
5.根据权利要求1所述的求解软集群弧路径优化问题的双级混合迭代搜索方法，其特征在于：所述步骤(4)中相似性驱动的混合扰动的具体步骤包括：
