考虑员工满意度的多目标外卖订单配送路径优化研究_高椿林.pdf

河北工业大学学报JOURNAL OF HEBEI UNIVERSITY OF TECHNOLOGY2023 年 2 月February 2023第 52 卷 第 1 期Vol.52 No.1考虑员工满意度的多目标外卖订单配送路径优化研究高椿林1，张维存1，许建2（1.河北工业大学 经济管理学院，天津 300400；2.河北工业大学 人文与法律学院，天津 300400）摘要针对外卖订单配送问题，首先对员工满意度影响因素进行量化分析，并构建了以配送总成本、客户满意度、员工满意度为目标的外卖订单配送路径优化模型;其次提出适用于外卖订单配送的两阶段初始解构造法、基于“HV贡献值”的邻域解评价策略以及新的拆分和修复算子，对自适应大邻域搜索算法进行改进;最后以饿了么外卖平台的实际数据设计仿真实验，与原始自适应大邻域搜索算法求解结果进行对比，验证了模型在提升员工满意度上的实用性和改进算法对外卖订单配送的有效性。关键词外卖订单配送；车辆路径优化；离散多目标问题；自适应大邻域搜索算法中图分类号F274；TP301.6文献标志码AResearch on multi-objective takeout delivery routing optimizationconsidering employee satisfactionGAO Chunlin1,ZHANG Weicun1,XU Jian2（1.School of Economics and Management,Hebei University of Technology,Tianjin 300400,China;2.School of Humanities andLaws,Hebei University of Technology,Tianjin 300400,China）AbstractTo 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 employeesatisfaction 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 wordsdistribution of takeout orders;vehicle routing optimization;discrete multi-objective problem;adaptivelarge neighborhood search algorithm文章编号：1007-2373（2023）01-0086-11DOI：10.14081/ki.hgdxb.2023.01.012收稿日期：2022-05-01第一作者：高椿林（1995），男，硕士研究生。通信作者：张维存（1975），男，副教授，。高椿林，等：考虑员工满意度的多目标外卖订单配送路径优化研究0引言在互联网经济高速发展背景下，外卖市场迎来了广阔的发展空间，外卖订单配送路径优化问题逐渐成为车辆路径问题（Vehicle Routing Problem，VRP）的研究热点之一。在外卖订单配送路径优化问题目标设定上，目前平台和学者大多将平台配送总成本、客户满意度作为外卖订单配送的主要目标。徐倩等1构建了以外卖平台总成本最小为目标的外卖订单配送模型；余海燕等2将平均每单配送距离以及平均每单完成时间最小作为优化目标，建立了实时订单分配与路径优化模型；陈萍等3提出一个基于时间参数的顾客满意度函数，优化目标是顾客订单总的时间满意度最大；范厚明等4构建了最小化超时订单比例、单均配送时间和单均行驶距离为目标的两阶段优化模型；张力娅等5引入外卖平台顾客优先级概念，从顾客满意度和配送成本两个角度出发，建立了多目标取送货模型。但对于配送活动中的另一行为主体外卖骑手，在现有文献中却很少得到关注。近年来外卖骑手数量不断攀升，社会对外卖骑手的关注度的越来越高。外卖骑手员工满意度是从客户满意度的概念引申而来，其不仅可以在一定高椿林，等：考虑员工满意度的多目标外卖订单配送路径优化研究87第 1 期程度上衡量外卖订单配送工作状况，而且直接影响到客户能否获得准时、满意的配送服务。因此构建以平台配送总成本、客户满意度、员工满意度的多目标外卖订单配送路径优化问题模型具有十分重要的价值。在外卖订单配送路径优化问题求解上，由于“先取后送、一单一线、准时送达”等外卖订单配送约束存在，使得外卖订单配送路径优化问题求解难度增大，并且车辆路径问题已被证实为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=RC；河北工业大学学报88第 52 卷S表示骑手位置，取/送单节点集合S=OA；参数：i+：订单i的取单位置，iN；i-：订单i的送单位置，iN；k：骑手（车辆）k的初始/终止位置；vk：骑手（车辆）k行驶速度，kP；K：骑手（车辆）总数；Mk：骑手（车辆）k的装载量，kP；：骑手（车辆）固定成本；1：骑手（车辆）单位距离运输成本；2：早到取单节点的时间惩罚成本；3：晚到送单节点的时间惩罚成本；Di：订单i的配送费，iN；Bi：订单i的平台派单时间，iN；Ei：订单i预计的取单时间，iN；Li：订单i预计的送单时间，iN；dij：节点i,j之间的距离，i,jS；tik：骑手（车辆）k到达节点i的时间，iS,kP；mik：骑手（车辆）k离开节点i时的载重，iS,kP。Tk：骑手（车辆）k的全天工作时长；决策变量：Xijk：当车辆k从节点i行驶到节点j时为1，否则为0，i,jS,kP；Yik：若订单i指派给车辆k，其值为1，否则为0，iN,kP。1.3目标函数1）最小化配送总成本人员运营成本C1，外卖平台支付给外卖骑手参与配送的固定成本C1=kPiOjSXijk。（1）行驶距离成本C2，骑手在为订单提供配送任务时产生的相关费用C2=1kPiSjSXijkdij。（2）时间惩罚成本C3，因未按约定的时间取送单而产生的成本，由取单时间惩罚成本C3a与送单时间惩罚成本C3b之和表示C3a=2()Ei-ti+k0ti+kEiti+kEi，（3）C3b=03()ti-k-LiQti-kLiLiti-kLi+5ti-kLi+5，（4）C3=C3a+C3b。（5）在Ei之后到达取单节点，在Li之前到达送单节点，不产生惩罚成本；在Ei之前到达取单节点，在Li之后5 min内到达送单节点，将会产生一定的惩罚成本；在Li之后5 min后到达送单节点，客户拒绝服务，惩罚成本设为某一最大值Q。2）最大化客户满意度客户满意度主要由外卖骑手到达送单节点时间与时间窗约束的差距决定。在规定时间Li内送单，满意高椿林，等：考虑员工满意度的多目标外卖订单配送路径优化研究89第 1 期度为100%；超时5 min以内，客户满意度逐渐减少，超时5 min后，客户满意