随机运输服务网络设计场景树压缩及应用研究

.Service network design is one of the core problems in freight logistics. Compared to vehicle routing problem, service network design can readily model freight transfers and consolidation and, therefore, is more suitable for large transportation network optimization. Due to an uncertain environment in which freight transportation operates and reliability requirements from users, stochastic service network design is becoming a focused research area recently. In contrast to the other relevant research which concentrates on optimization algorithms, this project mainly focuses on the scenario tree compression in the context of service network design. In this way, we can reduce the number of iterations between the two stages of stochastic programming. To achieve this, we will investigate both the dynamic scenario clustering methods and evolutionary based scenario classification approaches. These will be combined with decomposition based methods, integer programming approaches and latest meta-heuristics to improve the performance of algorithms for the stochastic service network design. These algorithms will be tested on the well-known international benchmark instances as well as the real world container transportation problem at Ningbo Port. The project will advance the state-of-the-art algorithms for stochastic service network design significantly. It will also significantly benefit relevant practical transportation network design applications both economically and environmentally.

服务网络设计是运输物流的核心问题，比车辆路径VRP模型更适合建模货物运输的中转、充实等增效策略，因此更适用于解决大规模运输网络优化问题。随着用户对服务质量和可靠性要求的不断提高，随机服务网络设计近年来成为一个研究热点,但国际上目前对于该问题的求解算法还远远达不到实际应用要求。为此，本项目创新性的从随机服务网络设计的场景树（Scenario Tree）入手，研究场景树在服务网络设计应用中的压缩方法，以减少随机规划两个阶段之间的迭代次数来达到提高算法效率的目的。项目拟分别研究动态场景聚类法和演化计算场景分类法，结合以场景类为基础的分割法、整数规划和最新的启发式领域搜索算法，从根本上提高随机网络优化算法性能，并采用国际标准问题集和宁波港内陆集卡运输真实数据加以测试验证。研究将大大提高现有随机服务网络设计算法效率，对国内外相关运输网络问题具有巨大经济价值和环境效益。

服务网络设计是运输物流的核心问题，比车辆路径VRP 模型更适合建模货物运输的中转、充实等增效策略，因此更适用于解决大规模运输网络优化问题。本项目以高效随机服务网络设计的算法研究及应用为对象，研究内容包括：（i）基于场景类的无重调度高效服务网络设计算法研究；（ii）基于场景类的带重调度的高效服务网络设计算法研究；（iii）随机服务网络优化技术在宁波港集装箱运输网络中的应用研究；（iv）随机服务网络设计高效优化算法。项目组研究了利用K-means“硬”场景聚类方法与“逐步对冲法”（progressive hedging），将大量场景的随机服务网络设计问题分割成基于较少数量聚类的随机服务网络设计问题，从而获得快速求解方法；在分析对比了包括随机聚类、非相似性聚类，K-Means聚类等“硬”场景聚类的特点和不足基础上，在学术界首次提出了Fuzzy C-means和高斯混合模型（GMM）聚类2个“软”的随机场景聚类方法，使得同一场景在不同聚类中通过参数控制以较小概率重复出现在多个聚类，从而提高了不同子问题收敛到一致解（consensus solution）的速度，平均计算时间节省30%。研究发表在2017IEEE智能计算会议，还有1篇期刊论文提交到INFORMS Journal on Computing。项目组成功将服务网络设计建模和优化技术应用到宁波港集装箱转码头运输问题，并在学术界首次引入了双向多班次整车运输问题及高效优化算法，相关研究成果发表在2015年Transportation Research Part B。后期研究融入了宁波港另外15个无水码头的集装箱运输问题，并提出了超启发式搜索算法，相关研究发表在Applied Intelligence。提出了演化分支定价算法，将计算时间从13.5小时缩短到15分钟，相关文章提交到INFORMS Journal on Computing。项目组提出了一种新的更高效的基于网络节点的可行解邻域生成及遍历方法（k-node邻域），发表文章Computers & OR。本项目一共发表期刊论文7篇，项目组产生2项软件著作权，1项专利，在宁波港测试应用能产生每年超过1000万元的经济效益。