本发明属于路径优化方法，具体涉及基于多模态多目标优化算法的外卖配送路径优化方法。
背景技术：
1、随着外卖行业的快速发展，外卖配送效率的提高对于保证服务质量至关重要。目前外卖配送过程中常面临客户点分布分散、订单量波动大等问题，给配送路径的优化提出了挑战。传统的配送路径优化方法多集中于单一目标如最小化总行驶距离，但现实中的配送决策往往需要权衡多个目标，如快速配送和能耗效率。多模态多目标优化算法能够在不确定性条件下为配送路径选择提供更好的决策支持。例如可以综合考虑配送时间预测、交通流量信息、订单分析等多模式数据。多目标优化理论也为以平衡的方式满足速度、成本等多个优化目标提供了框架。
技术实现思路
1、本发明的目的在于提供基于多模态多目标优化算法的外卖配送路径优化方法，解决了现有外卖配送路径优化问题求解多样性差，可找出更多的配送候选路径。
2、本发明所采用的技术方案是：基于多模态多目标优化算法的外卖配送路径优化方法，包括以下步骤：
3、步骤1、构建目标函数，以最小化总行驶距离、最小化配送费用和最小化配送时间作为优化目标；
4、步骤2、初始化种群，种群中的每个个体对应一个外卖配送路径优化问题的解决方法，设置邻域更新参数及小生境参数，初始化个体最优存档，将初始种群存入存档；
5、步骤3、采用小生境技术为每个种群个体生成多个候选邻域；
6、步骤4、使用候选邻域评价函数对个体候选邻域进行评估并从中选择演化邻域；
7、步骤5、个体在演化邻域中使用基于邻域的粒子群优化算法进行优化并产生子代；
8、步骤6、通过环境选择保留优质解；
9、步骤7、更新个体最优存档；
10、步骤8、对当前种群演化次数进行判断，若未达到最大迭代次数，则使用邻域更新参数对当前迭代次数进行判断，若满足条件则跳转至步骤3，反之则跳转至步骤5；若达到最大迭代次数，则输出当前种群作为最终解即最优配送路径。
11、本发明的特点还在于，
12、步骤1中构建的目标函数为：
13、
14、
15、
16、其中，n表示总的地点数量，dij是地点i和地点j之间的距离；cij是从地点i到地点j的费用；tij是从地点i到地点j的预计时间；xij表示车辆从地点i是否行驶到地点j，若行驶到地点j则为1，否则为0；
17、目标函数的约束条件为：
18、
19、
20、
21、
22、其中，公式(4)表示每个顾客地址只能被配送一次；公式(5)为二进制变量约束，对决策变量进行限制，使其只能取0或1的值；公式(6)为容量约束，以确保载货量足够；其中qj是地点j的需求量，即订购的外卖数量；n表示所有顾客地址的集合，q表示最大载货量，即最多可以携带的外卖数量；公式(7)为时间约束，是为了确保外卖配送到达每个顾客地址j的时间不晚于规定的最晚时间窗口lj，其中ei表示到达地点i的时间，tij表示从地点i到地点j的预计行驶时间，lj表示顾客地址j的最晚时间窗口，即必须在lj时间之前到达，m是常数。
23、步骤3具体为：在种群中分别根据基于随机的邻域生成方式、基于拓扑结构的邻域生成方式和最近邻居的邻域生成方式为每个种群个体生成多个候选邻域；其中，基于随机的邻域生成方式为：随机选取若干个个体形式邻域的方式；基于拓扑结构的邻域生成方式为：将个体进行编号并依据编号将个体进行连接，对于第i个个体，其邻域范围由第i-1个个体与第i+1个个体及其本身组成，对于第1个个体，其邻域范围由第2个个体和最后一个个体组成，对于最后一个个体，其邻域范围由其前一个个体和第1个个体组成；最近邻居的邻域生成方式为：个体与其欧式距离最近的若干个体形成邻域的方式。
24、步骤4具体为：通过候选邻域评价函数对个体所处的不同邻域进行评估得到评估分数，选择评估分数最大的个体候选邻域作为个体的演化邻域，候选邻域评价函数nef(x)表示为：
25、nef(x)＝(1-ω)nrm(x)+ωem(x) (10)
26、式(10)中，x为目标个体；ω为度量权重，如式(11)所示；nrm(x)为邻域范围度量，如式(8)所示；em(x)为熵度量，如式(9)所示：
27、
28、式(11)中，gen和maxgen分别表示当前迭代计数和最大迭代数；
29、
30、式(8)中，x表示目标点，xi表示邻域内的第i个点，dist(x，xi)表示从x到xi的距离，n表示邻域内的点数；
31、
32、式(9)中，x为目标点，xi表示目标点x邻域内的其他点，n表示邻域内点的个数，p(xi)表示点xi出现的概率。
33、步骤5中的粒子群优化算法计算公式如下：
34、vi(t+1)＝wvi(t)+c1r1(xpbest-xi(t))+c2r2(xnbest-xi(t)) (12)
35、xi(t+1)＝vi(t+1)+xi(t) (13)
36、其中，vi(t)表示第t代中第i个个体的速度；xi(t)表示第t代中第i个个体的位置；w表示惯性权重；c1和c2表示代表个体经验和社会经验的权重；r1和r2表示随机数，取值范围为小于1的正数；xpbest表示第i个粒子的个体最佳位置；xnbest表示粒子的局部最佳位置。
37、步骤6具体包括以下步骤：
38、步骤6.1、将种群和后代种群合并，对于合并后种群中的个体，计算个体的邻域优势率ndr和决策目标空间拥挤距离docd：
39、
40、式(14)中，ndri表示第i个个体的邻域收敛率，neighbornumi表示第i个个体的邻域个数，n表示第i个个体的邻域内由第i个解主导的解的个数；
41、
42、式(15)中，表示个体i在目标函数j上的值，其中fj，max和fj，min分别表示群体内目标函数j的最大值和最小值；表示个体i在决策空间中的值，xj，max和xj，min分别表示总体决策空间中j维上的最大值和最小值；
43、步骤6.2、对于合并后种群选取ndr大于0.5的个体作为优质个体，直到达到最大种群数量；若ndr大于0.5的个体数量大于最大种群数量，则按照docd对于满足条件的个体从大到小进行排序，选择docd大的个体作为优质个体；若ndr大于0.5的个体数量小于最大种群数量，则按照docd对剩余个体从大到小进行排序，选择docd大的个体，直到满足最大族群个数。
44、步骤7具体为：首先为每个个体创建一个存档来记录其历史最佳位置，排名最高的个体被设置为个体最优位置，用于粒子群算法中的速度更新，每次产生新的子代后，将产生的子代个体存储到存档；然后，通过特殊非支配排序计算出的存档中个体的排名；随后，检查存档中存储的个体数量，如果存档中个体的数量超过预定义的最大存储数量，则从存档的末尾开始依次消除粒子，直到存档中个体的数量与最大存储数量匹配为止。
45、本发明的有益效果是：本发明的基于多模态多目标优化算法的外卖配送路径优化方法，实现了配送效率与成本的综合优化，适应动态变化的外卖配送需求，可更高效地规划配送路线，有效提升配送企业的服务能力。
1.基于多模态多目标优化算法的外卖配送路径优化方法，其特征在于，包括以下步骤：步骤1、构建目标函数，以最小化总行驶距离、最小化配送费用和最小化配送时间作为优化目标；步骤2、初始化种群，种群中的每个个体对应一个外卖配送路径优化问题的解决方法，设置邻域更新参数及小生境参数，初始化个体最优存档，将初始种群存入存档；步骤3、采用小生境技术为每个种群个体生成多个候选邻域；步骤4、使用候选邻域评价函数对个体候选邻域进行评估并从中选择演化邻域；步骤5、个体在演化邻域中使用基于邻域的粒子群优化算法进行优化并产生子代；步骤6、通过环境选择保留优质解；步骤7、更新个体最优存档；步骤8、判断当前种群演化次数达到最大迭代次数后输出当前种群作为最终解，即最优配送路径。
2.如权利要求1所述的基于多模态多目标优化算法的外卖配送路径优化方法，其特征在于，所述步骤1中构建的目标函数为：
3.如权利要求1所述的基于多模态多目标优化算法的外卖配送路径优化方法，其特征在于，所述步骤3具体为：在种群中分别根据基于随机的邻域生成方式、基于拓扑结构的邻域生成方式和最近邻居的邻域生成方式为每个种群个体生成多个候选邻域；其中，基于随机的邻域生成方式为：随机选取若干个个体形式邻域的方式；基于拓扑结构的邻域生成方式为：将个体进行编号并依据编号将个体进行连接，对于第i个个体，其邻域范围由第i-1个个体与第i+1个个体及其本身组成，对于第1个个体，其邻域范围由第2个个体和最后一个个体组成，对于最后一个个体，其邻域范围由其前一个个体和第1个个体组成；最近邻居的邻域生成方式为：个体与其欧式距离最近的若干个体形成邻域的方式。
4.如权利要求1所述的基于多模态多目标优化算法的外卖配送路径优化方法，其特征在于，所述步骤4具体为：通过候选邻域评价函数对个体所处的不同邻域进行评估得到评估分数，选择评估分数最大的个体候选邻域作为个体的演化邻域，候选邻域评价函数nef(x)表示为：
5.如权利要求1所述的基于多模态多目标优化算法的外卖配送路径优化方法，其特征在于，所述步骤5中的粒子群优化算法计算公式如下：
6.如权利要求1所述的基于多模态多目标优化算法的外卖配送路径优化方法，其特征在于，所述步骤6具体包括以下步骤：
7.如权利要求1所述的基于多模态多目标优化算法的外卖配送路径优化方法，其特征在于，所述步骤7具体为：首先为每个个体创建一个存档来记录其历史最佳位置，排名最高的个体被设置为个体最优位置，用于粒子群算法中的速度更新，每次产生新的子代后，将产生的子代个体存储到存档；然后，通过特殊非支配排序计算出的存档中个体的排名；随后，检查存档中存储的个体数量，如果存档中个体的数量超过预定义的最大存储数量，则从存档的末尾开始依次消除粒子，直到存档中个体的数量与最大存储数量匹配为止。
