基于众包配送模式的超市订单分配与路径规划研究

李四兰 郭伟钰 宋孟珂

摘  要：随着互联网的快速发展，O2O商业模式已经成为一种潮流。超市作为连接广大消费者和生产者的终端场所，其在转型升级的过程中也采用了全新的O2O商业模式。由于超市末端配送服务具有即时性，超市配送员大多数属于社会闲散人员，并没有接受过专业的培训。导致在配送过程中发生无人接单、配送超时、顾客满意度低等问题。造成这些问题的主要原因是众包配送平台订单分配模式缺乏科学的并单指导，文章将杭州市B连锁超市的151个订单用改进的K-means算法进行聚类，再将聚类完成的订单用蚁群算法进行路径优化。最后验证了所使用的方法在解决超市订单分配和路径优化问题方面的可行性和有效性。

关键词：众包配送;车辆路径优化;K-means算法;蚁群算法

中图分类号：F252.14    文献标识码：A

Abstract： With the rapid development of internet， O2O business model has become a trend. As a terminal place connecting consumers and producers， supermarkets also adopt a new O2O business model in the process of transformation and upgrading. Due to the immediacy of the terminal distribution service in supermarkets， most of the delivery workers in supermarkets belong to the social idle people and have not received professional training. In the process of distribution， there are many problems， such as no order， delivery overtime， low customer satisfaction and so on. The main reason for these problems is that the order allocation mode of crowdsourcing distribution platform lacks scientific guidance. In this paper， 151 orders of B chain supermarket in Hangzhou are clustered by improved K-means algorithm， and then the clustered orders are optimized by ant colony algorithm. Finally， the feasibility and effectiveness of the method in solving the supermarket order allocation and path optimization problems are verified.

Key words： crowdsourcing distribution; vehicle routing optimization; K-means algorithm; ant colony algorithm

0  引  言

外卖众包配送是众包外卖平台以众包的形式从社会中获取闲散的资源（众包配送员），再将众包外卖平台获取的外卖配送任务交由众包配送员，最终通过众包配送员完成外卖配送服务。在传统配送模式下，要求车辆统一从配送中心出发，遍历所有顾客需求点后仍需返回配送中心，其目标函数多为运输成本较低、运输距离较短等。而众包配送作为一种新颖的第三方配送方式，在配送完成后无需返回配送中心，可直接在众包平台软件点击结束即可完成本次配送。具有更大的自主性和选择权。

国外相比国内较早的开始研究众包物流和路径规划问题，Klumpp（2017）[1]通过分析众包物流商业模式，结合具体实际情况，提出了如何有效的评价众包物流服务质量。LiX和LiY[2]讨论了众包外包O2O平台的订单分配和配送路径优化的组合问题，但未考虑到众包配送人員手动获取订单的实际情形。同时，国内学者也对该问题进行了研究。邓娜、张建军等（2018）[3]基于外卖订单目前配送模式的缺点，提出了一种基于聚类分析和TSP路径优化订单集指派模式，按照取餐点、送餐点、需求量和订单送达时间对订单进行聚类分析，并规划最优配送路线，验证了提出的方法可以有效的加快订单处理效率，纪汉霖等（2016）[4]分析了当前生鲜电商行业的发展现状和存在问题，介绍了众包配送在生鲜电商行业中的应用，以及众包配送在生鲜电商行业中的优势和缺陷，最后提出众包信息化和完善众包诚信制度建设的对策建议。

通过对众包配送路径优化文章的研究和分析，可以看出众包模式在配送过程中还存在着诸多问题。针对连锁超市末端配送范围是三公里之内。本文采用改进的K-means聚类算法以各个消费者的地理位置坐标为标准对配送订单进行聚类分析，使得同一类中消费者位置较近，每位骑手只能派送某一聚类范围内的订单。得到聚类结果后建立带时间窗和车辆装载量约束的配送路径优化模型，以顾客满意度最大为目标函数。最后用改进的蚁群算法对数学模型进行求解，得到多条配送行驶路线。

