考虑员工满意度的多目标外卖订单配送路径优化研究

高椿林 张维存 许建

摘要 针对外卖订单配送问题，首先对员工满意度影响因素进行量化分析，并构建了以配送总成本、客户满意度、员工满意度为目标的外卖订单配送路径优化模型;其次提出适用于外卖订单配送的两阶段初始解构造法、基于“HV贡献值”的邻域解评价策略以及新的拆分和修复算子，对自适应大邻域搜索算法进行改进;最后以饿了么外卖平台的实际数据设计仿真实验，与原始自适应大邻域搜索算法求解结果进行对比，验证了模型在提升员工满意度上的实用性和改进算法对外卖订单配送的有效性。

关 键 词 外卖订单配送；车辆路径优化；离散多目标问题；自适应大邻域搜索算法

中图分类号 F274；TP301.6      文献标志码 A

Research on multi-objective takeout delivery routing optimization considering employee satisfaction

GAO Chunlin1， ZHANG Weicun1， XU Jian2

（1. School of Economics and Management， Hebei University of Technology， Tianjin 300400， China; 2. School of Humanities and Laws， Hebei University of Technology， Tianjin 300400， China）

Abstract To solve the delivery problem of takeout orders， first， the factors influencing employee satisfaction are quantified， and the delivery route optimization model aiming at the total delivery cost， customer satisfaction as well as employee satisfaction is constructed; secondly， a two-stage initial solution construction method suitable for takeout order distribution， a neighborhood solution evaluation strategy based on "HV contribution " and new split and repair operators are proposed to improve the adaptive large neighborhood search algorithm; finally， a simulation experiment of the actual data design of ELEME platform is used to compare the results with the original adaptive large neighborhood search algorithm， which verifies the practicability of the model in improving employee satisfaction and the effectiveness of the improved algorithm for the distribution of takeout orders.

Key words distribution of takeout orders; vehicle routing optimization; discrete multi-objective problem; adaptive large neighborhood search algorithm

0 引言

在互聯网经济高速发展背景下，外卖市场迎来了广阔的发展空间，外卖订单配送路径优化问题逐渐成为车辆路径问题（Vehicle Routing Problem，VRP）的研究热点之一。

在外卖订单配送路径优化问题目标设定上，目前平台和学者大多将平台配送总成本、客户满意度作为外卖订单配送的主要目标。徐倩等[1]构建了以外卖平台总成本最小为目标的外卖订单配送模型；余海燕等[2]将平均每单配送距离以及平均每单完成时间最小作为优化目标，建立了实时订单分配与路径优化模型；陈萍等[3]提出一个基于时间参数的顾客满意度函数，优化目标是顾客订单总的时间满意度最大；范厚明等[4]构建了最小化超时订单比例、单均配送时间和单均行驶距离为目标的两阶段优化模型；张力娅等[5]引入外卖平台顾客优先级概念，从顾客满意度和配送成本两个角度出发，建立了多目标取送货模型。但对于配送活动中的另一行为主体——外卖骑手，在现有文献中却很少得到关注。近年来外卖骑手数量不断攀升，社会对外卖骑手的关注度的越来越高。外卖骑手员工满意度是从客户满意度的概念引申而来，其不仅可以在一定程度上衡量外卖订单配送工作状况，而且直接影响到客户能否获得准时、满意的配送服务。因此构建以平台配送总成本、客户满意度、员工满意度的多目标外卖订单配送路径优化问题模型具有十分重要的价值。

