【摘要】文中主要研究外卖配送路径优化问题，针对外卖配送过程中存在的成本高、配送延误等一系列问题，考虑配送车辆容量、配送里程和时间窗等约束条件，将顾客满意度最大化、员工满意度最大化以及配送成本最小化作为目标，建立了配送过程中车辆路径问题(VRP)模型。经过算例验证，发现通过遗传算法找到的路径能够有效地降低成本，提高顾客和员工的满意度，使配送时间更有保障，验证了算法的可行性和有效性。

　　【关键词】外卖；配送路径优化；遗传算法；员工满意度

　　目前，国内外有关外卖配送的研究多停留在宏观层面，很少涉及到现实场景中的配送路径规划问题。随着外卖平台的迅速扩张，其配送过程中出现了延迟配送等大量问题，不仅影响了消费者对配送服务的满意程度，还制约了配送服务的进一步发展。所以，从物流配送的角度来看，在降低物流配送费用的前提下，如何提高物流配送效率，并制定出有利于物流配送长期发展的策略，是目前物流配送领域亟待解决的问题。目前，相关研究主要集中在外卖行业的空间分布特征[1]、食品安全[2]、外卖服务的商业模式[3]、商家和顾客满意度[4]、顾客时间满意度[5]、时间惩罚成本[6]、顾客满意度和配送成本[7]等方面。外卖配送是一类典型的车辆路径问题，但由于其订单中同时包含“取”和“送”两个动作，并有严格的到达顺序和高时效要求，导致其从生成到完成，通常需要45分钟。因此，外卖配送路径优化问题可归结为带有时间窗口的即时取送货车辆路径问题。

　　车辆路径问题(vehicle routing problem,VRP)最早于1959年由Dantzig和Ramser首次提出[8]。余海燕等[5]以线上到线下(O2O)外卖服务为背景，以顾客总满意度随时间的最大化为目标，基于改进的遗传算法找到了一个满意的解决方案。吴腾宇等[9]在外卖O2O服务的背景下，提出了一个带提货和送货的在线旅行商问题，并进一步设计了TAIB算法来解决该问题。黄心等[10]应用蚁群优化(ACO)算法来规划配送路线，以最小化外卖分配的总时间。但是对外卖配送过程进行研究时，却忽略了其中重要的主体—外卖员，外卖骑手的员工满意度是从顾客满意度的概念引申而来的，它不仅能够在一定程度上对外卖订单配送工作状况进行度量，还对顾客能否获得准时、满意的配送服务产生直接影响。

　　本文针对某外卖平台的现状，以石家庄市某区域真实路网为例，分析单配送中心多配送车辆的外卖配送路径问题，并建立以顾客满意度最高、员工满意度最高、配送总成本最低为目标条件的车辆路径问题模型，最后选择研究较为成熟的遗传算法进行求解，以期达到缩短外卖配送时间，提高配送效率，给予顾客更好体验的目的。

　　1问题描述与模型构建

　　1.1外卖配送路径问题描述

　　本文以石家庄市某区域的外卖配送为例，该区域存在一定数量的外卖骑手，在外卖配送过程中，外卖骑手从配送中心出发。顾客在外卖平台上提交订单，商家接收订单，开始制作餐品。配送服务遵循“先取后送”原则，配送食品不得超出最大载重，若配送员在配送过程中超时，将受到相应的处罚。因此，外卖平台应优化配送路径，尽可能让外卖骑手在时间窗内到达取送餐节点。针对该问题做如下假设。

　　假设１：顾客的坐标点已知，且顾客的时间窗已知。

　　假设２：所有的配送车辆都是电瓶车，并且具有３０ｋｍ／ｈ的行驶速度，在不考虑道路交通堵塞和天气异常的情况下，行驶过程中不会发生扰乱配送的不可控因素。

　　假设３：骑手首先去往商家节点取餐，再往顾客节点送餐，完成配送任务后不需要返回初始点。

　　假设４：根据顾客对商品的不同需求，可以采用一辆电瓶车进行配送，也就是说同一电瓶车进行混合运输。

　　假设５：外卖送达后，等待顾客取餐的时间不计。

　　假设６：每一个客户点仅可被一辆电瓶车服务，而且客户需要的外卖数量是有限的。

　　假设７：一辆电瓶车可同时服务于多名顾客。

　　１．２符号说明

　　１．３模型构建

　　１．３．１计算顾客满意度

