基于TS算法的公路干线货运平台车货匹配研究

， ，

(浙江理工大学，a.理学院；b.经济管理学院,杭州 310018)

公路货运在我国货物运输行业中占有重要地位，目前我国公路货运量占全国货运总量的75%左右。以2017年为例，当年全国货运总量479.4亿吨，其中公路货运量为368.0亿吨，占比76.8%[1]。然而，我国公路货运多年来一直存在着“散、乱、差”的局面：市场中90%为运输业个体户；车辆等待回程货的平均时间是72小时，平均回程空驶率为44%[2]。公路货运市场出现如此局面的原因是整个市场中存在严重的信息不对称。虽然货运中介的出现一定程度上使得这类问题有所缓解，但车货信息往往经过多个中介的转手导致信息传递缓慢，物流成本增加。随着互联网和智能手机的普及，“平台+App”车货匹配模式出现，匹配重心开始由线下向线上移动端转移，匹配对象从货运中介变为车主与货主双方。

双边市场是利用一个或多个双边平台实现用户的交互，并通过对双方收取合理的费用而将其维持在平台上的市场[3]。公路货运市场由车主和货主两方进行交互，因此属于典型的双边市场，平台在其中发挥着重要作用。Armstrong等[4-5]认为，市场中的某些活动必须借助平台来完成，平台通过为双方提供产品或服务来促成交易并从中获取利润，平台中一方用户获得的利益多少取决于另一方用户的规模大小。Abrahamsson等[6]认为，物流平台是信息管理与控制中心，是物流系统非常重要的一部分。宋娟娟等[7]对公路货运平台发展现状及运营机制进行了分析，指出平台在发展过程中应解决好“鸡蛋相生”问题。张松[8]对南京市三种货运配载模式进行了对比分析，发现基于物流平台的车货匹配模式具有一定优势。公路货运市场中的车货匹配属于典型的双边匹配问题。Gale等[9]对双边匹配问题进行了开创性研究，并用Gale-Shapley算法成功解决了婚姻匹配问题，证明稳定的婚姻匹配总是存在的。Zhang等[10]以滴滴出行平台为例，在考虑司机接单概率的情况下，建立了最大化订单成交率的滴滴出租车分单模型。陈静[11]在分析公路货运平台订单分配问题现状的基础上，建立了订单分配模型，提高了运输资源利用率。陈火根等[12]将配载过程分解为资源分类、资源匹配、交易协商三个子任务，在此基础上设计了在线算法对车货双方进行匹配，通过原型系统实验证明：基于网格技术的货物配载系统不仅可以方便地集成异构系统，而且可以确保配载处理的实时性。李玉花[13]建立了以能力和资源限制为约束条件，以物流供需匹配度大化为目标的流线型优化模型。李慧[14]通过把影响车货双方匹配的指标划分为硬指标和软指标的方法，建立了以匹配度最大为目标的车货配载多目标匹配排序模型。

我国公路干线货物运输具有很强的季节性和区域性：春夏季相对于秋冬季而言货源较少，西部地区相对于东部地区而言货源较少。淡季时货物数量少，可以利用穷举的方法求得最优匹配调度方案；旺季时货物数量较多，穷举方法求解耗时过长，需要利用启发式算法进行求解。求解匹配调度问题的算法主要有粒子群算法(Particle swarm optimization，PSO)、禁忌搜索算法(Tabu search，TS)、蚁群算法(Ant colony optimization，ACO)、遗传算法(Genetic algorithm，GA)，以及各种算法的改进算法、混合算法等。其中TS算法是求解匹配调度问题的常用有效算法。Montané等[15]建立了具有最大行程约束的随机车辆调度模型，并通过TS算法求解取得了较好的效果。Brandal[16]采用TS算法研究了不同车型对车辆调度问题求解效果的影响。郎茂祥等[17]构造了求解车辆匹配调度问题的新禁忌搜索算法，并通过实验进行模拟计算，结果表明该算法求解车辆调度问题具有较好的效用。刘兴等[18]在TS算法的基础上提出了一种新算法，将车辆匹配调度问题按不同的车辆和顾客分解成若干子问题，然后用TS算法求解每个子问题，并从所有子问题的最优解中选出全局最优解。

