随着交通运输物流领域中信息化应用的普及，相关数据环境已经拥有大量的运输车辆和货物等物流信息资源，为了解决货运业务中车源和货源信息不对称造成的车辆闲置和空驶等问题，出现了大量物流公共信息平台或配货网站用于促进车源和货源信息的流通与共享，在大规模的数据资源中如何为物流供需资源产生合理的匹配方案也是一种组合优化问题，即车货匹配问题（Vehicle Cargo Match，VCM），与VRP问题不同的是，VCM问题主要解决运输资源如何匹配与推荐，用于形成资源分配预选方案。在实际应用的业务场景中，VRP问题应属于VCM问题的后续过程，首先应在大量的运输资源中筛选出运输条件和运输要求相似的车源信息和货源信息集合，然后通过车货匹配算法形成匹配方案并推荐给车主和货主进行业务对接和确认，最后车主根据已经确认的货物信息进行路径和时间的规划，形成运输车辆调度方案。总体业务流程如图4.15所示。

图4.14　模拟实时流式数据聚类结果

图4.15　总体业务流程图

针对VCM问题，近几年相关研究主要集中在配货平台运营机制和信息化技术手段，但是作为物流信息平台核心功能之一的车货供需匹配方法，其相关研究较少，目前主要有两类方法。第一类从信息语义检索角度出发，针对物流信息规范化程度低造成的用户查询效率低下、体验差等问题，建立车源和货运信息语义知识模型，通过其语义推理能力，实现更复杂的供需关系语义检索与推荐，此类方法由于知识语义建模过程与推理过程较为烦琐等原因，造成在实际应用中较难实现。第二类方法首先为车货信息资源建立评价指标体系，使用相关评判方法，根据历史信息为车源与货源的匹配程度进行评价和综合排序，此类方法需要大量收集与指标体系相关的业务数据后进行评价，给用户体验造成了一定的影响，产生的匹配方案受主观评价因素影响也较大，此类方法在进行评价和匹配时主要针对的是每个车源或货源，没有从整体考虑资源的统一分配问题，容易造成“优秀资源总是被推荐，新资源难于被发现”的恶性循环，即新资源的“零启动”问题。另外，以上两类方法均没有考虑大数据环境中流式数据的特殊性以及车货匹配的实时性需求，无法在实际应用中体现物流供需信息资源的动态性，也无法为用户提供及时更新的物流供需匹配方案。

1.车货信息匹配模型构建

设需要为K（k=1，2，3，…，K）辆车和I（i=1，2，…，I）个货物运输需求进行匹配，已知每辆车的运输能力为bk，每个货物需求为di，lki为车辆当前所在位置与货物所在位置的距离，所有车辆与货物需求点组成距离矩阵为L，车辆与货物需求的一个匹配xki定义为

定义1　由所有匹配xki组成的矩阵VCM（Vehicl-Cargo Matrix）为车货匹配问题的一个解。VCM每一个行向量对应每一辆车的匹配方案，每一个列向量对应每一个货物运输需求的匹配方案。

定义2　VCM匹配率R的计算公式为

针对车货匹配模型的假设条件如下：

（1）在进行匹配过程的时间窗口内，待匹配货物所在位置不变；

（2）在进行匹配过程的时间窗口内，已知车辆的位置是近似固定不变的；

（3）待匹配货物的位置在待匹配车辆最远行驶距离之内；

（4）待匹配车辆运输能力不同且运输能力已知；

（5）待匹配货物重量不同且货物重量已知；

（6）参与匹配过程的车辆的运输载运条件与货物运输需求方所要求的条件相符。

为了充分利用车源和货源信息，匹配过程需要考虑追求最大化的车货匹配率R，还要综合考虑匹配后所有推荐方案所产生的总体成本C最小，成本函数C由车辆当前位置与货物的起运位置的距离、用户时间窗口和货物目的地距离等变量综合构成，目标函数定义如下：

其中w1和w2为平台决策者对成本和匹配率两个指标的偏好，设w1+w2=1，易证目标函数在［0，1］区间上。

证明：设Zmax为目标函数的理论最大值，则

基于上述模型参数、模型假设条件与目标函数分析，其中成本函数C被简化为车辆当前位置与货物的起运位置需要行驶的距离，在实际应用中可以根据具体需要构建其他形式的成本函数。车货匹配模型如下：

