文献阅读：Fragkos, I., Cordeau, J.-F., Jans, R., 2021. Decomposition methods for large-scale network expansion problems. Transportation Research Part B: Methodological 144, 60-80.
什么是网络设计问题？
网络设计问题（Network Design Problem，简称NDP）是运筹学中的一个复杂问题，它涉及到如何优化网络的结点、弧段、容量等，以提高效率、减少拥堵、降低成本、提高安全性等。这里的网络可以是交通网络、电力网络、通讯网络等。
论文中考虑的是交通网络中新建路段的问题。对于一般(单周期)的网络设计问题，可参考文章：固定费用网络设计问题的模型和方法—以道路网络设计为例。
对于新建路段的问题，本人和程琳教授考虑路段出行时间均值和标准差下进行了网络设计：Song, M., Cheng, L., 2023. Incorporating travel time means and standard deviations into transportation network design problem: A hybrid method based on column generation and Lagrangian relaxation. Transportation Letters.
此外还有需要同时新建路段和结点的问题，例如地铁网络的设计问题。在此问题中，路段代表地铁线、结点代表地铁站。可参考：Bucarey, V., Fortz, B., González-Blanco, N., Labbé, M., Mesa, J.A., 2022. Benders decomposition for network design covering problems. Computers & Operations Research 137.
2. 什么是多周期网络设计问题？
多周期网络设计问题是指在多个时间段或运营周期内对网络进行规划和设计的问题。这类问题通常需要考虑在不同时间段内网络的需求变化、资源限制、成本效益等因素，以实现整个网络在多个周期内的最优性能。在多周期网络设计中，关键的挑战之一是如何在满足当前周期需求的同时，也为未来的周期做好准备，确保网络的可持续性和灵活性。
需求已知且会随着周期逐渐增加。为了满足不断增长的需求，需要在每个周期对网络进行扩建。假设前一个周期建设的设施，在后续的周期中均可使用。如何设计每个周期的扩建方案，以满足各个周期的所有需求且总费用最小？即多周期下的网络设计问题，本次阅读的文献中为此问题构建了数学模型，并构建了分解算法。
3. 论文有没有值得探究的拓展？
文献假设已知各个周期的需求，即为输入值。能否将需求设置为变量？
路网特性方面的拓展，例如考虑动态性、随机性
论文只考虑了路段拓展，可加入结点的拓展
论文中路段容量是固定值，可考虑增加路段容量的拓展
您觉得还有哪些方面可以拓展呢？
4. PPT内容
第1部分是问题介绍
第2部分是单周期网络设计问题
第3部分是多周期网络设计问题
第4部分是求解思路
网络设计问题的拉格朗日松弛算法推荐学习：Holmberg K, Hellstrand J. Solving the Uncapacitated Network Design Problem by a Lagrangean Heuristic and Branch-and-Bound[J]. Operations Research, 1998, 46(2): 247-259
网络设计问题的Benders分解算法推荐学习： Costa A M. A survey on benders decomposition applied to fixed-charge network design problems[J]. Computers & Operations Research, 2005, 32(6): 1429-1450.
微信公众号后台回复
加群：加入全球华人OR|AI|DS社区硕博微信学术群
资料：免费获得大量运筹学相关学习资料
人才库：加入运筹精英人才库，获得独家职位推荐
电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...
加入我们：加入「运筹OR帷幄」，参与内容创作平台运营
知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流
文章须知
文章作者：宋茂灿
责任编辑：张云天
微信编辑：疑疑
文章转载自『时空网络流优化』公众号，原文链接：文献阅读: 多周期下的网络设计问题
关注我们
FOLLOW US