目前大多数对于平台车货匹配的研究是建立在车主和货主与平台无合作或从属关系的背景下，匹配以交易撮合、提高推荐成功率为目的。平台如何提高车货双方的可控性，发挥宏观匹配调度作用，提高匹配效率，降低物流成本将是亟待解决的问题。本文提出平台利用信用评价体系筛选高信用车主，与其合作成立虚拟车队，进而对车货双方进行匹配调度的新思路。建立运力可控情景下的车货匹配调度模型，给出求解算法，并通过不同算法对比分析来验证TS算法的求解性能。本文的研究结论可为线上货运平台的未来发展提供理论参考。

一、车货匹配模型建立

(一)问题描述

从“车多货少”的实际背景出发，根据文献[15]建立的信用评价体系，对车货双方信用情况进行评价，淘汰低信用的车主与货主，筛选出高信用的车货双方。对于筛选出的高信用车主，线上平台与之合作成立虚拟车队实现运力可控。某时刻某区域内虚拟车队中存在不同车型、不同载重水平的车辆，如果只进行一对一整车匹配可能出现较多车辆低满载的情况，而通过一车对多货的调度匹配可以有效提高车辆满载率，降低物流成本。因此，本文在考虑车货双方信用的基础上，建立无配送中心、多车型、先集货再送货并以最小匹配成本为目标的一对多车货匹配调度模型。匹配调度成本分为两部分，即从车辆当前位置到货主处的空驶成本和车辆载货行驶的载货成本。假设：

a)货主与目的地一一对应，每个货主与其对应的目的地都要被匹配且只能匹配一次；

b)货主给定的时间为要求车主到达目的地的最晚时间，考虑信用评价体系的稳定性，平台匹配时不允许车主迟到；

c)同一车主可以匹配一位或多位货主，但每阶段只允许匹配一次；

d)不同货主的货物可以相互拼装；

e)同一车辆载货成本仅与车辆单位距离行驶成本和行驶距离有关，与载货量等无关；

f)不同车辆空驶成本和载货成本不同；

g)运输过程中采取“人歇车不歇”的不间断运输方式；

h)车辆停留装卸货时间为常数，不考虑货物吨位等因素对车辆装卸货时间的影响；

i)车货双方经过平台信用筛选，车主的信用不小于平台允许其加入虚拟车队的信用，货主的信用不小于平台允许其参加匹配的信用；

j)车辆行驶距离Djk用两点(Xj,Yj)和(Xk,Yk)之间的经纬度距离表示：

(二)符号说明

V：车主集合；

G：货主集合；

F：目的地集合；

m：车主数量；

n：货主数量；

i：车主编号；

j：车主、货主以及目的地的编号；

k：车主、货主以及目的地的编号；

C:匹配的运输成本；

Eei：车主的车辆单位空驶成本；

Efi：车主的车辆单位满载成本；

Li：车主的车辆最大载重量；

TGk：货主给定要求货物送达目的地的时间；

Tij：车主到j的实际时间；

Tα：车主每次停留装卸货时间；

v：车主的车辆平均行驶速度；

Wj：货主的货物重量；

RVi：车主信用值；

RGj：货主信用值；

RVα：平台允许加入虚拟车队的最小车主信用值；

RGα：平台允许参与匹配的最小货主信用值。

(三)车货匹配模型

为发挥平台宏观匹配调度的作用，实现提高车货匹配效率、降低社会物流总成本的目的，本文以最小化匹配成本为目标建立车货匹配模型，该模型可以用公式表示为：

(1)

aij=ai(j+n)，j∈G

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

式(1)是目标函数，匹配总运输成本最小，成本分为空驶成本和载货成本；式(2)是货主与对应目的地匹配，即若车主与货主匹配，则车主也与货主对应的目的地也匹配；式(3)是所有货主均被匹配；式(4)—(5)是目的地的车辆流入流出平衡；式(6)—(10)是车辆行驶路径约束，即车主不能从当前位置到其他车主位置、不能从当前位置直接到目的地、不能从货主位置到车主位置、不能从目的地到车主位置、不能从目的地到货主位置；式(11)是车辆载重约束，与车主匹配的货物总量不能超过车的载重；式(12)是时间约束，车主运输到达目的地的时间不能超过货主给定的时间；式(13)—(14)是决策变量。

