同城货运众包平台的车货匹配模式对比研究

余海燕, 逯 楠, 李小甫

(重庆交通大学 经济与管理学院,重庆 400074; 2.重庆口岸物流管理与航运经济研究中心,重庆 400074; 3.智能物流网络重庆市重点实验室,重庆 400074; 4.智深圳依时货拉拉科技有限公司重庆分公司,重庆 400000)

0 引言

进入互联网时代以来，同城货运市场也迎来了发展黄金期。2009～2018年，中国同城货运行业市场规模从3728亿元增长至8050亿元，年均复合增速为8%。但长期以来货运需求与货运司机的精准匹配一直是同城货运行业的痛点问题，因此同城货运车货匹配平台应运而生。

在货拉拉等同城货运车货匹配平台上，客户根据需求实时下单，下单时发布取送货地点、所需车型和出发时间等信息，平台上有大量众包货运车，每辆车有车容量限制，且其工作时间与开始工作的地点是不确定的，结束工作后司机也可不停留在送货点处。目前的同城货运车货匹配平台均通过让司机抢单的方式将配送订单分发给相应的司机。需求订单实时产生，每个订单都需要尽快接受服务，避免客户因等待时间过长而取消订单。在目前抢单模式下，存在一些弊端：(1)司机自主抢单，订单匹配率下降。由于就近抢单会使得部分司机抢不到单或部分订单无人抢的情形，导致配送效率有待提升。(2)司机为了抢单会在驾驶过程中频繁关注手机导致注意力不集中，因此容易出现交通事故或产生不必要的交通违章等不利于提高司机和平台粘性的行为。为了避免抢单模式的以上弊端，本文提出基于滚动时域完美匹配算法的平台派单模式，并研究该派单模式与抢单模式在客户平均等待时长方面的差异，从而得到不同模式的适用性。

与本文相关的研究包括众包配送服务问题、取送货问题和匹配问题。

众包配送是将众包理念引入物流领域的新型配送模式，将原本由企业内部员工承担的配送任务分配给社会大众。很多学者对众包配送的优势进行研究，指出众包配送模式在应用过程中具有成本低、效率高以及改善交通环境等优势[1～3]。Castillo[4]发现众包物流更能提高物流配送效率。目前对众包配送研究多集中于对众包定义、优势以及众包工人的特点进行研究。取送货问题是车辆路径问题的一个分支，一般情况下车辆从同一车场出发，完成配送后要回到车场且配送过程中考虑车辆的配送能力，每个任务点只能访问一次[5]。Kuo[6]等提出不同目标函数进行优化研究。Gerardo[7]研究了不同的求解算法。除了对求解算法进行不断优化，杨东林等[8]对不同的配送模型进行了仿真研究。Douglas等[9]采用延迟插入的方法解决动态拨号叫车问题。目前的取送货问题研究集中于多配送中心、取送配对有序、取送货与时间窗等领域上的研究。针对车货匹配问题，目前主要的匹配方法是贪婪算法，而朱江洪[10]、牟向伟[11]等诸多学者对不同匹配算法进行了深入研究。

综上所述，在现有的文献中，对于众包配送的研究，较多的学者关注于众包配送的可行性、优势以及路径优化等问题，将众包物流与同城货运相结合的相关文献较少；其次，对于取送货问题，学者一般研究车辆从同一车场出发完成所有的任务后再回到车场的过程，本文研究的同城货运众包平台的车货匹配问题研究车辆从任意位置出发且完成任务后无需返回初始位置；最后，在现有的匹配问题文献方面，较多的学者关注于匹配算法的优化及改进，而对于动态需求下的不同匹配模式对比的研究还很欠缺。

因此，本文研究基于众包平台的同城货运车货匹配派单模式与抢单模式的差异，通过数值仿真实验验证模型和算法的有效性，得到不同模式的适用性。主要创新性体现在以下方面：

(1)提出将派单模式应用于同城货运的新思路，对比研究了抢单模式与派单模式的差异。

(2)引入时间维度刻画订单的动态性，构建了一个全新的动态车货匹配模型。

(3)通过仿真研究证明了派单模式滚动时域完美匹配算法的优越性，并分析了两种不同模式算法的有效性和适用性。

下文将从问题描述与建模、匹配算法设计、仿真结果分析及结论几个方面来论述。

1 问题描述与建模

本文重点研究了基于众包平台的同城货运车货匹配模式，将现有的抢单模式和本文提出的派单模式进行对比研究，探索在不同环境中减少客户平均等待时长的匹配模式。下面是同城货运车货匹配问题的一般描述：