1  众包模式下车辆的路径优化问题

1.1  问题描述

本文所研究的是在众包配送模式下连锁超市如何高效配送货物使得顾客满意度最大化。主要可以描述为一个配送中心O向n个消费者进行订单配送，V=0，1，2，3，…，n表示各个节点的集合，N=1，2，3，…，n表示各个消费者需求点的集合，O表示超市配送中心。每个消费者的需求量为qi=1，2，3，…，n。每一辆配送车运输货物的最大载货量是相同的，均为Q，且maxq≤Q。

1.2  模型假设

（1）配送中心的位置已知，各个需求点的位置以及需求量已知。

（2）配送员使用电动车作为配送车辆，所有配送车辆的类型一致，即配送车辆的载重量、油耗、行驶速度均相等，单位运输成本为定值。

（3）众包模式下，配送车辆由众包配送员自己提供，所以配送成本不包括车辆的启动成本和运输成本，仅包括众包快递员的报酬。

（4）每辆配送车均从配送中心出发，车辆完成配送任务后不需要返回商家。

（5）每辆配送车的载货量不能超过其最大载重量。

（6）众包配送员将商品送达需求点后会产生一定的服务时间，且为定值。

（7）所有众包配送员均能完成配送任务，即不存在接单后不配送的情况。

（8）配送员在配送过程中不考虑天气、交通状况等外界意外事件的发生。

（9）众包配送员每配送一单报酬为一个固定值。

1.3  符号说明

1.4  构建模型

1.4.1  目标函数

maxf=xz-cy                                       （1）

其中：

c=                                         （2）

1.4.2  约束条件

qy≤Q， k∈S                                           （3）

y=1， i∈N                                            （4）

t=t+t+                                              （5）

x=s                                                （6）

ET≤t≤LT， i∈N                                            （7）

n=n    0≤n≤n                                        （8）

x∈0，1， ？坌i∈N， ？坌j∈N， ？坌k∈S                                    （9）

y∈0，1， ？坌i∈N， ？坌k∈S                                       （10）

公式（1）為目标函数，第一项表示众包配送人员配送报酬，第二项表示每个需求点配送完成后，超出客户要求的时间窗的惩罚成本。整个目标为众包配送人员的配送报酬达到最大，即顾客的满意度最大。公式（2）为众包配送员在不同时间内到达，惩罚成本的分段函数。公式（3）为载重约束，表示每一辆配送车的载重量不能超过其最大容量。公式（4）表示同一个需求点只能由一辆车提供配送服务。公式（5）表示连续服务两个消费者的时间递推关系。公式（6）表示所有的配送车辆均从连锁超市出发。公式（7）表示各个需求点只在一定时间段内接受服务。公式（8）表示每个需求点都必须得到配送服务。公式（9）、公式（10）为0-1型变量。公式（9）表示第k辆车是否从需求点i服务到需求点j，若服务值为1，否则为0。公式（10）表示第k辆车是否服务于第i个需求点，若服务值为1，否则为0。

2  基于改进K-means聚类算法的众包配送区域划分

由于K-means算法无法事先知道需要的聚类数，初始聚类点的选择是随机产生的。随机产生的初始聚类点可能会得到不同的聚类结果。本文先使用AP算法得到最佳的聚类数量，然后用K-means算法根据AP算法得到的聚类数量进行聚类，并用轮廓系数评价聚类结果的优劣，具体步骤如下：

步骤1：将某时间段内的订单利用百度地图拾取坐标的方式得到所有订单分布的经纬度;

步骤2：利用AP算法对需求点进行聚类，得到最佳聚类数量K;

步骤3：设置聚类数量为K，并随机选择K个聚类中心。用K-means算法计算所有样本点到聚类中心的欧氏距离，选取距离最小的聚类中心并将点规划到其簇中;