二、基于TS算法的模型求解

TS算法最早由Glover于1986年提出，是一种模仿人类记忆功能的算法。它的基本思想是：为了找到“全局最优解”，不应执着于某一特定区域，因此在搜索全局最优解的过程中，标记对应已搜索的局部最优解的对象，在进一步迭代搜索中有意识地避开它，从而获得更多的搜索区间。TS算法中有三个重要的概念：禁忌表、禁忌长度和特赦准则。禁忌表是用来存放禁忌对象的容器，禁忌表中的对象在解禁之前不能被再次搜索。禁忌表的大小影响搜索速度和解的质量：禁忌表长度过小，搜索可能进入死循环；禁忌表过大则限制了搜索区域，好的解可能不会被搜索到。禁忌长度是指禁忌对象在禁忌表中被禁忌的步数。特赦准则是用来释放特定解，实现全局优化搜索的准则，当全部候选解或优于当前最优解的候选解被禁时，特赦准则就会发挥作用。TS算法流程如图1所示，具体步骤如下：

a)给定禁忌长度等参数，随机产生一个初始解，并清空禁忌表；

b)判断是否满足终止条件，若满足则停止搜索，输出最优值，否则进行步骤c)；

c)利用当前解的邻域函数，产生所有或若干邻域解，从中选定若干解作为候选解；

d)判断候选解是否满足特赦准则，若满足则执行步骤f)，否则执行步骤e)；

e)判断候选解的禁忌属性对候选解所对应的各种对象进行分析，选择在候选解中且不在禁忌表中的对象对应的最佳状态作为新的当前解，并将该对象对应的禁忌对象替换掉原有的禁忌对象；

f)执行步骤b)。

图1 TS算法流程图

由于以最小成本为目标的一对多车货匹配问题不但涉及车货双方是否匹配，还涉及匹配后的路径规划，且路径中集货地与送货地是一一对应的，所以在设计TS算法编码时采取将编码分为两段的方法。车主与货主段编码组成第一部分，其作用是判定车货匹配，并确认车辆在车主与货主之间以及货主与货主之间的行驶路径。目的地编码为第二部分，其作用是确认车辆在货主和目的地之间，以及目的地与目的地之间行驶路径。

对于m个车主，n个货主，货主对应的目的地有n个。为了方便解释TS算法的编码与解码过程，下面以m=4，n=3为例进行演示。

1.编码方法

a)将编码(m+2n-1)分为两部分：编码第一部分从1至(m+n-1)，编码长度为(m+n-1)，将这部分编码的类别设为1；编码第二部分从(m+n)至(m+2n-1)，编码长度为n，将这部分编码的类别设为2。当m=4，n=3时，第一部分编码为1至6，第二部分编码为7至9。编码及其类别如表1所示。

表1 编码及其类别

b)计算维数为(m+2n-1)的邻域解位置，设定位置中各维度的取值范围为[0,1]。经过计算得到各个编码的取值，编码取值组成邻域解的位置，邻域解位置如表2所示。

表2 邻域解位置

2.解码方式

a)根据邻域解位置中各维度取值的大小进行映射解码。其中第一部分按照位置取值从小到大的顺序分别映射为1至(m+n-1)之间的数字。以邻域解1位置为例，第一部分1至6的编码位置取值按从小到大顺序的映射为2、4、3、5、6、1，如表3所示。

表3 邻域解映射

b)从映射后数字1至(m+n-1)中选取最小的(m-1)个数字作为分割点，用Y表示该映射为分割点，N表示该映射为非分割点。邻域解1共产生三个分割点，对应编码为1、3、6，编码分割点如表4所示。

表4 分割点

c)(m-1)个分割点将编码拆分为m段，对应m辆车。m段按照编码从小到大的顺序再次映射为(m+1)到(m+n)之间的数字，此时映射的数字即为与该车主匹配的货主。邻域解1中三个分割点将编码拆分为四段，第一段车主1无匹配的货主，第二段车主2匹配货主5，第三段车主3匹配货主6、7，第四段车主4无匹配的货主，匹配解码如表5所示。

