2.3　交通优化问题中的双层规划

如前所述，交通网络的优化建模涉及两个问题，如何制定交通网络优化决策，以及如何预测交通网络用户对决策的行为反应。双层规划模型是解决上述两个问题的常用方法。

双层规划问题（Bi-level Programming Problem）又称双层优化问题（Bi-level Optimization Problem），是指包含上、下两层规划问题，其中上层问题是以下层问题为约束条件的规划问题。双层规划问题同时考虑了决策过程中不同决策者（领导者和追随者）的作用和表现。上层问题是领导者（即交通网络规划管理者）问题，包括可度量的优化目标（如交通网络通行效率最大化、建设或修复成本最小化），约束条件（政策、经济、环境等多方面的现实约束），以及需要做出的决策（如需要新建或修复的路段、建设或修复的时序安排）。上层问题假设领导者能够预测出行者的行为；下层问题是追随者（即交通网络出行者）问题，出行者决定是否出行、出行方式、出行路线等决策。在这种双层结构下，交通网络管理者可以考虑出行者的反应，通过优化交通网络来影响用户的出行选择，但不能直接控制用户的出行选择。另外，这种双层结构并不允许出行者预测交通网络管理者的决策，只允许他们在知道管理者的决策后决定自己的出行选择。双层规划模型的一般形式如下。

上层模型：

minF（x, y（x））　（2.1）

s.t.

G（x, y（x））≤0　（2.2）

H（x, y（x））=0　（2.3）

其中，x是上层决策者的决策变量，F（x, y（x））是上层决策者的目标函数，公式（2.2）和公式（2.3）是上层决策者在决策过程中受到的约束条件。y（x）是在上层决策变量x给定的条件下，如下所示的下层模型的最优解。

下层模型：

minf（x, y）　（2.4）

s.t.

g（x, y）≤0　（2.5）

h（x, y）=0　（2.6）

其中，y是下层决策者的决策变量，f（x, y）是下层决策者的目标函数，公式（2.5）和公式（2.6）是下层决策者在决策过程中受到的约束条件。

在决策过程中，上层模型首先给出决策，然后观察下层模型的反应。下层模型在上层模型决策方案给定的前提下，寻求自己的最优决策。下层模型给出行动方案后，上层模型将根据下层模型的反应调整其决策方案，力求使自己的目标函数最大化。接下来，下层模型将再次根据上层模型新给出的决策调整自己的决策。反复进行上述过程，直至上层模型和下层模型都不再调整自己的决策为止。此时模型达到一个相对平衡、满意的状态，这时的决策方案被称为相对最优方案。

交通优化问题中的双层规划模型的特殊之处在于其下层模型。y（x）又被称为反应函数（Reaction or Response Function），一般它将下层交通网络出行者的反应行为最终描述为交通流量分配的模式，该模式往往表现为交通网络上每条路段或每条路径上的交通流量。由于对出行者出行选择的刻画维度不同，以及行为准则的假设不同，下层问题又可以分为多种形式。下层问题中最常见的形式是考虑出行者的路径选择，即交通流分配问题（Traffic Assignment Problem）。交通流分配问题的基础问题是用户均衡配流（User Equilibrium），该问题假设所有出行者都能随时精确掌握每条路径的通行时间，并且相互之间不存在合作关系，所有OD对之间的出行量保持不变。如果假设出行者对路径通行时间的感知存在随机误差，基础问题就拓展为随机用户均衡配流（Stochastic User Equilibrium）。如果假设OD对之间的出行量会随着通行时间变动，基础问题就拓展为需求变动的用户均衡配流（User Equilibrium with Variable Demand）。如果假设出行者之间的行为是协作的，大家的共同目标是使交通网络的总出行时间最小，则基础问题就拓展为系统最优配流（System Optimization）。

以上所提下层模型虽然假设不同，但都有一个基础假设，即出行者的其他选择行为给定，因此只考虑出行者的路径选择行为。如果假设出行者的目的地选择也不固定，同时考虑出行者的目的地选择行为和路径选择行为，则下层问题就变为均衡出行分布和交通配流组合问题（Combined Equilibrium Trip Distribution and Traffic Assignment Problem）。2.4节将详细介绍本书用到的用户均衡配流模型、均衡出行分布和交通配流组合模型。更多关于上述其他模型的详细信息可以参见Sheffi和黄海军的研究。

Ben-Ayed等人证明了即使上层模型和下层模型均是线性规划的简单双层规划问题，也依然是NP-hard问题。Luo等人证明了即使上层模型和下层模型均是凸问题，也无法保证双层规划问题依然是凸问题。NP-hard问题和非凸问题的特点极大地增加了双层规划模型的求解难度。因此，在交通优化问题的研究中，往往选择采用启发式算法而非精确算法来求解此类双层规划模型。