在外卖订单配送路径优化问题求解上，由于“先取后送、一单一线、准时送达”等外卖订单配送约束存在，使得外卖订单配送路径优化问题求解难度增大，并且车辆路径问题已被证实为NP-hard问题，智能算法是目前普遍使用的求解方式。李桃迎等[6]引入k-means对“商家-客户”进行聚类，类内设计“商家-客户”遗传算法，得到启发式路径优化方案；Ren等[7]采用插入启发式算法构建初始解，引入前向连续交叉和差分突变策略，设计改进了遗传算法；赵向南等[8]设计了可有效求解混合整数规划模型的带有精英策略的非支配排序遗传算法（NSGA-II）；陈希琼等[9]在蚁群算法中加入禁忌搜索表以及贪婪转移准则，从而在迭代过程中进行局部的禁忌搜索以产生更优解。其中，自适应大邻域搜索算法凭借其“搜索空间大、搜索效率高”的特点，在求解VRP问题上取得了良好的效果。例如Xue等[10]设计一个两阶段模型，将订单根据时间和位置分配到子区域后，在子区域内设计了自适应大邻域启发式算法，以减少配送员数量；Pelletier等[11]针对不确定因素背景下的电动车车辆路径问题，设计一种基于大规模邻域搜索的两阶段启发式算法进行求解；南丽君等[12]提出新的删除、修复算子及动态阶段加速策略改进了自适应大邻域搜索算法求解异质车辆路径优化问题；Ropke等[13]提出由多个竞争子启发式算法组成的自适应大邻域搜索算法求解带时间窗的取送货问题。尽管如此，原始算法的邻域解评价机制导致解的进化方向单一，仅适用于单目标问题，无法求解多目标问题。因此本文将依据模型特点，对自适应大邻域搜索算法进行改进，提出一种多目标自适应大邻域搜索算法（Multi-objective Adaptive Large Neighbourhood Search Algorithm，MALNS）。

综上所述，本文的创新点如下：1）面向外卖订单配送问题，对外卖骑手的员工满意度进行分析和量化，构建了以降低配送总成本，提高客户满意度和员工满意度为目标的多目标车辆路径问题模型；2）设计了MALNS，改进了邻域解评价策略以应用于离散多目标问题的求解，提出了适用于外卖订单配送的两阶段初始解构造法，基于问题特性设计了新的拆分和修复算子，以保证非支配解集的多样性和精确性。

1 问题与模型

1.1 问题与假设

问题描述：某区域内有一定数量的外卖骑手，他们处在不同位置，各自的装载量、速度也不相同。客户在外卖平台提交订单，订单有取单节点和送单节点，以一个配送任务对的形式分布在该区域范围内不同位置，平台接到订单后预设了取单节点时间窗及送单节点时间窗。当外卖骑手在平台派单时间[Bi]收到订单配送任务后，根据系统给出的行驶路线，在配送其他订单的过程中，需要先到取单节点并在取单时间[Ei]后取单，随即出发按照规定的路线将该订单在规定的时间[Li]前送到相应的送单节点。平台综合考虑订单和骑手相关信息，将订单配送任务分配给合适的外卖骑手，并规划出最佳行驶路线，实现订单和外卖骑手的最优匹配，使得我们关注的目标（配送总成本、客户满意度、员工满意度）达到最优。

假设条件：1）骑手（车辆）的装载量以外卖份数核算；2）骑手（车辆）无最大行驶里程约束；3）每个订单有且仅有一个骑手提供服务；4）骑手在完成配送后从最后一个配送节点随即返回到骑手出发位置；5）骑手出发位置、取单节点、送单节点的坐标及相对距离已知，订单取、送单节点时间窗的限制已知，骑手（车辆）的位置、装载量、行驶速度固定且已知。

1.2 参数变量

集合：

[N]表示订单集合[N=1，2，…，i]；

[P]表示骑手（车辆）集合[P=1，2，…，k]；

[O]表示骑手（车辆）位置集合[O=1′，2′，…，k′]；

[R]表示取单节點集合[R=1+，2+，…，i+]；

[C]表示送单节点集合[C=1-，2-，…，i-]；

[A]表示取单节点和送单节点集合[A=R∪C]；

[S]表示骑手位置，取/送单节点集合[S=O∪A]；

参数：

[i+]：订单[i]的取单位置，[i∈N]；

[i-]：订单[i]的送单位置，[i∈N]；

[k′]：骑手（车辆）[k]的初始/终止位置；

[vk]：骑手（车辆）[k]行驶速度，[k∈P]；

[K]：骑手（车辆）总数；

[Mk]：骑手（车辆）[k]的装载量，[k∈P]；

[θ]：骑手（车辆）固定成本；

[θ1]：骑手（车辆）单位距离运输成本；

[θ2]：早到取单节点的时间惩罚成本；

[θ3]：晚到送单节点的时间惩罚成本；

[Di]：订单[i]的配送费，[i∈N]；

[Bi]：订单[i]的平台派单时间，[i∈N]；

[Ei]：订单[i]预计的取单时间，[i∈N]；

[Li]：订单[i]预计的送单时间，[i∈N]；

[dij]：节点[i，j]之间的距离，[i，j∈S]；