约束公式（4.7）限制每个货物运输需求至多有MI个匹配车辆；约束公式（4.8）限制每辆车至多匹配MK个货物运输需求；约束公式（4.9）要求每辆车匹配的所有的货物运输需求的总体货物重量要小于gbk，使得运输能力强的车辆能够获得更多的匹配方案；约束公式（4.10）给每辆车推荐的每个方案中的货物重量都小于运输车辆的载重，避免给车推荐超重的货物。

其中，约束公式（4.7）和约束公式（4.8）用于控制匹配方案的数量，可以用于针对车辆和货物的Top-N匹配推荐应用中，当待匹配的车辆和货物数量较多时，应设置MI≪I，MK≪K。

定义3　车货匹配问题弱可行解的定义：满足约束公式（4.10）的解，既所有的匹配满足车辆的载重能力大于货物的重量。

定义4　车货匹配问题强可行解的定义：满足车货匹配问题所有约束的解。

由定义易证，强可行解集合属于弱可行解集合，当MI=I，MK=K且g→∞时，强可行解集合与弱可行解相等。车货匹配问题模型的目标为找到目标函数最大的强可行解。

2.基于QEA的车货信息匹配方法

量子进化算法（Quantum-inspired Evolutionary Algorithm，QEA）建立在量子态矢量表述方式的基础上，将量子比特的概率幅表示作用于染色体的编码，使得个体的每个染色体可以同时表达多个状态的叠加，并利用最新个体信息使用量子旋转门来调整量子比特概率幅，实现染色体的更新操作，并加速算法收敛，从而实现目标的优化求解，与传统的进化计算方法相比其特点是能用规模小的种群实现较大空间的搜索，具有较强的全局搜索能力。由于量子计算的并行性大大地降低了算法的复杂度，被广泛地用于解决需要大量计算空间的组合优化问题中。

在量子计算中，量子比特位充当信息存储单元的物理介质，它是一个双态量子系统，简称量子位，与对应的经典位不同，量子位可以同时处在两个量子态的叠加态之中。

其中α、β为复数，分别表示|0＞和|1＞的概率幅度，且满足

在量子进化算法中，采用量子比特位存储和表达一个状态。该状态可以为一个“0”态或“1”态，或它们的任意叠加态。所以量子位所表达的信息不唯一，而是包含所有可能的信息，对该量子位的任一操作也不会只作用于一条信息。一个有n个量子位的量子个体可以基于概率幅表示2n种量子状态，其表现形式为

采用量子比特位表示的量子个体能够丰富种群的多样性，体现更好的全局搜索能力，避免进化算法陷入局部最优解。

QEA的进化过程采用量子旋转门U（θ）改变量子比特的概率幅，使量子个体逐渐逼近最优解。量子旋转门计算公式为：

其中［α'，β'］T为经过量子旋转门进化后新的量子比特概率幅，θ为旋转角并满足以下公式：

S（α，β）和△θ分别用于确定旋转的方向和角度增量。

由于量子位具有量子个体可以表示若干个量子位状态叠加的特殊表现形式，从而一个小种群的量子个体可以对应普通表示方法下的极大数量个体，与传统进化方法相比，QEA具有更丰富的种群多样性，同时基于量子旋转门的量子群进化方式有着较强的全局搜索能力。随着量子群的进化，算法逐渐收敛，每个量子个体的量子位取1或0的概率逐渐趋近于1。

1）量子个体编码设计

量子个体Q的比特位编码长度为K×I，第n个比特位的αn在初始状态随机给出，并根据公式（4.13）给出对应位置上的βn。定义Q的第n个量子比特位测量值为

其中thn为每次量子进化后，针对每一个比特位随机给出的阈值，且满足0＜thn＜1，则αn越小量子个体的第n个量子比特位表现为1的概率越大。量子个体测量值由每一个量子比特位测量值组成。

对车货匹配问题采用二进制编码设计，使每个量子个体测量值代表一种匹配方案，并与车货匹配矩阵对应。解码过程需要将量子个体的每一个比特位的测量值与VCM矩阵的每一项元素进行映射，映射关系为

每一个量子个体的测量值对应一个车货匹配问题的解。

2）有约束惩罚的量子适应度函数