给定一个网络图G=(V,E)，其中顶点集合V={v1,v2,…,vn1}，边集合E={e1,e2,…,en2}。l(vi,vj)表示网络图中vi与vj之间的距离。所有取货点与送货点、车辆均在网络图G上产生，网络图中每个点既可以是取货点又可以是送货点，但同一个点不能既是一个订单的取货点又是送货点。在某一时间段内同城货运平台接收到n个订单。订单序列表示为σ={O1,O2,…,On}，订单Oi表示为(ri,ui,di,qi)，其中ri表示需求订单i的释放时间即订单出现的时刻，ui∈V表示订单i的取货点位置，di∈V表示订单i的收货点位置，qi表示第i个订单的载货量,i∈I={1,2,…,n}。所有订单是实时产生的，只有时刻ri时，该订单的所有信息才被获知。同城货运平台共有m辆车可进行匹配，车辆Ck为最大装载容量，k∈K={1,2,…,m}。车辆均以速度v行进，并且在完成订单后无需返回原起始位置，一辆车一次只为一个订单服务。假设所有订单不会被取消，配送车辆需要先到取货点取货然后送至送货点以完成该订单，不考虑车辆在该服务点的等待时间。研究的问题是同城货运车货匹配平台如何将实时出现的订单与货车进行匹配，使得客户平均等待时长最短。

模型中用到的参数或变量:

已知参数：

n：某一时段内同城货运平台合计订单数量;i∈I：i表示订单，I为所有订单的集合;σ={O1,O2,…,On}：订单序列Oi=(ri,ui,di,qi)，其中ri表示订单i的释放时间，ui表示订单i的取货点位置，di表示订单i的收货点位置，qi表示订单i的载货量。

决策变量：

根据问题描述，服务完所有订单的平均客户总等待时长最短的模型和目标函数如下：

(1)

以上建立的基于众包平台的同城货运车货匹配模型中，由于订单的释放时间ri是无法提前获知的，故该问题是一个动态实时性的问题，无法直接进行最优化求解,故通过设计动态策略并用模拟仿真的方法进行研究。对于该动态问题，现实中的同城货运车货匹配平台绝大多数都使用抢单模式进行车货匹配，针对该模式的不足，本文提出派单模式并在后文中对比分析两种不同模式的适用性。

2 抢单与派单模式下的算法分析

下面将对目前车货匹配平台抢单模式使用的就近随机配对算法进行描述，然后提出派单模式，并设计滚动时域完美匹配算法进行车货匹配。

2.1 抢单模式及其就近随机配对算法

现实中的抢单模式为客户在平台下单，平台根据距离近、车容量大小等因素筛选符合条件的车辆，然后将订单推送给司机，司机进行抢单。该模式的匹配算法可以抽象为就近随机配对算法。

该算法的核心思想是将新产生的订单即时推送给距离近且符合车容量限制的多辆车，然后从选取的多辆车中根据随机概率达成匹配。其具体步骤如下：

第1步当没有新订单出现时，等待。当出现新订单时，立即转至第2步。

第2步查询当前待服务订单数和待服务车辆数，转至第3步。

第3步判断待服务订单数是否小于等于待服务车辆数，若是则执行第4步，否则大于车辆数部分的订单等待下次分配，其余订单参与此次分配，转至第4步。

第4步选取所有需服务的订单，排除车辆载重量小于订单容量的车辆。选择min{c,h}辆车参与抢单。其中c为各车辆前往单个订单的距离升序集合中所有车辆，h为该集合中前h辆车，转至第5步。

第5步根据随机概率完成车辆和订单匹配，达成最终匹配结果，记录各车辆到达取货点的时间，转至第6步。

第6步运用式(1)计算服务完所有订单的平均客户总等待时长。

为验证就近随机配对算法的有效性，构建了就近随机算法仿真流程图，如图1:

根据上述仿真框架图，设计仿真实验。仿真关键点为如何处理实时出现的订单，在该仿真流程中将各个订单的释放时间作为关键时间节点，每个关键节点调用就近随机配对算法并进行更新。

2.2 派单模式及其滚动时域完美匹配算法

为了解决当前抢单模式造成的客户平均等待时间较长和交通隐患问题，提出了由车货匹配平台汇总一定时间段内的车辆与订单信息，然后进行统一匹配的派单模式。在该模式中，关键点在于动态信息的处理和匹配算法的设计。本文利用滚动时域将动态化信息进行静态化处理，运用匈牙利算法进行匹配，提出滚动时域完美匹配算法。

