多时间粒度下端到端煤炭供应链增效方法研究

Coal is one of the essential resource supply in China, and is responsible for up to 70% energy consumption of the nation. Our coal production is about 3.5 billion tonnes in 2011, which is more than 40% of the world's total production for that year. But, there are issues: tradinationally, coal producing companies are mostly small-scaled and scatterly located; coal logistics is difficult to manage and is lack of efficiency which is not only because of the lack of rail capacity but also because of the complexity of the underlying system; and coal product is not fully utilized and low quality coal is often wasted. These problems result in an unhealthy development of China's coal industry. Researchers from the coal chain area presented the idea of end-to-end coal chain, which is trying to connect all intermediate processes ranging from the production end to the consumption end of the coal. The end-to-end coal chain enbales allocation of resource and coordination between partners in a global and optimal way and makes the management to be service-oriented other than product-oriented. Early practitioners even received financial benefits from doing business by following this idea. Recently, the government also issued a series of polices and carried on a set of plans to show the national support of the development of coal supply chain in this direction. However, making decisions on coal chain operations is not easy. The system is large and complicated, and information is often fragmented and available only to its own section. Furthermore, procedures on the chain are interacted: optimizing one doesn't make the system succeed as a whole. In this project, we plan to optimize the integrated coal chain with mathematical methods which include modelling the coal chain operations from end-to-end either in a long term or whitin different time granularities, and developping advanced algorithms, especially the hybridized optimization methods to solve the models. We aim to develop intelligent computer based system to assist the management team in making better decisions on, for example, capital investment, collaboration polices or operaional plans; and we aim, for more important, to advance mathematical modelling and computing approaches in applications of coal supply chains.

煤炭供应链的规划和运作是非常复杂的系统行为：系统的有效容量取决于各子系统的相互作用结果；作用于不同时间跨度的短期、中期、长期等规划和调度需要协调和衔接才能保证各阶段决策的正确和有效。最大效率地利用煤炭资源，需要动态配煤，即将正确的原材料在正确的时间送到正确的地点生成配煤产品，从而最大程度地满足客户需求。针对这些复杂性，本项目为煤炭供应链建立端到端的优化模型，将系统作为一个整体统一运作。本研究通过对时间粒度的控制，确定不同时间跨度下决策模型的充分必要精细度；基于对偶性理论和分解算法探索新的方法，将铁路等复杂子模块融入端对端的主系统模型以简化优化模型结构；设计和开发集中约束规划、数学规划和局部搜索等算法优势的混合优化算法，对模型求解。本项目的研究成果对煤炭供应链精益、高效地管理有重要的理论和实践意义。

我国长期以煤炭为基础能源且需求持续增加，煤炭物流成本居高不下高、资源紧缺和浪费是严重的经济、社会问题。煤炭资源优化整合需要以先进的科学方法为手段进行精益、集约化的管理。本项目研究煤炭供应链协同管理下作用于不同时间规划期的战略、规划和调度管理问题，旨在通过供应链管理、数学优化、人工智能算法相结合的方法，为复杂的管理决策问题探索新的解决思路和方法。经过三年的努力，按计划在理论和应用方面同时开展了相关合作和研究，取得了一定的科研成果。理论研究方面的成果主要体现在三个方面：一是利用列生成（column generation）和Benders分解等方法对带复杂约束的大规模网络优化问题建立了多尺度的分层模型，并通过为子问题单独设计优化算法以及与主问题交互迭代过程的优化，在基于标准测试包的计算实验中取得了较好结果；二是在高性能混合优化算法研发中，开发了将线性规划（linear programming）和禁忌（Tabu）搜索相结合，约束规划（Constraint Programming）和分支定界（Branch and Bound）相结合的算法用于求解煤炭供应链管理中的中期规划问题和短期调度问题，实验结果验证了混合算法的可行性和性能，同时利用机器学习方法，开发了基于参数优化（parameterized）的元启发算法，并应用于煤炭供应链中期维护规划管理中，实验结果证明了方法的可行性；三是在基础理论研究中，首次研究了带资源约束的基础最短路（resource constrained elementary shortest path）问题的多面体结构 (polytope)，该问题是经典带时间窗的路径规划问题（VRPTW）的子问题，研究证明了该多面体结构的维度并提出了基于包含小平面定义（facet-defining）不等式的多个有效不等式的割平面（cutting plane）算法，应用于改进的Solomon标准测试包的结果证明了方法的有效性。在应用研究方面，与神华黄骅港合作，为其特殊的筒仓配煤调度问题和一体化的泊位配煤装船计划问题开发了基于约束规划和动态规划的模型和算法，应用于实际生产数据效果明显。本项目为以煤炭为代表的散货供应链管理提供了新的思路和手段，有利于煤炭物流成本的减少、煤炭资源的节约和以响应时间为代表的服务质量的提升。