[tik]：骑手（车辆）[k]到达节点[i]的时间，[i∈S，k∈P]；

[mik]：骑手（车辆）[k]离开节点[i]时的载重，[i∈S，k∈P]。

[Tk]：骑手（车辆）[k]的全天工作时长；

决策变量：

[Xijk]：当车辆[k]从节点[i]行驶到节点[j]时为1，否则为0，[i，j∈S，k∈P]；

[Yik]：若订单[i]指派给车辆[k]，其值为1，否则为0，[i∈N，k∈P]。

1.3 目标函数

1）最小化配送总成本

①人员运营成本[C1]，外卖平台支付给外卖骑手参与配送的固定成本

②行驶距离成本[C2]，骑手在为订单提供配送任务时产生的相关费用

③时间惩罚成本[C3]，因未按约定的时间取送单而产生的成本，由取单时间惩罚成本[C3a]与送单时间惩罚成本[C3b]之和表示

在[Ei]之后到达取单节点，在[Li]之前到达送单节点，不产生惩罚成本；在[Ei]之前到达取单节点，在[Li]之后5 min内到达送单节点，将会产生一定的惩罚成本；在[Li]之后5 min后到达送单节点，客户拒绝服务，惩罚成本设为某一最大值[Q]。

2）最大化客户满意度

客户满意度主要由外卖骑手到达送单节点时间与时间窗约束的差距决定。在规定时间[Li]内送单，满意度为100%；超时5 min以内，客户满意度逐渐减少，超时5 min后，客户满意度为0，如式（6）所示：

总体客户满意度[U]由每个客户满意度的平均值决定，关系式如下：

3）最大化员工满意度

外卖骑手作为谋生型员工[14]，其员工满意度主要取决于生理层次的满意度构成因素，即工资待遇、工作强度。由此，本文刻画了工作时间饱和度[ωt]、工作薪酬满意度[ωs]分别表示外卖骑手的工作强度和工资待遇。

工作时间饱和度[ωt]由骑手配送任务时长在全天工作时长的比率表示，假设某外卖骑手[k]订单[ii∈Nk]的派单时间为[Bi]，送单时间为[Li]，全天工作时长为[Tk]，则工作时间饱和度计算公式如下：

工作薪酬满意度[ωs]由所有配送订单的配送费与外卖骑手驾驶车辆装载量的比率表示，即外卖骑手送单报酬和工作能力的比值。订单的配送费[Di]的计费方式按照取单节点与送单节点直线距离计算，在3 km以内[?]5，超过3 km的[?]2/km。假设某外卖骑手[k]的装载量为[Mk]，其订单[ii∈Nk]的配送费为[Di]，则工作薪酬满意度计算公式如下：

基于公平理论的思想，外卖骑手员工满意度取决于所有骑手工作时间和工作薪酬是否均衡。本文取所有骑手的工作时间饱和度、工作薪酬满意度的离散系数刻画骑手工作时间饱和度和工作薪酬满意度的均衡性。

①骑手工作时间饱和度均衡，由所有外卖骑手的骑手工作时间饱和度的离散系数表示。某外卖骑手[k]的工作时间饱和度为[ωtk]，假设所有外卖骑手的工作时间饱和度均值为[ωt]，则骑手工作时间饱和度均衡的计算公式为：

②骑手工作薪酬满意度均衡，由所有外卖骑手的骑手工作薪酬满意度的离散系数表示。某外卖骑手[k]的工作薪酬满意度为[ωsk]，假设所有外卖骑手的工作薪酬满意度均值为[ωs]，则骑手工作薪酬满意度均衡的计算公式为：

1.4 数学模型

本文外卖订单配送路径优化模型如下：

式（12）～（14）表示配送总成本最小，客户满意度和员工满意度最大；式（15）表示每个订单当且仅当被一个外卖骑手服务一次；式（16）表示一个订单必须被同一个外卖骑手服务；式（17）表示订单取单节点和送单节点的前后顺序；式（18）表示外卖骑手驾驶配送车辆[k]的装载量约束；式（19）表示外卖骑手配送路线的连贯性；式（20）表示骑手只有订单派单后才能为订单服务；式（21）表示每个骑手从初始位置出发，配送任务结束后务必回到出发位置；式（22）表示到达节点的时间推导；式（23）表示各节点车辆载重推导；式（24）表示对于所有的节点[i]有且只有一个外卖骑手访问一次。