该算法的核心思想：将时间按照滚动时域时长划分为多个时间段，每个时间段即滚动时域t1，每个时域结束时进行订单匹配。匹配时收集该时域的订单和车辆信息，再根据最优匹配算法批量匹配给各车辆到达取货点平均距离最短且符合车容量限制的车辆。

第1步当没有新订单出现时，继续等待。当出现新订单时，等待t1时长后转至第2步。

第2步查询当前待服务订单数和待服务车辆数，转至第3步。

第3步判断待服务订单数是否小于等于待服务车辆数，若是则执行第四步，否则大于车辆数部分的订单等待下次分配，其余订单参与此次分配，转至第4步。

第4步选取所有需服务的订单，排除车辆载重量小于订单容量的车辆。根据各车辆前往多个订单的平均距离最短筛选车辆，选择与订单数相同的车辆数进行匹配，转至第5步。

第6步调用匈牙利算法达成车辆和订单的精确匹配结果，转至第6步。

第6步运用式(1)计算服务完所有订单的平均客户总等待时长。

在该仿真流程中，对于时间的离散化处理是将其划分为多个滚动时域，在每个时域结束时调用滚动时域完美匹配算法并进行更新。

3 仿真分析

为了验证模型与设计算法的正确性和真实有效性，使用数值仿真软件编程，实验运行环境为i7- 4770HQ处理器，16G 内存，Windows10 64 位操作系统。

本文在调查重庆市货拉拉有限公司实际情况基础上，构建以下仿真环境：生成长度为10km范围的方形网络图，1000个客户点，以车辆服务完所有订单的平均客户总等待时长为目标函数，分别设计了抢单模式就近随机配对算法和派单模式滚动时域完美匹配算法进行求解分析，通过分析不同参数对目标函数的影响，解释两种模式目标函数变化的原因，分析不同模式在不同参数影响下的适用性，最终得出结论。

3.1 有效性分析

通过专业的数学仿真软件对派单模式滚动时域完美匹配算法和抢单模式就近随机配对算法进行编程，仿真时间均为120分钟，仿真次数为50次，其中车辆数量m为400辆，订单数量n为500个，单个订单的最多抢单车辆h为10辆，滚动时域时长t1为2分钟，车速v为50km/小时，网络图中任意两点距离大于5km。从表2可以看出，抢单模式平均客户总等待时长为4.7分钟，派单模式为4.5分钟，考虑交通道路拥堵时间，现实中的车辆到达客户取货点时间大约为15～18分钟，差值为合理范围，故本文设计的抢单模式和派单模式均有效。

3.2 适用性分析

分析抢单模式就近随机配对算法和派单模式滚动时域完美匹配算法的适用性，观察订单滚动时域时长、订单数量、车辆数量、网络图任意两点距离对客户平均等待时长的影响。由于订单数量与车辆数量的相对大小变化会对客户平均等待时长造成影响，同时为突出对比在不同参数变化下两种模式客户平均等待时长的差异，故作如下定义。

定义1(订单饱和度) 订单饱和度为订单数量与车辆数量的比值，即订单饱和度=订单数量/车辆数量。

定义2(差异比) 差异比为抢单与派单模式客户平均等待时长差值所占抢单模式比重，即差异比=(抢单客户平均等待时长-派单客户平均等待时长)/抢单客户平均等待时长×100%。

仿真次数均为50次，记录平均值。车辆分为小车型载重800kg，大车型载重1500kg的限制条件，分别采用滚动时域完美匹配算法和就近随机配对算法去服务所有订单。下面将调整各参数变量，记录目标值，并加以分析：

表1 适用性分析表

注：抢单模式无订单滚动时域时长，故取多次仿真平均值

结论1派单模式客户平均等待时长与订单滚动时域时长呈正相关关系。

研究订单的滚动时域时长对目标值的影响，调整订单的滚动时域时长，发现派单模式的客户平均等待时长起初均小于抢单模式平均值，派单模式客户平均等待时长小于抢单模式最高可达10.71%，但随着订单滚动时域时长的增加，派单模式的客户平均等待时长呈上升趋势。由于订单滚动时域时长增加故匹配时间也相应推迟导致平均等待时长增加的现象。

结论2订单饱和度增大，抢单模式与派单模式客户平均等待时长差值由负转正。