　　顾客满意度受多种因素影响，本文将配送到顾客手中时的准时性作为顾客满意度的标准；式（１）中，Ｍｉ为顾客ｉ的满意度，ｔｉ为外卖配送车辆到达顾客ｉ的时刻。如果骑手在顾客所希望的时间窗口［ｅｉ，ｌｉ］内到达，则顾客的满意度为１；反之，随着等待时间的延长，顾客的满意度将会逐渐降低。如果骑手超过顾客允许的最长时间到达顾客节点，则顾客满意度等于０。基于软时间窗的顾客满意度函数表达式如下：

　　１．３．２计算员工满意度

　　经调查，外卖骑手员工满意度主要取决于工资待遇和工作强度，工作待遇取决于工作薪酬满意度ｇｓ，工作强度取决于工作时间饱和度ｇｔ。工作薪酬满意度ｇｓ由所有配送订单的配送费与外卖骑手驾驶电动车的装载量的比率表示。假设某外卖骑手ｋ送取订单（ｄ∈Ｄ）的配送费为Ｈｉ，装载量为Ｑｋ，则工作薪酬满意度计算公式如下：

　　工作时间饱和度ｇｔ由骑手配送任务时长在全天工作时长的比率表示。假设某外卖骑手ｋ订单ｄ（ｄ∈Ｄ）的送单时间为Ｗｄ，派单时间为Ｐｄ，一天工作时长为Ｔｋ，则工作时间饱和度计算公式如下：

　　１．３．３计算总成本

　　①骑手的骑行成本。

　　本文提出的ＶＲＰＰＤＴＷ问题所涉及的骑行者的骑行成本被认为是可变成本，主要包括电动自行车的用电量成本和电动自行车充电服务费。在单位运输成本固定的条件下，骑行成本与骑行里程成正比。因此，根据该领域的相关研究成果，考虑车辆在骑行过程中产生的成本，构建骑手骑行成本函数如下：

　　②电动车的启动成本。

　　从配送中心取外卖的电动车启动需要一定的固定成本，通常包括骑手的工资和电动车的维护成本和折旧费用。根据所提问题建立电动车启动成本公式，如式（５）所示。

　　③顾客的惩罚成本。

　　本文采用了分阶段惩罚函数来刻画惩罚成本。ｔｉ为外卖配送车辆到达顾客ｉ的时刻，当ｔｉ≤Ｔｉ时，无惩罚成本；当骑手超过预期送达时间到达顾客ｉ时，顾客的满意度会下降，因此出现了惩罚成本，ｃ１为此阶段的单位时间惩罚成本；设定一个最迟送达时间Ｔ０，Ｔ０＞Ｔｉ，当到达时间超过最迟送达时间Ｔ０，顾客满意度会急剧下降，惩罚成本急剧增加，ｃ２为此阶段的单位时间惩罚成本，ｃ２＞ｃ１＞０。外卖送达时间ｔｉ与惩罚成本Ｐｉ关系式如（６）所示。

　　式(7)表示配送总成本最小的目标函数；式(8)表示顾客满意度最高的目标函数；式(9)表示员工满意度最高的目标函数；式(10)和式(11)共同表示每笔订单仅被一辆配送车辆服务一次；式(12)表示每个外卖消费者只能被一辆配送电动车送餐；式(13)和式(14)确保每辆车从配送中心出发，并最终返回到配送中心；式(15)表示骑手不能停留在客户端节点；式(16)表示调度骑手总数不超过配送中心可用骑手总数；式(17)表示配送车辆携带的外卖总量不超过配送车辆的最大装载量Q;式(18)表示配送车辆k的取送餐总量相等；式(19)表示车辆最大行驶里程约束；式(20)表示决策变量，当xijk为1时，表示骑手k从节点i行驶到节点j,否则为0。

　　2遗传算法设计

　　在求解组合优化问题时，遗传算法具有很好的应用前景。简单来说，遗传算法就是通过搜索最优解，淘汰适应度低的解，即类似于生物自然进化过程。与传统算法相比，遗传算法拥有更高的计算效率、更实用的算法技术，近年来发展迅速，在很多领域都有非常广泛的应用。本文针对石家庄市某区域的外卖配送路径问题设计的遗传算法流程包括染色体编码、种群初始化、构建适应度函数、遗传操作（选择操作、交叉操作、变异操作）、终止条件设计等环节。

　　2.1染色体编码

　　将C个顾客点转化成以1到10的自然数，将它们排列组合形成染色体，数字“0”代表配送中心，在染色体的多个位置点随机插入，例如染色体4,7,8,2,0,3,2,9,8,0,1,6,10,表　　示：车辆1的配送路线为0-4-7-8-2-0,车辆2的配送路线为0-3-2-9-8-0,车辆3的配送路线为0-1-6-10-0。

　　2.2种群初始化

