基于时间窗约束下的外卖配送路径优化

翟劲松，台玉红　（上海理工大学，上海 200093）

ZHAI Jinsong,TAI Yuhong　(Shanghai University of Science and Technology,Shanghai 200093,China)

0　引言

随着互联网的发展以及生活节奏的加快，越来越多的人购买外卖。当下最主流的外卖销售形式是通过的O2O方式，即消费者线上下单，商家接单后线下送货上门。由于外卖配送的特殊性，于是配送问题一直是各大商家需要解决的难点，在提供配送服务的过程中，顾客往往约定外卖送达时间，商家需保障外卖的准时送达，一旦外卖未能准时送抵顾客处，顾客满意度会受到影响，顾客会将不满信息反馈到外卖平台以供其他顾客参考，会损伤外卖提供商的品牌效应，对经营业绩产生不良影响。因此，以时间窗为约束条件，以配送时间最短为目标，合理高效地组织配送服务对提高商家的自身竞争力具有重要意义。

带时间窗的车辆路径问题（Vehicle Routing problem with Time windows，VRPTW）是在VRP的基础上增加了客户要求访问的时间窗口，是VRP的一类重要拓展，可简单描述为：在不违背车辆限制的条件下，用于送货的若干车辆从配送中心出发，在返回到配送中心前，以最低的总成本满足处在不同地理位置的客户对供货数量、质量和服务时间的要求。许多与时间相关的运输调度问题都可归结为VRPTW，例如邮件的投递、公交的调度、JIT模式下物料的配送等，根据时间要求合理安排车辆路线是提高服务质量和经济效益的重要手段。由于VRPTW本身的复杂性以及相应的实践问题，各国学者进行了大量研究。同时VRPTW属于NP难问题，一般采用启发式算法求解，例如节约法[1-2]、遗传算法、捕食搜索算法[3]。张建强、潘立军（2012）[4]等都曾利用遗传算法求解物流配送路径优化问题。马韶涵（2016）[5]等将外卖的配送分为了餐饮企业配送模式，外卖平台配送模式，第三方物流企业配送模式三种方式，并对外卖平台配送模式进行了研究，对该配送模式存在的问题进行了分析和提出了解决对策。郭月（2016）[6]等通过使用节约里程法对校园外卖配送路径的优化，从而达到配送的高效率。张弘颖（2014）[7]为了实现熟食运送的快速和经济合理，采用遗传算法对配送路径进行了优化，最后通过实验验证该方法是可行的、有效的。王帅（2017）[8]通过遗传算法有效地计算出响应顾客需求的最优车辆路径，并分析了顾客完全满意度区间大小、顾客满意度敏感性以及配送车辆数量等因素对配送方案总体满意度水平的影响，最后提出了提高外卖O2O配送满意度的建议。

1　问题描叙

本文是研究带有时间窗约束的外卖车辆配送问题，目标是在顾客需求时间约束的情况下，商家的配送总时间最短。通过对周边的商家进行调研，将本论文的问题进行了简单的描述，主要可描述为一个商家也是配送中心，所有的订单都是在配送中心进行处理和分配，之后向周边多个顾客点进行配送服务，由配送中心的多辆车从配送中心出发，在顾客约定的时间限制下进行配送，最后在配送完之后再返回配送中心的一个过程，如图1所示：

图1　一条路径的配送过程

2　模型建立

2.1　问题假设

在外卖配送过程中，会有出现很多情况，导致配送时间的浪费。（1）配送物损伤，如果配送车辆装载过多，可能出现货物被挤压受损等情况，配送员需要花费时间解决该种情况；（2）配送车辆由于出现一些情况，无法进行配送，导致配送不及时；（3）出现重复配送情况，使得配送效率降低，等等。于是为了避免出现上述的一些情况，本文做出如下的假设：

假设一：在每条送餐路径上，车载重不小于顾客订单总需求和。

假设二：每条送餐路径的配送时间不大于配送车辆的最大行驶时间。

假设三：一个客户的订单只能由一辆车进行配送。

2.2　模型参数

对于本论文模型，其中的主要参数如下：

K为商家配送车辆数；

Qk为每辆车的车载量；

Tk为车辆配送的最大行驶时间；

En为顾客订单要求最早达到时间；

Fn为顾客订单要求最晚达到时间；

L为配送送货点个数，其订单量记为qi（i=1,2,）…；

tij为客户点i到j的配送时间；

nk为第k辆车配送的顾客配送点数；

Rk表示第k条路径的集合；

rki表示顾客点rki在路径k中的顺序为i；

令rk0=0表示商家的配送中心。

2.3　模型设立

针对本论文的目标，建立如下的模型：

其中：式（1）为目标函数，式（2）确保顾客订单在顾客规定的时间窗内送到，式（3）确保每条配送路径上的车载量顾客订单的总和，式（4）确保每条路径的配送时间≤配送车辆最大行驶时间，式（5）每条路径的顾客订单数≤总的顾客订单总数，式（6）确保货物送到每个客户，式（7）确保每个顾客的订单由一辆车进行配送，式（8）中的0表示该辆车没有被使用。

3　算法求解