根据车辆匹配模型的目标函数公式（4.4）定义量子个体的适应度函数为：

其中

因为量子个体的测量值Qψ取决于当前测量阈值与测量比特位的取值，不能确定在进化后相同量子个体的测量值一定是相同的，因此一个量子个体对应的解是否为强可行解并不是确定的，拥有较高适应度的弱可行解量子个体，有可能在下一代量子群中测量为拥有较高适应度的强可行解量子个体，即当代量子群的最优强可行解可能由上一代的弱可行解量子个体进化后测量得到。为了使量子群在进化过程中，保持较优弱可行解量子个体的信息，增强量子进化过程的全局搜索能力，需要对弱可行解的适应度进行适当的惩罚后，参与最优量子个体的竞争。

定义5　一个弱可行解转换为强可行解的距离ξ定义为

其中IMV为Qψ中不符合约束公式（4.6）或者约束公式（4.8）的车辆个数，IMC为不符合约束公式（4.7）的货物个数。若在量子群初始化和进化过程中能够保证每个量子个体对应的解为弱可行解，即满足约束公式（4.9），则当ξ=0时，表示量子个体对应的解为强可行解。

引进有约束惩罚的量子适应度函数对弱可行解量子个体的适应度进行惩罚。公式为：

(www.daowen.com)

公式（4.23）产生的适应度惩罚效果主要用于当量子群中的个体不存在强可行解时，如何在弱可行解中选取最优的量子个体。

3）量子旋转门设计

确定量子旋转角公式（4.16）中的S（α，β）和Δθn需建立选择策略表，如表4.4所示。

表4.4　旋转角选择策略

4）算法流程

基于以上算法设计，有约束惩罚的QEA求解车货匹配问题的算法可以分为量子群初始化、量子个体适应度计算、选取最优量子个体、算法退出条件判断、量子群进化和最优量子个体解码等6个阶段，算法总体流程如图4.17所示。

图4.16　量子旋转门策略

图4.17　算法流程图

Step1.量子群初始化：在进行量子群初始化时需首先给定车货匹配模型的相关参数K、I、L、bk、di、w1、w2、MI、Mk、g，给定量子个体的数量P和比特位的长度（K×I），随机给出每个量子个体的初始测量阈值thn和比特位量子态α=β=。

Step2.量子个体适应度计算：根据公式（4.17）确定每一个量子个体的初始测量值Qψ。检测量子个体测量值为1的比特位，不符合约束公式（4.10）则将该比特位的测量值设置为0，同时该比特位量子态设置为α=1，β=0，使得所有量子个体测量值对应的解至少为弱可行解。根据初始测量值Qψ和公式（4.22）确定每个量子个体的ξ值，根据约束惩罚适应度函数公式（4.23）得到每个量子个体的适应度。

Step3.选取最优量子个体：若当前量子群存在强可行解，即ξ=0，则将强可行解的量子个体与历史最优量子个体BestQψ的适应度进行比较，保存最优强可行解量子个体为BestQψ。若不存在强可行解，则保存最优弱可行解量子个体为BestQψ。

Step4.算法退出条件判断：算法退出的前提是历史最优量子个体BestQψ为强可行解，且同时满足以下条件之一：F（BestQψ）大于某给定阈值，或量子群进化次数大于某给定阈值。算法退出判定成功则进入Step6，否则算法转向Step5。

Step5.量子群进化：给定量子旋转门的角度增量△θ，按照前文所述的旋转策略和公式（4.15）、公式（4.16）对每个量子个体的比特位量子态进行改进，生成新一代量子群。算法转向Step2。

Step6.最优量子个体解码：根据公式（4.19）将历史最优量子个体的测量值解析为SVM并输出结果。

3.仿真实验与结果分析

实验运行环境为CPU 2.5GHz，内存4GB，使用JDK1.6编程。目前针对车货匹配问题的实验数据还没有标准的测试数据库，而且为了能够使用遍历算法在可行的时间内得到精确解并与QEA算法最优解进行比较，本书限制了实验数据的规模，实验数据包括5辆车与6个货物运输需求，如表4.5所示，其中bk列为每辆车的运输能力（吨），di行为每种货物运输需求量（吨），其他表示货物点与车辆的距离（km）。

表4.5　实验数据表

