基于统计预测的多集装箱装载问题优化决策研究

In 2013, the total volume of containerized global trade reaches 160 million TEUs, and the total road transport turn over volume reaches 67 billion ton kilometers in China. Improving the space utilization of containers and trucks will bring tremendous social economic value. This project combines statistical forecasting model with optimization techniques to investigate new models and algorithms for the multiple container loading problem, a common planning problem in logistics. We employ the rich operational data accumulated by the company to establish an effective statistical forecasting model ，which is able to quickly forecast the solutions of subproblems based on the data characteristics. We combine various optimization techniques to quickly estimate the overall decision based on forecasts instead of the computationally intensive process of solving subproblems , and then attempt to fully solve the subproblems to construct complete solutions only after promising regions of search space are identified. Since the performance of typical 3D packing algorithms is heavily influenced by data characteristics, such as sizes and assortments of goods, and the data characteristics vary greatly across industries (contrasting typical home appliances, such as refrigerators, to typical consumer electronic products, such as mobile phones), our new methods can better utilize such differences in data characteristics, compared to the solution processes that are solely based on optimization techniques. We extend our new methods to solve a new and complex multiple container loading problem, which can help the clients slightly adjust their order quantities so as to fully utilize the loading space and reduce the unit transportation cost.

2013年全球由集装箱运输的贸易量有1.6亿集装箱，我国公路货物运输总周转量为6.7万亿吨公里。提高集装箱和货车的装载率能带来巨大的社会经济效益。本项目针对安排货物运输时常见的多集装箱装载问题，结合统计预测和优化理论研究多集装箱装载问题的新模型与算法。我们首先利用企业积累的运营大数据创建统计预测模型，通过数据特征快速地预测子问题的解；然后结合优化理论以快速预测代替耗时的子问题求解过程，加速全局决策的评估；在锁定包含优质解的搜索空间后，才仔细地求解子问题以构建完整的解。由于三维装箱算法的性能极受数据特征如货物尺寸和组合的影响，且不同行业的数据特征差异极大（冰箱等白色家电对比手机等电子产品），新方法比单纯用优化理论的方法能更有效的利用这种数据的差异性。我们将新方法扩展后应用于一个新的、更复杂的多集装箱装载问题：即协助客户基于货物优先级微调订单数量从而充分利用装载空间、降低单件货物的运输成本。

2013年全球由集装箱运输的贸易量有1.6亿集装箱，我国公路货物运输总周转量为6.7万亿吨公里。提高集装箱和货车的装载率能带来巨大的社会经济效益。本项目针对运输中常见的多集装箱装载问题，结合统计预测和优化理论研究多集装箱装载问题的新模型与算法。我们首先利用企业积累的运营大数据创建统计预测模型，通过数据特征快速地预测子问题的解（研究内容一）；然后结合优化理论以快速预测代替耗时的子问题求解过程，加速全局决策的评估（研究内容二）。由于三维装箱算法的性能极受数据特征如货物尺寸和组合的影响，且不同行业的数据特征差异极大（冰箱等白色家电对比手机等电子产品），新方法比单纯用优化理论的方法能更有效的利用这种数据的差异性。我们将新方法扩展后应用于一个新的、更复杂的多集装箱装载问题：即协助客户基于货物优先级微调订单数量从而充分利用装载空间、降低单件货物的运输成本（研究内容三）。.针对研究内容一，我们先通过忽略3维单集装箱装载这个子问题中货物的3维形状将之转化为背包问题，然后采用神经网络预测背包问题与原子问题间解的差距，来预测原子问题的解。在对应不同应用场景的7组测试数据上，预测模型的平均误差为19%-36%。针对研究内容二，我们改进基于集合覆盖模型的原型列生成算法，利用预测模型的对子问题的快速且相对准确的评估加快算法的收敛速度。在7组测试数据上，维持解的平均质量相同的情况下，新算法可以平均提速7%-37%。针对研究内容三，我们将可行装箱方案按照优先级和运输成本分成方案集合，以可行方案集合为单位组织高效的全局搜索，利用研究内容二的算法求解一个可行方案。该算法可以在20分钟内求解实际生产规模问题实例。.本研的结果说明结合统计预测模型与优化理论可以有效利用不同场景下的数据特征加速优化算法。由于集合覆盖模型可以广泛应用于复杂的优化问题，比如车辆路径规划问题、人员排班问题。我们的思路可以启发相关领域的研究。