本发明提供了一种最大化承运能力的车货匹配智能决策方法，首先根据货车厂内到达顺序构建动态时间窗口，在各个时间窗内以滞留尾单数最小化为目标用动态规划技术和枚举剪枝策略生成装车清单集合，而后基于车辆与待运输货物的装车清单集合构建车货二部图，再以货物发运重量最大化为目标使用Kuhn‑Munkres算法计算产生车货二部图的最大权匹配结果。特别地，为了优化长期全局货物发运重量最大化，该决策框架使用强化学习技术获取满足货物发运最大化需求的窗口切割策略。
1.一种最大化承运能力的车货匹配智能决策方法，其特征在于，包括以下步骤：步骤S1：对历史数据进行分析，提取货车历史流向数据，包括装车清单数据以及出库清单数据，获得货车运输终点的偏好；
步骤S2：根据顺序到厂的车辆构建自适应时间窗口，在货车到厂时，基于步骤S1分析出的运输终点的偏好，使用动态规划和枚举剪枝策略为每辆货车生成对应的装载计划，确保滞留尾单数最小化，并将货车与运输货物的装载计划加入到当前时间窗口对应的车辆集合与装车清单集合；所述步骤S2具体包括：+
步骤S2.1，定义：车辆节点集合T＝{Tj|j∈N ，1≤j≤M}，Tj为实时到厂车辆列表中的第j辆货车，货车标载上限和下限表示为Twu，Twl；
所有货物表示为C＝{Ci|i∈N ，1≤i≤N}，所有合同运单Wb＝{Wba|a∈N ，1≤a≤Z}，每+件货物都隶属于某一合同运单，表述为{Ci∈Wba，i∈N，1≤i≤N，1≤a≤Z}；
LPS为当前库存货物构成的装载计划集合，表示为LPS＝{LPc|c∈N，1≤c≤K}，其中M是实时到厂车辆数，N为厂内实时货物数，K是运单集合Wb打包后的装载计划数，其中装载计划由LPc＝[d1c，d2c，...，dNc]构成，其中 装载计划决策表示为 一件货物最多只能属于一个装载计划，所以有约束条件
TOS是当前库存中的尾单集合，表述为{Tod∈TOS，d∈N，1≤d≤ψ}，其中ψ为仓库中为尾单数，尾单源自于运单集合，都包含一系列货物；尾单重量小于单车标载，无法独自分配给一辆卡车；
自适应时间窗口为：DTW＝(ll，lr，l，BG)，其中ll为该时间窗内到厂的车辆数，lr为实时库存可发装载计划数量，l表示为自适应时间窗口的大小，BG是自适应时间窗口内车辆集合和可发装载计划集合对应的二部图，表示为BG＝(T，LPS，E)，其中 表示两类节点的边的集合，车辆Tj与装载计划LPc边权值定义为 是LPc的装载重量；
最大化货物发运重量的同时尽可能最小化尾单数量，即库存货封装后的LPS重量最大化，优化目标的公式为 其中wi为货物i的重量；
步骤S2.2，对于顺序到达的货车Tj，加入当前时间窗口的车辆集合T，根据当前车辆的历史流向集合，使用动态规划技术按照步骤S2.1中所述的优化目标对库存中的运单以剩余尾单数最少来对货物进行动态拆分，生成同流向可发装载计划，并加入时间窗口对应二部图中的装载计划集合LPS，剩余未被打包成装载计划的货物，加入尾单集合TOS；
步骤S2.3，对于步骤S2.2中得到的TOS，使用枚举剪枝策略，在不违反拼货规则条件下，组合得到满足重量限制的拼货装载计划，并加入时间窗口对应二部图中的装载计划集合LPS；
步骤S3：结合Q‑Learning算法学习到的历史数据中收益最大的窗口匹配决策，确定切割后待车货匹配的时间窗口大小；
步骤S4：根据步骤S3得到的时间窗口大小，将所有到厂运输的车辆和装载计划作为节点，根据到厂车辆运输终点与装载计划建立连接，构成以发运重量为边权的带权二部图，然后使用Kuhn‑Munkres算法计算该二部图的最大权匹配，保证平台全局发运重量的最大化；
步骤S4.2，根据步骤S3得到的车货二部图BG，二部图中的车辆节点集合T和可发装载计划集合LPS，计算节点之间的边权，得到边权集合E；
步骤S4.3，对于计算边权集合后的二部图BG，使用Kuhn‑Munkres算法计算二部图BG的最大权匹配，得到车货匹配决策CLMD。
2.根据权利要求1所述的最大化承运能力的车货匹配智能决策方法，其特征在于，所述步骤S1具体包括：对来自物流科技公司的真实数据集进行分析，所述真实数据集中包含历史的装载计划和货物出库记录；提取货车司机的历史流向数据中的历史运输流向，以此作为后续二部图匹配的限制与参考。
3.根据权利要求1所述的最大化承运能力的车货匹配智能决策方法，其特征在于，所述步骤S3具体包括：根据步骤S2中得到的自适应时间窗口大小，结合Q‑Learning算法学习到的历史数据中收益最大的窗口切割决策，判断当前时间窗状态是否是最优决策，若是，则做出匹配决策产生窗口切割后对应的待车货匹配的二部图BG，否则时间窗口大小继续扩展，直到得到车货匹配的二部图BG为止。
4.一种最大化承运能力的车货匹配智能决策系统，其特征在于，包括：存储器和处理器；
所述存储器上存储有计算机程序，当所述计算机程序被所述处理器执行时，实现如权利要求1‑3任一项所述的方法。
5.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，所述计算机程序被处理器执行时，实现如权利要求1‑3任一项所述的方法。
一种最大化承运能力的车货匹配智能决策方法及系统
技术领域
[0001] 本发明属于数据挖掘技术领域，具体涉及一种最大化承运能力的车货匹配智能决策方法和系统。
背景技术
[0002] 钢铁物流行业隶属于大宗商品物流行业，区别于其他物流行业，钢铁物流行业运力资源有限，大宗钢铁物流企业普遍存在货物积压问题，货物数量远超过可用的运输能力是常态，在有限运力的情况下最大化货物发运重量一直是亟需解决的问题。
[0003] 大宗钢铁物流传统分货策略是即来即分配，然而这样的分配策略忽略了各个流向运力资源和货物所需运力的平衡，缺乏考虑当前车辆分货结果对未来车货匹配结果的影响，导致各流向运力供需不平衡，使得后续到厂车辆不能及时分配到待运输的货物。此外，传统的车货匹配方法未考虑滞留尾单数最小化这一优化目标，尾货是大宗物流场景一个特有的概念，它指的是合同运单中剩下的待发运货物不满足货车载重下限而滞留的货物，尾单是尾货对应的运单，尾货只能与其他运单货物拼单运输，长时间不能发运导致尾货积压，平台只能通过调度其他运力来完成订单运输，增加了运输成本。为了提高钢铁物流平台的利润，亟需一个智能的车货匹配决策方法解决匹配过程中面临的流向供需不平衡问题与尾单积压问题。
[0004] 现有的关于物流领域任务资源分配的研究成果，大多使用运筹优化等传统方法，这类方法通常是多阶段执行，首先使用预测技术完成各代理供需的预测，再使用组合优化技术完成供需匹配的优化，但是由于这类方法预测阶段与优化阶段存在相互依赖性，所以离线的预测结果容易受到在线的组合优化结果影响而失效。鉴于此，出现了一批协作式多智能体强化学习解决方法，但其强调不同代理之间资源的调度，与大宗钢铁物流的车货匹配工作不符；现有的关于物流领域车货匹配的研究成果，普遍采用启发式算法，这类方法应对发运重量目标优化时能取得不错的结果，但无法实现发运重量目标全局最大化。此外，有部分解决方案使用组合优化的传统方法来解决，但是需要获悉全部待匹配的车货信息，才能保证方案的有效性，这不能满足车货匹配的实时性需求，同时，它们都未关注尾货最少这一优化目标。
发明内容
[0005] 本发明所要解决的技术问题是针对上述现有的技术不足，提供一种最大化承运能力的车货匹配智能决策方法。
[0006] 本发明第一阶段为离线车货匹配决策学习，对于顺序到达的车辆，根据其运输终点，以滞留尾货数最小化为目标生成装载计划，同时，引入滑动窗口模型技术，在各个时间窗口内完成车货匹配决策，而对于自适应的每一个时间窗口大小，利用Q‑Learning技术学习不同车货状态(货车车辆数，待运输货物的装载计划数)下的窗口大小，在学习过程中得到Q表为在线策略提供窗口大小的切割决策支持。
[0007] 本发明的第二阶段为在线车货匹配决策，根据第一阶段得到的Q表，为各个包含顺序到厂的车辆和装载计划对应的时间窗口进行实时决策，得到待车货匹配二部图，利用KM算法获得其最大权匹配，最后生成车货匹配结果，从全局出发逼近离线车货匹配最优解，在有限运力下，最大化车辆承运能力。
[0008] 为了实现上述技术目的，本发明采取以下技术方案：
[0009] 提供一种最大化承运能力的车货匹配智能决策，包含以下步骤：
[0010] 步骤S1：对历史数据进行分析，提取货车历史运输流向数据，包括装车清单数据以及出库清单数据，获得货车运输终点的偏好；
[0011] 步骤S2：根据顺序到厂的车辆构建自适应时间窗口，在货车到厂时，基于步骤S1分析出的运输终点的偏好，使用动态规划和枚举剪枝策略为每辆货车生成对应的装载计划，保证滞留尾单数最小化，并将货车与运输货物的装载计划加入到当前时间窗口对应的车辆集合与装车清单集合；
[0012] 步骤S3：结合Q‑Learning算法学习到的历史数据中收益最大的窗口匹配决策，获得切割后待车货匹配的时间窗口大小；
[0013] 步骤S4：根据步骤S3得到的时间窗口大小，将所有到厂车辆和装载计划作为节点，根据到厂车辆运输终点与装载计划建立连接，构成以发运重量为边权的带权二部图，然后使用KM算法计算该二部图的最大权匹配，保证平台全局发运重量的最大化；
[0014] 为优化上述技术方案，采取的具体措施还包括：
[0015] 上述步骤S1包括：
[0016] 对来自物流科技公司的多个真实数据集进行分析，所述真实数据集中包含历史的装车清单数据集，出库清单数据集以及货物库存数据集。通过分析发现装载计划的分配容易受货车司机的运输偏好因素限制，货车司机是否接受一个装载计划决策与货物流向具有强关联，因为货车司机隶属于地方车队，他们更易于在偏好城市拿到回程货以赚取更多利益，所以本发明提取货车司机的历史运输流向，以此作为后续二部图匹配的限制与参考。
[0017] 上述步骤S2包括：
[0018] 步骤S2.1、定义：车辆节点集合T＝{Tj|j∈N+，1≤j≤M}，Tj为实时到厂车辆列表中+的第j辆货车，货车标载上限和下限表示为Twu，Twl；所有货物表示为C＝{Ci|i∈N ，1≤i≤+
N}，所有合同运单Wb＝{Wbi|i∈N ，1≤i≤Z}，每件货物都隶属于某一合同运单，表述为{Ci+
∈Wbj，i∈N ，1≤i≤N，1≤j≤Z}；LPS为当前库存货物构成的装载计划集合，表示为LPS＝+
{LPj|j∈N ，1≤j≤K}，其中M是实时到厂车辆数，N为厂内实时货物数，K是运单集合Wb打包后的装载计划数，其中装载计划由LPj＝[d1j，d2j，...，dNj]构成，其中
装载计划决策表示为 一件货物最多
只能属于一个装载计划，所以有约束条件 TOS是当前库存中的尾单集合，表
+
述为{Toi∈TOS，i∈N ，1≤i≤ψ}，其中ψ为仓库中为尾单数，尾单源自于运单集合，都包含一系列货物，但尾单重量小于单车标载，无法独自分配给一辆卡车。
[0019] 自适应时间窗口为：DTW＝(ll，lr，l，BG)，其中ll为该时间窗内到厂的车辆数，lr为实时库存可发装载计划数量，l表示为自适应时间窗口的大小，BG是自适应时间窗口内车辆集合和可发装载计划集合对应的二部图，表示为BG＝(T，LPS，E)，其中 表示两类节点的边的集合，车辆Tj与装载计划LPi边权值定义为 是LPi的装载重量；
[0020] 本发明的优化目标是在最大化货物发运重量的同时尽可能最小化尾单数量，即库存货封装后的LPS重量最大化，优化目标的公式可表示为 其中wi为货物i的重量；
[0021] 步骤S2.2，对于顺序到达的货车Tj，加入当前时间窗口的车辆集合T，根据当前车辆的历史流向集合，使用动态规划技术按照步骤S2.1中所述的优化目标对库存中的运单Wb以剩余尾单数最少来对货物进行动态拆分，生成同流向可发装载计划，并加入时间窗口对应二部图中的装载计划集合LPS，剩余未被打包成装载计划的货物，加入尾单集合：TOS。
[0022] 步骤S2.3，对于步骤S2.2中得到TOS，使用枚举剪枝策略，在本发明中，在不违反拼货规则条件下，组合得到满足重量限制的拼货装载计划，并加入时间窗口对应二部图中的装载计划集合LPS；在本发明中，所应用的枚举剪枝策略为分支定界法，一般用于求解整数规划问题，本发明将尾单中的剩余货物拼货问题，看做是整数规划问题，对于TOS中的货物列表{C1，C2，......，Cn}，本发明求解线性最优初始解{l1，l2，......，ln}，其中0≤li≤1，且Twl≤w1·I1+w2·I2+...+wn·In≤Twu，并求出线性最优解对应的整数最优解{i1，i2，......，in}的最大分支节点，作为下次迭代的搜索节点，直到整数最优解无最大分支节点，得到最后的拼货决策。
[0023] 上述步骤S3包括：
[0024] 根据步骤S2中得到的自适应时间窗口大小，结合Q‑Learning算法学习到的历史数据中收益最大的窗口切割决策，判断当前时间窗状态是否是最优决策，如图3所示，根据当前时间窗DTW的状态，Q‑learning算法所学习的决策结果Q表给出最优切割决策，即时间窗口的大小l′，若l′＝l，则执行匹配决策获得窗口切割后对应的待车货匹配的二部图BG，否则时间窗口继续扩展，特别地，直到得到车货匹配的二部图BG为止。
[0025] 上述步骤S4包括：
[0026] 步骤S4.1，给出定义：车货匹配决策 其中一个装载计划最多只能分配到一辆货车，所以有约束条
件
[0027] 步骤S4.2，根据步骤S3得到的车货二部图BG，二部图中的车辆节点集合T和可发装载计划集合LPS，计算节点之间的边权，得到边权集合E。
[0028] 步骤S4.3，对于计算边权集合后的二部图BG，使用KM算法计算BG的最大权匹配，具体来讲：对于二部图中的每个卡车节点，KM算法首先搜索出能其匹配的最大权重的装载计划节点，若有装载计划节点被分配两辆不同货车，KM算法为则在该匹配结果上搜寻增光路径，使得每个装载计划只分配给一个车次且与每个货车匹配的装载计划尽可能大，最终得到BG的最大权匹配，即车货匹配决策CLMD。
[0029] 基于以上方法，本发明还提出了一种最大化承运能力的车货匹配智能决策系统，包括：存储器和处理器；所述存储器上存储有计算机程序，当所述计算机程序被所述处理器执行时，实现上述的方法。
[0030] 本发明还提出了一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时，实现上述的方法。
[0031] 本发明具有以下有益效果：
[0032] 1、本发明利用自适应时间窗口和强化学习技术，优化运力资源使用效率，能够保证全局发运重量最大化，提高平台收益；
[0033] 2、本发明引入滞留尾单数最小化的优化目标，产生的装载计划最大限度减少尾单数，即在单天车货匹配过程结束后，最大限度地减少滞留尾单数，减少平台额外调度的运力，减少运输成本。
附图说明
[0034] 图1是动态规划拆分订单生成装载计划算法的流程图。
[0035] 图2是分支定界法求解剩余货物拼车生成装载计划算法的流程图。
[0036] 图3是基于Q‑Learning算法的车货匹配决策学习流程图。
[0037] 图4是基于Q‑Learning算法的车货匹配决策实施流程图。
具体实施方式
[0038] 结合以下具体实施例和附图，对发明作进一步的详细说明。实施本发明的过程、条件、实验方法等，除以下专门提及的内容之外，均为本领域的普遍知识和公知常识，本发明没有特别限制内容。
[0039] 本发明提供了一种最大化承运能力的车货匹配智能决策方法，首先根据货车厂内到达顺序构建动态时间窗口，在各个时间窗内以滞留尾单数最小化为目标用动态规划技术和枚举剪枝策略生成装车清单集合，而后基于车辆与待运输货物的装车清单集合构建车货二部图，再以货物发运重量最大化为目标使用KM算法计算产生车货二部图的最大权匹配结果。特别地，为了优化长期全局货物发运重量最大化，该决策框架使用强化学习技术获取满足货物发运最大化需求的窗口切割策略。
[0040] 本发明第一阶段为离线车货匹配决策学习，顺序到达的车辆根据运输终点，按照滞留尾货数最小化生成装载计划，一起加入到当前时间窗口对应的车辆集合与装车清单集合，在该时间窗口内完成车货匹配，并利用Q‑Learning算法学习匹配决策，最后得到训练匹配好的分货决策Q表；本发明的第二阶段为在线车货匹配决策，根据第一阶段得到Q表，为各个包含顺序到厂的车辆和对应的装载计划时间窗实时做出决策，得到待车货匹配二部图，利用KM算法得到最大权匹配，最后得到车货匹配结果。
[0041] 动态规划拆分订单装载计划集合生成算法描述如图1所示。
[0042] 对于货物列表CLj，根据其总重量、件重、件数生成装车类型列表LPType，构造动态规划矩阵dp，其中dp[i][j]表示当重量为j，选择第i种装车类型时所剩货物的最小重量，状态转移方程为： 使用状态转移方程更新动态规划矩阵dp，并根据dp[i][j]对应的拆分策略，将货物列表CLj拆分成重量为LPType[i]的整车订单，并加入装载计划集合LPS，未被打包成装载计划的剩余货物加入TOS。
[0043] 图2给出了剩余货物拼车生成装载计划的算法描述。
[0044] 对于TOS中的每件货物，首先通过拼货限制条件获取可以拼货的货物列表CML，其中CML＝[C1，...，Cn]，基于此构建0‑1整数规划问题，限制条件为：Twl‑wi≤C1·i1+C2·i2+...+Cm·im≤Twu‑wi，i1，...，im∈{0，1}，然后使用上文所述的分支定界法求解该0‑1整数规划问题，将获得拼货生成的装载计划加入LPS，对应的货物同时从TOS中移除。
[0045] 图3给出了基于Q‑Learning算法的车货匹配决策学习流程图。
[0046] 首先初始化涉及决策的Q表，顺序到达的车辆根据运输终点，按照滞留尾货数最小化生成装载清单集合，一起加入自适应时间窗口，每到厂一辆车则更新自适应时间窗口，并根据Q表做出分货决策。若做出匹配决策，则将当前时间窗转换为二部图，图的边权为装载计划的装载重量，对加权二部图使用KM算法计算其最大权匹配，得到即时分货决策收益与时间窗口的下一个状态，并根据Q‑Learning算法对应的Bellman方程更新Q表中的状态‑动作价值；若未做出匹配决策，则即时收益为零，车辆继续到厂得到下一个状态的时间窗口，同样根据Bellman方程更新Q表，决策更新直到训练结束。
[0047] 图4给出了基于Q‑Learning算法的车货匹配决策实施流程图。
[0048] 顺序到厂的车辆根据运输终点，按照滞留尾货数最小化生成装载计划集合，一起加入自适应时间窗口，货车每次到厂，都会引起时间窗口内状态的改变，根据训练好的Q表，实时生成分货决策，若执行匹配决策，则将当前时间窗转换加权二部图，使用KM算法计算其最大权匹配，得到分货决策结果LPD；若未实施匹配决策，则等待下一辆货车到厂，直到车货匹配动作完成，进行下一轮的车货匹配。
[0049] 通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到上述实施例方法可借助软件的方式来实现，当然也可以通过硬件，但很多情况下前者是更佳的实施方式。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来。
[0050] 本发明的保护内容不局限于以上实施例。在不背离本发明构思的精神和范围下，本领域技术人员能够想到的变化和优点都被包括在本发明中，并且以所附的权利要求书为保护范围。