　　种群初始化是形成初始的配送方案。每辆车都按照该车服务的次序进行连接，组成了一个整体路径的子分支，然后，把所有的子分支连接在一起，组成了一条完整的染色体，它代表了所有的客户被分配到了一条路径中，从而组成了初始的配送方案。

　　2.3构建适应度函数

　　本文的适应度函数是最小成本目标函数的倒数。即fi=1/Zi,其中，fi为适应度值，Zi代表总成本。

　　2.4遗传操作

　　2.5终止条件设计

　　重复以上步骤，直到满足最大迭代次数，算法终止，输出所有迭代过程中适应度最好的解，作为该问题的一个较优解。

　　3算例与结果分析

　　3.1算例描述

　　为了验证上述算法和模型的有效性及可行性，本文选取石家庄市某区域的一个配送中心和25位顾客节点在11∶00-13∶00的外卖配送数据，通过实地调研和百度地图获得实际经纬度，将其标准化，得到坐标位置，顾客位置的坐标信息如表3所示。利用MATLAB软件进行遗传算法的实现。

　　3.2参数设定

　　在仿真实验中，设置最大装载量为20份外卖，配送速度为30km/h,单位距离配送成本为1元/km,最远行驶距离设定为100km,单位超出时间窗(15min以内）惩罚成本c1为0.5元/min、(15min以外）c2为1元/min,单位距离运输成本a为0.5元/km,电动车的单位启动成本b为0.8元/km,设置遗传算法最大迭代次数=50,种群规模=100,被选择概率=0.9,变异概率Pm=0.05,交叉概率Pc=0.9。

　　3.3实验结论

　　本文中采用遗传算法求解得到的路径解如表5所示，得到的结果是：优化后总成本为461.41元，与优化之前的总成本851.85元相比，减少了390.44元，即配送总成本减少了45.83%;优化后路径总长度为136.6km,与优化前的172.3km相比，减少了35.7km,即配送路径总距离减少了20.7%。外卖配送员由优化前的5名变为优化后的4名，减少了1名，从这方面看，优化后不仅减少了配送总距离、配送成本，还节约了人力成本，提高了顾客和员工的满意度。由此可见，基于遗传算法建立的数学模型科学可行。

　　4结论

　　在“互联网＋”的浪潮下，“互联网＋餐饮”的外卖行业蓬勃发展，而外卖配送是直接关系到外卖质量和品质的重要一环，选取恰当的配送路径，可以加快配送速度，缩短配送时间，提高服务质量，增强顾客的满意度，降低成本。本文就石家庄市某区域的外卖配送路径优化为例，建立了以顾客满意度最高、员工满意度最高以及配送总成本最低为目标的外卖配送路径优化数学模型，并用遗传算法进行求解，解决了外卖配送路径规划不合理的问题。但在外卖的实际配送过程中，还会受到天气、路况、交通等因素的影响，为更贴近实际生活仍需进一步研究。

　　［参考文献］

　　[1]Richard P.Hornstra,Allyon Silva,Kees jan Roodbergen,et al.The vehicle routing problem with simultanerous pickup and delivery and handing costs[J].Computers and Operations Research,2020,115.

　　[2]Xiong Jie,et al.Optimal design of community shuttles with an adaptive-operator-selection-based genetic algorithm[J].

　　Transportation Research Part C:Emerging Technologies,2021,126.

　　[3]Wei Li et al.An ant colony optimization algorithm with adaptive greedy strategy to optimize path problems[J].Journal of Ambient Intelligence and Humanized Computing,2021.

　　[4]Teng Ren,et al.Optimisation of takeaway delivery routes considering the mutual satisfactions of merchants and customers[J].Computers&Industrial Engineering,2021,162.

　　[5]余海燕，唐婉倩，吴腾宇．带硬时间窗的O2O生鲜外卖即时配送路径优化[J].系统管理学报，2021,30(03):584-591.

　　[6]周成昊，吕博轩，周翰宇，等．以商圈为中心的O2O动态外卖配送路径优化模型与算法[J].运筹学学报，2022,26(03):17-30.

　　[7]张力娅，张锦，肖斌．考虑顾客优先级的多目标O2O外卖即时配送路径优化研究[J].工业工程与管理，2021,26(02):196-204.

　　[8]G.B.Dantzig,J.H.Ramser.The truck dispatching problem[J].Management Science,1959,6(1).

　　[9]吴腾宇，陈嘉俊，蹇洁，余海燕.O2O模式下的配送车辆实时取送货路径选择问题[J].系统工程理论与实践，2018,38(11):2885-2891.

　　[10]黄心，吴学群，袁清冽．蚁群算法在外卖配送路径规划中的应用[J].价值工程，2017,36(05):65-67.