doi: 10.3969/j.issn.1007-7375.2021.02.016
戴 韬，沈 静
(东华大学 旭日工商管理学院，上海 200051)
摘要: 各外卖平台均提供了兼职配送员参与众包服务的渠道。与专职配送员相比，兼职配送员有着“路径开放、时间有限、最终目的地确定”等诸多不同的特点。基于兼职配送特点，为了提高众包配送员的接单效率，提高兼职收益，对众包模式下的订单选择及订单执行路径进行深入分析，提出将二者进行统一考虑的双层算法：在底层建立众包外卖配送路径规划模型，并使用改进的遗传算法求解；第2层利用贪心算法调用底层模型，通过比较配送收益进行订单选择，使得兼职人员的配送收益最大。通过算例实验，验证模型及算法的合理性及有效性条件，发现算法的计算时间随备选订单数量增加线性增加。在现实应用中，需要通过对备选订单进行打分排序，控制“订单池”规模，则能在可接受时间内得到较高质量的选择结果。
关键词: 外卖配送；众包；订单选择；路径优化
中图分类号: U16 文献标志码: A 文章编号: 1007-7375(2021)02-0125-09
A Research on Take-away Delivery Task Selection in Crowdsourcing
DAI Tao, SHEN Jing
(Glorious Sun School of Management, Donghua University, Shanghai 200051, China)
Abstract: Nearly all the take-away platforms provide opportunities of part-time delivery service. Compared with full-time staff, part-time deliverers have several features when they participate in crowdsourcing delivery, including "multiple delivery path, limited working time, fixed destination and etc". Considering these characters, a research is made on take-away distribution task selection and task routing problem in crowdsourcing mode and a two-layer algorithm is proposed in order to enhance deliverers' efficiency and raise their revenue. A delivery routing problem model is built in the bottom layer, and solved with improved genetic algorithm. The upper layer adopts greedy algorithm and compares delivery revenue according to the model in the bottom layer to select tasks, so that the crowdsourcing workers' revenue can reach the largest level. A numerical case is given to test and verify the effectiveness of model and algorithm, the solving time increases linearly with the number of potential orders. In practice, this method can achieve a relatively high-quality solution in an acceptable time when the scale of alternate orders has been controlled.
Key words: take-away delivery; crowdsourcing; task selection; routing optimization
外卖配送是外卖O2O中重要的服务环节，外卖平台为了提升竞争力，保证较高的服务质量和用户体验，纷纷建立基于众包的配送平台，如蜂鸟众包、美团众包等。众包模式的引入，既解决了平台自建物流配送模式中固定的配送员运力与波动的订单量不匹配的问题，也为临时配送员兼职服务提供可能。
外卖配送主要有3种订单分配方式：派单、抢单和抢派结合。对于参与众包的兼职配送员来说，工作时间更灵活，抢单的自主选择性更强。在抢单模式下，外卖平台以取餐点与配送员位置等指标向附近配送员推荐一批订单，配送员抢单成功则必须完成该订单。而众包配送员在选择订单时往往凭经验与下意识的反应，若接受不适合的订单容易导致送餐延误产生赔付、客户投诉等情况，既影响众包配送员的收益，降低其参与众包的积极性，又影响
有关中秋的故事第 24 卷 第 2 期工业工程Vol. 24 No. 2 2021 年 4 月Industrial Engineering Journal April 2021
收稿日期：2019-11-09
基金项目：国家自然科学基金资助项目(71872037)
作者简介：戴韬(1983-)，男，副教授，博士，主要研究方向为物流管理、服务运作管理。
外卖平台的服务声誉。
因此，本文从配送员的角度出发，对众包模式下的外卖配送订单选择问题进行研究，提出基于路径规划的双层算法，通过比较接受不同订单所带来收益进行订单选择，使得在满足各项约束下配送员的实际所得收益最优。本文的研究结果能提高众包配送员的工作效率及收益，也能提高外卖平台的订单推荐效率。
1 相关文献综述
订单选择是从大量任务中选择最适合的若干个任务进行执行，也被称为任务推荐，不少学者为众包模式下的任务推荐提供了多种解决思路。Azi 等[1]对空间众包下实现工人收益最大的在线配送路径进行研究，在此基础上为动态任务推荐提供参考，文中采用自适应大型邻域搜索启发式算法求解。Sun等[2]同样关注了该问题，不同的是采用基于预测的路径推荐算法进行任务推荐。Deng等[3]提出基于动态编程和分支定界策略的精确算法，用于求解时空众包模式下，单个工人完成任务数最多的任务推荐问题。邓娜等[4]采用基于聚类分析和TSP 路径规划的外卖配送订单集指派模式，以配送距离最短为原则将配送员和订单匹配。宋天舒等[5]将众包任务地点也作为考虑因素，提出自适应随机阈值算法进行任务内容、众包人员和任务地点的三维匹配，使得总效用最大。
外卖配送及众包物流的路径规划成为近几年的研究热点之一。李桃迎等[6]对动态外卖订单调度及配送
路径问题进行研究，提出基于商家和顾客聚类的路径规划。蒋丽等[7]在对众包外卖配送路径规划的研究中，提出加入未来潜在客户数量影响因子的蚁算法，使得配送成本最小。吴腾宇等[8]针对O2O 外卖配送中需求不确定及取送货的特点，建立相应的路径规划模型，设计了TAIB算法和IGNORE算法，实现外卖配送车辆的实时调度。慕静等[9]基于众包物流参与人员积极性不高等问题，以最大化收益为目标，构建众包物流运力调度问题模型。陈萍等[10]提出基于时间满意度的外卖配送路径优化模型，并使用改进的遗传算法求解。Liu等[11]构建一个纳入出租车众包配送的外卖配送网络，采用包括构造算法和大邻域搜索算法的两阶段方法解决配送问题，使得所需出租车数量最少。Veenstra等[12]研究包含取送货按后进先出处理成本的取送货旅行商问题，基于此特点建立模型，并采用大邻域搜索算法求解。
外卖配送路径规划与取送货旅行商问题(pickup and delivery travelling salesman problem, PDTSP)比较接近。由于VRP问题为NP难问题，因此通常使用启发式算法求解，主流的有遗传算法、蚁算法、禁忌搜索算法和粒子算法等。Zhao等[13]提出一种混合遗传算法，用于解决取送货一体的旅行商问题。潘立军等[14]在传统遗传算法的基础上，采用时差插入法改进交叉算子、变异算子与变异算子的设置，并使用非代际搜索策略求解带时间窗取送货问题。Ai等[15]提出一种基于随机密钥解决方案的粒子算法，用于实现取送货车辆路径问题，基于客户优先级列表和车辆优先级矩阵构建车辆路线。
综上，任务匹配与取送货一体化TSP问题的先期研究为本文奠定了很好的理论基础，但是本文研究的
配送订单选择问题是一个“开放性”的决策问题，配送员可以根据自身情况选择一个或多个备选订单；在执行一系列订单过程中，与TSP问题不同，具有“路径开放(不用回到起点)”、“参与时间有限”、“最终目的地确定”等特点。这些特点让问题变得更加复杂，因此本文提出将订单选择与执行路径统一考虑的双层算法。
2 决策模型与算法
2.1 问题描述
T
m
n
外卖配送订单选择的实际场景为众包配送员在尚有未完成的待配送订单情况下，如何从系统推荐订单列表中选择多个订单，使得配送收益最大化的问题。可以抽象描述为配送员在时刻前到达某个指定点，在此之前可参与兼职配送，现有个订单尚未配送(可能部分已取)。此时外卖平台的配送订单推荐列表中有个订单可供配送员进行抢单，配送员如何从列表中选择合适的订单，使得完成所有订单后按时到达终点，同时配送收益最大化。
2.2 双层算法逻辑与说明
由于外卖配送的所得收益不仅是订单配送费用的简单相加，还需扣除因延迟配送导致的惩罚，因此在选择订单时需考虑是否能在规定时间内送达、是否会产生惩罚等情况。配送路径规划本身是NP难问题，订单选择是基于配送路径规划的更高层次的
126工 业 工 程第 24 卷
决策问题，而且由于现实问题的特点，模型的求解速度要求较高，更加大了决策难度。
n n 本文提出双层算法基本逻辑是上层逻辑为贪心算法，即通过某个评分机制，对待选择订单进行评分。由于平台实时推荐的订单数量较多，为了提高求解速度，将根据评分结果筛选出分数较高的个订单进入考虑选择的范围，由大到小逐个加入这
个订单进行配送路径规划，并得到相应的配送收
益，若加入新订单后的配送收益大于配送原有订单所带来的收益，则接受该订单，否则，不接受，直到再加入新订单无法得到可行解；下层逻辑为以配送收益最大为目标的考虑时间窗、延迟配送惩罚、配送携带订单数量约束等现实因素的配送路径规划模型，对应的求解算法是改进的遗传算法。
双层算法流程如图1所示。三月三走娘家真的会死丈夫吗
图 1 双层嵌套算法逻辑图
Figure 1 The logic diagram of two-layer algorithm
2.3 订单评分模型
n A n n 在上层算法中，依次加入推荐订单的顺序将直接影响最终订单选择的结果，而个订单所有可能的顺序组合有种。为了减小求解规模，同时增加较优的订单被选择的可能性，本文建立订单评分模型，根据分数高低确定订单加入的顺序与规模。
本文考虑影响配送订单选择的主要因素包括订单配送费、订单服务点(取餐点或送餐点)与待访问点(待配送订单的取餐点或送餐点)间的距离、送餐点与配送员计划终点的距离、取送餐方向。针对上述4个主要因素构建评分模型为
s (FR)i i 其中，为基础配送收益，本文将用订单的配送费占推荐列表中所有订单配送费总和的占比
s (PDN)i s (DDN)i i s (DDR)i i s (PDN)i s (DDN)i s (DR)i i FW NW DDW DW 表示；、为订单的取餐点、送餐点
与原计划下一访问点间的距离得分，距离越近分数越高；为订单送餐点与计划终点间距离得分，计算方法与以及相同；是取送餐方向得分，订单的取餐点或送餐点若在配送员当前位置至计划终点的方向相反的区域，则该项得分为0，反之为1。、、、分别表示各因素所占权重。
2.4 众包外卖配送路径规划模型
外卖配送有以下几个特征：1) 每个订单需先取餐再送餐；2) 取餐及送餐均有时间窗；3) 因为保温箱容量有限，有携带订单数量限制。除此之外，众包(兼职)配送员可以在任意空闲时间开始或停止接单，因此，众包配送员的配送路线一般不是闭环：从当前位置开始配送，完成所有任务后在某个最晚
第 2 期戴 韬，沈 静：基于众包的外卖配送订单选择研究127
时间前回到一个预期的终点，如图2所示。配送电动车受电瓶电量限制有行驶里程约束，全职配送员一般会配备多个电瓶克服里程限制。而众包配送员多为兼职参与，因此需考虑电动车电量所能支持的行驶里程。综上，在前3个基本特征之外，众包配送新增的特征为：4) 开放式取送货旅行商问题；5) 有最晚到达终点时间约束；6) 有行驶里程约束。
图 2 众包模式下兼职配送员送餐图
Figure 2 An typical part-time delivery path in crowdsourcing mode
2.4.1 问题描述及模型假设
n 2n T V ={0,2n +1}∪
R ∪C 02n +1R ={1,2,···,n }C ={n +1,n +2,···,2n }i n +i i T 考虑个配送任务时，配送网络包含1个配送员当前位置、1个配送员计划终点和个服务点(取送餐)，配送员须在时间前完成所接受的配送任务并回到计划终点。定义网络中节点集合，其中，节点表示当前位置；节点表示
终点；集合表示所有订单的取餐点；集合表示所有订单的送餐点；
和分别对应订单的取餐点和送餐点。配送员将
决策收益最大的配送路径，要满足的约束有：须在每个节点的时间窗内访问该节点；若超出最晚送餐时间则产生延时惩罚；同时每个订单必须“先取再送”；配送过程中携带的订单数有限；时间前到达计划终点。
本文假设如下。1) 配送员在取餐和送餐过程中的服务时间忽略；2) 车辆在行驶过程中行驶速度确定；3) 行驶成本与行驶路径成正比；4) 对于超时送餐的订单，将取消配送费，并惩罚一倍配送费的金额。
2.4.2 参数说明及数学模型
1) 符号定义。家庭吧台设计
O ：所有订单集合。
2) 模型参数。①车辆相关参数。
v Q L α为车辆行驶速度；为车辆携带订单容量；为最大里程限制；为行驶成本系数。
②网络图相关参数
d i j i j a i i
s i i w i i q i i 为节点到节点的距离；为车辆到达节点的时间；为车辆离开节点的时间；为车辆在节点的等待时间；为车辆离开节点时所载订单数量。
③订单参数。
[e i ,l r i ]i l c i i I i i 为订单取餐时间窗；为订单最晚送餐时
间；为订单的配送费。
3) 决策变量。
根据上述定义，得到配送路径模型为
受贿罪量刑标准128工 业 工 程第 24 卷
j i 其中，式(2)为目标函数，表示配送收益最大化；式(3)、(4)表示配送员从当前位置节点0出发；式(5)、(6)表示配送员最后回到计划终点；式(7)、(8)表示每一个订单的取餐点和送餐点都必须被访问一次；式(9)计算车辆到达节点的时间；式(10)、(11)为配送员在节点的等待时间以及离开该点的时间；式(12)保证最晚取餐时间被满足；式(13)确保先取餐点后送餐点；式(14)表示配送员在预期时间内完成待配送任务并到达终点；式(15)、(16)为车辆携带订单数量约束；式(17)保证配送行驶路程不超过当前电动车剩余电量所能满足的里程。
2.5 改进遗传算法设计
1) 编码方式。
·········i i i +n 为了便于体现取餐点和送餐点的区别，本文采用自然数编码的方式对取餐点和送餐点进行编码，0,1,2,,2n +1表示2n +2个访问点，其中，0为起点，1,2,…,n 为取餐点，分别对应第1,2,,n 号订单，送餐点对应为n +1, n +2,, 2n ，终点为2n +1，即订单的取餐点编码为，送餐点为。例如，假设当前有5个待配送订单，取餐点和送餐点编码如表1所示，起点为0，终点编码为11。以上编码组随机排序组合成一条染体，代表一条配送路线，如0-2-1-6-4-7-3-8-5-10-9-11，其中，每个编码代表染体上的一个基因。
2) 初始化种及改进的个体构造方法。由于带有取送餐顺序约束以及携带订单数量约
束，随机生成的初始种符合约束的概率较小，遗
传难以进行下去。为了提高初始种的质量以及算法运算速度，本文提出2个构造方法在随机生成初始种的基础上，对不符合约束的染体重新构造。① 取送餐顺序约束构造。
若随机生成的染体中存在某个送餐点在对应订单的取餐点之前访问，则将该订单的取餐点移到送餐点前一位，送餐点与原取餐点位置中间的访问点依次后移一位。例如，当前有5个待配送订单，假设随机生成的某一染体为0-2-3-4-6-7-8-1-9-5-10-11，其中，1号订单的取餐点1
漫反射出现在对应的送餐点6之后，不符合取送餐顺序约束，因此将基因1移至基因6前一位，原染体中基因6与1之间的基因依次后移一位，其余基因位置保持不变，形成新的染体，其操作如图3所示。
图 3 取送餐顺序约束调整操作图
Figure 3 Examplefor sequence constraint adjustment
② 携带订单数量约束构造。
配送员在访问取餐点后车辆携带订单数量加1，访问送餐点后数量减1。若在访问某点后，车辆携带订单数量超过容量，那么该点一定为取餐点，同时，该取餐点前一定有其他尚未送餐的订单的取餐点。因此，为了避免破坏取送顺序约束，本文以该取餐点所在的基因位为界限，从该取餐点之后的基因中选取已经取餐但尚未送餐订单的送餐点，将该送餐点前移。以图4为例，假设车辆携带订单容量为2，车辆访问取餐点4后订单数量为3，超过容量限制，因此从取餐点4往后寻已经在该点之前取过餐的订单对应的送餐点，先到送餐点7，将7移至4
前一位，原染体中4与7之间的基因均依次后移一位，其余基因位置保持不变，形成新的染体。
图 4 携带订单数量约束调整操作图
Figure 4 Example for order amount constraint adjustment
经过一次调整可以得到新染体，但该染体
仍有可能违反约束，例如取餐点1。因此，需要按
表 1 5个待配送订单的取餐点及送餐点编码Table 1 Serial ID of 5 orders pickup and delivery nodes
订单号取餐点编码
送餐点编码
1 1 6
2 2 7
3 3 8
4 4 9 5
5
10
第 2 期戴 韬，沈 静：基于众包的外卖配送订单选择研究129
乔任梁死亡图片
发布评论