步骤4：所有需求点分配完毕后，重新计算聚类中心，比较与前一次的聚类中心是否相同，若相同，则停止迭代输出聚类结果;若不同，则返回步骤3;

步骤5：比较AP算法和改进K-means算法的聚类结果，并通过轮廓系数得到最佳的聚类结果。

3  众包配送路径优化模型算法设计

3.1  路径转移规则

当蚂蚁完全依赖随机概率规则访问下一个需求点，由公式（11）决定：

p=                       （11）

其中：q为随机产生的数，取值在0到1之间。τ是路径i，j上的信息素浓度，η是路径i，j上的启发式因子，Ω为需要访问的需求点的集合，ω和ω分别表示与信息量和通往下一需求点的时间窗口宽度和到达下一需求点的时间相关的权重系数。ω和ω取值均在0和1之间，且满足ω+ω=1。

3.2  信息素更新规则

本文采用全局更新信息素的方法，其更新规则如下：

τt+1=1-p·τt+pΔτt                                    （12）

Δτt=Δτ                                            （13）

信息素濃度τt+1等于t时刻的信息素浓度的残留值与t到t+1时刻之间的信息素Δτ为相关路径ij上的信息素增量。

4  案例分析——以杭州市B连锁超市为例

本文选取杭州市B连锁超市11：00～12：00内的151条订单数据来验证本文提出数学模型和方法的有效性和可行性。首先利用MATLAB软件绘制出B连锁超市在时间段11：00～12：00内需要配送151个需求点订单的经纬度散点图，如图1所示。从图1中可以看出消费者的地理位置分布比较分散，且距离远近不同，通过随机分配订单是不合理的，需要将订单聚类后再进行分配，保证配送资源的合理利用。

针对超市和顾客的地理位置分布，首先使用AP算法对订单需求的经纬度坐标进行聚类分析，由于AP算法不需要预先规定聚类数，所以先运用AP算法聚类得到151个需求点的聚类数量K值，得到聚类数量k值为4，如图2所示。再使用

K-means算法进行聚类，得到的聚类结果如图3所示。

改进的K-means聚类算法得到的需求点序号所属的聚类号以及各聚类序号需求点的数量如表1所示：

为了检验用AP算法改进K-means算法的有效性，本文引用轮廓系数作为评价两者相结合的聚类算法的标准。通过比较用AP算法改进K-means算法与AP和K-means算法单独使用的轮廓系数来验证所提出的有效性，指标结果如表2所示。

通过表2的轮廓系数可以看出用AP算法改进K-means算法的聚类方式对超市订单的顾客需求点进行聚类的方法较好，验证了本文提出的方法的有效性。

基于上文的聚类结果，选取聚类序号为1的顾客需求点进行路径优化。利用Excel软件进行高斯克—克吕格投影换算，将经纬度坐标换算成高斯平面直角坐标。例如配送超市0的经纬度为（120.129254，30.294442），换算之后得到的平面直角坐标为（5 123，5 668）。建立坐标系，并用Matlab绘制散点图，如图4所示。

参数设置：迭代次数=200、蚂蚁个数=43、信息素重要程度=1、启发式因子重要程度=3、信息素挥发因子=0.85、更新信息素浓度常数=5。

众包模式下假设配送员车辆最大载重量为80kg，众包配送每单报酬5元，车辆平均行驶速度15km/h，每个顾客的服务时间均为5分钟，所有顾客需求点的时间窗均为11：00～12：00，超出时间窗的惩罚成本每单10元。众包配送路径优化模型求解结果如表3所示：

传统模式下车载量、快递员报酬、车辆行驶速度、顾客服务时间、以及需求点的时间窗都相同的情况下，每辆配送车的启动成本为50元/辆。单位距离的行驶成本为10元/km，用蚁群算法分别计算众包模式和传统模式的路径优化如图5、图6所示。两种配送模式比较如表4所示。