设车货匹配问题模型的相关参数分别为K=5，I=6，w1=0.6，w2=0.4，MI=MK=4，g=2，L、bk和di如表4.5所示。本书首先使用遍历方法求出了以上数据的精确解，所有车货匹配方案共25×6=1073741824种，遍历算法每秒解析并计算约50000个方案，用时约6小时，得到此问题的精确解适应度为0.283226。

1）算法性能分析

实验分析中引进了量子个体成熟度（Quantum Maturity Value，QMV）与量子群体成熟度两个指标。量子个体Q的成熟度为：

QMV可以用于说明量子个体测量值的稳定性，成熟度越大，代表其测量值的随机性越低。量子群体成熟度（Quantum Swarm Maturity Value，QSMV）定义为量子群中所有量子个体成熟度的平均值。QSMV越大则量子群活性越低，算法收敛程度越高。

量子进化算法相关参数分别为：量子群规模为100个量子个体；进化次数为1000次；△θ=0.01π。算法用时约0.6秒，得到最优强可行解为0.28320，算法在第358次进化时首次得到该最优解。量子群进化过程如图4.18所示。

图4.18　量子进化算法收敛过程

当QSMV较小时，量子群中的量子个体的量子态差别不大，表现为测量值随机性较大，表现出较强的全局搜索能力，当QSMV较大时，虽然量子群中的量子个体已经普遍失去活性，测量值都已趋于稳定，但是算法依然可以在一定范围内进行搜索优化，如表4.6所示，当进入第358次进化后，QSMV＞0.8，算法依然3次搜索到了更好的最优强可行解。

表4.6　量子进化过程适应度与QSMV变化表

经过多次实验发现当QSMV＞0.98后，由于量子群过于成熟，其测量值已经趋于稳定，很难产生更优秀的强可行解，因此，QSMV可以作为量子进化算法退出判定的辅助条件。

使用相同的车货匹配模型、参数和数据，将QEA算法和标准遗传算法（Genetic Algorithm，GA）进行比较，设定种群数量同样为100个，随机独立运行30次，算法结果统计指标如表4.7所示。

表4.7　QEA与GA算法对比

由统计结果可见，QEA算法与遗传算法GA相比具有更优秀的性能。

在算法收敛速度方面，QEA算法平均进化191次即可以获得当前种群最优解，而GA算法平均需要进化463次，说明QEA算法可以用更少的迭代次数获得最优解，收敛速度更快。

在算法准确性方面，QEA在30次独立运行后与精确解相比平均误差为3.3E-05，GA算法的平均误差为24.2E-05，QEA平均误差比GA降低了86%，说明QEA拥有更优秀的准确性以及更好的全局搜索能力。

在算法稳定性方面，QEA算法30次运行结果的标准差为10.81E-05，而GA算法为16.02E-05，说明QEA算法30次运行的结果值更集中稳定。

2）算法参数影响分析

设置量子个体数量分别为50、100、150、200、250、300，其他参数同上，针对不同的量子个体数量，算法分别独立随机运行10次，结果如表4.8所示。当量子群规模较小时，算法耗费时间短，但是算法收敛速度、准确性和算法稳定性较差。当量子群规模较大时，算法耗费时间较长，但是算法收敛速度、准确性和算法稳定性较优。对于实验环境给定的数据和算法参数，发现算法的计算机耗时和收敛速度随量子群规模变化呈现近似线性变化，计算机耗时随量子群规模的扩大稳定增长，而收敛速度也稳定增加。但是算法的准确性和稳定性存在“规模瓶颈”现象，当量子群规模达到100以上时，算法准确性和稳定性提高得并不明显。对于实际应用中的车货匹配问题应根据其问题规模和计算环境能力综合考虑设置量子群规模。

表4.8　不同量子群规模算法效果对比

设定量子旋转角增量△θ分别为0.0001π、0.001π和0.01π，量子群规模为100，其他参数同上。QEA算法分别在第3018次、782次和387次进化时搜索得到了精确解。算法进化过程如图4.19所示，量子群成熟度进化曲线如图4.20所示。

