本发明属于物流管理领域，具体涉及一种利用改进遗传算法实现中心选址及路径协同优化的方法。
背景技术：
1、当发生自然灾害或突发事件导致某个区域出现社会管理失序时，一般需要从该地的应急物资中心向灾区内的各个需求点派发物资。在这种特殊的物流场景中，涉及到多个可选的物资中心并要求对多个需求点进行遍历，因而在物流管理中需要进行物资中心选址，还需要根据选址对途径各个需求点的路径进行规划。现有技术对于这一类应急物资中心的选址和路径规划问题的研究还比较少，而传统的物资配送方法多依赖经验判断，缺乏对于灾害发生后需求不确定性和道路通行可靠性不稳定情况的考虑，容易导致资源浪费或配送不及时。
2、此外，现有的选址-路径优化研究大多关注单一方面问题，缺少对应急物资中心选址与物资配送路径协同优化的研究，无法全面解决实际应急管理中遇到的问题。例如，现有研究在实际的协同优化的求解过程中，一般将协同优化分解成选址问题与路径优化问题，再分别求解，虽然简单快速，这就失去了协同优化的统一求解、优化、管理的思想，使得求解的流程更复杂，效率更低。其次，协同优化在考虑多种因数的研究中发展到对不确定性因数的研究，但在应急物资中心的选址和路径协同优化研究中将选址与路径相结合的少数研究仅仅考虑了灾后某一特定情况下的选址决策和路径规划。
3、在目前的物流研究中，不乏考虑机会约束的研究，但主要是以应急物资中心的选址与路径问题分开独立研究，且多数只考虑需求的不确定性，而在实际问题中，应急物资中心的选址与路径问题是相互影响的，道路的可靠性等因数亦是不确定的，单纯的考虑其中一个问题在机会约束下的解，达到最优并不能表示另外一个问题在机会约束下的解也是最优，忽略了现实情境下救灾运输问题运输时间的不确定性及选址和路径规划间深切的关联性。
技术实现思路
1、为了解决现有技术难实现多中心多目的地场景下的物流高效管理的问题，本发明提供一种利用改进遗传算法实现中心选址及路径协同优化的方法。
2、本发明采用以下技术方案实现：
3、一种利用改进遗传算法实现中心选址及路径协同优化的方法，其用于在一个包含多个应急物资中心和多个需求点的场景中，确定满足多重优化目标的物资选址点，并生成遍历所有需求点的最佳路径。该方法包括如下步骤：
4、s1：分析当前的物流运输场景，获取配送车辆的基本信息以及备选址点与需求点之间的配送信息。包括：备选址点和需求点的集合，配送车辆的最大载重量和组织成本，备选址点和需求点间的通行时间分布，及各需求点的物资需求。
5、s2：以物资选址点，以及选址点与需求点间的路径与配送车辆的既定路线间的关系为决策变量，构建一个应急物资中心选址-路径协同优化模型。
6、s3：基于改进遗传算法对应急物资中心选址-路径协同优化模型进行迭代寻优，确定满足约束条件和优化目标的最优选址点和路径。其中，遗传算法的改进包括：
7、(1)将应急物资中心选址-路径协同优化模型中的目标函数的倒数作为改进遗传算法的适应度函数。
8、(2)设置种群中染色体的编码规则为：将备选址点和需求点采用不同区间内的连续数字进行编码，将从每个选址到达的各个需求点的路径采用对应数字按顺序相连构成一个染色体片段，多个选址点对应的染色体片段间采用0作为分隔符相连。每个染色体片段中的选址点的编码记为选址基因，选址基因后连接的各个需求点的编码记为路径基因。
9、(3)定义染色体更新采用的交叉算子为：将种群中的染色体随机配对，按照一定交叉概率，以非0基因交叉的方式进行交叉运算，子代分别遗传其中一个父代的路径基因和另一个父代的选址基因。
10、(4)定义染色体更新采用的变异算子包括3类，分别为：(a)选址基因突变：依概率在备选集合中随机另选一个非重复的选址点替换原选址点。(b)选址基因交换：依概率对当前染色体内的任意两个染色体片段中的选址基因部分进行交换。(c)路径基因交换：依概率对当前染色体内的任意两个染色体片段中的路径基因的部分节点进行交换。
11、(5)采用机会约束的方法等价设计容量约束和时间约束，以用于遗传算法中对迭代更新后的染色体种群进行容量检查和时间检查。
12、其中，容量约束的表达式为：
13、
14、上式中，i表示需求点i的集合；λi表示车队需配送需求点i的应急物资需求量；zri为表征车队r是否对需求点i进行服务的状态标志；σr是一个确保总需求高于vr的概率至少等于αr的泊松随机变量的最大期望值。
15、时间约束的表达式为：
16、
17、上式中，tab表示车队在a、b两点之间的车队运输时间；zrab为表征两点a、b间存在的路径ab是否在车队r的运输路线上的状态标志；w表示选定的应急物资中心和需求点的集合；εr是一个确保配送时间高于tmax的概率至少等于1-βr的泊松随机变量的最大期望值。
18、作为本发明进一步的改进，步骤s2中，应急物资中心选址-路径协同优化模型的决策变量包括：zj、zrab、zri、zrj。其中，zj为表征备选址点是否作为应急物资中心的状态标志；zrj为表征车队r是否以备选址点j为起始点并对其进行服务的状态标志。
19、作为本发明进一步的改进，应急物资中心选址-路径协同优化模型的目标函数c为：
20、
21、上式中，i表示需求点i的集合；r表示车队r的集合；cj表示应急物资中心备选址点j的固定成本；cw表示单位应急物资的采购成本；vr表示车队需配送的应急物资量；v0表示配送车辆满载时的应急物资运输量；cr表示配送车辆的调动成本；pi表示第i个需求点的总人口；hi表示需求点i的灾害程度系数；q0表示需求点中每个人的单位物资需求量；qi表示需求点i的当前救灾应急物资需求量；μi表示需求点i在灾情下的扰动因子；tmin表示救援时限；ct表示单位时间的超时成本；cab表示车队在路径ab上的单位应急物资的运输成本。
22、作为本发明进一步的改进，应急物资中心选址-路径协同优化模型中的约束函数包括：
23、
24、上式中，j表示应急物资中心的备选址点的集合；k表示应急物资中心的备选址点j的数量；n表示需求点i的数量；k表示车队r的数量；gj表示容量限制。
25、作为本发明进一步的改进，步骤s3中，迭代寻优的过程如下：
26、s31：初始化遗传算法的各个参数和适应度函数，包括：种群大小ps、当前进化次数g、最大进化次数gmax，种群交叉概率cp，种群变异概率mp。
27、s32：采用轮盘赌策略从备选址集合中挑选初始的选址点，并生成遍历所有需求点的初始路径；然后结合选址点及其对应的需求点完成染色体编码，得到初始种群。
28、s33：对种群中的染色体进行识别，提取选址点和路径方案。
29、s34：依次检查每个染色体对应的选址和路径方案是否满足容量约束和时间约束：
30、(1)是则计算方案的总成本，并记录最优方案的各项成本。
31、(2)否则调整染色体对应的方案中的路径，更新染色体，并返回步骤s33重新进行染色体检查。
32、s35：计算种群中各个染色体的适应度函数值，并判断是否达到迭代终止条件：
33、(1)是则结束染色体的迭代更新。
34、(2)否则采用选择、交叉和变异算子对当前种群进行迭代更新，生成下一代种群，并返回步骤s33进行下一轮迭代。
35、s36：结束染色体的迭代更新后，根据当前轮次中成本最优的染色体，生成对应的最优配送方案。
36、作为本发明进一步的改进，步骤s31中，种群变异概率mp的区间为：(0.05，0.1)；种群交叉概率cp的区间为：(0.5，0.8)。
37、作为本发明进一步的改进，步骤s33中，调整染色体对应的方案中的路径的过程为：
38、若某个染色体不满足约束条件，则将该染色体的第一个选址基因对应的路径基因序列中第一个需求点编号删去，并将其添加到下一选址基因的路径基因的尾部，得到新的染色体序列，并更新染色体。若仍不满足，则依次后移染色体中调整的节点，直至调整后的染色体基因序列满足容量和时间约束条件为止。
39、其中，若染色体中最后一个选址基因对应的路径基因序列需调整，则将其添加到第一个选址基因的路径基因的尾部，得到新的染色体序列，并更新染色体。
40、作为本发明进一步的改进，在步骤s34中，利用二维搜索获得总需求量的最大期望值，对每个配送车队进行容量约束检查。该过程如下
41、(1)定义当前应急物资中心为jm、中心容量gj、车队运输物资量vr、搜索范围sr、步长s、总需求量和阈值αr。
42、(2)使用循环遍历搜索范围内的可能最大期望值σr，并计算当前中心的概率值。
43、(3)根据概率值做出判断：如果该概率值不小于1-αr，则更新最大期望值σr为当前值；否则提前结束搜索。
44、(4)最终返回满足条件的最大期望值σr。
45、(5)若提前结束搜索或则进行路径调整，直至满足约束。
46、作为本发明进一步的改进，在步骤s34中，利用二维搜索获得时间的最大期望值，对每个配送车队进行时间约束检查。该过程如下：
47、(1)定义当前中心为jm，其泊松分布的期望值为tmax＝24h，搜索范围sr、步长s、车队的运输时间为和阈值βr。
48、(2)使用循环遍历搜索范围内的可能最大期望值εr，并计算当前中心的概率值。
49、(3)根据概率值做出判断：如果该概率值不小于βr，则更新最大期望值εr为当前值；否则提前结束搜索。
50、(4)最终返回满足条件的最大期望值εr。
51、(5)若提前结束搜索或则进行路径调整，直至满足约束。
52、作为本发明进一步的改进，步骤s35中，最优配送方案包括：从m个应急物资中心备选址点中确定的k个应急物资中心选址点编号，每个应急物资中心对应配送车队所行驶的路径上途径的需求点数量及编号，配送车队访问受灾需求点的顺序，配送车队运输应急物资量和完成运输需要的时间。
53、其中，前三者通过对迭代出的最优染色体进行解码后获得，后两者则根据迭代出的最优染色体经历的容量约束检查和时间约束检查的检查结果确定。
54、本发明提供的技术方案，具有如下的有益效果：
55、本发明提出了一种将应急物资中心选址与物资配送路径规划进行协同考虑与优化，通过设计改进的遗传算法，有效地解决了选址与路径规划问题的复杂性和不确定性的新思路；并提供了利用遗传算法解决该np-hard问题的完整策略，给出了染色体编码、交叉、变异等操作的详细规则；因而实现了理论上的创新。
56、本发明在构建的协同优化模型的约束条件中考虑了灾害发生程度、物资需求量、道路可靠性等不确定因素，使得选址方案和路径规划更加符合实际需求，既减少了资源浪费，也优化了运输结构，提高了运输效率。并在该协同优化方法综合考虑了地理位置、交通便捷性、灾害易发性等多个因素，通过多目标优化模型，有效平衡了成本、速度、可靠性等关键指标。这种方法不仅保证了应急物资中心的选址合理性，还在确保快速响应的同时降低了总体成本，提高了系统的容错率和应急响应能力。
57、针对重大地质灾害下运输时间无分布规律函数的随机机会约束，难以采用传统的解析法进行求解的问题，本发明先通过机会约束模型找到一个确定性的等价公式，再采用随机模拟与cdf函数结合的方法进行求解。这种为不确定需求的容量机会约束提供确定性的等价公式的策略，还可以为类似问题的求解提供启示。
1.一种利用改进遗传算法实现中心选址及路径协同优化的方法，其用于在一个包含多个应急物资中心和多个需求点的场景中，确定满足多重优化目标的物资选址点，并生成遍历所有需求点的最佳路径，其特征在于，其包括如下步骤：
2.如权利要求1所述的利用改进遗传算法实现中心选址及路径协同优化的方法，其特征在于，步骤s2中，所述应急物资中心选址-路径协同优化模型的决策变量包括：zj、zrab、zri、zrj；其中，zj为表征备选址点是否作为应急物资中心的状态标志；zrj为表征车队r是否以备选址点j为起始点并对其进行服务的状态标志。
3.如权利要求2所述的利用改进遗传算法实现中心选址及路径协同优化的方法，其特征在于，所述应急物资中心选址-路径协同优化模型的目标函数c为：
4.如权利要求3所述的利用改进遗传算法实现中心选址及路径协同优化的方法，其特征在于，所述应急物资中心选址-路径协同优化模型中的约束函数包括：
5.如权利要求1所述的利用改进遗传算法实现中心选址及路径协同优化的方法，其特征在于，步骤s3中，迭代寻优的过程如下：
6.如权利要求5所述的利用改进遗传算法实现中心选址及路径协同优化的方法，其特征在于：步骤s31中，种群变异概率mp的区间为：(0.05，0.1)；种群交叉概率cp的区间为：(0.5，0.8)。
7.如权利要求5所述的利用改进遗传算法实现中心选址及路径协同优化的方法，其特征在于：步骤s33中，调整染色体对应的方案中的路径的过程为：
8.如权利要求5所述的利用改进遗传算法实现中心选址及路径协同优化的方法，其特征在于，在步骤s34中，利用二维搜索获得总需求量的最大期望值，对每个配送车队进行容量约束检查，过程如下
9.如权利要求5所述的利用改进遗传算法实现中心选址及路径协同优化的方法，其特征在于，在步骤s34中，利用二维搜索获得时间的最大期望值，对每个配送车队进行时间约束检查，过程如下：
10.如权利要求5所述的利用改进遗传算法实现中心选址及路径协同优化的方法，其特征在于，步骤s35中，所述最优配送方案包括：从m个应急物资中心备选址点中确定的k个应急物资中心选址点编号，每个应急物资中心对应配送车队所行驶的路径上途径的需求点数量及编号，配送车队访问受灾需求点的顺序，配送车队运输应急物资量和完成运输需要的时间。