2 算法设计

根据上文对考虑员工满意度的多目标外卖订单配送路径优化问题模型的分析，算法设计要点如下。

1）由于本文提出的模型为离散多目标问题模型，MALNS将非支配解集代替原始算法中最优解，改进了邻域解评价策略，引入单个解[HV]贡献值的概念“[IHV]”，计算新解的“[IHV]”与当前非支配解集[D]超体积[HV]的比值，判断新解对非支配解集的改进效果。

2）由于本文提出的模型具有多项约束条件，约束条件的增多导致解空间的不规则的可能增大，因此针对性地提出了新的拆分和修复算子以提高搜索效率，同时为了保证搜索效果，MALNS采用“两阶段初始解构造法”提高初始解质量，保证了非支配解集的精确性和多样性。

2.1 初始解的构造

2.1.1 编码设计

本文研究的是考虑车辆异质性且具有取送顺序的外卖订单配送路径优化问题，关键在于订单分配及取单节点和送单节点访问次序进行优化。为了便于理解和操作，本文采用自然数编码，编码方案为[1′，i11，i12，…，i1v，1′，2′，i21，i22，…，i2u，2′，…，k′，ik1，ik2，…，ikm，k′]，其中[k′]表示骑手[k]的初始/终止位置，[ikm]表示订单的取/送单节点。

2.1.2 初始解的构造

为了保证初始解的质量和多样性，本文将外賣订单配送初始解的构造划分为2个阶段。

1）将订单合理地分配给外卖骑手。针对订单[i]，计算每个外卖骑手[k]从初始位置[k′]出发，先到取单节点[i+]取单，再到送单节点[i-]送单，最后回到终止位置[k′]的配送时间[Tk=dk′i++di+i-+di-k′/vk·Rnd]，从所有外卖骑手[P]中选出配送时间最短的骑手[k]即[minTk]，将订单[i]分配给该骑手。该订单分配方式尽可能多的保证外卖骑手配送的订单在一定的距离范围内，缩短了配送距离，降低了配送总成本。其中，扰动系数[Rnd∈（0.9，1.1）]，可以保证初始解的多样性，使得初始解在解空间中随机分布，以免在搜索中陷入局部最优解。

2）规划取送订单的路径。首先生成只包含外卖骑手[k]初始位置和终止位置的车辆路径[k′，k′]，将该骑手在1）分配到的订单随机生成一个订单序列[Uk]。在满足订单需求及车容量限制条件下，按照订单序列[Uk]中的订单顺序，采用贪婪插入法依序将订单插入到骑手[k]的车辆路径中。直到所有骑手的订单均完成插入，最终生成该初始解的车辆调度方案。针对骑手[k]的车辆路径规划具体步骤如下所示。

步骤1    根据式（1）～（5）计算当前路径成本[F1]，将第一个订单[i]从订单序列[Uk]中剔除。