当△θ=0.0001π时，算法具有较强的搜索能力，量子群成熟速度较慢，能够获得更多的较优强可行解，但是算法收敛速度较慢，需要更多的进化次数才能搜索到最优强可行解。当△θ=0.01π时，算法收敛速度较快，虽然能够很快地得到最优强可行解，但是由于量子群成熟过快，对于更大规模的车货匹配问题容易陷入局部搜索，失去了搜索更多强可行解的机会，有可能使得算法精确度降低。因此，△θ值的选择对算法的效率有着较大的影响，△θ值太大可能会使结果发散或过早收敛到局部最优解，△θ值太小则可能会使算法收敛缓慢，造成需要过多的迭代次数才能获得更优秀的解。

图4.19　不同旋转角增量下适应度进化过程

图4.20　不同旋转角增量下量子种群成熟度进化过程

4.大规模流式数据环境下车货实时匹配方法框架

物流运输中的车源数据和货源数据来自实时数据自动采集环境，如车辆通过车载设备实时上报位置和运输状态信息，货物通过移动终端扫描二维码或者现场业务处理功能上传数据，这些数据具有明显的量大、覆盖面广、更新频繁以及价值密度低等流式数据特征，数据的流速、流量、流向复杂多变。流式数据环境下车货实时匹配方法的主要作用在于能够在大规模的流式数据环境中稳定高效地对车货信息资源进行处理，对时间维度、空间维度和业务属性维度进行综合分析，从而提高信息资源利用效率，产生更加合理的、满足物流配货业务实时性要求的车货匹配方案。

大规模流式数据环境下的车货实时匹配方法分为在线和离线两个部分，在线部分主要是实现针对无界持续动态车货数据的实时处理以及按类型筛选；离线部分的主要作用是在指定的时间窗内完成对多维度车货数据进行聚类与匹配处理。如图4.21所示。

图4.21　大规模流式数据环境下的车货实时匹配方法流程示意图

1）在线部分

步骤1　通过分布式队列服务器实时获取车源与货源信息。

步骤2　按照货物类型和车辆运载条件对车源与货源信息进行筛选，相同类型的车辆货物信息归并到同一个车货类型数据集中。同时对数据集中已有的车源与货源信息进行实时更新。

2）离线部分

步骤3　微聚类：在设置好的时间窗内执行以下操作，对在线部分已筛选的每一个同类型车货数据集，使用基于距离的聚类算法，得到空间距离较近的多个车货类簇。在下一个时间窗中重新获取同类型车货数据集并执行步骤3。

步骤4　车货匹配：在设置好的时间窗内，对上一步骤得到的车货类簇利用进化算法对其进行车货供需匹配方案组合优化，形成车货匹配推荐方案并保存到目标存储位置。相关信息服务和功能通过访问存储位置中的最新匹配方案结果实现车货资源的实时匹配。

其中步骤1中分布式消息队列服务器可以使用Apache Kafka来实现，针对不同终端上传的车源与货源的流式数据建立实时动态消息队列服务，实现消息传递服务与业务逻辑解耦，增强流式数据处理的可靠性，实现流式数据的送达保证与顺序保证；步骤2～4可用实时计算框架Apache Storm来实现，具体来说，步骤2中通过Apache Storm中的spout组件实现在分布式消息队列服务器中按流式数据送达顺序先入先出地获取车源数据与货源数据，其中车源信息状态包括车辆信息新增、车辆状态更新和车辆信息退出。货源信息状态包括货源信息新增和货源信息退出。按照已经定义好的类型特征划分车货类型，相同车货类型的数据给予相同且唯一的类型ID。根据类型ID字段进行分组，在Apache Storm的计算拓扑结构中分割流式数据，实现不同类型车货数据集在不同Bolt中的分布式处理。步骤3中要使用Apache Storm的Bolt组件建立一个用于在不同类型车货数据集中进行距离聚类的Bolt层，该层的Bolt接收上一步骤分发的车货数据，按照车货数据状态更新自己所负责处理的车货数据集，并按距离进行聚类，形成车货类簇，之后采用随机分组的方式将不同的车货类簇随机分发给下一个Bolt层。步骤4中同样使用Apache Storm的Bolt组件建立一个用于在不同车货类簇中进行匹配计算的Bolt层，使用上一层Bolt随机分发的车货类簇进行车货匹配计算，计算方法可以参考前文介绍的基于量子进化算法的车货匹配方法，最终车货匹配方案数据的存储使用Apache Hbase实现。整个过程的技术实现框架如图4.22所示。

图4.22　流式数据环境下车货实时匹配技术实现框架