城市公交管理的Stackelberg博弈模型.pdf

第9卷 第3期 2009年6月 交通运输系统工程与信息 Journal of Transportation Systems Engineering and Information Technology Vol19No13 June 2009 文章编号 100926744 2009 0320121207 系统工程理论与方法 城市公交管理的Stackelberg博弈模型 孙连菊 1 2 高自友 31 1 北京交通大学 轨道交通控制与安全国家重点实验室 北京100044 2 曲阜师范大学 运筹与管理学院 山东日照276826 摘要 公交市场上运营者之间的自由竞争往往会走入 囚徒困境 即所达到的Nash 平衡不是Pareto最优 针对此 本文引入公交管理者进行宏观调控使运营者走出困境 本文首先建立了描述管理者与运营者之间的动态调整过程的Stackelberg博弈模型 鉴 于该双层模型的复杂性 文中将下层广义Nash均衡博弈模型转化成变分不等式问题 并讨论了博弈均衡解的存在性 然后给出了增广Lagrange罚函数算法及其收敛性结 论 最后给出具体算例 关键词 公共交通 Stackelberg博弈 间隙函数 增广Lagrange罚函数 中图分类号 U491 1 7 O225文献标志码 A Stackelberg GameManagementModel of Public Transit SUN Lian2ju 1 2 GAO Zi2you 1 1 State KeyLaboratory of Rail Traffic Control and Safety Beijing JiaotongUniversity Beijing 100044 China 2 College ofOperations Research andManagement Qufu NormalUniversity Rizhao 276826 Shandong China Abstract The enterprises in free competition are always in Prisoner sDilemma in otherwords the Nash equilibrium is usually not the Pareto optimal solution In this paper a static non2cooperative Stackelberg gamemodel is developed to describe the dynamic interactive adjustmentprocess between themanager and op2 erators in which the manager is the leaderwho attempts to reach the system optimization Then the game is transformed into a single2level optimization problem with the variational inequality and the characters of the solutions are also discussed The augmentedLagrange algorithm is used and its local convergent conclusion is drawn An example is given at the last section Key words public transit Stackelberg game gap function augmented Lagrange penalty function CLC number U491 1 7 O225Document code A 收稿日期 2008212202 修回日期 2009204213 录用日期 2009205211 基金项目 国家重点基础研究规划项目 973计划 2006CB705500 作者简介 孙连菊 1977 女 山东人 讲师 博士生 3通讯作者 gaoziyou jtys bjtu edu cn 1 引 言 城市公交系统作为一个以出行者位移为商品 的经济市场 其中的决策问题多样而复杂 随着博 弈论在交通中应用的不断加深 动态模型Stackel2 berg博弈在交通中的应用也日益广泛 其特点是引 入了决策者行动的先后次序 Patriksson和Rockaf2 ellar 2002 给出一个描述交通管理的双层规划模 型 上层为交通管理者 下层为用户平衡 1 Cas2 telli et al 2004 描述了货运网络中有不同分工的 两公司之间的博弈 作者分别以公司1和2轮替作 为上层决策者 另一公司作为追随者建立了两个 Stackelberg博弈模型 2 Zhou et al 2005 将公交 系统建模为双层规划 公交运营者之间的竞争被描 述为n人非合作博弈 并将之作为上层问题 下层 问题为随机用户 3 Yang et al 2007 将网络上 混合行为均衡描述为Stackelberg博弈均衡 4 作 者将出行者分为用户平衡类 UE 系统最优类 SO 和古诺 纳什类 CN 并以SO类局中人为 上层领导者 UE和CN类局中人为下层追随者建 立了Stackelberg博弈模型 Yang et al 2007 模型中的上 下层决策者都 是出行者 不同的仅是各自的目标 从经济学上分 析 运营者和出行者的目标都是追求个人效用最大 化 因而公交系统中以系统最优作为目标的局中人 常常被认为是有一定宏观调控权力的管理者 且管 理者对出行者的调控是通过运营者而间接作用的 公交管理者 作为上层决策者 通过改造基础设施 或信号灯方案等对运营者进行某种控制或引导 以 达到系统最优 而运营者 作为下层决策者 则在 管理者提供的软硬件条件下优化自己的运营方案 以使自己的利润达到最大 管理者根据运营者的 决策和实际的交通状况调整决策 运营者再次优化 运营方案 依此下去 直到管理者和运营者的目标 都达到最优 这一调整过程就是非合作静态Stack2 elberg博弈 2 模型建立 本文中仅讨论上层有一个管理者的城市公交 管理模型 下层的运营者有一个或多个 2 1 符号和假设 公交网络记为图G M S 其中M为网络 中所有站点的集合 S为路段的集合 本文用到的 记号如下 N 运营者的集合 N 1 2 m W 所有O2D对的集合 w W As 通过路段s的所有可行线路的集合 v l k s 线路l上通过路段s的属于第k位运 营者的流量 t l k s 乘坐由运营者k提供的服务在线路l 上通过路段s的车内时间 x l k s 路段s上的乘客选择线路l及第k位 运营者提供服务的概率 y l k s 线路l中的路段s上的第k位运营者 给定的票价 向量y l s y l 1 s y l 2 s y l m s T v l s 线路 l上通过路段s的流量 并记vs 6 l As v l s为路段s上的总流量 v k 第k位 运 营 者 的 客 流 向 量 v k v l k s T s S l As 本文中根据实际交通状况给出如下假设 1 车内出行时间固定 即 k 1 2 m t l k s 为定值 不受季节 天气等外界因素的影响 这 一假设虽然在研究中比较常用但却是较为理想化 的假设 2 线路中各路段上的票价未必相等 如北京 公交中的相关规定 12公里内1元 每增加5公里 以内加价0 5元 10公里内2元 每增加5公里以 内加价1元等 单一票价等 3 任意一条公交路线上不会包括同一条公 交线路中不相邻接的两部分 也即出行者在一次出 行中不会换乘本次出行中已经乘坐过的任何一路 公交车 2 2 运营者的决策模型 固定需求条件下 在不考虑交通事故和旅游等 因素造成的交通异常的前提下 城市中某时段公交 出行的流量是一定的 运营者作为经济个体 假定 他们满足 理性经济人 假设 为争取个人利润最 大 他们努力争取更多的流量 而单个人所做的决 策不仅影响其他人的利润 还会影响其它人的决策 变量的选取空间 这是一个典型的广义Nash博弈 问题 运营者的目标是利润最大 其利润为收入减掉 成本所得 给定路段s上的流量vs 乘客选择线路 l As且由运营者k提供服务的概率由logit模型 给出 x l k s exp t l k s y l k s 6 j As exp t l k s y l k s 1 从而估计线路l上通过路段s的属于运营者k 221交通运输系统工程与信息 2009年6月 的流量为v l k s x l k s vs l As 则运营者k在路段 s上的收入为 R k s 6 l As v l k s y l k s 2 由前面假定 上层决策变量x进入到下层运营 者的成本函数 另外其他运营者的票价也会影响到 运营者k的票价水平 因而运营者k的成本函数为 C k x y k 其中y k y 1 y k 1 y k 1 y m T 表示除运营者k外其他运营者的票价向量 从而运营者k的利润为 Q k x y 6 s S R k s C k x y k 6 s S 6 l As x l k s vsy l k s C k x y k 3 记 k x y Q k x y 则运营者k的目标为 min yk k x y 4 运营者需满足流量守恒约束 即 6 m k 1 v l k s v l s v l k s 0 k N s S l As 具体到第k位运 营者即为 v l k s v l s 6 m j 1 j k v l j s v l k s 0 s S l As k N 5 从而运营者之间的博弈模型为 k N 运营 者k求解 min yk k x y k3 y k s t v l k s v l s 6 m j 1 j k vs l j3 v l k s 0 s S l A 6 其 中 y k3 y 13 y k 1 3 y k 1 3 y m3 T 为除运营者k外其他人的最优价格策略 2 3 公交管理博弈模型 实际管理过程中 公交管理者和运营者之间的 调整过程可描述如下 管理者首先给出自己的决策x X 下层运营 者进行博弈并将该博弈的均衡解反馈给上层管理 者 上层调整决策变量 下层再次博弈 因而上 层管理者的目标函数可记为 x y Rs n R y 为由所有下层运营者的策略y i R ni i N 构成 的向量 记下层运营者i的策略集和目标函数分别 为 i x y 和K i x y i i N 此处 K i x y i y l i s T s S j As 6 m k 1 v l k s v l s y l i s 0 7 下层问题 6 重写为 i N 运营者i求解 m in yi i x y i yi s t y i K i x y i 8 上层给定其决策x X 记系统 8 的解集为 Y x 当然 Y x 未必是单点集 从而城市公交管理模型为 MPEC min x y s t x X y Y x 9 3 模型分析 公交管理模型 9 是一个带均衡约束的优化 问题 讨论和求解这类问题最大的困难在于多数情 况下其可行区域非凸 甚至不连通 造成此严重后 果的主要原因在于等价描述集合Y x 的K K T系统中的互补松弛条件 通常是一组非线性甚至 高次的等式或不等式 灵活而缜密的数学工具给 我们提供的另一出路 就是变分不等式 V I 和拟 变分不等式 QV I 3 1 下层问题解的存在性 变分不等式问题是包括许多数学问题的一般 描述 它是作为一种研究工具而发展起来的 本文 中 我们关心的是定义在有限维空间上的变分不等 式问题 定义如下 定义 1 变分不等式问题 有限维变分不等式 问题V I F 就是确定一个向量x 3 使得 F x 3 x x 3 0 x 10 其中 F R m 是给定的连续函数 R m 是 给定的闭凸集 为欧氏空间中的内积 若 将闭凸集 替换为点到集映射 Rm Rm 则变 分不等式就变为拟变分不等式 定义 2 拟变分不等式问题 有限维拟变分 不等式问题QV I F 即求x 3 x 3 使得 F x 3 x x3 0 x x 3 11 在给出广义Nash均衡博弈的拟变分不等式转 化形式之前 首先给出广义Nash均衡博弈问题均 321第3期城市公交管理的Stackelberg博弈模型 衡解的概念 定义3 给定x X 称y 3 y 13 y 23 y m3 T R n 为问 题 8 的 广 义Nash均 衡 点 GNEP Generalized Nash Equilibrium Point 若对 i 1 2 m y i3 是如下给定y i3 时参数优化 问题的解 min yi i x y i3 y i s t y i K i x y i3 12 记 9 的可行区域为 x y x y R s n x X y Y x 定义4 称 x 3 y 3 为静态Stackelberg博弈 9 的解 若y3 Y x3 x 3 X 且对 x y x y 有 x y x 3 y 3 令 K x y 7 m i 1 K i x y i 13 F x y yi i x y m i 1 R n 14 则有如下结论 定理5 给定x X y 3 y 13 y 23 y m3 T R n 为广义Nash均衡的充要条件是y 3 K x y 3 且 z y 3 T F x y 3 0 z K x y3 15 证明 对单个优化问题min yi i x y i3 y i y i K i x y i3 有如下结论 若y i3 是其局部最优解 则在y i3 点不存在可 行下降方向 即对 y i K i x y i 有 yi i x y i y i3 T y i y i3 0 从而系统 8 等价于 i 1 2 m 有 yi i x y i y i3 T y i y i3 0 y i K i x y i 由其独立性 对上述各式相加有 6 m i 1 yi i x y i yi3 T y i y i3 0 y y 1 y m 7 m i 1 K i x y i 即 y y 3 T F x y 3 0 y K x y3 证毕 将式 13 写的更具体一些 K x y y Y x X y i K i x y i i 1 2 m 可以看 出 上层管理者给定他的决策x X后 集合K x y 为向量y的集合 函数F x y 是向量y的函 数 即在集合K x y 和函数F x y 中 上层给定 的决策变量x可被视为字符常数 而不必看作参 数 从而式 15 是一个关于下层决策向量y的拟 变分不等式问题 为表示出与x的对应关系 记之 为QV I F K x 其解集记为Sol x 定理5也就 是说给定x X y 3 为广义Nash均衡的充要条件 是y 3 是QV I F K x的解 即y 3 Y x y 3 Sol x 关于有限维拟变分不等式问题解的存在性 Chan和Pang 1982 讨论了函数F为集值映射时 的拟变分不等式解的情况 5 我们可以套用其定 理而不加证明地给出下层广义Nash均衡博弈问题 解的存在性定理 定理6 给定x X F x R n R n为点到 点映射 K x R n 2 Rn 为点到集映射 F K定 义如式 13 14 若存在非空紧凸集合 R n 使得如下各式成立 y K x y F x y 关于y在 上连续 y 集合K x y 非空且为关于y的 闭凸集 K x y 关于y在 上连续 则广义Nash均衡博弈问题 8 至少有一个均 衡解 3 2 变分不等式转化 Harker 1991 证明了在一定条件下 可以通 过求解变分不等式来间接地求解拟变分不等 式 6 此处可以稍加改动得到下述结论 定理7 给定x X 对拟变分不等式问题 15 若存在非空紧凸集 使得 y 有K x y y 有y K x y 则V I F x的所有解都是QV I F K x的解 但反之未必真 说明 在上层给定x X后 由下层广义Nash 均衡问题转化来的拟变分不等式中的函数和集合 都与x有关系 因而与此相关的变分不等V I F 中的集合 也与x有对应关系 因而将变分不 等式问题记为V I F x 证明 设y 3 是V I F x的解 即y 3 且 421交通运输系统工程与信息 2009年6月 对 y 有 F x y 3 T y y 3 0 由 y 3 y 3 K x y 3 再由 y K x y 故y 3 K x y 3 且对 y K x y 有 F x y 3 T y y 3 0 即y3也是QV I F K x 的解 证毕 由此 MPEC模型 9 的下层问题可以转化为 下述变分不等式 求y 3 K x y 3 使得对 z K x y 3 有 z y3 T F x y 3 0 于是式 9 转化为如下优化问题 min x y s t x X y解如下优化问题 F x y 3 T y y 3 0 y 16 4 求解算法及其收敛性 4 1 变分不等式的间隙函数 式 16 的求解难点在于问题的可行域可能非 凸 这使得不易直接对双层模型进行迭代计算 一 类重要的算法思想就是将双层规划问题单层化 然 后进行求解 问题 16 的下层是一个变分不等式 问题 它作为一类特殊的优化问题 没有明确的目 标函数无法进行迭代 在变分不等式的求解方法 中 间隙函数法 gap function method 是近年来研 究的热点 也是比较实用而方便的方法之一 该法 的主要思路是找到一个性质良好 如凸 可微 连 续等 的函数 把变分不等式的求解转化为求解方 程组或优化问题 定义8 令K X 称函数p X R为变分不 等式V I F K 的间隙函数 若满足 p y 0 y K p y 0 y K的充要条件是y是V I F K 的解 Fukushima于1992年首次给出变分不等式的 连续可微间隙函数 g y max x K F y x y 1 2 x y M x y 其中 M为对称正定 矩阵 后来Zhu和Matcotte对上述结果进行了推 广 基于此 下面给出变分不等式V I F K 的间隙 函数 定理9 若集合K X为闭集 y K 函数 f x y F y x y 关于 x可微 下半连续且 凸 x X f x y 关于y可微 f y x y 在K K 上连续 令H x y X X R在K K上连续可 微 在K上关于x强凸 且对 y K有H y y 0 H x y y 0 则函数h y max x K f x y H x y 是变分不等式问题V I F K 的连续可微 的间隙函数且其梯度为h y f y x y y H y x y y 其中 函数 x y arg min x K f x y H x y 有了上述结果 在上层公交管理者给定其决策 变量x X后 式 16 的下层问题V I F x可以 用间隙函数等于零来代替 等价的转化为等式约束 h x y 0 具体为 h x y max x F x y z y H x y 函数H x y 满足定理10中的 条件 从而问题 9 进一步写为如下单层优化问题 17 min x y s t x X y h x y 0 17 4 2 增广Lagrange罚函数算法 增广Lagrange罚函数方法的思想是先构造原 约束优化问题的Lagrange函数代替原目标函数 得 到一个增广的极值问题 然后再构造该增广极值问 题的外点罚函数作为原问题的无约束优化子问题 具体到问题 17 其Lagrange函数为 L x y x y T h x y 其中 为Lagrange乘子向量 然后构造增广La2 grange罚函数 L x y x y T h x y 6 m i 1 h 2 i x y 18 其中 为罚因子 下面给出增广Lagrange罚函数法的算法步骤 步骤一 初始化 给定 0 0 0 0 0 0 T 初始点 x 0 y 0 R m n 增长因子 1和允许误差 0 并置k 0 步骤二 求解 以 x k 1 y k 1 为初始点 用无约束优化方法来计算函数L x y k k 的 最小值点 x k y k 521第3期城市公交管理的Stackelberg博弈模型 步骤三 终止判断 若max hi x k y k i 1 2 m 算法终止 否则 转下一步 步骤四 修正罚因子 若 h x k y k h x k 1 y k 1 令 k 1 k k 1 k 置k k 1 转步二 步骤五 修正Lagrange乘子 若 k k 1 或 h x k y k 1 4 h x k 1 y k 1 令 k 1 k 据 k 1 i k i 2 ihi x k y k 调整 k 1 置k k 1 转步二 否则 令 k 1 k k 1 k 置k k 1 转步二 容易证明 若 x k y k 为增广Lagrange罚函 数的最优值点 而且是式 17 的可行点 则 x k y k 就是式 17 的最优点和K T点 算法自然终 止 算法步一中的 是提前给定的精度要求 算法中关于乘子的修正问题我们略去了相关 的论证 对于步二中的函数L x y k k 的求 解 可以视具体情况选用合适的无约束优化算法 关于增广Lagrange罚函数方法的可行性 有如下结 果做保证 定理10 设 x 3 y 3 为式 17 的局部最优 解 hi x 3 y 3 i 1 2 m 线性无关 3 是关于 x 3 y 3 点的最优Lagrange乘子 并且在 x 3 y 3 点满足二阶充分条件 则存在 3 0 使 得对任意 3 x 3 y 3 为由定义的罚 函数L x y 3 的关于 x y 的一个严格局部 极小值点 特别地 若 x y 为凸函数 hi x y i 1 2 m为线性函数 则对于任意的 0 问 题 17 的最优解都是式 18 定义的罚函数L x y 3 的关于 x y 的最小值点 5 简单算例 下面给出一个简单算例 该算例来自于参考文 献 4 图1为一个简单的交通网络图 其中只有 一个OD对AB 该OD对间有3条路径 分别记为 1 2 3 假设两节点A和B之间有100单位的流量 被两个运营者 k a b 所分享 设3条路径上的 成本函数依次为t1 10 5v1 t2 50 v2 t3 100 v3 根据上述网络特点 可以得到运营者k k 图1 有一个OD对3条路径的小网络 Fig 1 Simple network with one OD pair and three paths a b 的利润为Q k x y 6 3 t 1 x t k t v t ty t k t C k x y k 则函数 k x y C k x y k 6 3 t 1 x t k t v t ty t k t 流量约束为 6 k v s k s v s s v s k s 0 s 1 2 3 运营者k k a b 的优化问题为 min yk k x y s t 6 k v s k s v s s v s k s 0 s 1 2 3 19 管理者作为上层决策者 其目标函数为使得总 的交通成本 时间成本和票价成本 最小 即 x y 6 3 s 1 tsvs 6 k y k v k 从而公交管理模型具体为 min 10 5v1 v 1 50 v2 v 2 100 v3 v 3 6 k y k v k s t 对 k a b y k 是如下问题的解 min yk 6 3 s 1 y k sv k s s t 6 k a b c v k s vs v k s 0 s 1 2 3 0 y k s ps 20 其中票价的上界ps事先给定 6 3 s 1 v3 100 随机给定3条路径上的流量若分别为60 30 10 考察下层运营者之间的博弈均衡 根据二者指 定的票价不同 在其均衡点处 他们所赢得的流量 和收入如下表1所示 当运营者b调整票价后 可得如表2所示的 结果 621交通运输系统工程与信息 2009年6月 表1 两运营者在固定流量条件下的博弈均衡 Table 1 Game equilibrium of two operators under fixed volume 路段 运营者a 票价流量收入 运营者b 票价流量收入 系统总收入系统总费用 11 026260 83427 253 2 21 21214 41 0181832 4T 98 8 31 5461 267 213 2 总收入46 452 498 8 表2 运营者b调整票价后的结果 Table 2 Results of price adjustment from operatorb 路段 运营者a 票价流量收入 运营者b 票价流量收入 系统总收入系统总费用 11 031311 12931 962 9 21 21821 61 31215 637 2T 115 4 31 5710 51 634 815 3 总收入63 152 3115 4 可以看出 票价水平越高的运营者赢得的流量 越少 总收入也越少 当两个运营者不再进行价格 战而试图合作时 票价水平差别