由于众包配送模式下配送完成后不用返回配送中心，相比于传统配送模式车辆配送完成后返回配送中心。众包配送减少了配送里程配送路径不再是一个闭环。从表4可以看出，众包配送比传统配送车辆行驶里程少5 650m。同时众包配送不考虑车辆成本，对连锁超市来说成本只有众包配送员的工资和超时配送的惩罚成本。在规定时间内送达不会产生惩罚成本。而对于传统的配送模式，连锁超市的成本C包括车辆的启动成本c、车辆的运输成本c以及配送员的工资c三部分组成。配送成本相比众包配送增加了，为了保证顾客的满意度。两种模式均在规定的时间里完成配送，但是成本相差很大。

5  总结与展望

本文以众包外卖配送为研究对象，从众包配送平台的角度出发，聚焦于解决订单分配和路径优化问题。以杭州市B连锁超市为例，考虑顾客要求的时间窗，配送车辆的载重量等因素，将配送所有订单的配送路线最短、配送人员薪酬最高、顾客满意度最大、惩罚成本最低作为目标对订单先进行聚类。对聚成一类的需求点进行路径优化，并与传统配送模式相比较得出众包配送在路径距离、成本等方面都优于传统配送模式。众包配送多为社会闲散人员，在一定程度上增加了我国的就业率。车辆配送路径优化模型中假设车辆都是同一类型且在配送中速度是均匀的，而现实中众包配送员的配送车辆可能存在各种各样的差异，配送途中的速度情况都有一定的不确定性，很难满足模型中提出的假设条件。在以后的研究中应提出更加符合实际情况的模型。其次，众包配送人员专业性低于全职配送员，所以目前只能考虑一些小额订单，未来可以考虑众包配送员的优选问题，在众包配送过程中选择服务质量较好的配送骑手。

参考文献：

[1]  Klumpp M. Crowdsourcing in Logistics： An Evaluation Scheme[M]. Bermen： Springer International Publishing， 2017：401-411.

[2] LiX， LiY. Crowd sourcing Takeout Distribution Route Optimization Considering Pickup and Delivery[C] // 第30届中国控制与决策会议，2018.

[3] 邓娜，张建军. O20外卖订单配送任务分配模式研究[J]. 上海管理科学，2018，40（1）：63-66.

[4] 纪汉霖，周金华，张深. 生鲜电商行业众包模式研究[J]. 物流工程与管理，2016（1）：93-95.

[5] 陈萍，李航. 基于时间满意度的O20外卖配送路径优化问题研究[C] // 中国管理科学学术年会，2016.

[6] 石荣丽. 分享经济视阈下的众包物流信息服务平台模型构建[J]. 华南理工大学学报（社会科学版），2017，19（2）：15-21.

[7] 馬冠群. 基于众包物流模式的同时送取车辆路径问题研究[D]. 济南：山东大学（硕士学位论文），2019.

[8] 程月娇，施炯，黄彬. 众包物流环境下订单合并及配送路径优化方法研究[J]. 浙江万里学院学报，2017，30（4）：27-33.

[9] 张晓雯，盛宇华. 共享经济背景下生鲜电商“最后一公里”众包配送问题研究[J]. 价格月刊，2017（10）：66-69.

[10] 范青. 基于改进蚁群算法的物流配送路径优化及应用研究[D]. 西安：西安建筑科技大学（硕士学位论文），2014.

[11] 蒋丽，王静，梁昌勇，等. 基于改进蚁群算法的众包配送路径研究[J]. 计算机工程与应用，2019，55（8）：250-255.

[12]  Miranda D M. The vehicle routing problem with hard time windows and stochastic travel and service time[M]. Pergamon Press， Inc， 2016.

[13]  Kang Y， Lee S， Chung B D. Learning-based logistics planning and scheduling for Crowdsourcing parcel delivery[J]. Computers & Industrial Engineering， 2019，132（6）：271-279.

[14]  Zhang D， Cai S， Ye F， et al. A hybrid algorithm for a vehicle routing problem with realistic constraints[J]. Information Sciences， 2017，394：167-182.