步骤2     插入取单节点[i+]。将订单[i]的取单节点[i+]按顺序插入骑手[k]路径中的初始位置到终止位置间的未插入过的位置上，根据公式（25）计算路径[k]上取单节点[i+]及后续所有节点的载重[mik]，并判断其中所有取单节点[j+]是否满足车辆装载量。根据公式（26）计算取单节点[i+]及后续所有节点的到达时间[tik]，并判断其中所有送单节点[j-]是否满足配送时间窗。如果2个条件均满足，则转入步骤3，否则进一步判断取单节点[i+]插入位置是否终止位置[k']的紧前位置，如果不是，则重复步骤2，否则，直接转入步骤6。

步骤3    插入送单节点[i-]。将订单[i]的送单节点[i-]按顺序插入路径[k]的取单节点[i+]到终止位置间的未插入过的位置上，根据式（26）计算送单节点[i-]及后续所有节点的到达时间[tik]，并判断其中所有送单节点[j-]是否满足配送时间窗。如果满足，则根据公式（1～5）计算当前路径成本[F1′]，并转入步骤4，否则转入步骤5。

步骤4    计算插入取单节点[i+]和送单节点[i-]的成本差值[Δki=F1′-F1]，记录取单节点[i+]和送单节点[i-]的插入位置及该插入位置下的成本变化[Δki]。

步骤5    判断送单节点[i-]插入位置是否是终止位置的紧前位置，如果不是，则转回步骤3，否则，进一步判断取单节点[i+]插入位置是否是终止位置的紧前位置，如果不是，则转回步骤2，否则，转入步骤6。

步骤6    将订单[i]插入最佳位置。选择记录下的成本变化最小值[Δki]对应的取单节点[i+]和送单节点[i-]的插入位置作为订单[i]在路径中的最佳插入位置，将订单[i]插入到配送路径中。

步骤7    判断订单序列[Uk]是否为空集，如果是，骑手[k]的车辆路径规划完成，否则转回步骤1。

2.2 订单“拆分-修复”策略

2.2.1 订单拆分策略

订单拆分策略即拆分算子，其中包含了4种订单移除操作，每种移除操作的结果都是将[q]笔订单从当前解[S]中移除：

1）随机移除策略：将随机选中的[q]笔订单都从[S]中移除，此策略不考虑订单的特点和订单间的相关性，只为增加邻域解的多样性。

2）相似订单移除策略：根据订单之间的相似度对订单进行移除处理。订单[i]和订单[j]之间的相似度[R（i，j）]最早由Shaw[15]提出，本文[R（i，j）]的计算从时间、距离2个方面来考虑，权重分别用[α，β]表示。[R（i，j）]的数值越小，订单[i]和订单[j]的相似度越高。通过选择相似匹配度高的订单进行移除，便于相似度高的订单交换配送顺序，有可能构造出更高质量的邻域解。

3）移除成本最高的订单：定义订单[i]的成本为[costi，S=fS-f-i（S）]，其中[f-i（S）]表示从当前解[S]中移除订单[i]后的成本。对[S]中各订单按[costi，S]数值按从大到小的顺序构成序列。选择[costi，S]最高的[q]笔订单进行移除，有可能构造出成本更低的邻域解。

4）移除浪费时间最长的订单：外卖骑手无论是提前到达取单节点还是送单节点都是对外卖平台运力的一种浪费。定义订单[i]的浪费时间为[wastei，S=Ei-ti+k+Li-ti-k]。对[S]中各订单按[wastei，S]数值按从大到小的顺序构成序列。选择浪费时间最多的[q]笔订单进行移除，有可能构造出高质量邻域解。

2.2.2 订单修复策略

移除[S]中[q]笔订单之后，然后再将这些订单重新插入到各路径中获得邻域解。订单修复策略即修复算子，其中包含4种插入操作。

1）贪婪插入策略：筛选出符合约束条件的位置，按照贪婪原则选择订单[i]插入到每条路径中成本增量最低的位置上。用[?f（i，k）]表示在每一次插入过程中订单[i]插入路径[k∈K]中所带来的成本增量，如果在路径[k]中无法插入订单[i]，则[?fi，k=∞]。然后，定义[ci=min?f（i，k）]表示将订单[i]插入第[k]条路径中某位置使得路径配送成本最低，而产生的最低成本增量。最后，从未插入订单集合[U]中选出插入成本增量最小的订单[i]，即[min ci]，从[U]中删除并插入对应位置，直到所有订单被插入或没有订单可以被插入后停止。

2）最大后悔值準则插入策略：用变量[xik∈1，2，…，m]表示第[k]低插入成本的一条路径，对贪婪插入中所定义的[?f（i，k）]，表示将订单[i]插入路径[k∈K]中最佳位置（成本最低）所带来的成本增量，当[k

3）均衡工作时间饱和度插入策略：为了达到目标中骑手工作时间饱和度均衡，需要尽可能将订单分配给工作时间不饱和的外卖骑手。从未插入订单集合[U]中选择[di+i-]（起止距离越远，工作时间越长）最大的订单，根据第[k]条路径上的外卖骑手的工作时间饱和度[ωtk]，用[?i，k=ωt′k-ωt]表示在每一次插入过程中订单[i]插入路径[k]后该路线[ωtk]与所有路线均值[ωt]的差值，差值越小，工作时间饱和度越均衡。从所有路线[P]中，选择[?i，k]最小的路径[k]，再根据“贪婪插入策略”在该路线上选择最佳位置进行插入，该过程持续到所有订单被插入后停止。

4）均衡工作薪酬满意度插入策略：为了达到目标中骑手工作薪酬满意度均衡，需要尽可能将订单分配给工作能力不饱和的外卖骑手。与“均衡工作时间饱和度插入策略”相似，为了均衡工作薪酬满意度，从未插入订单集合[U]中选择[Di]最大（配送费越高，工作薪酬越高）的订单，根据第[k]条路径上的外卖骑手的工作薪酬满意度[ωsk]，用[?i，k=ωs′k-ωs]表示在每一次插入过程中订单[i]插入路径[k]后该路线[ωsk]与所有路线均值[ωs]的差值，差值越小，工作薪酬满意度越均衡。从所有路线[P]中，选择[?i，k]最小的路径[k]，再根据“贪婪插入策略”在该路线上选择最佳位置进行插入，该过程持续到所有订单被插入后停止。

2.3 邻域解评价策略

在多目标优化问题中，最后求解得到的往往是一组非支配解集，由于非支配解之间没有明显的优劣关系，所以原始自适应大邻域搜索算法在求解多目标优化问题时，无法评选出最优解，也无法比较“当前解”与“新解”的质量。因此本文将非支配解集[D]代替最优解，并在非支配解集的超体积（[hypervolume，HV]）的理论基础上，引入单个解[HV]贡献值的概念“[IHV]”设计邻域解评价策略，计算“新解”的单个解[HV]贡献值，并计算其与当前非支配解集[D]超体积[HV]的比值，判断“新解”对非支配解集的改进效果，用来动态选择较优的订单“拆分-修复”策略组合生成邻域进行搜索。

非支配解集的超体积[HV]是在多目标优化问题中，评价解性能的重要指标之一，它度量了非支配解集[D]与参考点围成的目标空间中区域的尺寸大小。[HV]值越大，说明算法得到的非支配解集的覆盖率越好，即算法性能越好。超体积[HV]计算公式如下：

式中：[xref]为参考点；[xj]是非支配解集[D]中的非支配解。

以双目标优化问题为例，该问题求解2个最小化目标函数，假设[fub1]和[fub2]分别表示单个目标问题的上界，则参考点设定为[xref=fub1，fub2]。如图1所示，2个非支配解集[D1]、[D2]和参考点围成的区域分别表示[HVD1]和[HVD2]，由图可知[HVD1>HVD2]，因此解集[D1]中的非支配解优于[D2]中的非支配解。

[HV]越大，表明非支配解集的綜合性越好，所以单个解对非支配解集的超体积[HV]贡献值[IHV]越大，那么该解的性能就越好，对算法搜索引导效果越好。单个解[HV]贡献值[IHV]计算公式如下：

如图2所示，假设[fub1]和[fub2]分别表示单个目标问题的上界，则参考点设定为[xref=fub1，fub2]。通过在非支配解集里加入一个解的[HV]变化，刻画了单个解[HV]贡献值“[IHV]”的概念。假设非支配解集[D=a，b，c，d，e]，单个解[a]的[HV]贡献值[IHV]可以用图片中的点阵阴影部分表示。

2.4 算法框架

为了适应该模型的求解，本文对自适应大邻域搜索算法流程进行了改进，改进后算法MALNS求解具体流程为：

1）根据初始解构造方案生成初始解集（详见2.1），根据解的非支配关系得到非支配解集，记为[D*]，计算[D*]的[HV]值。

2）计算其中每个解的[HV]贡献值[IHV]（详见2.3），选择[IHV]最大的解进行标记，并将其设定为当前解[S]，如果该解曾被标记，则选贡献率次大的解，依此类推。

3）根据算子权重随机选择拆分算子、修复算子（详见2.2）对当前解[S]进行拆分并修复获得新解[S′]，将[S′]与[D*]合并，通过非支配判断更新非支配解集[D*]，转入步骤4）。

4）如果[S′]在与[D*]合并中被支配，直接转步骤7）。否则更新非支配解集[D*]的[HV]，并令[S=S′]，计算[S′]的[IHVS′]与非支配解集[D*]的[HV]值比率Δ%。如果非支配解集改进明显（Δ%＞0.01），则转步骤5），否则转步骤6）。

5）令模拟退火温度[T]=[Tinit]，对所选择的拆分和修复算子增加相对应的分数[δ1]，转步骤8）。

6）对所选择的拆分和修复算子增加相对应的分数[δ2]，转步骤8）。

7）利用模拟退火温度[T]以式（30）计算相应的概率接受新解，如果接受，令[S=S′]，对所选择的拆分和修复算子增加相对应的分数[δ3]，转步骤8）。

8）将模拟退火的温度[T=T*c]，如果温度[T

9）利用式（31）判断是否达到更新算子权重的条件，如果达到则依据算子得分更新权重，将算子得分重置为0。

10）判断是否达到最大迭代次数[N*]，若达到则转到步骤11），否则转到步骤3）继续搜索。

11）判断[D*]中是否存在未被标记的解，存在则转到步骤2），否则解除所有标记，输出非支配解集[D*]，算法停止。

本文依据模拟退火算法的判断准则，将经过“拆分-修复”得到的邻域解[S′]与当前解[S]进行比较，设定解[S′]的接受概率如下：

算子权重的更新取决于算子的一段迭代次数所取得的分数。根据当前算子权重，算法在拆分、修复时会通过轮盘赌方法，依照概率选择算子进行操作。在算法进行搜索初期设定拆分算子、修复算子选择权重均为0.25。每当达到一定的迭代次数ψ，则表示算法进入一个新的阶段，根据算子上阶段表现情况，以及算子综合表现情况对算子进行重新评价并给予新的权重，权重更新公式如下：

式中：[πi，j+1]代表在[j+1]阶段算子[i]的权重；[πi，j]代表算子[i]在[j]阶段获得的评分；[ai，j]表示算子[i]在[j]阶段的使用次数；[πi，j]表示算子[i]在[j]阶段的权重。

3 实验分析

3.1 参数设定

为了确保算法求解的稳定性，首先对算法进行试运行以调整算法参数，本文对迭代次数[N*]和移除订单数量上限[q] 2个主要参数进行了求解实验。经多次实验分析，算法在[N*=900]时，算法搜索能力接近最大极限；移除订单数量上限[q]为[10]，既能保证算法搜索能力又能尽可能减小算法运行时间。

另外，算法采用模拟退火判断准则接受部分解，以Ropke[16]中各参数作为参考，初始温度[Tinit]的值基于初始可行解[s]的单个解[HV]值进行设置，将其设置为[Tinit=ω·HVS/ln2]，即如果解[S′]的单个解[HV]值比当前解小ω%，则该解会以50%的概率予以接受，冷却率[c=0.998 7]。对拆分和修复算子增加的分数[δ1]、[δ2]、[δ3]的取值分别为33、13、9。

3.2 仿真实验

本文收集饿了么外卖平台外卖订单数据模拟外卖订单配送情形设计10个外卖骑手配送100个订单的仿真实例，在win8.1系统上，利用python3.8编译MALNS进行求解。为了直观的分析非支配解集的相对位置，将非支配解集的目标函数值进行过归一化处理，非支配解的分布如图3所示。

由图3分析可得，非支配解在目标空间的分布基本满足非支配解集的多样性的要求，但是在均匀性表现一般，分析原因可能是因为在外卖订单配送问题是一个离散问题，解空间的不规则导致目标函数空间相互割裂。在该仿真测例上可能是订单数量有限，无法保证均匀的分配给每个员工，进而导致员工满意度无法进一步提高。

为验证本文设计改进的自适应大邻域搜索算法在外卖订单配送优化问题求解精确性和多样性的具体表现，本文将该算法与原始自适应大邻域搜索算法的求解结果进行比较，在相同运算条件下，根据非支配解的拥挤度进行排序，分别选取前10个非支配解，求解结果如表1所示。

首先从2个非支配解集的超体积（[HV]）指标上来看，改进后算法MALNS非支配解集[HV]值为0.352，改进前算法非支配解集[HV]值为0.275，[HV]值提升了0.077，说明MALNS求得的解集更接近真实的非支配解集最优边界。从表中各目标函数均值可以看出，MALNS所得的非支配解集各目标函数值均优于原始算法，分别提高了3.7%，4.4%，3.0%。从单个目标函数值来看，MALNS所得各目标函数最优值仍均优于原始算法，分别提高了0.7%，25.5%，0.6%。由此可见，MALNS不仅提高非支配解集的目标函数值，而且还保证了非支配解集的空间分布质量，兼顾了非支配解集的收敛性和多样性。

在MALNS得到的非支配解集中，解1配送總成本最低，解8客户满意度最高，解9员工满意度最高（已加粗标出）。以解1的各目标函数值举例分析，此解配送总成本3 045.755元，虽然在非支配解集中配送总成本最低，但是客户满意度为86.8%，员工满意度为1.318，相对其他非支配解而言员工满意度相对较低，进一步分析该情况下外卖骑手工作时间饱和度均衡为0.903、工作薪酬满意度均衡为0.415，可见由于外卖骑手工作时间分配存在较大差异，导致外卖骑手员工满意度低，如果员工因此产生不满情绪，建议外卖平台选择其他外卖订单配送方案以提高员工满意度。

通过对仿真实验结果分析得出，本文算法MALNS较原始算法相比求解能力有一定幅度的提升，求解该问题模型可以保证解集的精确性、多样性，能够为外卖平台提供决策需求。

4 结语

本文主要研究了考虑员工满意度的外卖订单配送问题，将员工满意度进行量化融入多目标外卖订单配送路径优化模型，并改进了自适应大领域搜索算法对问题模型进行求解。研究表明：

1）从员工满意度的角度出发，将员工满意度作为模型的目标之一，结合最小化配送总成本、最大化客户满意度，构建了考虑员工满意度的多目标外卖订单配送路径优化模型，有利于平台协调成本、客户、员工三者之间的平衡。

2）本文设计的两阶段初始解构造法，可以保证初始解的质量和多样性；提出的基于非支配解集超体积的“[HV]贡献值”邻域解评价策略以及新的拆分和修复算子，可以改进自适应大邻域搜索算法以适用于求解多目标路径优化问题，并生成高质量的非支配解集。

参考文献：

[1]    徐倩，熊俊，杨珍花，等. 基于自适应大邻域搜索算法的外卖配送车辆路径优化[J]. 工业工程与管理，2021，26（3）：115-122.

[2]    余海燕，蒋仁莲. 基于众包平台的外卖实时配送订单分配与路径优化研究[J]. 工业工程与管理，2022，27（2）：146-152.

[3]    陈萍，李航. 基于时间满意度的O2O外卖配送路径优化问题研究[J]. 中国管理科学，2016，24（S1）：170-176.

[4]    范厚明，咸富山，王怀奇. 动态需求下考虑订单聚类的外卖配送路径优化[J]. 系统仿真学报，2022. DOI：10. 16182/j. issn1004731x. joss. 21-0965.

[5]    张力娅，张锦，肖斌. 考虑顾客优先级的多目标O2O外卖即时配送路径优化研究[J]. 工业工程与管理，2021，26（2）：196-204

[6]    李桃迎，吕晓宁，李峰，等. 考虑动态需求的外卖配送路径优化模型及算法[J]. 控制与决策，2019，34（2）：406-413.

[7]    TENG R，Xu H B，JIN K N，et al. Optimisation of takeaway delivery routes considering the mutual satisfactions of merchants and customers[J]. Computers & Industrial Engineering，2021，162：107728.

[8]    赵向南，邢磊，靳志宏. 考虑不确定行驶时间的双目标外卖配送路径优化[J]. 大连海事大学学报，2019，45（4）：65-72.

[9]    陈希琼，胡大伟，杨倩倩，等. 多目标同时取送货车辆路径问题的改进蚁群算法[J]. 控制理论与应用，2018，35（9）：1347-1356.

[10]  XUE G Q，WANG Z，WANG G. Optimization of rider scheduling for a food delivery service in O2O business[J]. Journal of Advanced Transportation，2021：5515909.

[11]  PELLETIER S，JABALI O，LAPORTE G，et al. The electric vehicle routing problem with energy consumption uncertainty[J]. Transportation Research Part B：Methodological，2019，126：225-255.

[12]  南丽君，陈彦如，张宗成. 改进的自适应大规模邻域搜索算法求解动态需求的混合车辆路径问题[J]. 计算机应用研究，2021，38（10）：2926-2934.

[13]  ROPKE S，PISINGER D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[J]. Transportation Science，2006，40（4）：455-472.

[14]  孙林辉，黄放，袁晓芳，等. W电子商务公司物流员工工作满意度测评研究[J]. 人类工效学，2015，21（4）：30-35，46.

[15]  SHAW P. Using constraint programming and local search methods to solve vehicle routing problems[C]// Principles and Practice of Constraint Programming — CP98. Berlin：Springer，1998：417-431.

[16]  ROPKE S，CORDEAU J F. Branch and cut and price for the pickup and delivery problem with time windows[J]. Transportation Science，2009，43（3）：267-286.