本发明适用于装箱问题优化技术领域，尤其涉及一种考虑货物库存成本的卡车货物分配优化方法，包括以下步骤：利用贪心策略，将所有货物分配至库存成本为零的卡车中，直到所有库存成本为零的卡车的分配量达到最大值，得到初步分配方案；根据未被分配的货物与未被分配货物的卡车建立总成本最小化分配模型并求解，获得总成本最小化分配方案；合并初步分配方案和总成本最小化分配方案，得到分配组合方案，将分配组合方案中未被分配的货物使用货物再分配算法进行再次分配，得到货物再分配方案，并使用模拟退火算法迭代优化货物再分配方案，得到最终分配方案。本发明可以减少人工安排货物到卡车中的工作量，减少了时间损耗。
1.一种考虑货物库存成本的卡车货物分配优化方法，其特征在于，所述卡车货物分配优化方法包括以下步骤：S1、利用贪心策略，将所有货物分配至库存成本为零的卡车中，直到所有所述库存成本为零的卡车的分配量达到最大值，得到初步分配方案；
S2、根据步骤S1中未被分配的所述货物与未被分配所述货物的所述卡车建立总成本最小化分配模型，并进行求解，获得总成本最小化分配方案；
S3、合并所述初步分配方案和所述总成本最小化分配方案，得到分配组合方案，按照所述分配组合方案进行装箱优化计算，将所述分配组合方案中未被分配的所述货物使用货物再分配算法进行再次分配，得到货物再分配方案，并使用模拟退火算法迭代优化所述货物再分配方案，得到最终分配方案，之后，按照所述最终分配方案在所有所述卡车中进行所述货物的装载；
S11、初始化包含所有未被分配的所述货物的数据的货物列表，同时，初始化包含所述库存成本为零的卡车的数据的计划卡车列表，其中，所述货物的键值为所述计划卡车列表的哈希值，所述计划卡车的键值为所述货物列表的哈希值；
S12、在所述货物列表中，计算每一个所述货物的货物优先分配分数，并按照所述货物优先分配分数的大小对所述货物列表中的所述货物进行降序排序；
S13、对所述货物列表进行遍历，并将遍历的所述货物移出所述货物列表，若无法完全遍历，执行步骤S14；若遍历完成，执行步骤S19；
S14、对遍历到的每一个所述货物，获取其对应的所述计划卡车列表，并计算所述计划卡车列表中对应所述卡车的卡车优先分配分数，并按照所述卡车优先分配分数的大小对所述计划卡车列表中的所述卡车进行降序排序；
S15、对所述计划卡车列表进行遍历，若完全遍历，执行步骤S16；若无法完全遍历，执行步骤S17；
S16、将完成遍历的所述货物放回所述货物列表，并返回步骤S13；
S17、判断被遍历的所述货物是否满足被遍历的所述卡车的装载约束，若是，执行步骤S18；若否，返回步骤S15；
S18、根据被遍历的所述卡车，从所述计划卡车列表中生成一个包含被遍历的所述货物的已分配货物列表；
S19、对所述已分配货物列表进行遍历，若完成遍历，将当前的分配结果输出作为所述初步分配方案；若无法完全遍历，执行步骤S110；
S110、判断所述卡车分配到的所有所述货物是否满足预设体积限制参数，若是，执行步骤S111；若否，返回步骤S19；
S111、将所述卡车分配到的所有所述货物放回所述货物列表中，并返回步骤S19；
其中， 表示第 种货物分配到第 种卡车上的数量， 表示第 种卡车是否使用，表示第 种卡车使用的数量， 表示货物库存成本的权重， 表示调用卡车的运输成本的权重， 表示第 种货物最晚到达工厂的时间， 表示第 种卡车到达工厂的时间，表示第 种货物的库存成本， 表示第 种卡车是否已经使用了计划卡车，表示第 种卡车的计划卡车的调用费用， 表示第 种卡车的额外卡车的调用费用， 表示第 种货物的数量， 表示第 种货物能满足时间窗约束以及装载约束装入第 种卡车中， 表示第 种货物的重量， 表示第 种货物的体积， 表示第 种卡车的最大允许承重， 表示第 种卡车的容积， 表示卡车的最大允许容积，表示极大数；
为决策变量，a表示货物，b表示卡车，s表示货物的总数；
步骤S3中，合并所述初步分配方案和所述总成本最小化分配方案，得到分配组合方案，按照所述分配组合方案进行装箱优化计算，将所述分配组合方案中未被分配的所述货物使用货物再分配算法进行再次分配的步骤，包括以下子步骤：S31、从所有所述卡车中，选择可以装载至少一个剩余货物的所述卡车，并放入卡车选择列表中；
S32、计算所述卡车选择列表中每一所述卡车的剩余货物分配数量；
S33、建立以所述剩余货物为键，所述计划卡车列表为键值的剩余货物分配列表，以及一个包含未装载所述货物的额外卡车的额外卡车列表；
S34、遍历所述剩余货物分配列表，若其中的每一所述剩余货物都有对应的键值，将当前的分配结果输出作为所述货物再分配方案；若否，执行步骤S35；
S35、从所述额外卡车列表中选择所述额外卡车加入所述计划卡车列表；
S36、计算所述计划卡车列表中每一所述卡车的优先分配分数，并按照所述优先分配分数的大小对所述计划卡车列表进行降序排序；
S37、对所述计划卡车列表进行遍历，若完全遍历，执行步骤S310；若无法完全遍历，执行步骤S318；
S38、判断被遍历的所述剩余货物是否满足被遍历的所述卡车的装载约束，若是，执行步骤S39；若否，返回步骤S37；
S39、将所述剩余货物分配至被遍历的所述卡车，并重新计算所述卡车的装载约束；
S310、判断是否存在所述剩余货物没有被分配到所述计划卡车列表中的任何一辆所述卡车之中，若是，执行步骤S311；若否，返回步骤S34；
S311、根据所述计划卡车列表中排序最前的所述卡车生成属性相同的一辆所述额外卡车，并将所述剩余货物分配至所述额外卡车中。
2.如权利要求1所述的考虑货物库存成本的卡车货物分配优化方法，其特征在于，步骤S12中，所述货物优先分配分数满足：；
其中， 表示所述货物优先分配分数， 表示所述货物的每日库存成本， 表示所述货物的体积， 表示所述货物在所述货物列表中所述键值对应的所述计划卡车列表的长度。
3.如权利要求1所述的考虑货物库存成本的卡车货物分配优化方法，其特征在于，步骤S14中，所述卡车优先分配分数满足：；
其中 ， 表示所 述卡车 优先分配 分数 ， 、分别表示已经分配到所述卡车上的所有所述货物的体积、重量，表示所述卡车需要到达的所有供应商取货点的数量。
4.如权利要求1所述的考虑货物库存成本的卡车货物分配优化方法，其特征在于，步骤S36中的所述优先分配分数满足：；
其中， 表示所述优先分配分数， 表示所述剩余货物分配数量， 分别表示所述货物最晚到达工厂的时间、所述卡车到达工厂的时间、所述卡车中已经分配到的所有所述货物的总体积、所述卡车中已经分配到的所有所述货物的总重量。
5.如权利要求1所述的考虑货物库存成本的卡车货物分配优化方法，其特征在于，步骤S3中，所述使用模拟退火算法迭代优化所述分配组合方案，得到最终分配方案的步骤，包括以下子步骤：S312、以所述货物再分配方案作为初始解，使用退火算法计算第一函数解，得到目标函数值 ：；
其中，和 分别为货物库存成本 的权重和卡车调用成本 的权重，表示所述卡车的数量， 表示每一辆所述卡车中装入的所述货物的数量， 为惩罚项；
S313、从 中随机选出两辆所述卡车，并随机将两辆所述卡车中库存成本不为零的所述货物进行调换，按照S312的函数值计算方法计算第二函数解，得到第二函数值 ；
S314、判断 是否小于 ，若是，转到步骤S315；若否，转到步骤316；
S315、用所述第二函数解替换所述第一函数解，并更新 为，之后，执行步骤S317；
S317、判断迭代次数是否已经达到等温迭代次数 ，若否，迭代次数加1，返回步骤S313；
S318、判断温度是否已经达到终止温度，或忍耐不接受更优解的次数 是否已经达到设定忍耐次数，若否，使温度 减1，返回步骤S313；若是，输出当前的所述第二函数解作为所述最终分配方案。
6.如权利要求5所述的考虑货物库存成本的卡车货物分配优化方法，其特征在于，步骤S316中，所述 准则满足：；
其中 ， 为 所述 准 则执行 时 将 更 新 为的概率。
考虑货物库存成本的卡车货物分配优化方法
技术领域
[0001] 本发明适用于装箱问题优化技术领域，尤其涉及一种考虑货物库存成本的卡车货物分配优化方法。
背景技术
[0002] 企业在生产过程中，一般需要从不同供应商采购零件包装成货物，并使用卡车将货物运输到工厂处进行产品加工。对于大型生产企业而言，供应链往往涉及数十个城市的几千家供应商以及几十个工厂。企业每一个生产周期都需要安排大量的卡车往返于供应商和工厂，而货物占地庞大且库存有限，需要将货物在指定的时间段到达工厂，货物在工厂积压会产生库存成本以及卡车调运需要运输成本，面对庞大的供应链和复杂的采购需求，不合理的安排策略不仅会降低生产效率，还会造成巨大的利润损失。
[0003] 对于大型生产企业而言，由于每一次采购零件运输货物需要涉及到众多的供应商以及不同种类的货物，并且还要考虑装载约束、货物到达工厂的硬时间窗约束以及卡车的承重约束、体积约束等众多约束，人工计算特别困难，完成耗时较久，效果不佳。分配问题属于组合优化问题，时间复杂度会随着问题规模增大迅速增长，现有技术中，采用单一的精确式算法以及智能优化算法在货物种类上万、卡车数量过千等数据规模庞大的情况下无法在可接受时间内寻找到较优解；另外一方面，由于规模庞大，简单使用贪心策略求解分配问题的结果也并不理想。
发明内容
[0004] 本发明旨在解决现有技术对于数据规模庞大的卡车货物分配问题较难得到最优解的技术问题。
[0005] 为解决上述技术问题，本发明实施例提供一种考虑货物库存成本的卡车货物分配优化方法，所述卡车货物分配优化方法包括以下步骤：
[0006] S1、利用贪心策略，将所有货物分配至库存成本为零的卡车中，直到所有所述库存成本为零的卡车的分配量达到最大值，得到初步分配方案；
[0007] S2、根据步骤S1中未被分配的所述货物与未被分配所述货物的所述卡车建立总成本最小化分配模型，并进行求解，获得总成本最小化分配方案；
[0008] S3、合并所述初步分配方案和所述总成本最小化分配方案，得到分配组合方案，按照所述分配组合方案进行装箱优化计算，将所述分配组合方案中未被分配的所述货物使用货物再分配算法进行再次分配，得到货物再分配方案，并使用模拟退火算法迭代优化所述货物再分配方案，得到最终分配方案，之后，按照所述最终分配方案在所有所述卡车中进行所述货物的装载。
[0009] 更进一步地，步骤S1包括以下子步骤：
[0010] S11、初始化包含所有未被分配的所述货物的数据的货物列表，同时，初始化包含所述库存成本为零的卡车的数据的计划卡车列表，其中，所述货物的键值为所述计划卡车列表的哈希值，所述计划卡车的键值为所述货物列表的哈希值；
[0011] S12、在所述货物列表中，计算每一个所述货物的货物优先分配分数，并按照所述货物优先分配分数的大小对所述货物列表中的所述货物进行降序排序；
[0012] S13、对所述货物列表进行遍历，并将遍历的所述货物移出所述货物列表，若无法完全遍历，执行步骤S14；若遍历完成，执行步骤S19；
[0013] S14、对遍历到的每一个所述货物，获取其对应的所述计划卡车列表，并计算所述计划卡车列表中对应所述卡车的卡车优先分配分数，并按照所述卡车优先分配分数的大小对所述计划卡车列表中的所述卡车进行降序排序；
[0014] S15、对所述计划卡车列表进行遍历，若完全遍历，执行步骤S16；若无法完全遍历，执行步骤S17；
[0015] S16、将完成遍历的所述货物放回所述货物列表，并返回步骤S13；
[0016] S17、判断被遍历的所述货物是否满足被遍历的所述卡车的装载约束，若是，执行步骤S18；若否，返回步骤S15；
[0017] S18、根据被遍历的所述卡车，从所述计划卡车列表中生成一个包含被遍历的所述货物的已分配货物列表；
[0018] S19、对所述已分配货物列表进行遍历，若完成遍历，将当前的分配结果输出作为所述初步分配方案；若无法完全遍历，执行步骤S110；
[0019] S110、判断所述卡车分配到的所有所述货物是否满足预设体积限制参数，若是，执行步骤S11；若否，返回步骤S19；
[0020] S111、将所述卡车分配到的所有所述货物放回所述货物列表中，并返回步骤S19。
[0021] 更进一步地，步骤S12中，所述货物优先分配分数满足：
[0022]
[0023] 其中，freightScore表示所述货物优先分配分数，costi表示所述货物的每日库存成本，volumei表示所述货物的体积，truckListSize表示所述货物在所述货物列表中所述键值对应的所述计划卡车列表的长度。
[0024] 更进一步地，步骤S14中，所述卡车优先分配分数满足：
[0025]
[0026] 其中，truckScore表示所述卡车优先分配分数，usedVolumej、usedWeightj分别表示已经分配到所述卡车上的所有所述货物的体积、重量，supplierDockNumj表示所述卡车需要到达的所有供应商取货点的数量。
[0027] 更进一步地，步骤S2中，所述总成本最小化分配模型满足：
[0028]
[0029] 其中，xij表示第i种货物分配到第j种卡车上的数量，yj表示第j种卡车是否使用，numj表示第j种卡车使用的数量，α表示货物库存成本的权重，β表示调用卡车的运输成本的权重，lti表示第i种货物最晚到达工厂的时间，eti表示第i种货物最早到达工厂的时间，eti表示第j种卡车到达工厂的时间，costi表示第i种货物的库存成本，uj表示第j种卡车是否已经使用了计划卡车，planCostj表示第j种卡车的计划卡车的调用费用，extraCost表示第j种卡车的额外卡车的调用费用，freightNumi表示第i种货物的数量，canPickupij表示第i种货物能满足时间窗约束以及装载约束装入第j种卡车中，weighti表示第i种货物的重量，volumei表示第i种货物的体积，maxWeightj表示第j种卡车的最大允许承重，maxVolumej表示第j种卡车的容积，γ表示卡车的最大允许容积，maxValue表示极大数；
[0030] 所述总成本最小化分配模型的目标满足：
[0031]
[0032] 更进一步地，步骤S3中，合并所述初步分配方案和所述总成本最小化分配方案，得到分配组合方案，按照所述分配组合方案进行装箱优化计算，将所述分配组合方案中未被分配的所述货物使用货物再分配算法进行再次分配的步骤，包括以下子步骤：
[0033] S31、从所有所述卡车中，选择可以装载至少一个剩余货物的所述卡车，并放入卡车选择列表中；
[0034] S32、计算所述卡车选择列表中每一所述卡车的剩余货物分配数量；
[0035] S33、建立以所述剩余货物为键，所述计划卡车列表为键值的剩余货物分配列表，以及一个包含未装载所述货物的额外卡车的额外卡车列表；
[0036] S34、遍历所述剩余货物分配列表，若其中的每一所述剩余货物都有对应的键值，将当前的分配结果输出作为所述货物再分配方案；若否，执行步骤S35；
[0037] S35、从所述额外卡车列表中选择所述额外卡车加入所述计划卡车列表；
[0038] S36、计算所述计划卡车列表中每一所述卡车的优先分配分数，并按照所述优先分配分数的大小对所述计划卡车列表进行降序排序；
[0039] S37、对所述计划卡车列表进行遍历，若完全遍历，执行步骤S310；若无法完全遍历，执行步骤S318；
[0040] S38、判断被遍历的所述剩余货物是否满足被遍历的所述卡车的装载约束，若是，执行步骤S39；若否，返回步骤S37；
[0041] S39、将所述剩余货物分配至被遍历的所述卡车，并重新计算所述卡车的装载约束；
[0042] S310、判断是否存在所述剩余货物没有被分配到所述计划卡车列表中的任何一辆所述卡车之中，若是，执行步骤S311；若否，返回步骤S34；
[0043] S311、根据所述计划卡车列表中排序最前的所述卡车生成属性相同的一辆所述额外卡车，并将所述剩余货物分配至所述额外卡车中。
[0044] 更进一步地，步骤S36中的所述优先分配分数满足：
[0045]
[0046] 其中，score表示所述优先分配分数，loadableNum表示所述剩余货物分配数量，lt、at、usedVolume、usedWeight分别表示所述货物最晚到达工厂的时间、所述卡车到达工厂的时间、所述卡车中已经分配到的所有所述货物的总体积、所述卡车中已经分配到的所有所述货物的总重量。
[0047] 更进一步地，步骤S3中，所述使用模拟退火算法迭代优化所述分配组合方案，得到最终分配方案的步骤，包括以下子步骤：
[0048] S312、以所述货物再分配方案作为初始解，使用退火算法计算第一函数解，得到目标函数值f(oldSolution)：
[0049]
[0050] 其中，α和β分别为货物库存成本的权重和卡车调用成本的权重，n表示素数卡车的数量，m表示每一辆所述卡车中装入的所述货物的数量，ξ为惩罚项；
[0051] S313、从f(oldSolution)中随机选出两辆所述卡车，并随机将两辆所述卡车中库存成本不为零的所述货物进行调换，按照S312的函数值计算方法计算第二函数解，得到第二函数值f(newSolution)；
[0052] S314、判断f(newSolution)是否小于f(oldSolution)，若是，转到步骤S315；若否，转到步骤316；
[0053] S315、用所述第二函数解替换所述第一函数解，并更新f(oldSolution)为f(newSolution)，之后，执行步骤S317；
[0054] S316、用Metropolis准则接受差解；
[0055] S317、判断迭代次数是否已经达到等温迭代次数l，若否，迭代次数加1，返回步骤S313；若是，执行步骤S318；
[0056] S318、判断温度T是否已经达到终止温度，或patientNum是否已经达到设定忍耐次数，若否，使温度T减1，返回步骤S313；若是，输出当前的所述第二函数解作为所述最终分配方案。
[0057] 更进一步地，步骤S316中，所述Metropolis准则满足：
[0058] Δf＝f(newSolution)‑f(oldSolution)
[0059]
[0060] 本发明所达到的有益效果，在于利用贪心策略、模型求解、智能启发式算法逐步缩小卡车分配货物问题的规模，并进行分阶段优化，使得卡车分配货物问题可以在较短时间内寻找到较优解，而且解的质量相比于简单的贪心策略明显更优，在实际部署时，能够运行于现有的计算机设备上，可以减少人工安排货物到卡车中的工作量，减少了时间损耗。
附图说明
[0061] 图1是本发明实施例提供的考虑货物库存成本的卡车货物分配优化方法的步骤流程示意图。
具体实施方式
[0062] 为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。
[0063] 请参照图1，图1是本发明实施例提供的考虑货物库存成本的卡车货物分配优化方法的步骤流程示意图，所述卡车货物分配优化方法包括以下步骤：
[0064] S1、利用贪心策略，将所有货物分配至库存成本为零的卡车中，直到所有所述库存成本为零的卡车的分配量达到最大值，得到初步分配方案。
[0065] 具体的，大规模多约束卡车货物分配问题的数学模型由于决策变量和约束条件过多而无法直接求解，所以，在本发明实施例中，首先使用贪心策略缩小问题规模。为了避免贪心过程对后面优化步骤造成较大影响而使结果过多偏离最优解，贪心过程仅分配库存成本为零，即卡车刚好能够在货物的时间窗最后一天将货物运送到卸货点的货物至卡车之中。
[0066] 更进一步地，步骤S1包括以下子步骤：
[0067] S11、初始化包含所有未被分配的所述货物的数据的货物列表，同时，初始化包含所述库存成本为零的卡车的数据的计划卡车列表，其中，所述货物的键值为所述计划卡车列表的哈希值，所述计划卡车的键值为所述货物列表的哈希值。
[0068] 具体的，初始化未分配的货物列表notDistributeFreightList，初始化键为货物freight，值为计划卡车列表truckList的哈希表freightTruckListMap以及键为卡车truck，值为货物列表freightList的哈希表truckFreightListMap，在freightTruckListMap之中，计划卡车列表中的所有计划卡车都可以装载与计划卡车列表对应的货物，且所有计划卡车的到达工厂时间均处于货物的允许最晚到达工厂时间，即库存成本为零。
[0069] S12、在所述货物列表中，计算每一个所述货物的货物优先分配分数，并按照所述货物优先分配分数的大小对所述货物列表中的所述货物进行降序排序。
[0070] S13、对所述货物列表进行遍历，并将遍历的所述货物移出所述货物列表，若无法完全遍历，执行步骤S14；若遍历完成，执行步骤S19。
[0071] 遍历降序完毕的notDistributeFreightList中每一个freight并将freight移出。
[0072] S14、对遍历到的每一个所述货物，获取其对应的所述计划卡车列表，并计算所述计划卡车列表中对应所述卡车的卡车优先分配分数，并按照所述卡车优先分配分数的大小对所述计划卡车列表中的所述卡车进行降序排序。
[0073] S15、对所述计划卡车列表进行遍历，若完全遍历，执行步骤S16；若无法完全遍历，执行步骤S17。
[0074] 遍历降序完成的truckList中每一辆truck。
[0075] S16、将完成遍历的所述货物放回所述货物列表，并返回步骤S13。
[0076] 将遍历的freight放回所述货物列表。
[0077] S17、判断被遍历的所述货物是否满足被遍历的所述卡车的装载约束，若是，执行步骤S18；若否，返回步骤S15。
[0078] 具体的，本发明实施例中的所述装载约束指容积约束以及承重约束。
[0079] S18、根据被遍历的所述卡车，从所述计划卡车列表中生成一个包含被遍历的所述货物的已分配货物列表。
[0080] 由遍历到的truck在truckFreightListMap之中得到一个货物列表，将遍历到的freight从notDistributeFreightList移出放入该列表之中。
[0081] S19、对所述已分配货物列表进行遍历，若完成遍历，将当前的分配结果输出作为所述初步分配方案；若无法完全遍历，执行步骤S110。
[0082] S110、判断所述卡车分配到的所有所述货物是否满足预设体积限制参数，若是，执行步骤S11；若否，返回步骤S19。
[0083] S111、将所述卡车分配到的所有所述货物放回所述货物列表中，并返回步骤S19。
[0084] 步骤S1使用零库存成本贪心分配，仅仅分配了一部分库存成本为零的货物到一部分计划卡车之中。
[0085] 更进一步地，步骤S12中，所述货物优先分配分数满足：
[0086]
[0087] 其中，freightScore表示所述货物优先分配分数，costi表示所述货物的每日库存成本，volumei表示所述货物的体积，truckListSize表示所述货物在所述货物列表中所述键值对应的所述计划卡车列表的长度。该分数的意义是优先分配单位体积库存成本较大且仅能被少数计划卡车装载的货物。
[0088] 更进一步地，步骤S14中，所述卡车优先分配分数满足：
[0089]
[0090] 其中，truckScore表示所述卡车优先分配分数，usedVolumej、usedWeightj分别表示已经分配到所述卡车上的所有所述货物的体积、重量，supplierDockNumj表示所述卡车需要到达的所有供应商取货点的数量。该分数的意义是让货物尽量被分配到要到达更少的供应商取货点且已经分配了多个货物的卡车中。
[0091] S2、根据步骤S1中未被分配的所述货物与未被分配所述货物的所述卡车建立总成本最小化分配模型，并进行求解，获得总成本最小化分配方案。
[0092] 具体的，多约束卡车货物分配问题指给定总数量为m的货物列表M和总数量为n的卡车列表N，要求在满足装载约束、时间窗约束、体积约束、重量约束等多种约束条件下，将M中的m个货物分配到N中的p(p≤n)辆卡车中，目标是最小化货物到达工厂时产生的库存成本和调用卡车时产生的运输成本。
[0093] 更进一步地，步骤S2中，所述总成本最小化分配模型满足：
[0094]
[0095] 其中，xij表示第i种货物分配到第j种卡车上的数量，yj表示第j种卡车是否使用，numj表示第j种卡车使用的数量，α表示货物库存成本的权重，β表示调用卡车的运输成本的权重，lti表示第i种货物最晚到达工厂的时间，eti表示第i种货物最早到达工厂的时间，eti表示第j种卡车到达工厂的时间，costi表示第i种货物的库存成本，uj表示第j种卡车是否已经使用了计划卡车，planCostj表示第j种卡车的计划卡车的调用费用，extraCost表示第j种卡车的额外卡车的调用费用，freightNumi表示第i种货物的数量，canPickupij表示第i种货物能满足时间窗约束以及装载约束装入第j种卡车中，weighti表示第i种货物的重量，volumei表示第i种货物的体积，maxWeightj表示第j种卡车的最大允许承重，maxVolumej表示第j种卡车的容积，γ表示卡车的最大允许容积，maxValue表示极大数。
[0096] 对于所述总成本最小化分配模型中的约束，其含义如下：
[0097] 约束一，所有货物必须被分配到计划卡车或者额外卡车上：
[0098]
[0099] 约束二，货物具有时间窗约束，分配给卡车的物品与卡车之间必须满足硬时间窗约束，且每一辆卡车都具有可装载货物列表，只有列表中的货物才能被分配到卡车上：
[0100]
[0101] 约束三，每一辆卡车都有固定的承重能力和容积，分配给卡车的所有物品不能超出卡车的承重和容积：
[0102]
[0103]
[0104] 约束四，当卡车数量为0时，卡车一定不会被调用，当卡车数量不为0时，卡车一定会被调用：
[0105]
[0106]
[0107] 约束五，当货物没有被分配到卡车中时，卡车一定不会被调用：
[0108]
[0109] 在本发明实施例中，当使用零库存成本贪心分配初步缩小问题规模之后，将剩余未被分配的货物和未被调用的卡车输入所述总成本最小化分配模型中进行求解，考虑到模型规模仅分配了第i种货物的xij个货物到第j种车的numj辆卡车之中，没有对xij个货物具体在第j种车的numj辆车中如何进行分配进行求解，所以需要另外建立一个模型目标，尽可能多地将xij个货物具体分配到numj辆卡车之中。
[0110] 令常量s表示第j种车分配到的货物种类数量。决策变量qab表示第a(a≤s)种货物要分配到第b(b≤numj)辆车中的数量。
[0111] 所述总成本最小化分配模型的目标满足：
[0112]
[0113] 上述目标中的约束含义包括：分配到卡车之中的所有货物体积不能超出卡车容积、重量不能超出卡车承载能力、第a种货物分配到第b辆车的货物数量不能超出第a种货物的总数量。
[0114] 步骤S2建立的所述总成本最小化分配模型在极少数情况下会出现货物无法完全分配到numj辆卡车之中的情况，将分配不完的货物统一放入剩余货物列表中。
[0115] S3、合并所述初步分配方案和所述总成本最小化分配方案，得到分配组合方案，按照所述分配组合方案进行装箱优化计算，将所述分配组合方案中未被分配的所述货物使用货物再分配算法进行再次分配，得到货物再分配方案，并使用模拟退火算法迭代优化所述货物再分配方案，得到最终分配方案，之后，按照所述最终分配方案在所有所述卡车中进行所述货物的装载。
[0116] 具体的，将所述初步分配方案和所述总成本最小化分配方案进行合并之后，可以得到许多卡车、货物列表的一一对应的分配组合。但是，由于在装箱过程中要考虑卡车的车轮中轴、后轴的承重能力，分配的货物可能会出现一部分无法装入卡车之中的情况。将装箱之后无法装入卡车之中的货物统一放入剩余货物列表，使用货物再分配算法将货物再次分配到计划卡车或者额外卡车之中。
[0117] 更进一步地，步骤S3中，合并所述初步分配方案和所述总成本最小化分配方案，得到分配组合方案，按照所述分配组合方案进行装箱优化计算，将所述分配组合方案中未被分配的所述货物使用货物再分配算法进行再次分配的步骤，包括以下子步骤：
[0118] S31、从所有所述卡车中，选择可以装载至少一个剩余货物的所述卡车，并放入卡车选择列表中。
[0119] 在已分配货物的卡车列表和未分配货物的卡车列表中选出可以装载至少一个剩余货物的卡车到列表selectTrcukList之中。
[0120] S32、计算所述卡车选择列表中每一所述卡车的剩余货物分配数量。
[0121] 计算selectTrcukList中每一辆车理论上最多可以分配到的剩余货物分配数量loadableNum。
[0122] S33、建立以所述剩余货物为键，所述计划卡车列表为键值的剩余货物分配列表，以及一个包含未装载所述货物的额外卡车的额外卡车列表。
[0123] 建立剩余货物freight为键，卡车列表truckList为值的哈希表代mainFreightTrcukListMap，同时，建立一个空的额外卡车列表extraTruckList。在remainFreightTrcukListMap之中，每一个freight都可以被分配到对应的truckList中每一辆卡车之中。
[0124] S34、遍历所述剩余货物分配列表，若其中的每一所述剩余货物都有对应的键值，将当前的分配结果输出作为所述货物再分配方案；若否，执行步骤S35。
[0125] S35、从所述额外卡车列表中选择所述额外卡车加入所述计划卡车列表。
[0126] 在extraTruckList中，将可以装载遍历到的freight的所有卡车选出，放入遍历到的truckList之中。
[0127] S36、计算所述计划卡车列表中每一所述卡车的优先分配分数，并按照所述优先分配分数的大小对所述计划卡车列表进行降序排序。
[0128] S37、对所述计划卡车列表进行遍历，若完全遍历，执行步骤S310；若无法完全遍历，执行步骤S318。
[0129] S38、判断被遍历的所述剩余货物是否满足被遍历的所述卡车的装载约束，若是，执行步骤S39；若否，返回步骤S37。
[0130] 判断遍历的freight是否可以满足遍历到的卡车的承重约束、容积约束而被分配到卡车上。
[0131] S39、将所述剩余货物分配至被遍历的所述卡车，并重新计算所述卡车的装载约束。
[0132] 此时，卡车的loadableNum减1。
[0133] S310、判断是否存在所述剩余货物没有被分配到所述计划卡车列表中的任何一辆所述卡车之中，若是，执行步骤S311；若否，返回步骤S34。
[0134] S311、根据所述计划卡车列表中排序最前的所述卡车生成属性相同的一辆所述额外卡车，并将所述剩余货物分配至所述额外卡车中。
[0135] 用truckList头部的卡车生成一辆属性完全相同的额外卡车，将freight分配到该额外卡车之中。最后将额外卡车放入列表extraTruckList之中。
[0136] 更进一步地，步骤S36中的所述优先分配分数满足：
[0137]
[0138] 其中，score表示所述优先分配分数，loadableNum表示所述剩余货物分配数量，lt、at、usedVolume、usedWeight分别表示所述货物最晚到达工厂的时间、所述卡车到达工厂的时间、所述卡车中已经分配到的所有所述货物的总体积、所述卡车中已经分配到的所有所述货物的总重量。该分数的意义是尽量使剩余货物freight被分配到可以装载多个剩余货物、已经分配了较多货物且可以使freight库存成本较小的卡车中。
[0139] 所述货物再分配算法结束后，所有货物都可以被装入计划卡车或者额外卡车之中。于是得到了一个初始卡车装货规划方案。由于使用了贪心方法来保证算法在超大规模算例下的计算速度，该方案并不是最优解，因此在本发明实施例中需要进一步使用退火算法进行优化。模拟退火算法是应用于组合优化问题的一种基于Monte‑Carlo迭代求解策略的概率型随机寻优算法，其具有全局寻优特点。在物理退火过程中，给予固体足够高的初始温度，再让其缓慢降温。在温度充分高时，固体内部粒子呈现无序状，降温时粒子逐渐有序，并且每个温度下都达到平衡状态，最后降温至常温时达到基态，固体粒子有序排列。模仿物理退火的过程，模拟退火算法可以求解组合优化问题。
[0140] 更进一步地，步骤S3中，所述使用模拟退火算法迭代优化所述分配组合方案，得到最终分配方案的步骤，包括以下子步骤：
[0141] S312、以所述货物再分配方案作为初始解，使用退火算法计算第一函数解，得到目标函数值f(oldSolution)：
[0142]
[0143] 其中，α和β分别为货物库存成本的权重和卡车调用成本的权重，n表示素数卡车的数量，m表示每一辆所述卡车中装入的所述货物的数量，ξ为惩罚项；
[0144] S313、从f(oldSolution)中随机选出两辆所述卡车，并随机将两辆所述卡车中库存成本不为零的所述货物进行调换，按照S312的函数值计算方法计算第二函数解，得到第二函数值f(newSolution)；
[0145] S314、判断f(newSolution)是否小于f(oldSolution)，若是，转到步骤S315；若否，转到步骤316；
[0146] S315、用所述第二函数解替换所述第一函数解，并更新f(oldSolution)为f(newSolution)，之后，执行步骤S317；
[0147] S316、用Metropolis准则接受差解；
[0148] S317、判断迭代次数是否已经达到等温迭代次数l，若否，迭代次数加1，返回步骤S313；若是，执行步骤S318；
[0149] S318、判断温度T是否已经达到终止温度，或patientNum是否已经达到设定忍耐次数，若否，使温度T减1，返回步骤S313；若是，输出当前的所述第二函数解作为所述最终分配方案。
[0150] 更进一步地，步骤S316中，所述Metropolis准则满足：
[0151] Δf＝f(newSolution)‑f(oldSolution)
[0152]
[0153] 所述Metropolis准则执行时，以概率Paccept更新oldSolution为newSolution，更新f(oldSolution)为f(newSolution)，忍耐不接受更优解的次数patientNum加1。
[0154] 本发明所达到的有益效果，在于利用贪心策略、模型求解、智能启发式算法逐步缩小卡车分配货物问题的规模，并进行分阶段优化，使得卡车分配货物问题可以在较短时间内寻找到较优解，而且解的质量相比于简单的贪心策略明显更优，在实际部署时，能够运行于现有的计算机设备上，可以减少人工安排货物到卡车中的工作量，减少了时间损耗。
[0155] 需要说明的是，在本文中，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者装置不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者装置所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括该要素的过程、方法、物品或者装置中还存在另外的相同要素。
[0156] 通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到上述实施例方法可借助软件加必需的通用硬件平台的方式来实现，当然也可以通过硬件，但很多情况下前者是更佳的实施方式。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质(如ROM/RAM、磁碟、光盘)中，包括若干指令用以使得一台终端(可以是手机，计算机，服务器，空调器，或者网络设备等)执行本发明各个实施例所述的方法。
[0157] 上面结合附图对本发明的实施例进行了描述，所揭露的仅为本发明较佳实施例而已，但是本发明并不局限于上述的具体实施方式，上述的具体实施方式仅仅是示意性的，而不是限制性的，本领域的普通技术人员在本发明的启示下，在不脱离本发明宗旨和权利要求所保护的范围情况下，还可做出很多形式用等同变化，均属于本发明的保护之内。
