金建鋼：列生成算法在交通和物流網絡設計問題中的應用

數據魔術師
運籌優化及人工智能系列講座第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.

加入會議方式

歡迎大家加入數據魔術師粉絲群，我們的活動將會通過粉絲群優先發布， 學習資料將通過粉絲群分享。
欲入群，請轉發此文，然后掃描下方二維碼聯系數據魔術師小助手.