表5 匹配解码

d)比较与车主匹配的货主邻域解位置中各维度取值的大小，按照每段中从小到大的顺序，确定车辆行驶路径。车主2从当前位置到货主5处，车主3从当前位置先到货主6再到货主7的位置，货主路径解码如表6所示。

表6 货主路径解码

e)对于第二部分，由于货主与目的地位置一一对应且编号相差n，第一部分车货匹配后，车与目的地也是匹配的，只需按照位置取值从小到大确定行驶顺序即可。车主2与货主5匹配，则车主2与货主5对应的目的地8也匹配，且路径顺序为：2→5→8。车主3与货主6和7匹配，则车主3与货主6、7对应的目的9、10也匹配，且路径是顺序为：3→6→7→10→9。路径解码如表7所示。

表7 目的地路径解码

3.更新迭代编码与解码

a)对邻域解中任意两个编码的位置进行互换。当编码长度较小时，可以选取并计算所有编码两两位置互换的邻域解；当编码长度较大时，为减少运算量可以选取并计算部分编码位置互换的邻域解。以邻域解1中编码2和3的互换为例，如表8所示。

表8 编码位置互换

b)按照解码方式对调换位置的编码进行解码，得到新的车货匹配方案和新的车辆行驶路径：车主3匹配货主5、6、7。对应的车辆行驶路径为：3→5→6→7→8→10→8，如表9所示。

表9 更新迭代编码与解码

若此时求得的匹配结果优于更新迭代前，则将车主3与货主5的匹配加入到禁忌表中，进行下一次迭代更新；当该禁忌表中的匹配超过禁忌步长时，则将该匹配移出禁忌表。

三、案例分析

货车帮是一个互联网货车车库平台，成立于2011年，2013年货车帮App发布。该平台通过“货车帮车主”端整合车主、“货车帮货主”端整合货主的方式，现已积累了大量的用户。货车帮的车货匹配模式主要有主动、被动、推荐三种。主动模式下，货主可以利用车库功能，主动筛选所需车辆并联系车主沟通运价达成交易；而车主可以通过对货源进行筛选并主动联系货主沟通运价的方式找货。被动模式下，货主可以选择将出发地、目的地、需要车长车型、货物类型、货物重量、运费金额、装车时间、装卸方式、付款方式等信息发布到平台，等待车主联系达成交易；车主则可以通过车主端发布出发地、目的地、重量等货物需求信息的方式找货。推荐模式下，当货主需要发货时，平台会优先向货主推荐与其发生过交易的车主；而除了车主可以通过订阅路线功能及时收到订阅路线上的货运信息外，平台还会根据车主出发地和目的信息将周边货源推荐给车主。货车帮作为信息交互平台，并不实际参与到车货双方匹配交易中去，车主与货主将交易信息发布到平台后，双方根据需要进行自由匹配交易。

(一)TS算法模型求解

从货车帮平台采集某时刻浙江到京津冀地区所有车源和货源信息。由于货物本身的价值通常高于运费的价格，交易中货主承担的风险高于车主，因此取RVα=0.9,RGα=0.7。筛选所有车主与货主后剔除低信用者，剩余共60位车主和35位货主。假设经过筛选的车主均同意与平台建立合作关系，加入虚拟车队成为可控运力。

1.小规模车货数量求解

选取10位车主和7位货主作为求解数据。其中，车主编号为1—10，货主编号为11—17，货主对应的目的地编号为18—24。最大迭代次数设置为200，禁忌长度设置为20，选取全部的邻域解作为候选解。Matlab R2016a在配置为i5-3337U，CPU@1.8GHz的环境下运行38.74 s，得到最小匹配成本23966.92元。车货匹配结果如表10所示。

表10 小规模TS算法匹配结果

从表10可以看出，共用5位车主即可匹配完全部7位货主，且车辆载重率均较高，减少了运力浪费。通过与Lingo穷举思想下求得的“精确解”对比，发现其求解结果与“精确解”结果完全一致，证明TS算法在求解小规模车货匹配问题上具有较好性能。

2.大规模车货数量求解

