首页 > 论文范文 > 自然科学论文 > 数学论文 > 数学分析论文 > 遗传算法基础上外卖配送路径优化探究

遗传算法基础上外卖配送路径优化探究

2020-12-02 429 上传者：管理员

摘要：随着外卖行业的不断发展，外卖的配送成本备受关注。本文针对外卖配送的路径优化问题，建立包括距离成本和惩罚成本在内的总配送成本最小为目标的外卖配送路径优化模型。利用混合遗传算法求解，通过实验仿真结果表明，与遗传算法相比，混合遗传算法在该模型的寻优结果上有明显优势。

关键词：
外卖行业
外卖配送
混合遗传算法
遗传算法
配送成本
加入收藏

1、引言

在快节奏的生活中，人们对于餐饮便捷性的追求，使得外卖行业不断壮大。外卖配送作为外卖行业的重要环节，受到了各大外卖平台以及顾客的广泛关注。在配送过程中，如果只依据配送员的经验进行配送，很容易出现配送超时以及配送路径不合理的现象，以此带来不必要的损失。因此，在外卖配送方面进行各种优化，对于提高外卖配送水平具有重要意义。

外卖配送路径问题属于NP-hard问题，与车辆路径问题（Vehicleroutingproblem,VRP）类似。传统的VRP一般是指由一个或多个配送中心对多个客户进行合理的路线规划，在配送过程中需要满足一定的约束条件，如货物的取送时间、货物需求量、配送车辆的数量、车辆载货状况等，并且在完成配送任务的基础上实现一定的优化目标。针对车辆路径问题，学者们进行了不同的优化模型以及求解算法的研究。宋强[1]研究了带有时间窗和释放时间约束的多行程场景下的车辆路径问题，以总配送时长最小化为目标构建了数学模型；张涛等[2]考虑了同时送取货的情况，带有随机旅行时间的机会约束规划模型，设计了分散搜索算法的求解策略；范厚明等[3]基于可信性测度理论，构建了以总行驶距离最小、车辆使用数最小和平均客户满意度最大的多目标模糊机会约束模型；RichardP.Hornstra等[4]也在同时取货的情况下，研究了考虑运输和装卸成本（VRPSPD-H）的车辆路径问题，并提出了一种自适应大邻域搜索（ALNS）元启发式方法；BoPeng等[5]为研究多车辆的取送问题，提出了一种基于学习的模因算法。

与传统VRP不同的是，外卖配送需要完成多个商家到多个客户之间的配送任务，且每个配送任务中的商家与客户都是存在对应关系的；为了避免在配送过程中影响餐食的口感和质量，所以针对外卖配送的时间约束则更加严格。在模型建立和求解算法方面，也有众多学者做了研究。靳志宏等[6]以运输效率最大化为目标，构建了骑手配送路径优化的混合整数规划模型，在传统蚁群算法中加入新算子对实例进行求解；徐肇元[7]建立了基于客户时间满意度和配送总成本的多目标外卖配送线路优化模型，首先用SWEEP算法划分门店区域，再用改进了信息素更新规则的蚁群算法进行路径优化；王荃菲[8]针对餐饮企业自营外卖配送和第三方外卖平台配送两种场景建立路径优化模型，并对正常路况和拥堵路况的情形进行研究，分别设计了不同的配送路径方案。

通过文献的查阅，发现大多数关于外卖配送的研究都是利用蚁群算法、禁忌搜索算法等启发式算法对模型进行求解，使用遗传算法的研究比较少。为进一步研究，将遗传算法和爬山算法结合形成混合遗传算法，来弥补遗传算法局部搜索能力不足的缺点。因此，本文建立了包括距离成本和惩罚成本在内的总配送成本最小为目标的外卖配送路径模型，并利用混合遗传算法对模型进行求解。

2、外卖配送路径优化模型

2.1问题描述

在外卖配送的过程中，配送员需要完成手中所有的待配送任务，即配送员从起点开始需要遍历完所有的商家节点和顾客节点。每个订单中的商家与顾客都是一一对应的关系，配送员要遵循“先取餐，后送餐”的顺序原则并在顾客要求的时间窗内送达。如果配送员没有在规定的时间窗内达到，则需要接受一定的惩罚，由于在实际的配送过程中，顾客更希望配送员尽早到达，所以在配送员早到的情况下不会受到惩罚，只有在迟到的情况下才会受到惩罚。

为了更加直观的描述，建立了外卖配送结构图。如图1所示，以一个配送员与三个配送任务为例，配送员从起点开始，先去2号商家取货，取完货后接着去1号商家取货，然后为4号顾客送货，之后去3号商家取货，最后一次完成5号和6号顾客的送货，当完成所有商家节点配送任务后不需要返回起点。

图1外卖配送结构图

2.2模型假设

为更好地对问题进行研究，便于模型的建立和求解，对该问题做出以下的假设:

(1）由一名配送员为多个商家及对应的顾客服务，且商家和顾客的位置坐标、停留时间和时间窗要求都是已知的；

(2）配送员接单时不会超出车辆的最大载重量和最大行驶距离；

(3）配送员从起始位置出发后，必须先前往某个商家，才能给对应的顾客送餐，完成所有的配送任务后不用回到起始位置；

(4）每单配送任务中商家与顾客都是唯一对应关系，不存在一个商家对应多个顾客和一个顾客对应多个商家的情况；

(5）每个节点都有时间窗要求，配送员如果不能在规定时间内完成取送货任务时会有一定的惩罚成本；

(6）配送车辆匀速行驶，忽略配送过程中的路况问题以及配送员的自身问题。

2.3符号说明

参数和变量的说明如表1所示。

表1参数和变量的说明

2.4模型构建

根据上述的问题描述、假设，以及模型参数和变量的说明，建立包含距离成本和时间惩罚成本的总配送成本最小的外卖配送路径模型。如下：

约束条件：

目标函数（1）表示距离成本和时间惩罚成本之和最小；约束条件（2）表示将配送的起始时间设置为0；约束条件（3）表示配送员从起始位置出发后，下一个移动的节点必须是某个商家，不能是某个顾客；约束条件（4）表示每个订单配送员必须先去商家取餐，才能给对应的顾客送餐；约束条件（5）表示每个商家和顾客只能被服务一次；约束条件（6）表示当配送员完成所有配送任务后，不用回到起始位置；约束条件（7）表示配送员到达和离开每个节点的次数相同；约束条件（8）表示配送员从当前节点行驶到下一节点时，到达下一节点的时间为到达前节点的时间、在前节点停留时间和行驶时间之和；约束条件（9）表示判断配送员是否需要接受惩罚。

3、混合遗传算法的设计

遗传算法是一种通过模拟自然界种群进化的随机搜索算法。遗传算法具有良好的全局搜索能力，而且有较强的内在并行性，可以方便地进行分布式计算，加快求解速度。但是遗传算法也存在不足，其局部搜索能力较差，导致单纯的遗传算法比较费时，在进化后期搜索效率较低[9]。

爬山算法是一种局部择优的方法，采用启发式方法，是对深度优先搜索的一种改进，它利用反馈信息帮助生成解的决策，属于人工智能算法的一种。该方法的局部搜索能力很强，但外卖配送路径优化问题是一种多约束问题，由于爬山算法缺乏对问题的可行空间的全局性采样，所以较容易陷入局部最优解。

根据遗传算法和爬山算法各自的不足，把两个算法结合起来，借鉴郎茂祥等[10]学者的改进方法，在传统的遗传算法操作步骤中加入爬山操作，来提高算法的局部搜索能力和收敛速度。算法策略的如下。

(1）编码方法：采用自然数的编码方式，用节点的编号进行编码。

(2）适应度函数：把目标函数作为适应度评价函数，本文的目标函数是极小化问题，因此取其倒数用作适应度函数。

(3）选择策略：将个体的适应度从大到小排序，选择适应度大的个体和适应度虽然小，但是幸存下来的个体作为父代。

(4）交叉算子：采用PMX的交叉方法，操作方法为：首先，随机地在一对染色体中选择两个杂交点，如P1=0854|7316|92,P2=0546|9132|87，再交换交叉片段，得到P1'=0854|9132|92,P2'=0546|7316|87，最后按照映射关系（7-9,1-3,2-6）进行替换得到子代P1''=085913276,P2''=0542713689。

(5）变异算子：采用交换基因的方法，随机产生变异的基因位置，对个体的基因进行交换。

(6）爬山算子：采用基因换位算子来实现爬山操作,具体操作为：随机选择染色体中的两个位置，交换该位置上的基因，判断基因交换后的个体适应值是否增加，若增加，则以交换后的个体取代原个体[10]。

(7）终止条件：运算到指定迭代次数则终止。

算法的基本流程如图2所示。

图2混合遗传算法流程图

4、算例分析

为了验证算法和模型的有效性，使用20个节点信息来模拟一位配送员的配送情况，并利用python软件进行算法的实现。部分节点信息如下表所示，节点0表示起点，节点1-5表示商家，节点11-15表示顾客。假定配送员的行驶为匀速运动，速度为25km/h,单位距离成本为1，单位时间惩罚成本为2。

表2部分节点信息

分别对遗传算法和混合遗传算法进行10次实验，通对比实验可以得到，遗传算法和混合遗传算法的最优解分别为67.69和61.08，从寻优结果上看，在求解该模型时，混合遗传算法能够优于遗传算法。如图3可知，最优解对应的配送路径为0-6-16-2-4-12-3-1-10-7-11-20-9-13-5-17-8-14-15-18-19，总配送成本为61.08。

图3最优配送路径

5、结论

本文建立了带有时间窗约束和配送顺序限制的外卖配送路径的数学模型，并使用遗传算法和混合遗传算法对其进行求解，通过对比实验可知混合遗传算法可以对结果有一定的优化。

在外卖的实际配送过程中，还会受到天气、交通等多种因素的影响，而且外卖配送的过程是一个动态的过程，随时可能会增加新的配送任务。为更贴近实际情况，下一步会继续研究动态的外卖配送路径问题。

参考文献：

[1]宋强.Beam-PSO优化算法在多行程车辆路径问题的应用[J].计算机工程与科学,2019,41(10):1882-1891.

[2]张涛,余绰娅,刘岚,等.同时送取货的随机旅行时间车辆路径问题方法[J].系统工程理论与实践,2011,31(10):1912-1920.

[3]范厚明,吴嘉鑫,耿静,李阳.模糊需求与时间窗的车辆路径问题及混合遗传算法求解[J].系统管理学报,2020,29(1):107-118.

[6]靳志宏,鞠新诚,郭加佳,等.O2O模式下外卖骑手的配送路径优化[J].大连海事大学学报,2019,45(4):55-64.

[7]徐肇元.基于两阶段启发式算法的多目标外卖配送优化分析[J].测试技术学报,2019,33(4):340-345.

[8]王荃菲.快餐外卖配送路径方案研究[D].北京交通大学,2017.

[9]王尧山,朱毅,卢军.基于解空间优化的遗传算法的路径规划[J].电子技术与软件工程,2018(19):98-99.