金建钢：列生成算法在交通和物流网络设计问题中的应用

数据魔术师
运筹优化及人工智能系列讲座第19期

活动信息

演讲主题：列生成算法在交通和物流网络设计问题中的应用
Title: Column Generation Algorithms for Solving Transportation and Logistics Network Design Problems
主 讲 人: 金建钢 上海交通大学交通运输工程系副教授
主 持 人: 秦虎 华中科技大学管理学院教授
活动时间: 2021年7月12日 14:30 – 17:30
直播平台：通过数据魔术师粉丝群发布腾讯会议号及密码，入群方式见文末
主办单位：华中科技大学管理学院
赞助单位：杉数科技有限公司

主讲人简介

金建钢，博士，上海交通大学交通运输工程系副教授。分别于清华大学和新加坡国立大学获得学士和博士学位。专注于大规模组合优化、整数规划和网络优化等运筹优化方法在交通和物流系统中的应用研究。在Transportation Science, Transportation Research Part A/B/C/E等期刊上发表30余篇SCI/SSCI期刊论文。主持3项国家自然科学基金项目（中加国际合作研究项目、面上、青年）。入选交通部交通运输青年科技英才、上海市启明星计划、上海市晨光计划。获INFORMS Railway Application Section铁路优化竞赛一等奖、新加坡国立大学校长奖。担任期刊Computers & Industrial Engineering领域编辑。

报告摘要

网络设计问题是典型的大规模组合优化问题，在交通和物流领域应用广泛。由于问题规模大、决策耦合、约束复杂等原因，实际交通和物流网络设计问题的求解具有很大挑战性，列生成算法是求解大规模网络设计问题的有效方法。本次报告旨在分享列生成算法在交通和物流网络设计问题中的应用。具体针对海运、轨道交通、货运铁路等场景，结合所研究问题的特性，讨论问题的分解及建模思路，以及列生成算法与其他算法的融合求解方法。

【相关阅读】列生成算法（Column Generation，CG）的理论基础由Danzig等于20世纪60年代提出，是一种把线性规划问题分解为小规模子问题的技巧，用于解决大型线性规划问题。本质上，列生成算法是单纯形算法的一种形式，从一个基本解(Basic Solution)出发，主问题的系数矩阵只考虑基本解对应的列，然后求解子问题来生成主问题系数矩阵的列。这种迭代求解的方法使得我们可以求解一些具有指数多个变量的线性规划。列生成算法在运筹优化领域有着非常广泛的应用，已被用于解决许多经典的NP-hard问题，如，机组人员调度问题(Crew Assignment Problem)、切割问题(Cutting Stock Problem)、车辆路径问题(Vehicle Routing Problem)、单资源工厂选址问题(The single facility location problem )、旅行商问题（Travelling salesman problem）、车间调度问题（Scheduling）等。

参考文献：
P.C. Gilmore and R.E. Gomory. A linear programming approach to the cutting stock problem part i. Operations Research 9, 849–859, 1961.
P.C. Gilmore and R.E. Gomory. A linear programming approach to the cutting stock problempart ii. Operations Research 11, 863–888, 1963.

加入会议方式

欢迎大家加入数据魔术师粉丝群，我们的活动将会通过粉丝群优先发布， 学习资料将通过粉丝群分享。
欲入群，请转发此文，然后扫描下方二维码联系数据魔术师小助手.