对车主与货主以及目的地进行编号：车主编号为1—60，货主编号为61—95，目的地编号为96—130。最大迭代次数设置为200，禁忌长度设置为20，由于邻域解数量较大，为了减少求解时间，仅选取4%的邻域解作为候选解。Matlab运行127.95 s，得到最小匹配成本115000.86元，其迭代收敛图像如图2所示。

图2 TS算法迭代收敛图像

在大规模车货数量情况下，TS算法在第15次迭代中出现可行解，并持续搜索在第140次迭代中得到最终解，说明该算法具有较好的全局和局部搜索能力。得到的最终匹配中，23位车主将35位货主匹配，车主车辆载重率均较高，有效地减少了车辆空载或非满载造成的资源浪费。匹配结果相关信息如表11所示。

表11 大规模TS算法匹配结果

(二)算法性能比较分析

PSO算法是求解匹配调度问题的常用算法之一。为验证TS算法在求解大规模车货数量上的性能是否具有优越性，本文引入PSO算法和PSO-TS混合算法(Particle swarm optimization and tabu search hybrid algorithm，PSO-TS)进行对比分析。取采集到的全部60位车主和35位货主作为大规模车货匹配数据，最大迭代次数设置为800，某次求解三种算法迭代收敛图像如图3所示。

图3 不同算法迭代收敛图像

TS算法在第21次迭代中开始出现可行解，在第651次迭代中得到最终解；PSO算法在第148次迭代中开始出现可行解，在第725次迭代中得到最终解；PSO-TS算法在第166次迭代中开始出现可行解，在第718次迭代中得到最终解。从图3可以看出，与PSO和PSO-TS算法相比，TS算法不但搜索能力强，收敛速度快，而且最终得到的匹配成本也更小。

为了减小单次求解带来的随机性影响，相同数据下利用三种算法分别进行多次求解，从求得可行解概率、求解平均时间、最小匹配成本均值三个方面对算法在大规模车货数量情况下的求解性能进行统计。

a)求得可行解概率：TS算法在多次求解中均能得到可行解；PSO算法得到可行解的概率仅为10%；PSO-TS算法求得可行解的概率为85%。

b)求解平均时间：TS算法求解平均时间为499.12 s；PSO算法在10%的概率求得可行解情况下，求解平均时间为81.19 s；PSO-TS算法在85%的概率求得可行解情况下，求解平均时间为570.26 s。

c)最小匹配成本均值：TS算法最小匹配成本均值为121027.47元；PSO算法在10%的概率求得可行解情况下，最小匹配成本均值为144224.07元；PSO-TS算法在85%的概率求得可行解情况下，求得最小匹配成本均值为131874.02元。

从统计结果来看，TS算法求解性能最好，PSO-TS算法次之，PSO算法求解性能最差。TS算法在大规模车货数量求解中，不但可以在相对短的时间内求得“满意解”，且在求解稳定性和求解结果上明显优于PSO和PSO-TS算法。

四、结 论

本文针对公路干线货运平台在车货匹配效率不高，且现有研究大都以撮合双方提高交易成功率为目的的问题，提出了基于信用评价体系掌握可控运力，并以最小匹配成本为目标的车货匹配新模式。在新模式下，由于运力是可控的，因此车货双方交易成交概率为100%。在建立模型的基础上，利用TS算法对从货车帮平台采集到的不同规模车主与货主数据进行求解。通过与Lingo“精确解”对比，发现TS算法在小规模车货数量情况下具有较好的求解性能；通过与PSO和PSO-TS混合算法求“满意解”性能上的表现，发现TS算法在大规模车货数量情况下具有相对更好的求解性能。实验结果表明，新车货匹配模式和TS算法在提高车货匹配效率，降低车辆空载率，减少物流成本上具有有效性，为公路货运平台发展提供了一定的理论参考。

本文建立的车货匹配模型适用于公路干线中长途货运的车货匹配，对于同城以及干线短途车货匹配而言，先集货后送货的方式往往导致匹配调度成本增加，因此模型具有一定的应用局限性。另外，本文提出的车货匹配调度模型是建立在车主与平台合作基础上，至于两者如何建立合作关系，以及双方利益分配问题将是未来研究方向之一。