双层规划问题
\[\begin{aligned} \min_{(x,y)}\quad &f(x,y) \\ \mathrm{s.t.}\quad &g(x,y)\leqslant0\\ \quad &y\in S(x), \end{aligned}\]其中 $S(x)$ 表示下层问题：
\[\begin{aligned} \min_{y}\quad &F(x,y) \\ \mathrm{s.t.}\quad &G(x,y)\leq 0\\ \end{aligned}\]前者被称为上层规划，后者被称为下层规划。
上层的决策可能影响下层的行为，因而部分地影响下层的实现，但下层不能完全控制下层的选择行为，在上层的允许范围内，下层有自主决策权。
$x,y$ 是上层优化的决策变量，但 $x$ 在下层优化中是参数。所以，双层优化模型是一个优化问题受制于另一个优化问题的模型。
- 一般的求解方法是，利用 KKT 条件，将下层问题的 KKT 条件添加到上层优化问题中，将双层优化问题转换成单层优化。
- 转化下层问题最优值函数，可用抽象平稳性条件进行代替
其中，$V(x)=\min_{G(x,y)\leq0}F(x,y)$
- 上述两种方法的结合，在更弱的条件下给出一阶最优性条件或者通过近似求解算法将下层最优性条件转化成特殊结构
综述
-
国内外研究现状
- 国内：六个方面
- 双层规划模型与优化算法研究：启发式算法、遗传算法、蚁群算法
- 交通规划与优化研究：城市交通、拥挤收费、网络设计、高速公路
- 铁路客流分配与收益管理研究：开行方案、客流分配、弹性需求、收益管理
- 物流与配送优化研究：危险货物、选址
- 电动汽车需求预测研究
- 国际：遗传算法、模拟退火、禁忌搜索、粒子群、神经网络、库恩塔克最优性
- 国内：六个方面
-
发展溯源
- Stackelberg在1934年提出
-
近期进展
- 城市交通网络设计问题
- 道路网路设计
- 公交网络设计
- 多模式网络设计
- OD反推问题
- 静态反推问题
- 动态反推问题
- 城市交通网络设计问题
-
方法探究
-
通用求解方法
- 线性规划方法：k次最好法、格点搜索法、KKT最优性法、互补法、变量排除法、惩罚函数法、顶点枚举法、互补转轴法、分支定界法、割平面法、凸函数差法、相继锥松弛法、共轭梯度法、Benders分解法、直接搜索
- 非线性规划方法：下降法、最速下降法、聚束法、内点法、信赖域法、模式搜索法、非精确恢复法、序列二次规划法、投影梯度法、增广拉格朗日法、有效集法、分支定界法、变量排除法
-
与MPEC关系（平衡约束数学规划）
- \[\begin{aligned} \min\quad &f(x) \\ \mathrm{s.t.}\quad &g(x,y)\leqslant 0,h(x)=0 \\ &G(x)\geq 0,H(x)\geq 0,G(x)^\text{T}H(x)=0, \end{aligned}\]
- 将下层规划利用 KKT 条件加入上层规划后就转换成了 MPEC
- 转化下层问题最优值函数，可用抽象平稳性条件进行代替
- 上述两种方法结合，在更弱的条件下给出一阶最优性条件或者通过近似求解算法将下层最优性条件转化成特殊结构
-
-
未来展望
- 指挥交通探索揭示
- 建模该架构模式优选
- 计算平台互动共享
深入探究
A review of urban transportation network design problems
来自EJOR2013
介绍了城市交通网络设计问题（UTNDP），包括了道理网络设计问题（RNDP）和公共交通网络设计问题（PTNDP）。
综述探讨，没有技术探讨（连问题定义都没有，还要继续递归检索），简单看了一下，没仔细看。
A bi-level model for GHG emission charge based on a continuous distribution of travelers’ value of time (VOT)
来自TRD2016
双层的温室气体排放收费模型。
在双层模型框架中
- 上层，政府寻求一个最优的排放收费方案，根据不同的出行方式(如公共汽车、摩托车和汽车)收取不同的通行费，通过改变不同出行方式的旅客比例来实现给定的温室气体减排目标。
- 下层，旅行者会调整他们的旅行方式，以最小化他们的总旅行成本。
上层使用差分进化算法，下层“全有或全无”交通分配算法。
问题挺复杂的。
Time-dependent transportation network design that considers health cost
来自TRA2015
本文针对考虑健康影响的随时间变化的离散道路网络设计提出了一个双层优化框架。框架中提出并体现了一般健康成本函数。该函数同时考虑了道路交通排放、噪音和因网络扩张而导致的事故对健康的影响。为解决该问题，提出了人工蜂群（ABC）算法来搜索上层问题的网络设计方案，并采用连续平均法和弗兰克-沃尔夫算法来解决下层的随时间变化的土地使用交通问题。还提出了一种修复程序来补救不可行的解。通过数值研究说明了消费者剩余最大化与健康成本最小化之间的冲突。本文还揭示了一个悖论现象，即随着排放量的增加，健康成本会降低。此外，本文还证明了不同居住区之间存在健康不公平现象。本文采用了一个修改后的苏福尔斯网络，以展示求解算法的性能以及所建议的修复程序的有效性。
Implications of link-based equity objectives on transportation network design problem
来自Transportation2019
本研究的目的是从链路性能与能耗的角度提出公平的新定义，并将公平纳入交通网络设计问题（NDP）。首先，我们引入了一种综合公平度量，并提出了考虑自由流交通条件下链路旅行时间和能耗的公平理论框架。我们证明，所提出的公平衡量标准存在布雷斯悖论情况。其次，我们为基于链路的公平 NDP（LE-NDP）制定了一个双层建模框架。该模型是一个多目标优化程序，上层的目标是最大限度地减少系统总旅行时间，并优化旅行时间和能源消耗方面的公平水平。下层则表示用户平衡条件下的流量响应。为了量化相对于公平标准的性能损失，我们在 LE-NDP 中制定了公平价格函数。第三，为求解 LE-NDP 模型，我们开发了一种量身定制的启发式求解方法，该方法可模拟规划者与旅行者之间的互动。该求解方法使用ε-约束方法来确定帕累托效率解，并提出了约束优化公式来求解由此产生的单目标程序。最后，通过对三个交通网络的案例研究，验证了模型和求解算法的有效性。结果表明，当考虑到公平指标时，所提出的建模设备能够获得更平衡的解决方案，而且所开发的求解方法在实践中作为一种参考方法是有效的。结果还显示了旅行时间和基于链路的公平性之间的权衡，并表明在某些情况下，不同旅行成本（即旅行时间和能源消耗）的公平性指标是相互冲突的设计目标。
Multi-stage optimal design of road networks for automated vehicles with elastic multi-class demand
来自COR2021
随着自动驾驶汽车(AVs)的出现，人们提出了新的基础设施规划概念，如AV-ready道路子网，以提高交通网络的性能并促进自动驾驶汽车的采用。然而，这些子网应该随着时间的推移而发展，以响应不断增长的自动驾驶需求，这就需要一种多阶段建模方法。在本研究中，我们提出AV-ready子网的多阶段部署，并将其表述为一个时间相关的网络设计问题，这是一个双级混合整数规划问题。下层是一个具有连续决策变量的同时出行方式和路线选择均衡，上层是一个包括基础设施投资决策在内的设计问题，以确定哪些道路需要升级，哪些道路需要纳入混合交通的自动驾驶就绪子网。我们使用一个真实道路网络的案例研究来演示这个概念。由于计算效率是解决此类大规模问题的关键因素，我们开发了两种高效且量身定制的进化启发式方法来解决问题，并将其性能与计算要求高的基于遗传算法的解决方法进行比较。结果表明，本文提出的算法在满足所有场景约束的情况下都能有效地解决这一大规模问题，并且在阶段数较大的场景下优于遗传算法。此外，在所有场景中，部署AV-ready子网可以在总传输时间和成本方面提高网络性能。然而，这些改进总是伴随着总行驶距离的增加。变化的程度取决于自动驾驶汽车市场渗透率、自动驾驶就绪子网密度和密度化时间。
方向
- 求解器
- 有具体的问题，或许可以用强化学习搭建框架，比如：政府设置充电桩，然后顾客决定去哪充电/买不买车，一些选址问题
参考资料
- 魏贺,刘昊飞,许丹丹,韩雪华,王良,张晓东. 双层规划在城市交通领域研究与应用的系统综述[J]. 运筹学学报, 2023,27(2): 1-26
- https://blog.csdn.net/weixin_44209907/article/details/130469530