遗传算法由美国J.H.Holland教授在20世纪70年代提出。该算法是基于生物进化理论的自适应随机搜索算法，对于求解路径优化问题十分有效。路径优化问题是遗传算法应用十分成熟的领域，该算法求解路径优化问题的基本步骤为：编码操作、产生初始种群、计算适应度函数、遗传算子（包括选择、交叉和变异）、终止规则。针对本文中的问题，采用遗传算法进行求解，生成最优的路径。

（1）编码。路径优化问题的编码方式分为两种：路径表示法和相邻表示法。本文采用第一种编码方式。举例说明：设某商家有9个配送点需要进行配送，其中一个可行闭合路径为则对应的染色体编码可表示为1 4 3 7 2 5 8 6 9。

（2）产生初始种群。初始种群是进行遗传进化操作的第一代种群，由N个个体组成。本文初始种群通过随机方式生成，将初始种群规模设定为N=30，由此则随机生成30个个体，每个个体代表了一个初始解，由于暂没有进行遗传进化，因此这一代种群中个体适应度值偏低。

（3）计算适应度函数。适应度函数是目标函数在遗传算法中的反映。在遗传算法中，适应度值大的个体将有更大概率将优良基因信息传递给下一代。本文的目标函数是时间最低，因此本文采用时间的倒数作为适应度函数，个体的适应度值可表示为：Fitness=1/z。

（4）遗传算子。本文遗传算子分为三个部分为选择、交叉和变异，选择：本文依据种群中不同个体的适应度值采用轮盘赌方式进行选择，该方案能够保证适应度高的个体以更大的概率被选中。交叉：在遗传算法中，新个体的产生主要依靠交叉操作。本文进行交叉操作时，为使子代依旧为可行解，采用部分匹配交叉法（PMX）：对两个父代随机产生2个位串交叉点，两点间为交叉匹配区域，然后基于匹配区域内基因的映射关系重新排列区域外重复基因。举例如下：

父代染色体

父代1：138|27|4965

父代2：726|45|8139

交叉匹配

匹配1：138|45|4965

匹配2：726|27|8139

子代染色体

子代1：138|45|2967

子代2：546|27|8139

其中：子代1和子代2即为通过部分匹配交叉法获得的新一代个体。

变异：交叉操作能够使子代保持父代的优良特性，但也会导致算法过早收敛，陷入局部最优。变异操作能够弥补这一缺点，扩大遗传算法的搜索空间。本文采用对换变异法：首先，随机选择染色体的两个基因，然后交换位置，完成对换变异，举例如下：

变异前：2 3 8 6 7 1 9 5 4

变异后：2 3 9 6 7 1 8 5 4

（5）终止条件设定。遗传算法本质上是随机搜索算法，因此难以找到准确的收敛性判别标准。本文采用遗传算法进化代数作为终止条件。当进化代数达到预先设定值200代时，算法终止，并输出适应值最大的个体作为最优解。

4　算例分析

本文考虑某个餐厅在某天11:30到12:30时间段内对其9个配送点（编号为1,2,…,9）进行外卖配送服务，各配送点之间的配送时间和到商家的之间的行驶时间如表1，配送点的需求量和客户需求配送时间窗如表2，商家有三辆配送车，每辆车的最大装载量为15份，车辆配送的最大行驶时间为120分钟。

将以上数据带入模型，经过 Matlab编程进行总时间最小的最优车辆路径选择求解运算，可以得到最优配送路径方案3条（如表3）分别为：路径1：0-2-1-8-0；路径2：0-4-9-5-0；路径3：0-3-7-6-0；最小的配送总时间为93分钟，平均每条路径的配送时间为31分钟。

表1　各点之间的行驶时间　单位：分钟

表2　各点的需求量和时间窗

表3　配送最优路径

5　结束语

随着人们生活节奏越来越快，顾客对外卖配送时间的要求变得更高。本文通过建立以顾客满意时间为约束条件，以配送时间最短为目标，运用遗传算法进行路径优化，最后通过实例验证得出该模型可以进行外卖路径进行优化，即可以满足客户对时间的要求，同时还可以减少商家配送时间，提高了商家的竞争力。

参考文献：

[1] 郑静，程幼明.基于时间约束的节约里程法配送路径优化研究[J].物流工程与管理，2010,32(10):89-90.

[2] 于航，张凯.基于节约里程法的鲜活农产品物流配送车辆路线的最优设计[J].安徽农业科学，2011,39(28):17701-17703.

[3] 蒋忠中，汪定伟.有时间窗车辆路径问题的捕食搜索算法[J].控制与决策，2007,22(1):59-62.

[4] 潘立军，符卓.求解带时间窗取送货问题的遗传算法[J].系统工程理论与实践，2012,32(1):120-126.

[5] 马韵涵，李品峣.OTO外卖配送分析及对策[J].合作经济与科技，2016(22):96-98.

[6]郭月，张涵.校园外卖配送体系研究[J].中国市场，2016(20):67-69.

[7] 张弘颖.基于遗传算法的熟食配送路径优化[J].科技传播，2014,6(16):166-167.

[8] 王帅，赵来军，胡青蜜.随机旅行时间的外卖O2O配送车辆路径问题[J].物流科技，2017,40(1):93-101.