研究订单饱和度变化对目标值的影响，通过调整订单和车辆的总数量，改变订单的饱和度，发现抢单模式起初客户平均等待时长小于派单模式，后随着订单饱和度的增加，派单模式等待时长小于抢单模式，且优势持续扩大。从图2中可看出：①当订单饱和度为1.25时，抢单与派单模式客户平均等待时长相等。②当订单饱和度大于1.25且不断增大时，派单模式客户平均等待时长小于抢单模式，派单模式较于抢单模式可节省26.11%的时间。虽然派单模式和抢单模式的客户平均等待时长均增长，但抢单模式呈直线增长，增速较快。这是因为随着订单饱和度的增大，订单数量增加，车辆数远小于订单数量，平均某一订单一定距离范围内的车辆数有限甚至没有车辆，导致客户平均等待时长增加；而在派单模式下，通过某一时段内全局最优的匹配方式，将非最近距离的空闲车辆进行调度达成车辆与客户的匹配，从而减少了客户平均等待时长。③当订单饱和度小于1.25时，抢单模式客户平均等待时长小于派单模式，最多可节省22.5%的时间。由于该情形下，订单数量小于车辆数，在抢单模式中平均某一订单距离范围内的车辆数也较多，于是从距离排序中选取的参与抢单的前h辆车前往取货点距离也较短，即客户等待时长较短。在派单模式下，采用的选取匹配车辆规则为计算车辆到各取货点的平均距离，然后根据平均距离排序进行选择，而抢单模式根据每个订单与车辆距离直接排序。

结论3派单模式与抢单模式客户平均等待时长均与任意两点距离最小值呈正相关关系。

结论4任意两点距离最小值增大，抢单模式与派单模式客户平均等待时长差值由正转负。

研究任意两点距离变化对目标值的影响，发现派单模式和抢单模式下的客户平均等待时长均增长，派单模式起初客户平均等待时长小于抢单模式，且最多可节省6.38%的时间，后随着任意两点距离最小值的增加，抢单模式客户平均等待时长小于派单模式，但两种模式差异不大。由于车辆速度是一定的，故距离的增长必然影响时间的增长，其次抢单模式在距离增加后优于派单模式是因为两种模式的不同车辆选取规则造成的。

实验表明，在相同条件下，当订单滚动时域时长增加、订单饱和度较大、任意两点距离最小值较小时，选用派单模式客户平均等待时长小于抢单模式。由于抢单模式的匹配核心思想是通过随机概率达成车辆与客户的匹配，且在该模式下容易造成局部最优的情况，即车辆只知晓自身当前位置与订单的距离，因此会考虑订单距离较远选择不接单，而实际上其距离相对于其他车辆较近，最终客户订单很长时间才有车辆接单，导致客户平均等待时间较长，而随着订单滚动时域时长和订单数量增加后，派单模式可以实现在一定时间段内的全局最优；当订单饱和度较小和任意两点距离最小值较大时，抢单模式客户平均等待时长小于派单模式，是由于派单模式的匹配思想是根据多个订单多辆车平均距离最短进行最优化匹配而抢单模式是根据单个订单多辆车距离排序。

4 结论

针对车货匹配动态实时性的特点，对同城货运众包平台的车货匹配的抢单与派单模式进行了仿真对比研究，考虑动态的订单饱和度、订单的滚动时域时长、任意两点距离最小值等因素，以客户平均等待时长最短为目标函数，设计了抢单模式的就近随机配对算法和派单模式的滚动时域完美匹配算法，对比了抢单与派单模式平均客户等待时长的差异。

通过数值仿真实验验证了算法的有效性，并且发现当订单滚动时域时长增加、订单饱和度较大、任意两点距离最小值较小时，车货匹配平台适合采用派单模式；当订单饱和度较小和任意两点距离最小值较大时，车货匹配平台适合采用抢单模式。在实际应用中，可将抢单与派单模式相结合进行车货匹配，当订单饱和度随时间段的变化由小变大时，可由抢单模式转变为派单模式，以提高匹配效率。在目前的抢单模式下，车货匹配平台可通过调整总车辆数量、订单数量、分区域抢单，减少客户平均等待时长。研究结果可为众包车货匹配平台订单分配策略提供决策支持，有利于提高客户满意度，增强客户和众包人员对平台的使用粘性，提高平台收益。同城货运众包平台的车货匹配问题进一步还可以研究派单模式下的不同动态匹配算法、不同模式对环境的影响等。