A Game Theoretic Approach for Optimal Pricing of Taxi Markets By Gan Jiarui A Dissertation Submitted to University of Chinese Academy of Sciences In p

Transcription

1

2

3 A Game Theoretic Approach for Optimal Pricing of Taxi Markets By Gan Jiarui A Dissertation Submitted to University of Chinese Academy of Sciences In partial fulfillment of the requirement For the degree of Master of Engineering Institute of Computing Technology Chinese Academy of Sciences May, 2015

4

5 声 明 我声明本论文是我本人在导师指导下进行的研究工作及取得的研究成果 尽我所知, 除了文中特别加以标注和致谢的地方外, 本论文中不包含其他人已经发表或撰写过的研究成果 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意 作者签名 : 日期 : 论文版权使用授权书 本人授权中国科学院计算技术研究所可以保留并向国家有关部门或机构送交本论文的复印件和电子文档, 允许本论文被查阅和借阅, 可以将本论文的全部或部分内容编入有关数据库进行检索, 可以采用影印 缩印或扫描等复制手段保存 汇编本论文 ( 保密论文在解密后适用本授权书 ) 作者签名 : 导师签名 : 日期 :

6

7 摘 要 出租汽车以其特有的便捷性 灵活性以及舒适性在现代大都市的公共交通中发挥着重要作用 然而, 支撑着这些优越性的是一个由数量众多 ( 如北京市 6.6 万辆 ) 的出租车组成的庞大而分散的系统 相比公交汽车 轨道交通等其他公用交通系统, 它缺乏集中的调度和控制, 没有固定的线路和时间表 出租司机各自为政, 以个人盈利的最大化为目的 如何有效地分析和优化这样的系统成为一个极具挑战性的问题 由此引发的实际问题 ( 如高峰时段出租车出勤率低 ) 也亟待解决 目前关于这些问题的研究多来自于交通运输学以及经济学领域 这些研究对出租车系统中各个因素 ( 如乘客需求量 出租司机出勤率 道路行车速度等 ) 间的相互联系进行了深入的探索, 但对系统中相互竞争的出租司机作为智能个体的决策行为缺乏考虑 出租车司机们相互竞争, 以最优化的策略谋求最大化的收益 这些自由的 智能的决策行为对出租车独有的便捷性和灵活性至关重要, 在研究中不容忽视 因此, 本研究从多智能体系统 (Multi-agent System) 的角度出发, 基于计算博弈论对出租车系统进行建模和优化 借助博弈论, 出租司机独立决策并相互竞争的关系能够在模型中得到很好的阐释 该方法的关键在于求解出租车司机的最优策略 然而出租司机的策略空间的指数增长给最优策略的计算带来很大的难度 如何设计高效的算法去解决这些计算上的难点是本研究的一个重点 围绕这些问题, 本研究主要有以下贡献 :1) 对具有时间动态性的出租车市场建模, 模型特别考虑了出租车司机的决策行为 ;2) 提出两个基于紧凑表达法的算法 ASM 算法和 FLORA 算法, 对规模呈指数增长的模型进行求解 ;3) 考虑现实情况中出租车司机面临的工作强度以及市场规范方面的约束, 使模型更加精确地反映综合的实际情况, 并基于最优策略小支持集以及优化目标 ( 最大化 ) 为可导凹函数的特性, 提出适用于求解任意形式约束的 FLORA-A 算法 ;4) 通过基于真实数据的实验对本研究提出的模型和算法进行评估, 实验结果显示了紧凑表达算法在处理实际问题时的高效性以及使用 FLORA-A 算法考虑更多约束条件的必要性 关键词 : 博弈论 ; 优化算法 ; 多智能体系统 ; 出租车系统 I

8

9 A Game Theoretic Approach for Optimal Pricing of Taxi Markets Gan Jiarui (Software Engineering) Directed by Associate Professor An Bo Taxi service has long been an indispensable part of public transport in modern cities due to its unique convenience, flexibility, and comfortableness. However, lying behind these advantages is a highly decentralized system operated by a large number of selfcontrolled and profit-driven taxi drivers (e.g., 66 thousand as in Beijing). Therefore, unlike other transportation systems subjecting to fixed schedules and specified routes (such as bus and metro systems) taxi system is hard to manage and quite inefficient. How to properly manage and optimize a taxi system thus becomes a big challenge for decision-makers. Existing researches focusing on this challenge usually came from the transportation science and economics domain, featuring comprehensive studies of effects of and relationships among various factors in the taxi market, such as customer demand, number of working taxis, and traffic in the road network. None of these researches has looked into the more underlying intelligent behaviors of taxi drivers who compete with each other and adopts the best strategy to maximize their profits. These strategic behaviors are the key component contributing to the aforementioned advantages of taxi service, and cannot simply be ignored. To overcome the inadequacies of existing research, we propose a novel game-theoretic approach to capture taxi drivers strategic behaviors, and novel algorithmic techniques to solve the game-theoretic model in particular to address the scalability issue caused by exponential growth of taxi drivers strategy space. This research makes the following contributions: 1) A game-theoretic model of taxi market is built, based on which Taxi system Efficiency optimization Problem (TEMP) is formulated; 2) Two algorithms, ASM and FLORA, based on compact representations are designed to address the scalability issue in TEMP; 3) Algorithm FLORA-A is designed to handle more general scheduling constraints representing comprehensive real-world conditions, such as taxi drivers working capacity, and effects of market regulations; 4) Experiments based on real data are conducted to evaluate our algorithms and examine different constraint settings of our model. The results show high efficiency of ASM and FLORA in solving realistic problems, and the necessity of using FLORA-A to consider additional scheduling constrains when they indeed exist. Keywords: Game Theory, Optimization, Multi-agent System, Taxi System III

10

11 目 录 摘要目录图目录表目录 I V VII IX 第一章 研究背景与相关工作 研究背景及意义 研究方法与贡献 相关工作 论文组织结构 第二章 博弈建模 出租车市场基础模型 静态市场模型 出租司机决策行为的博弈建模 双层优化问题 第三章 模型求解 紧凑表达法 ASM 算法 基于元时间表的紧凑表达 ASM 紧凑表达法与原优化问题的等价性 等价权重向量的存在性 等价混合策略的存在性 FLORA 更加紧凑的表达法 第四章 解决任意约束下的问题 考虑任意约束条件 FLORA-A 算法 利用线性不等式表达约束条件 V

12 中国科学院大学硕士学位论文 基于计算博弈论的出租车市场最优定价研究 第五章 实验 算法运行效率 紧凑表达算法效率测试 FLORA-A 算法效率测试 优化结果分析 考虑约束 C1 和 C 考虑约束 C3 和 C 考虑约束 C 实验结果讨论 第六章 结束语 论文小结 未来研究 参考文献 47 致谢 作者简历 i iii VI

13 图目录 1.1 高峰时段出租车市场反常的供需情况 出租车市场主要因素间的复杂依赖关系 出租司机效用函数的严格凹形 ASM 算法 t i * = ˆn w + 1 可能的情形 图 3.2(d) 续 凸优化问题的最优解判别条件 ASM 算法运行效率随问题规模变化 FLORA 算法运行效率随问题规模变化 FLORA-A 算法运行效率 约束 C1 和 C2 下的优化结果 额外约束条件下的市场情况 VII

14

15 表目录 2.1 模型主要参数列表 与时段无关的参数 与时段相关的参数 IX

16

17 第一章 研究背景与相关工作 1.1 研究背景及意义出租车是现代城市重要的交通工具之一, 以其独有的便捷性 灵活性以及舒适性在城市交通中发挥着不可替代的作用 然而, 支撑着这些优越性的是一个由数量众多的出租车 ( 如北京市约 6.6 万辆 ) 组成的庞大而分散的系统 相比公交汽车 轨道交通等其他公用交通系统, 它缺乏集中的控制和管理, 每辆出租车相对独立地运行, 既没有特定的线路, 也不受制于固定的时间表 这些运营特点在为出租车服务带来上述优势的同时也使得出租车系统变得难以管理且效率低下 由此产生的实际问题也亟待解决 一个典型的例子是北京等大中城市出租车市场高峰时段的打车难问题 [4, 7] 在这些城市中, 高峰时段客流量猛增, 但出租车的出勤率不仅不增高, 反而比其他时段还低, 大多数出租车司机选择在这个客源充足的时段暂停服务 ( 图 1.1) 事实上, 由于国内普遍采用的是以行车距离为主的计价方式, 高峰时段严重的交通拥堵导致行车速度缓慢进而导致出租车司机在高峰时段盈利能力低下, 由此产生的负面效果抵消了增加的乘客需求带来的利润, 出租车司机甚至面临亏本运营的风险 作为以盈利为目的的个体, 出租车司机们不得不选择避开高峰时段工作 这些问题导致乘客不得不花费很长的时间等待出租车, 给市民的出行增加了很大的不便 此外, 出租车的短缺为不法经营的 黑车 提供了可乘之机, 又给城市交通带来诸多潜在的不安全因素 同时, 通过该例我们还可以看到, 出租车系统还受到客流量 路面交通情况等因素的影响, 这些因素相互作用, 并且呈现出时间上的动态性 如何研究和管理这样一个分布式的 随时间变化的复杂系统, 在不牺牲非集中控制带来的优越性的同时优化出租车系统, 提升系统效率, 成为城市管理者面临的一大挑战 1.2 研究方法与贡献针对上述问题, 我们从多智能体系统 (Multi-agent System) 的视角研究出租车系统效率优化问题 多智能体系统研究的对象是一组自治的个体之间相互作用 相互协调的智能行为, 以及他们如何通过知识 目标 技巧和规划联合起来采取行动或求解问题 [2] 多智能体系统体现了人类社会的群体智能, 适用于开放 动态的现实环境 出租车系统恰好是这样一个典型的多智能体系统 系统中, 出租车司机自由地行动 这些行动对整个大环境产生作用 : 例如, 出租车的出勤率会影响道路的拥堵程度 行车速度 行车的时间消耗, 进而又会影响到乘客的需求 出租司机间也相互影响 相互竞争, 出勤车辆的多少直接决定了每位司机在整个市场中能分得多少利润 在最大化利益的驱使下, 出租车司机们选择最优的运营策略 我们借助博弈论的思想, 对出 1

18 中国科学院大学硕士学位论文 基于计算博弈论的出租车市场最优定价研究 图 1.1: 高峰时段出租车市场反常的供需情况 ( 左图 : 高峰期排队等车的乘客 ; 右图 : 高峰期暂停服务的出租车 ) 1 租车司机的这些行为进行建模, 并将这部分模型融合到现有的出租车市场模型中 事 实上, 博弈论 ( 更具体地说, 计算博弈论 ) 已经成为多智能体系统研究的重要方法, 基于博弈论的研究和应用 ( 如研究安全资源分配的安全博弈论 [9, 29, 34, 36]) 已经成为 多智能体系统领域的重要分支 要确保这些研究和应用行之有效, 关键之处还在于设 计有效的求解算法对博弈模型进行求解 这也是计算博弈论与传统博弈论研究内容的 一个重要不同之处 传统的博弈论为博弈现象提供了形式化的数学表达和量化的模型, 计算博弈论则解决了如何从这些模型中导出切实可用的结果的问题, 是理论模型到现 实应用之间的桥梁 将多智能体系统以及博弈论的思想引入出租车市场优化问题是本 研究的第一个贡献 前面我们提到, 出租车系统呈现出随时间动态变化的特性 在这种动态性之下, 出租车司机的博弈策略变得非常复杂 求解本研究博弈模型的难点就在于出租车司 机策略空间的组合爆炸问题 策略空间的大小随问题规模呈指数增长, 导致对应的 待求解的优化问题也具有同样的规模, 从而变得难以求解 针对这个问题, 本研究 提出三个算法 这是本研究的另一重要贡献 第一个算法,ASM 算法, 采用元时间 表的概念对策略空间进行紧凑表达, 将问题的规模从指数级别降低为 O(n 2 ), 其中 n 为 模型包含的时段数 第二个算法,FLORA 算法, 运用凸多面体表达方法的转换导出 比 ASM 算法更加紧凑的表达法, 使得问题的规模进一步降低为 O(n), 从而能够更高 效地解决更大规模的问题 通常 ASM 算法能够轻松地处理以一天时间为优化周期的 问题, 而 FLORA 则可以轻松处理以一周甚至更长的时间为优化周期的问题 ( 考虑到 工作日与非工作日之间的差异, 出租市场的变化周期更倾向于是一周而非一天 ) 第 三个算法,FLORA-A 算法, 则考虑更一般的情形, 处理具有任意约束条件的问题 FLORA-A 利用混合策略支持集较小, 以及出租车系统效率优化问题目标函数为可微凹 函数的性质, 采用逐步扩大策略空间的思路巧妙地避免的使用策略集内所有的 ( 指数 多的 ) 策略 FLORA-A 使得我们能够研究更加复杂的市场状况, 考虑出租车司机在竞 争的过程中更加细节的行为 ( 如不可能过于频繁地在工作与暂停服务的状态间切换 ), 以及市场规定的实施对出租车司机行为的约束及其对市场的影响 我们通过实验对 1 图片来源 : 新华网 ( 2

19 第一章 研究背景与相关工作 算法效率进行测试, 并基于真实数据给出实验性的出租车系统优化方案 实验结果表明 ASM 和 FLORA 算法非常高效, 特别是 FLORA 算法, 其时间和空间开销随问题规模的增长极为缓慢 此外, 从实验结果我们还可以看出市场情况考虑不全面对优化结果造成的偏差, 说明了在这些情况下使用 FLORA-A 算法求解的必要性 1.3 相关工作我们从三个方面回顾与本研究相关的工作 :(1) 出租车市场建模及优化方面的研究, 主要来自于经济学及交通研究领域 ;(2) 人工智能及多智能体领域关于交通管理与模拟方面的工作 ;(3) 计算博弈论近年来在实际问题上的主要应用 对出租车市场模型以及经济学原理的研究可以追溯到 1969 年,Orr 指出传统经济学上的供需原理不适用于出租车市场的情况, 并对不同情况下由相互竞争的出租车组成的市场的均衡进行了研究 [28] 通常认为, 出租车市场的两个显著的特点将其与传统经济学研究中的理想市场区别开来, 即乘客候车时间以及乘客与出租车司机之间复杂的相互作用 1972 年,Douglas 提出了一个聚合的出租车市场供需关系模型, 该工作成为后续出租车市场经济学研究的基石 [18] 这些后续研究共同的假设是乘客对出租车服务的需求依赖于期望的经济上以及时间上的开销, 包括依赖于空车工时 ( 所有车辆空车时间总和 ) 的期望乘客候车时间 近年来,Yang 等人在出租车市场研究上做了大量的工作, 为出租车市场各因素基本依赖关系的建模提供了部分基础 他们采用离散化时间区间的方法对随时间变化的出租车市场进行了建模和研究 [38] 在该研究中, 乘客的最大需求作为与时间相关的外部参数, 每个出租车司机可以自由地在任意的时段上路工作或暂停服务 同样, 也有一些专门针对出租车票价优化的研究工作 例如, Schaller 于 1998 年研究了涨价对纽约出租车市场的影响 [32] Yang 等人将拥堵外部性融合到一个按距离以及延迟时间收费的计价模型, 并且通过数据实验检验了在垄断 社会最优 以及稳定竞争情况下的市场情况 [39] 他们还研究了非线性计价模式对香港出租车市场的影响, 并指出其相对现行票价的若干优势 [40] Kim Hwang 二人以最大化出租车平均利润为目标提出了一个逐级递减的计费模式 [27] 这些研究工作存在以下不足 首先, 这些工作或者忽略了市场因素随时间变化的特点, 或者忽略了拥堵对于出租市场的影响 其次, 更为重要的是, 它们没能考虑到出租车司机间相互竞争 最优决策的行为特点, 亦或是忽略了对这些行为潜在的约束 ( 如出租车司机的工作强度的限制等 ), 这些因素和出租车市场的低效性以及存在的若干突出问题 ( 如本研究针对的高峰时段出租车出勤率下降问题 ) 密不可分 这也是本研究所要重点考虑和解决的问题 上述相关研究主要来自于经济学与交通研究领域 事实上, 人工智能和多智能体系统研究者在交通研究和管理方面近年来也有了很多研究和应用 Bazzan 于 2009 年在她的文章中集中讨论了多智能体系统技术用于解决交通工程, 特别是交通信号管控问 3

20 中国科学院大学硕士学位论文 基于计算博弈论的出租车市场最优定价研究 题上的潜力, 并指出了这个新研究领域内存在的机遇和挑战 [13] Dresner 和 Stone 提出了一个带有通信协议的 基于预约的道口管控方法, 并通过模拟实验证明了其设计的机制相比于现有道口管控技术的若干优势 [19, 20] 基于以上思路,Au 等人又提出一种批量化处理的自动道口预约管理机制 [11] Pulter 等人则以最小化油耗为目标提出基于智能体的道口控制机制 [30], 显著地改善了油耗和等待时间 除了上述交通管理方面的研究, 也有研究者借助多智能体系统的手段对出租车市场进行研究, 主要采取模拟的方法 有学者采用多智能体模拟的手段构建了一个模拟出租车系统运行的平台去研究出租车市场 [16] 也有学者用同样的方法对出租车派遣系统进行研究[8, 33] 这些研究工作显示了人工智能与多智能体系统技术在交通研究和相关实际问题的解决上巨大的潜力, 对本研究起到了推动作用 最后, 我们把目光转向计算博弈论近年来的应用 近年来, 计算博弈论在安全资源分配问题上发挥了很大的作用, 逐步形成了安全博弈论这一研究分支, 激发了计算博弈论在全球面临的诸多新挑战上的应用 [25] 安全博弈论研究博弈场景下最优的安全资源分配问题 研究采用 Stackelberg 博弈模型, 其中一个 先行者 先进行决策, 一个 跟随者 在观察到前者的策略之后采取最优策略进行反馈 而研究者想要知道的是在这种情况下 先行者 应该如何最优地行动, 即如何分配安全资源能够使期望的效用达到最优 这种博弈模式与我们所研究的出租车系统优化问题有很大的相似之处 在我们的研究中, 票价制定者就是上述的 先行者, 而出租车司机作为 跟随者 在票价调整后反馈以最佳的运营策略 安全博弈论目前已有很多成功的实际应用, 基于安全博弈论开发的策略调度系统已经被成功地应用在了洛杉矶机场 美国海岸警卫队 洛杉矶地铁检票系统等众多重要的场合 [9, 10, 29, 34, 36] 此外, 与本研究类似, 目前大多数安全博弈研究也面临策略空间的组合爆炸问题 常见的处理方法包括通过紧凑表达法缩小策略空间 [26], 以及通过 Column Generation Double Oracle 等方法逐步扩大策略集 [23, 24] 这些解决思路也将被借鉴到本研究工作中 当然, 本研究所面临的问题也有自身的独特之处 其一, 本研究中的策略空间由特定的约束条件所确定, 需要设计新的与之相适应的紧凑表达法 ; 其二, 本研究中 跟随者 的目标函数为非线性函数, 相对安全博弈问题中的线性目标函数更加复杂 这些特点也要求本研究在算法设计方面需要有新的突破, 推动了本研究在这些新问题上的理论贡献 1.4 论文组织结构本文后续章节组织结构如下 在接下来的第二章中, 我们首先提出本研究所要解决的出租车系统优化问题 我们在现有的多时间段出租车系统模型之上加入博弈场景, 将出租车司机的决策行为融入模型 在此基础上, 我们导出问题的形式化表达, 明确问题求解上的难点 第三 四章为问题求解部分 我们在这两章中先后用紧凑表达法的思路和逐步搜索扩大策略空间的方法求解不同设定下的问题 其中, 第三章我们提出两个算法 :ASM 算法和 FLORA 算法, 第四章中我们在 FLORA 的基础上提 4

21 第一章 研究背景与相关工作 出 FLORA-A 算法 第五章为实验部分 我们通过基于真实数据的实验对本研究提出的 所有算法的效率进行测试和对比, 并通过算出的结果对不同设定下的出租车市场情况 进行讨论 第六章回顾本研究的主要内容, 总结主要贡献, 并展望未来的研究方向 5

22

23 第二章 博弈建模 出租车系统效率优化问题 (Taxi system Efficiency optimization Problem, 以下简称 TEMP) 旨在通过出租车票价这一杠杆调节出租车市场, 使其效率达到最优 为此, 首要的任务是建立一个出租车系统的模型, 并从中导出出租车票价于整个系统的效率之间的关系 来自交通领域的研究指出, 出租车市场受控于两个关键因素 出租车票价和工作中的出租车数量 [37, 38] 前者是我们作为决策者所要优化的对象, 而后者则决定于出租车司机 出租车司机们以盈利为目的, 相互竞争, 这样的行为决定了他们总会选择一个与给定票价相适应的最佳出勤率以最大化他们的收益 如此一来, 工作中的出租车数量归根结底也是受控于票价的 也正是如此,TEMP 通过票价调节市场效率的目标才变得可行 本章首先介绍一个基于现有交通领域研究的出租车市场模型, 并在此基础上从博弈论的角度对出租车司机的决策行为进行建模 从该模型中我们导出出租车市场与票价之间的关系, 并导出 TEMP 的形式化表达, 明确求解 TEMP 的主要难点 2.1 出租车市场基础模型出租车市场是一个随时间动态变化的模型 高峰时段的市场状况 ( 乘车需求 道路状况等 ) 同非高峰时段截然不同 为了充分地考虑这种时间上的动态性, 我们将所研究的时间周期 T ( 如一天 ) 等长度地离散为 n 个长度为 τ = T/n 的子时段 ( 简称时段 ) 当子时段足够短时, 市场的变动可以忽略不计, 从而我们可以将每个子时段内的市场视作静态的市场来建模 接下来, 我们首先介绍静态市场模型 在此基础上, 我们将模型和 TEMP 扩展到 n 个子时段 静态市场模型我们考虑第 i 个时段 为了便于后续的扩展, 所有与时段相关的变量均加上上标 i, 如时段 i 的出租车出勤率表示为 p i 如图 2.1 所示, 在静态的出租车市场中, 票价和出勤出租车比例 ( 加粗实线框 ) 通过一系列复杂的依赖关系决定了整个市场的其他因素 ( 此处考虑了出租车司机收益 运送乘客量 乘客平均等车时间 平均旅行时间 道路拥堵情况 ) 我们逐一介绍这些市场因素和依赖关系 为方便查阅, 我们将模型涉及的主要参数列在表 2.1 中 乘客运送量 : 用 D i 表示市场内所有出租车在时段 i 内所运送的乘客数量 D i 决定于平均的旅程花费, 既包括乘车的费用也包括时间上的开销 也就是说, 有出行需求的乘客会根据期望的开销决定是乘坐出租汽车, 还是选择其他交通工具 而在均衡状 7

24 中国科学院大学硕士学位论文 基于计算博弈论的出租车市场最优定价研究 表 2.1: 模型主要参数列表 参数符号类型 * 公式编号 参数描述 β + (2.1) 需求量敏感度指标 c g + (2.8) 油耗速率 D, D i (2.1), (2.2), (2.8) 整个出租车系统的乘客运送量 d 0 + (2.5) 起步距离 d + (2.5) 平均旅程距离 D i + (2.1) 理想乘客需求量 f i, f (2.5), (2.8) 单位距离车费 F i (2.1), (2.5), (2.8) 平均每段旅程的车费 f 0 + (2.5) 起步价 γ + (2.1), (2.2), (2.8) 平均载客数 L i (2.1), (2.2) 平均旅程时间 n + 划分的子时段数目 N t + (2.2), (2.4), (2.8) 出租车总数 N i v + (2.4) 路面其他车辆数量 n w + 总工作时间上限 N + (2.4) 道路承载力 ( 允许最大行驶车辆数 ) ω + (2.2) 出租车服务范围参数 p i, p (2.2), (2.4), (2.6), (2.8) PoW, 工作中出租车的比例 φ 1 + (2.1) 旅行时间开销价值 φ 2 + (2.1) 候车时间价值 s, s i (2.6) 出租车司机纯策略 S (2.6) 可行纯策略集 T + 市场周期 ( 所研究的整个时间区间 ) τ + (2.2), (2.8) 子时段长度 U, U i (2.8) 出租车司机效用 V i (2.4) 路网平均行车速度 V 0 + (2.4) 最高平均时速 W i (2.1), (2.2) 乘客候车时间 x, x s (2.6) 出租车司机混合策略 * 符号 + 表示给定参数, 表示其它变量 8

25 第二章 博弈建模 票价 运送乘客数量 出租车期望收益 候车时间 旅程耗时 A A 依赖于 B B 出租车出勤率 (PoW) 道路拥堵情况 图 2.1: 出租车市场主要因素间的复杂依赖关系 态下, 乘客的需求和出租车实际运送乘客量达到平衡 D i 由下式给出 : { ( ) } D i (F i, L i, W i ) = D F i i exp β γ + φ 1 L i + φ 2 W i, (2.1) 其中,exp( ) 表示以自然常数 e 为底的指数函数 ;F i 表示平均的票价,L i 表示平均的旅 途时间,W i 表示平均的候车时间 ;β > 0 是一个调节需求量敏感度的系数 ;φ 1 和 φ 2 是 用于统一时间和金钱开销的系数 ;γ 是出租车的平均载客量 ; D i 是理想的乘客量, 即 理想状况下当所有开销都为 0 时出租车系统所能运送的乘客量 ( 相反, 根据式 (2.1), 当 花费趋于无穷大时 D i 趋于零 ) 候车时间 : 平均等车时间 W i 反过来受到系统乘客运送量 D i 的影响, 并且同空车数 量成反比, 即 W i (D i, L i, p i ) = ω p i N t Di L i γ τ, (2.2) 其中 ω > 0 是一个表征出租车服务范围大小的参数 直观地说, 同样数量的出租车服务的范围越大, 乘客的等待时间相应地更长 出租车的总量 N t 是固定的 方便起见, 我们用出租车出勤率 ( 即工作中的出租车占比, 简记为 PoW Percentage of Working taxis)p i 表示当前工作中的出租车数量 在后文中我们将看到使用 p i 便于出租车司机的策略的表示 显然,p i N t D i L i /(γ τ) 表示当前的空车数目 可以证明, 当 F i L i 和 p i 都固定时,D i 和 W i 被公式 (2.1) 和 (2.2) 唯一地确定了 ( 命题 1) 因此,D i 和 W i 实际上可以看成是 F i L i 和 p i 三个变量的隐式函数 我们将 D i 和 W i 分别简记为 D i = D i (F i, L i, p i ) 及 W i = W i (F i, L i, p i ) 命题 1. 给定 F i L i 和 p i, 则 D i 和 W i 被公式 (2.1) 和 (2.2) 唯一地确定 1 1 该命题证明可见于 [38], 此处出于文章完整性亦给出 9

26 中国科学院大学硕士学位论文 基于计算博弈论的出租车市场最优定价研究 证明 : 将式 (2.2) 代入式 (2.1), 得 D i 为方程 x = D i( F i, p i, W (x, L i, p i ) ) 的解 下面 我们证明该方程有且仅有唯一解 为简单起见, 我们把 F i L i 和 p i 视为常数, 并 把 W i (D i, L i, p i ) 简记为 W i (D i ), 把 D i( F i, p i, W (D i, L i, p i ) ) 简记为 D i( W i (D i ) ) 定义 以下辅助函数 : Φ(x) = x D i( W i (x) ) (2.3) 根据式 (2.2) 以及 W i > 0 可得 0 < D i < γτp i N i t L i,φ(x) 为该范围内的连续函数, 同时 我们有 Φ (x) = 1 Di i W W i x = 1 + βφ 2 ωγτl i Di( W i (x) ) W i (x) 2 > 0 lim Φ(x) = Di( W i (0) ) < 0, x 0 lim Φ(x) = γτp i N x γτp i Nt i t i L i > 0 Li 因此, 有且仅有一个 x 使得 Φ(x) = 0 这说明 D i 被唯一地确定了 相应地,W i 也被唯一 确定 旅行速度 : 给定平均旅程距离 d i, 平均行车时间可以用平均车速 V i 表示, 即 L i = d i /V i 而在一个道路系统中, 平均车速和路面车辆数呈近似的线性关系 [35] 我们假 设路面上出租车以外的其他车辆的数目 N i v 在每个子时段内都是恒定的外部参数, 不受 出租车市场变化影响 平均车速可进一步表达为 PoW 的线性函数, 即 V i (p i ) = V 0 N (N t p i + Nv) i, (2.4) N 其中 N 是道路允许的最大承载能力, 即当路面上总车辆数达到 N 时路面的行车速度近乎为 0; 而 V 0 为路面允许的最大行车速度, 即当路面没有其他车辆时在路上行驶所能达到的行车速度 我们进一步将 L i D i 以及 W i 分别记为 L i =L i (p i ) D i =D i (F i, p i ) 以及 W i =W i (F i, p i ) 计价方式 : 考虑基于距离的计费方式, 乘车的费用表示为 F i = f 0 + f i (d i d 0 ), f 0 为起步价格,d 0 是起步价覆盖的距离,f i 是第 i 个时段的费率, 即单位距离的价格 我们通过调整单位距离票价 f i 优化票价, 且以平均的旅行距离 d 衡量平均的车费, 所以 F i 在该优化问题中被视为关于 f i 的函数, 即 F i (f i ) = f 0 + f i ( d d 0 ), (2.5) 10

27 第二章 博弈建模 相应地, 所有的其他变量, 特别是乘客运送量 D i, 现在都被视为 f i 和 p i 的函数 ( 即, D i = D i (f i, p i ) 等 ) 需要指出的是我们的模型也适用于其他计费方式, 此处仅以该模式为例 多时段变量 : 为了便于描述, 我们把每个变量对应到整个时间区间 T 内的所有量记作一个 n 维列向量 例如, 我们将整个时段的费率记作 f = f i, 将 PoW 记作 p = p i 到目前为止, 各个时段的模型相互独立 而在接下来的博弈建模中我们将看到各个时段的模型如何通过出租车司机的策略如何联系在一起 2.2 出租司机决策行为的博弈建模出租车司机选择合适的时间上路工作, 以最大化他们的收益 如果某个时段利润较高 ( 通常是乘客需求大 道路通畅的时段 ) 他们将倾向于在这种时间工作, 反之他们会尽量避开利润较低的时段 ( 如道路状况不佳的高峰时段 ) 除此之外, 出租车司机之间存在相互竞争的关系 如果所有人都集中在某个时段, 该时段的利润可能因为竞争过大而被拉低 从计算博弈论的角度来看, 出租车司机拥有一个策略集 S, 其中包含了他所有可行的纯策略 每个纯策略是一个时间表, 指明出租车司机在哪些时段工作, 在哪些时段休息 我们用一个 0/1 向量 s {0, 1} n 表示一个纯策略 ( 时间表 ), 其中 s i =1 表示出租司机在第 i 个子时段工作,s i =0 表示在第 i 个子时段休息 此外, 我们需要根据实际情况考虑一些约束条件以保证策略的可行性 我们暂时先考虑以下两个最基本的约束 : 约束一 (C1): 出租车司机不得工作多于 ˆn w 个子时段 约束二 (C2): 出租司机不得连续工作超过 ˆn c 个子时段 所以 S 包含且仅包含满足以上的所有纯策略 也就是说, 出租车司机在最大化收益的同时不得不受限于工作量和工作强度的限制 在后面的实验章节中我们将看到, 如果不考虑这些约束条件, 我们的模型和研究结果将偏离实际 出租车司机们采用混合策略, 即以一定的概率 ( 0) 选择策略集中的各个纯策略去执行 我们用向量 x 表示一个纯策略,x 的每个元素对应于 S 中的一个纯策略被选择的概率 鉴于大部分城市的出租车系统中, 大部分出租车都属于同一档次的车型, 采用同种收费方式和经营模式, 因而我们假设所有出租车司机都会采用同样的策略 当他们选择策略 x 时,PoW 由下式决定 : p(x) = x s s. (2.6) s S 同时, 出租车司机以盈利为首要目的, 他们总会选择使收益最大化的最优策略, 即 x * arg max x 0, 1 T x=1 U ( f, p(x) ). (2.7) 11

28 中国科学院大学硕士学位论文 基于计算博弈论的出租车市场最优定价研究 此处的效用函数𝑈 (f, p) 定义为所有子时段效用的和 即 𝑈 = 𝑖 𝑈 𝑖 而单个时段的 效用𝑈 𝑖 定义为 𝑈 𝑖 (𝑓 𝑖, 𝑝𝑖 ) = 𝐷𝑖 𝐹 𝑖 (𝑓 𝑖 ) 𝑝𝑖 𝑐𝑔 𝜏, 𝛾 𝑁𝑡 (2.8) 其中𝐷𝑖 𝐹 𝑖 /(𝛾 𝑁𝑡 ) 表示司机的收入 𝐷𝑖 /(𝛾 𝑁𝑡 )表示平均每辆出租车运送乘客的趟数 𝑐𝑔 表示单位时间内的油耗费用 可以看到 由于式 (2.7) 的存在 费率f 决定了出租车司 机的策略 这个策略再通过式 (2.6)决定PoW 注意到 如图 2.2(a) 在一个合理的费 2 率范围内 𝑈 的二阶导数 𝑝𝑈2 < 0 在除了𝑓 非常接近于0 极小的区域外均成立 我们去 除这部分区域 因为这部分面积极小 对应的PoW极低 在现实情况下几乎不会出现 从图 2.2(b) 也可以看出 𝑈 的形状几乎不受这部分区域的影响 因此 给定𝑓 的情况 下 𝑈 可以被视为关于𝑝的严格凹函数 strictly concave function 严格的凹函数的一 个性质是在一个凸 convex)的可行空间上仅有一个最大值[15] 这说明即便式(2.7)存在 多个解 所有的这些解都将对应于相等的PoW 从而确保了从f 到p 的一一对应关系 出租司机的效用 票 价 f=1.00 f=2.00 f=3.00 f=4.00 f= 出 勤 率 出 勤 率 2 (a) 二阶导数 𝑝𝑈2 等高线图 (b) 严格凹函数𝑈 图 2.2: 出租司机效用函数的严格凹形 2.3 双层优化问题 我们用总的乘客运送量𝐷(f, p) = 𝑖 𝐷𝑖 (𝑓 𝑖, 𝑝𝑖 ) 衡量出租车系统的效率 并将出租 车系统效率优化问题形式化地表达成以下双层优化问题 ( ) * max 𝐷 f, p(x ) * (2.9) f,x s.t. x* = arg max x 0, 1T x=1 ( ) 𝑈 f, p(x) (2.10) 需要说明的是 以上模型同样适用于其他系统效率的衡量方法 例如综合考虑乘客运 送量 乘客候车时间 以及对道路拥堵的影响 关键在于优化的目标是以f 和p 为 变量的函数 为了求解上述双层优化问题 一个实际的方法是离散化上层优化中的价 格空间 我们可以直接采用一个候选价格集合 如{U1.00, U1.20,..., U5.00}𝑛 并分别 带入该集合中的每个价格去求解下层 式(2.10))的优化问题 能导出最优最优系统效 12

29 第二章 博弈建模 率的价格即我们寻找的最优价格 问题的关键集中到下层优化上 不幸的是, 下层优化问题的求解也有很大的难度 究其原因是出租车司机的策略空间呈指数增大, 造成下层优化问题中的变量数也以同样的速度增加 ( 一个纯策略对应一个变量 ) 例如, 当 n = 18,ˆn w = 10,ˆn c = 4 时, 即便约束 C1 和 C2 筛除掉了部分不可行的策略,S 中剩下的策略仍有 个 在下一章中, 我们针对该问题提出的策略空间紧凑表达法以缩减问题的规模 13

30

31 第三章 模型求解 紧凑表达法 本章采用紧凑表达法解决下层优化问题中策略空间的组合爆炸问题 紧凑表达法的基本思路是将策略空间投射到另一个更易于表达的集合, 从而混合策略的表示更加紧凑 在原始的表达法中, 一个混合策略需要以所有纯策略线性组合的形式表示出来, 而事实上, 当纯策略集具备某些规律的时候 ( 如这里的纯策略集为 C1 和 C2 两个约束从所有 0/1 向量中划分出的空间 ), 它们能够组成的混合策略实际上具有一些固定的模式, 因而原始的表达法实际上是冗余的 借助策略空间本身所具有的规律, 我们可以将这种冗余的表达法进行简化 在下文中我们将看到两种紧凑表达法 ASM 算法和 FLORA 算法 我们先从比较直观的 ASM 算法开始介绍 3.1 ASM 算法 基于元时间表的紧凑表达 ASM 算法 (Atom Schedule Method) 适用于考虑约束条件 C1 和 C2 的出租车系统优化问题 算法的思路在于采用一组元时间表 (Atom Schedule) 去表示每一个符合 C1 和 C2 的时间表, 从而缩小策略空间, 并将原优化问题缩减成一个小规模的问题 图 3.1: ASM 算法 : 用一组元时间表 ( 第二行 ) 去表示一个符合 C1 和 C2 的时间表 ( 第一行 ) 我们把一个元时间表记作二元组 o j, k, 表示出租车司机从子时段 j 连续工作到子时段 k 这样一来, 我们就可以根据一个时间表中工作的区段将其转换成一组元时间表 ( 见图 3.1), 即 s = {o j, k 1 j k n, s j = s j+1 = = s k = 1}. 为了方便起见, 我们将纯策略 s 根据需要视为一个 0/1 向量或一个元时间表的集合 定义集合 O={o o s, s S}, 即用于表示可行纯策略集所需的所有元时间表 类似地, 我们为 O 中的每个元时间表 o 分配一个权重 w o, 表示出租车司机使用这个元时间表的概率 此时, 出租车司机的混合策略由向量 w = w o 表示, 而 PoW 可由下式得到 p i = w o δ(o, i), i = 1,..., n, o O 15

32 中国科学院大学硕士学位论文 基于计算博弈论的出租车市场最优定价研究 其中,δ ( o j, k, i ) = { 1, 如果 j i k ( 即,o 包含第 i 个子时段 ) 0, 其他情况 (3.1) 从而,p 现在被定义为一个关于 w 的函数 p = p(w) 同样地, 原优化问题现在被转换为以 w 而非 x 为变量的一个更加紧凑的问题 特别地, 在考虑约束 C2 的情况下, 连续工作时间不得超过 ˆn c 个子时段, 因而元时间表的长度也不会超过 ˆn c 也就是说 O {o j, k 1 j k n, 0 k j < ˆn c } 显然,O 的大小不会超过 ˆn c n, 转换后的优化问题的变量数也被限制在这个范围内 以下是紧凑表达下的出租车市场效率优化问题 : max w *,f s.t. D ( p(w * ), f ) (3.2) w * arg max U (p(w), f), (3.3) w W 其中, 0 w o 1, o O W = w R O p i (w) + q i (w) 1, i=1,..., n n i=1 pi (w) ˆn w (3.4) 类似于 PoW,q i (w) 表示在第 i 1 个子时段从工作状态切换到休息状态的出租车比例 同样地, 类似于式 (3.1) 中的 δ, 我们引入标记 δ, 并令 δ ( o j, k, i ) 1 如果 k = 1, 即 o 结束于时段 i 1 = (3.5) 0 其他情况我们有 q i (w) = o O w o δ (o, i) 在下一节中我们将证明上述定义的 W 保证了 ASM 紧凑表达法 ( 式 (3.2) (3.3)) 等价于原优化问题 ( 式 (2.9) (2.10)) 可以看出,ASM 表达法的下层优化问题的变量数和元时间表的个数相等 考虑开始和结束时间,n 个时段内可能的元时间表个数不超过 n 2 个,ASM 表达法的规模为 O(n 2 ) 3.2 ASM 紧凑表达法与原优化问题的等价性确切地说, 我们将要证明 ASM 紧凑表达法和原问题的解对应于相等的 D 和最优费率 f 我们首先定义两种表达下的混合策略的等价性 定义 1. 策略集 S 上的混合策略 x 与元时间表集合 O={o o s, s S} 上的权重向量 w 等价, 当且仅当它们对应于相同的 PoW 向量 p, 即 x s s i = w o δ(o, i), i = 1,..., n. (3.6) o O s S 16

33 第三章 模型求解 紧凑表达法 很显然, 根据上述定义我们只需要证明 :1. 对于每个混合策略 x (x 0, 1 T x = 1), 总能在 W 中找到一个等价的权重向量 w;2. 对于每个 w W, 总能在满足 x 0, 1 T x = 1 的向量中找到一个等价的 x 也就是说, 在这种情况下两种表达法把 p 限制在了同一个可行范围内, 它们的解自然相等 接下来我们分别证明上述两点 等价权重向量的存在性事实上, 对于每个混合策略 x, 我们可按下式构建一个等价的权重向量 w = w o : w o = x s, o O. (3.7) s S, o s 上式中的 w 与 x 等价 这是因为对于每个 i = 1,..., n 我们有 w o δ(o, i) = δ(o, i) x s = x s δ(o, i) = x s s i, (3.8) o O o O s S, o s s S o s s S 其中, 最后一个等式成立是因为当 s i = 1 时有且仅有一个元时间表会覆盖时段 i, 当 s i = 0 时则没有这样的元时间表 其次, 上述的构建方式保证了得到的每个 w 都在式 (3.4) 中定义的 W 内 这是因为 : 1. 根据式 (3.7),0 w o = x s x s = 1, o O, 因此 w 满足 (3.4) 中的第一个 s S, o s s S 不等式 2. 同一个时间表 s 中的两个相邻元时间表之间至少间隔一个休息时段, 因此如果 s 中有一个元时间表结束于时段 i 1 那么就不存在覆盖了时段 i 的元时间表 反之, 如果有元时间表覆盖了时段 i, 也就不可能存在元时间表结束于时段 i 1 那么, 对于所有的 i = 1,..., n, 我们有 δ(o, i) + δ (o, i) 1, o s o s p i + q i = o O w o δ(o, i) + o O w o δ (o, i) = o O = s S = s S δ(o, i) x s + s S, o O o s x s δ(o, i) + o s s S x s ( o s δ(o, i) + o s δ (o, i) s S, o s x s o s x s δ (o, i) ) δ (o, i) x s = 1, s S 即, 式 (3.4) 中的第二个不等式满足 17

34 中国科学院大学硕士学位论文 基于计算博弈论的出租车市场最优定价研究 算法 1: 根据一个权重向量 w W 构建一个满足约束 C2 的混合策略 x 1 A ; 2 B {o o O, w o > 0} (O 由式 (3.1) 定义 ); 3 while B = do 4 s ; 5 l 0 ; 6 for B 中的每个 o j, k 按 j 降序排列 do 7 if j > l + 1 then l k, s s {o}; 8 w min min o s w o ; 9 x s w min, A A {s} ; 10 for s 中每个元时间表 o do 11 w o w o w min ; 12 if w o = 0 then B B {o} ; 13 if s A x s < 1 then 14 s ; 15 x s 1 s A x s, A A {s} ; 16 return 纯策略集 A, 以及 A 上的混合策略 x; 3. 根据 x 和 w 的等价关系 ( 即式 (3.8)) 以及所有 s S 均满足约束 C1, 我们有 n p i = n w o δ(o, i) = n x s s i = s S x s n s i x sˆn w = ˆn w. s S i=1 i=1 o O i=1 s S i=1 即, 式 (3.4) 中最后一个不等式满足 等价混合策略的存在性类似地, 我们通过为任意权重向量构造等价混合策略的方式证明其存在性 我们为每个 w W 构造一个 x (x 0, 1 T x = 1) 这个方向的构造比较复杂, 我们分两步完成 首次, 我们构造一个初级的混合策略, 这个混合策略除了用到 S 中的纯策略外 ( 即同时满足 C1 和 C2 的纯策略 ), 还用到了一些只满足 C2 的纯策略 该步骤由算法 1 给出 其次, 我们调整上一步中产生的初级混合策略, 将其使用到的不满足 C1 的纯策略替换为同时满足 C1 和 C2 的纯策略 该步骤由算法 2 给出 下面我们详细介绍算法 1 和 2 算法 1: 算法 1 的 3 至 12 行的 while 循环产生一个纯策略 s 并指定其在混合策略中的概率为 x s 其中, 第 6 到 7 行不断将新的元时间表附加至正在构造的纯策略末尾 每次 18

35 第三章 模型求解 紧凑表达法 附加的元时间表不能和当前的 s 冲突, 即不能和 s 中已有的元时间表有重叠的部分, 且 必须和其他元时间表保持至少一个时段的间隔 ( 避免两个元时间表连接在一起组成 一个违反 C2 的区段 ) 我们称这样的元时间表为对于 s 可附加的元时间表 当存在多个 可附加的元时间表时, 算法选择开始时间最早的一个 ( 如果仍有多个, 则任意选取一 个 ) 显然, 这种方法产生的所有纯策略都满足 C2 接下来, 第 8 至 9 行为产生的纯策 略 s 分配一个概率 这个概率为 s 中所有元时间表剩余权重的最小值, 从而保证分配的 可行性 特别的, 每次分配过后我们将 消耗殆尽 的元时间表移除出 B, 在后续的分 配中不再考虑 这里, 一个关键的问题是我们必须保证最终产生的策略 x 满足 1 T x = 1, 以保证其为一个合理的概率分布 命题 2 证明, 在 while 循环结束后,A 中所有纯策略的 概率和不大于 1 而当这个概率和小于 1 时, 我们只需要添加一些 空 的纯策略 ( 即 不包含任何元时间表, 所有时段都不工作 ) 就可以将不足的空间填满 这个过程由 第 Lines 13 至 15 行执行 命题 2. 算法 1 中 while 循环后 ( 第 12 行 ) 产生的混合策略满足 s A x s 1 A 证明 : 令 A 中第 l 个被添加进的元时间表为 s l, 其概率为 x sl 我们用反证法证明 l=1 x s l 1 当 l = 1 时我们有 1 l=1 x s l = x s1 1, 假设对于某个 l 1, 我们有 l 1 以 及 l +1 l=1 x s l > 1 l=1 x s l 令 s l +1 中开始时间最早的元时间表为 o j, k, 即 j = min{j o j, k s l +1} 事实 上, 这部分 o j, k 在构造元时间表 s 1,..., s l 时没有被用到, 是因为在 s 1,..., s l 中时段 j 1 或 j 中至少有一个已经被覆盖了 ( 否则,o j, k 将会被优先附加, 因为第 6 至 7 行总是 使用开始时间最早的元时间表 ) 这就表明,s 1,..., s l 每个纯策略中都存在一个这样的 元时间表 o * j *, k *, 它或者覆盖了时段 j 或者结束于时段 j 1, 即 δ(o *, j)+δ (o *, j) = 1 定义 O j * = {o * j *, k * o * O, δ(o *, j) + δ (o *, j) = 1}, 对于所有 l = 1,..., l, 我们有 O j * s l 从而, p i + q i = o O w o δ(o, j) + o O o O * j w o = o O * j w o δ (o, j)] o O * j s A, o s x s = s A 这同式 (3.4) 中的第二个不等式矛盾 因此, l 地, 对于 l = A, A l=1 x s l 1 得证 x s o O * j s 1 = l=1 x s l w o [δ(o, j) + δ (o, j)] l x sl l=1 o O * j s l l +1 1 x sl > 1, l=1 1 对于所有 l 1 均成立 特别 算法 2: 算法 2 进一步调整算法 1 产生的混合策略, 以使所有纯策略都满足 C1 和 C2 该算法的核心是第 5 至 7 行的一个置换过程 我们将纯策略 s 的一个子时间表记作 s j,k = (s j, s j+1,..., s k )(1 j k n) 置换过程对应于两个时间表, 不妨记为 s 和 s 当 s 和 s 置换于时段 i, 我们先将他们分别断开成两个子时间表 :s 变为 s 1,i 和 s i+1,n ; 19

36 中国科学院大学硕士学位论文 基于计算博弈论的出租车市场最优定价研究 算法 2: 调整纯策略集 A 上一个满足 C2 的混合策略 x 使其同时满足 C1 和 C2 1 A k {s s A, s = k}, k = 1,..., n; 2 while n k=^n w+1 A k do 3 s 一个满足 n k= s +1 A k = 和 A s 的纯策略 ; 4 s 一个满足 s 1 k=1 A k = 和 A s 的纯策略 ; 5 for i = 1 to n do 6 if (s 1,i, s i+1,n) = ˆn w 且 (s 1,i, s i+1,n) 和 (s 1,i, s i+1,n) 均满足 C2 then 7 Break; 8 x min min{x s, x s }; 9 t (s 1,i, s i+1,n), t (s 1,i, s i+1,n); 10 if t A^nw then 11 x t x t + x min ; 12 else 13 x t x min, A^nw A^nw {t }; 14 if t A t then 15 x t x t + x min ; 16 else 17 x t x min, A t A t {t }; 18 x s x s x min, x s x s x min ; 19 if x s = 0 then A s A s {s }; 20 if x s = 0 then A s A s {s }; 21 A ^nw k=1 A k; 22 return 纯策略集 A, 以及 A 上的混合策略 x; 20

37 第三章 模型求解 紧凑表达法 s 变为 s 1,i 和 s i+1,n 然后再将它们交叉合并成两个新时间表, 记作 t = (s 1,i, s i+1,n) 和 t = (s 1,i, s i+1,n ) 令 s 表示 s 所覆盖的时段个数, 即 s = n i=1 s i 算法 1 返回的混合策略可能不满足约束 C1 也就是说存在 s A, 使得 s > ˆn w 算法 2 所做的也就是将 所有不满足 C1 的纯策略 s 和另一个满足 s < ˆn w 的纯策略 s 置换, 从而逐步将不满 足条件的策略消除 这里需要注意 : 1. 当存在一个不符合条件的纯策略 s 时, 我们总能找到一个上述的纯策略 s 与 s 置换 假设不存在这样的 s, 那么对于所有 s A, s ˆn w, 并且特别地 s > ˆn w 可得 s A x s s > s A x sˆn w = ˆn w, 这与式 (3.4) 中第三个不等式矛盾 因此假设不成立 2. 置换过程可能使得原来满足 C2 的两个纯策略置换后不再满足 C2 然而, 命题 3 表明, 对于给定的 s 和 s, 总是能找到一个合适的位置 i, 使得它们在置换后仍然满足 C2, 并且其中一个纯策略恰好覆盖了 ˆn w 个时段 第 5 至 7 行的 for 循环的目的就是寻找这样一个合适的位置 i 此处我们不妨设这个纯策略为 t, 即 t = ˆn w, 并设另一个纯策略为 t 我们有 t + t = s + s, t = s + s t = s + s ˆn w, s < t < s. (3.9) 也就是说, 置换过后, 其中的一个策略一定满足 C1 另一个策略即便不满足 C1, 它覆盖的时段也比之前的 s 少 所以, 我们只要继续使用置换过程, 不满足 C1 的纯策略所覆盖的时段只会越来越少, 直至所有策略覆盖的时段数都少于 ˆn w 3. 在置换过后,x s 和 x s 中较小的一个值被分配给新生成的两个纯策略 ( 第 8 行 ) 也就是说, 其中一个纯策略被全部置换掉了, 而另一个中可能还剩余一部分继续, 需要在后续的过程中继续置换 令 A k A 表示一个包含 A 中所有覆盖了 k 个时段的纯策略的集合 ( 第 1 行 ) 我们接下来说明随着置换的进行, 违反 C1 的约束会最终全部被移除, 即 n k=^n A w+1 k 会变为空集 注意到, 每次置换过后,A s 和 A s 至少有一个中的元素会减少一个 ( 第 19 和 20 行 ), 而 A^nw 和 A t 分别至多增加一个元素 ( 第 10 和 17 行 ) 这里因为 A t 的增加, 暂时无法保证 n k=^n A w+1 k 每次会逐渐减少 但事实上, 根据式 (3.9), 增大的集合的下标 ( t ) 会介于参与置换的两个原策略之间 ( s 和 s ), 且第 3 和 4 行选择 s 和 s 的方式保证了不存在覆盖时段数大于 s 或小于 s 的纯策略, 整个置换过程相当于不断地迫使下标大于 ˆn w 的集合 A k 中的元素向下标更小的集合中移动 一旦 s 和 s 参与了置换, 在后续的置换中 A s 和 A s 的大小将只减不增, 直至 n k=^n A w+1 k 变为空集 21

38 中国科学院大学硕士学位论文 基于计算博弈论的出租车市场最优定价研究 4. 显然, 算法 2 中的所有步骤 ( 主要是置换过程 ) 都不会导致 PoW 的变化, 其最终产 生的混合策略和 w 等价 命题 3. 给定两个满足 C2 的纯策略 s 和 s, 并且 s > ˆn w s < ˆn w 那么存在 i {1,..., n} 使得 (s 1,i, s i+1,n) = ˆn w 并且 (s 1,i, s i+1,n) 和 (s 1,i, s i+1,n) 满足 C2 证明 : 算法 2 第 5 至 7 行的 for 循环搜索满足题设条件的 i 我们证明 for 循环最终会因为 第 7 行中的条件不满足而跳出, 从而找到一个满足条件的 i 为便于描述, 令 t i = (s 1,i, s i+1,n), 令 t i = (s 1,i, s i+1,n) 注意到, 如果我们在 i = 0 处置换 s 和 s ( 即整个对调 s 和 s ), 我们得到 t i = t 0 = s < ˆn w ; 而如果我们 在 i = n 处执行置换, 我们得到 t i = t n = s > ˆn w 比较相邻的两个置换点, 我 们有 t i t i 1 = s i s i { 1, 0, 1}, 也就是说, 当置换点 i 从 0 变动到 n 时, t i 的值在 s 和 s 之间 连续 地变动, 从而这个区间内每一个离散的值都会被取到 ( 即 s, s + 1,..., s ) 特别地,ˆn w + 1 属于该范围, 也会被取到 现在我们假 设 for 循环没有停止, 并且在某个位置 i * 第一次使得 t i = ˆn w + 1 成立 接下来我们分 析每种可能的情形, 并最终证明这种情况不可能发生,for 循环在碰到 t i = ˆn w + 1 这 种情况前就必然因为找到满足命题条件的 i 而跳出 工作时段休息时段 s s i 2 i 1 i s s i 2 i 1 i (a) (b) s s i 2 i 1 i s s i 2 i 1 i (c) (d) 图 3.2: t i * = ˆn w + 1 可能的情形 22

39 第三章 模型求解 紧凑表达法 s s j 2 j 1 j i 1 i 图 3.3: 图 3.2(d) 续 我们考虑时段 i * 1 和时段 i * 的情形 图 3.2 列出了所有可能的模式 首先, 我们 有 s i * s i *, 因为否则的话,for 循环在 i * 1 处就有 t i = ˆn w + 1, 与假设的 i * 是第一个这样的点矛盾 进一步, 我们有 s i = 1 和 s * i = 0, 否则的话 s * i = 0 s i = 1, 那么就有 t i 1 = ˆn * w + 2, 这同样也说明在 i * 之前就应该有一个使得 t i = ˆn w + 1 的位置 事 实上, 上述这些情况都不可能出现 : 1. 显然, 在图 3.2(a) 和 3.2(b) 中, 我们有 t i * 1 = ˆn w, 并且注意到在 i * 1 处置换不会 造成合并后因两个元时间表连接在一起而违反 C2 因此,i * 1 是一个满足命题条 件的置换点,for 循环事实上在 i * 之前就已经跳出, 这两种情况都不会出现 2. 对于图 3.2(c) 中的情形, 可以验证 t i * 2 = ˆn w + 1 这和 i * 是第一个满足 t i = ˆn w + 1 的位置矛盾, 因此这种情况也不会出现 3. 对于图 3.2(d) 中的情形, 可以验证 t i * 1 = ˆn w 事实上, 在 i * 1 处置换也不会违 反 C2 我们可以假设在 i * 1 处置换违反了 C2 此时, 违反 C2 的只可能是 t i * 1, 同时, 如图 3.3 所示,s 中结束于 i * 1 的元时间表必然先于 s 中覆盖了 i * 1 的元时间 表开始 令 j 为 s 中覆盖了 i * 1 的元时间表开始的时段, 那么我们有 t j 2 = ˆn w + 1, 这和 i * 是第一个满足 t i = ˆn w + 1 的位置矛盾 因此, 在 i * 1 处置换不会违反 C2, for 循环在 i * 1 处就已经跳出, 图 3.2(d) 中的情形不会出现 综上所述,for 循环一定能找到一个满足命题条件的置换点 i 3.3 FLORA 更加紧凑的表达法 ASM 用一种直观的方法将原优化问题的规模从指数级别缩小为 O(n 2 ) 级别 通过进一步的挖掘, 本节将要介绍的算法 FLORA(FuLly compact RepresentAtion, 即完全紧凑表达法 ) 将这个规模继续缩小为 O(n) 同样的,FLORA 也适用于考虑了约束 C1 和 C2 的问题 不同的是,FLORA 不需要借助任何形式的时间表, 而是直接对 PoW 进行优化 从式 (2.9) 和 (2.10) 我们已经观察到,PoW 在出租车司机策略 x 和整 23

40 中国科学院大学硕士学位论文 基于计算博弈论的出租车市场最优定价研究 个模型之间起到一个 桥梁 的作用 事实上, 我们也并不关注微观层面上出租车司 机具体会采取什么样的策略, 而更关心宏观上出租车的供给状况 ( 出勤率 ), 因此我们 可以直接以 PoW 为优化对象, 将问题转化为如下形式 : max f,p s.t. D(f, p * ) (3.10) p * = arg max p P U(f, p) (3.11) 这样一来, 下层问题仅含有 n 个变量 ( 即 p = p 1,..., p n ) 但问题的关键是, 我们需要 显式地将可行域 P 表示出来 为此, 我们先从下式中 P 的一种隐式表达出发, 再由此 导出一种显式的表达, 并证明两者等价 我们有 P = p p = Rn s S x s, 0 x 1, 且 1 T x=1. (3.12) 将 S 视为一个 n 维空间的点集, 不难看出,P 实际上 S 的一个凸包, 表示一个以 S 中 的点为顶点的凸多面体 凸多面体有两种表达方式 [22]:1. 顶点表示法 (Vertex representation), 即表示为顶点的凸组合形式 ( 凸包内的任意一点都可以表示为凸 包顶点的凸组合 );2. 半空间表示法 (Half-space representation), 即以多面体的 边界划分出的半空间的交集表示, 而每个边界由一个线性不等式给出 一个简 单的例子是 2 维空间内的正方形区域 0 x 1, 0 y 1( 半空间表示法 ) 它 的顶点为四个点 (0, 0),(0, 1),(1, 0) 和 (1, 1), 因此这个区间内的所有点也都可以表示 成 (x, y) = k 1 (0, 0)+k 2 (0, 1)+k 3 (1, 0)+k 4 (1, 1) 的形式, 且 k 1,..., k 4 0,k 1 + +k 4 = 1 ( 顶点表示法 ) 式 (3.12) 是 P 的顶点表示法 我们希望通过半空间表示法将其转化为 n 维 空间的线性不等式, 从而可以不依赖于额外的系数 x 可以证明, 当 S 满足 C1 和 C2 时, 其对应的凸多面体 P 的半空间表示对应于下列一组线性不等式 : I n 1. 1 I n 0. p 0. (3.13) 1 1 ˆn w 1 1 ˆn c ˆn c ˆn c

41 第三章 模型求解 紧凑表达法 我们将上式定义的凸多面体记为 P H 我们说 P H 等价于 P, 这是因为 : 1. P P H 这是因为 P 的所有顶点, 即 S 中所有的点都满足式 (3.13) 注意到 式 (3.13) 虚线分为四个部分 : 前两个部分, 即 0 p 1 显然被 S 中所有的点满 足, 因为它们都是 0/1 向量 第三 四部分则分别对应于约束 C1 和 C2,S 中所有的 点都满足 2. P H P 可以证明,P H 的所有顶点都是 0/1 向量 ( 命题 4), 而根据 S 的定义,S 包 含了所有满足约束 C1 和 C2 的 0/1 向量 S 包含 P H 所有的顶点 P H P 将式 (3.13) 简记为 Ap b, 下层优化问题现转化为如下形式 : max p 仅含有 n 个变量和少于 3n 个约束, 问题规模进一步缩减 U(f, p) (3.14) s.t. Ap b (3.15) 命题 4. 令 P H 为式 (3.13) 定义的凸多面体, 则 P H 所有的顶点都是 0/1 向量 证明 : 假设 v = (v 1,..., v n ) T 为 P H 的一个顶点 我们证明 v {0, 1} n 首先, 一个 n 维 空间内的凸多面体的顶点位于这个凸面体的 n 个表面上, 可以被表示为这 n 个表面的交 点 因此,v 其实是式 (3.13) 中的 n 个不等式对应的等式 ( 即把不等号变为等号 ) 组成 的方程组的唯一解 我们将这个方程组写为 : A v = b (3.16) 其增广形式为 ( ) A = A b. (3.17) A 是式 (3.13) 中等号左边矩阵的一部分, 因而具有如下两条性质 : 性质一. 所有的元素非 0 即 1 性质二. 每行中的 1 都是连续出现的 根据上述性质, 对于增广矩阵的第 i 行 a i = [a i b i ], 我们定义 L(a i) = min{j a ij = 1, j {1,..., n}}, 其中 a ij 表示 a i 的第 j 个元素 同样地, 我们定义 R(a i) = max{j a ij = 1, j {1,..., n}} 换言之,L(a i) 和 R(a i) 分别表示 a i 中最左边和最右边的 1 的位置 接下来, 我们按算法 3 中的方式对 A 进行行变换 整个过程下来, A 将依次被变换成式 (3.18) 中的形式 其中星号标记处表示任意 ( 且未必相同 ) 的整数 我们对该过程作如下阐述 首先, 对于第一个步骤 ( 第 1 至 10 行 ): 25

42 中国科学院大学硕士学位论文 基于计算博弈论的出租车市场最优定价研究 算法 3: 行变换 1 for k = 1 to n do 2 L k {i L(h i) = k, i {1,..., n}}; 3 while 存在某个 L k 包含多于一个元素 do 4 i 0 arg min i {R i i {1,..., n}}; 5 for 每个 i L k {i 0 } do 6 a i a i a i 0 ; 7 L k L k {i}; 8 l L(a i); 9 L l L l {i}; 10 按 A 每行最左边的 1 的序数递增的顺序重新排列各行 ; 11 for i = n 1 to 1 do 12 for j = n to 1 do 13 a i a i a ij a j; 1. 整个第 1 至 10 行的过程都不会破坏 A 的两条性质 注意到, 唯一可能破坏这些性质的是第 6 行中的作差运算 但因为 L(h i) = L(h i 0 ) 且 R(h i) R(h i 0 ), 该操作实际上不会影响到 A 的性质 2. 第 3 行保证了每个 L k 至多含有一个元素 但如果某个 L k 一个元素都不含有, 那么 A 的秩将小于 n( 最终的上三角矩阵将缺少非零元素从第 k 列开始的行 ), 这和式 (3.16) 有唯一解矛盾 因此, 当 while 循环结束时, 唯一的结果只可能是每个 L k 都含且仅含一个元素, 最终的三角矩阵中对于每个 k = 1,..., n 有且仅有一行里的第一个 1 出现在第 k 位 A 算法 3, 第 1 至 10 行 1 * * * * * 1 * 算法 3, 第 11 至 13 行 1 * 1 * * (3.18) 26

43 第三章 模型求解 紧凑表达法 第 11 至 13 继续将 A 转化为最终的形式 左半部分为单位矩阵, 右半部分所有的值都是整数 ( 因为第 13 行中所有参与运算的都是整数 ) 因此, 方程 (3.16) 的解是整数 我们有 v Z n 再者, 式 (3.13) 要求 0 v 1, 因而 v {0, 1} n 27

44

45 第四章 解决任意约束下的问题 前一章的紧凑表达法巧妙的利用了约束 C1 和 C2 的特点 但这同时也是两种紧凑表达法的局限性所在, 它们无法紧凑表达其他约束下的策略空间 本章中我们首先分析在某些实际情况下考虑其他约束条件的必要性 然后我们在 FLORA 算法的基础上提出一个可以处理任意约束条件下的 TEMP 问题的算法 FLORA-A(FLORA with Arbitrary scheduling constraints) 4.1 考虑任意约束条件为了提高模型的准确性, 使其能更加精确地反映现实, 我们需要考虑更加细节的一些实际情况 其中, 在博弈建模这一部分, 出租车司机做决策时受到的约束限制是一个刻画现实细节的重要因素 前述的 ASM 算法和 FLORA 算法均针对于考虑了约束 C1 和 C2 的问题 虽然这两个最直观的约束能够满足大部分的实际问题, 我们依然看到, 在处理其他一些特定问题或采用更精细的模型时, 仅考虑这两个最一般的约束条件仍然是不够的 例如, 当模型划分得更加精细的时候, 一个时段可能持续较短的时间 ( 如半个小时 ) 这个时候, 除了考虑出租车司机工作时间的上限以外, 我们也有必要考虑连续工作时间的下限 否则, 就会出现出租车司机仅工作半个小时 ( 即一个时段 ) 后又切换回休息状态, 以及仅休息半个小时又再次出车的情况 很显然, 这都和现实情况不符 出租车司机为切换工作状态往往会付出一定的代价去寻找合适的停车地点, 且过于频繁地切换也不符合常人的工作习惯 因此, 在这些情况下, 我们有必要考虑下列的这些约束 : 约束三 (C3): 出租车司机每次工作最短需持续 ˇn c 个时段 约束四 (C4): 出租车司机每次休息至少休息 ˇn r 个时段 此外, 在一个受到市场规章制度良好管制的市场, 我们同时有必要将这些规章制度对出租车司机决策的影响考虑在内 例如, 在中国的很多大城市, 如武汉 福州 合肥 南京 [1, 3, 5, 6], 出租车司机禁止在高峰时段交接班 在这条规定实施前, 往往有大量的出租车司机以交接班为由在高峰时期乘客需求剧增的情况下拒载乘客, 使得高峰期出租车系统的效率大幅下降 而和北京 上海这类超级大城市不同, 在这些二 三线城市通过合理的监管和有效的惩罚机制, 这些规章制度的实际执行得到了很好的保障 因而它们的作用不可忽视, 我们也有必要将将其纳入建模的考虑范围 具体地说, 我们考虑下列约束 : 约束五 (C5): 出租车司机不得在指定的时段内 ( 如上下班高峰期 ) 交接班 29

46 中国科学院大学硕士学位论文 基于计算博弈论的出租车市场最优定价研究 不幸的是, 前述的两种紧凑表达算法均不能考虑上述列出的这些约束条件 其中, ASM 算法中的关键 部件 元时间表的结构极大地依赖于 C1 和 C2, 不能扩展到更为复杂的时间表 而 FLORA 算法所用到的凸多面体转换的方法, 虽然理论上可以将任何问题转换到 n 维的 PoW 空间上, 但实际上凸多面体表示法的转换问题 (Facet enumeration problem) 是一个极其复杂的问题 : 其一, 转换的时间复杂度可能很高, 目前还没有多项式时间内的算法 [12]; 其二, 即便能有效地转换, 转换的结果也可能非常复杂, 即便是 0/1 凸多面体 ( 以 0/1 向量为顶点的凸多面体 ) 在 n 维空间中, 它的面数也可能达到 O ( (n 2)! ), 对应于同样数量的线性不等式 [21, 31] 这些事实都决定了凸多面体表示法的转换的思想难以解决带有更加一般的约束条件的问题 在本章中, 我们提出新算法 FLORA-A 在目标函数为可微凹函数的情况下,FLORA-A 能处理具有任意约束条件的出租车系统效率优化问题 注意, 此处的任意约束条件指的是所有将 n 维 0/1 向量划分为可行和不可行两个部分的约束, 或者说这样的约束对应于一个判别函数 g : {0, 1} n {0, 1} 接下来, 我们对 FLORA-A 算法进行介绍 4.2 FLORA-A 算法 FLORA-A 的思想由算法 4 简要给出 在前文中我们提到过, 下层优化问题计算出租车司机最优策略时受制于出租车司机策略集的指数增长造成的规模过大问题 与这个巨大的策略集形成鲜明对比的是, 出租车司机事实上只需要很少的纯策略就可以实现其最优策略 这点可以通过 Carathéodory 定理 ( 定理 5) 进行说明 具体地说, 从 FLORA 算法使用的完全紧凑表达法中我们看到, 出租车司机的任意一个策略 x, 只要它对应于 (3.11) 的最优解 p * ( 即 p(x) = x * ), 那么这个策略就是一个最优策略 我们感兴趣的是所有这些对应于 p * 的混合策略里使用纯策略数最少的一个 ( 当一个混合策略里某个纯策略的概率大于 0 时, 我们说该混合策略使用了这个纯策略, 所有这些被使用到的纯策略组成该混合策略的支持集 ) 由式 (3.12) 可知,p * 是 P 这个凸多面体中的一个点, 进而由 Carathéodory 定理可知,p * 一定处于一个以 P 的 d 个顶点为顶点的凸多面体,d n + 1 也就是说,p * 可以被表示成 P 的 d n + 1 个顶点的凸组合 我们仅需这些顶点对应的纯策略就能构造出一个出租车司机的最优策略 因此, 在上述分析的小支持集结论的启发下,FLORA-A 算法的思想是将原问题 ( 式 (2.10)) 限制在一个较小的纯策略集 S S 上 ( 即求策略集 S 上的最优混合策略 ; 此时的变量 x 维度为 S ) 例如, 我们从 S 中选择任意 n + 1 个策略组成 S ( 关键在于 S 要足够小, 避免规模过大 ) 我们求解这个 局限 的问题 ( 暂且称其为 S - TEMP) 如果运气很好的话, 可能 S 恰好包含了所有构造最优策略必须得纯策略, 显然, 此时 S -TEMP 的最优解同时也是原问题的一个最优解 当然, 在大多数情况下我们不会那么走运, 我们选取的 S 未能包含所有必须的纯策略 在这种情况下, S -TEMP 的最优解比原问题最优解差, 我们需要其他一些未包含在 S 中的纯策略的支持, 以提升当前问题的解 于是,FLORA-A 在 S S 中寻找这样一个纯策略, 把它加 30

47 第四章 解决任意约束下的问题 算法 4: FLORA-A 算法 1 S n + 1 个从 S 中随机选取的纯策略 ; 2 repeat 3 x * arg max x: S 上的一个概率分布 U ( f, p(x) ) ; 4 p * p(x * ); 5 s arg max s S (s p * ) T U(p * ); 6 S S {s}; 7 until (s p * ) T U(p * ) 0; 入 S 并构造一个新的 S -TEMP, 再次求解 FLORA-A 重复上述求解 S -TEMP 寻找必要的纯策略添加到 S 求解 S -TEMP 的过程, 直至再也找不到这样能够提升问题的解的纯策略 相应地, 问题的解逐次递增, 直至达到原问题的最优解 那么, 问题的关键在于如何寻找能够提升 S -TEMP 的解的纯策略 为此,FLORA- A 借助于目标函数为可微凹函数的特性对 S -TEMP 的最优解进行评估 注意到,S - TEMP 的目标函数 ( 最大化 ) 为凹函数, 可行域 ( 即 S 的凸包 ) 为凸集, 这样的问题属于凸优化问题, 稍后我们将利用到这类问题最优解的判别条件 令 x * 为 S -TEMP 的最优解 FLORA-A 计算目标函数 U 在 PoW 空间上点 p * = p(x * ) 处的梯度, 并寻找 s S 中一个满足 (s p * ) T U(p * ) > 0 的点 s( 为便于叙述我们将 U(f, p) 简记为 U(p),f 在下层问题中其实是定值 ) 这样一来: 如果找到一个满足条件的 s,s 被扩展为 S = S {s}, 进而 PoW 的可行域从 S 的凸包 P 扩展为 S 的凸包 P 此时,U 在 P 上的最优值一定大于在 P 上的最优值, 因为此时最优判别条件 ( 定理 6) 对于 P 上的最优解 p * 在点 s P 处不成立 如此一来, 新构造的 S -TEMP 的解比上一个 S -TEMP 提高了 如果找不到满足条件的 s, 那么对于所有的 s S 我们都有 (s p * ) T U(p ) 0 那么容易验证, 对于 S 的凸包中所有的点 p, 我们也有 (p p * ) T U(p ) 0 ( 将每个 p 表示成 S 中的点的凸组合即可验证 ) 此时, 根据最优判别条件,p * 必然已经是 P 上的最优解 注意到, 第 5 行我们需要寻找 S 中使得 (s p * ) T U(p * ) 最大的点, 这一来是为了便于判断不存在符合条件的点的情况 ( 很显然, 当该最大值都小于零时将不存在符合条件的点 ), 二来将问题形式化为一个优化问题我们可以使用已有的方法和工具很容易地对问题进行高效地求解 我们将在下一节中详述这里的第二点 定理 5 (Carathéodory 定理 [17]). 如果一个 n 维空间中的点 p R n 在一个点集 S 的凸包中, 那么存在一个 S 的一个包含不多于 n + 1 个点的子集 S, 使得 p 包含在其凸包中 31

48 中国科学院大学硕士学位论文 基于计算博弈论的出租车市场最优定价研究 证明 : 1 点集 S 的凸包包含且仅包含所有能够被表示成 S 中有限个点的凸组合的点 假 设 p 是 S 中 m 个点的凸组合, 即 p = α 1 s 1 + α 2 s α m s m 其中 α α m = 1 且 s 1,..., s m S 如果 m n + 1, 那么命题条件已满足 如果 m > n + 1, 那么 s 2 s 1, s 3 s 1,..., s m s 1 这 m 1 个点线性必然线性相关 (n 维空间中的多于 n 个点 ) 令 β 2, β 3,..., β m 为 m 1 个不全为零的实数, 且满足 m β i (s i s 1 ) = 0. i=2 也就是说, 存在 m 个不全为零的常数 γ 1,... γ n (γ 1 = m i=2 β i,γ i = β i, i = 2,..., m), 使得 m m γ i s i = 0, 且 γ i = 0. i=1 令 I 为序号集 {i {1, 2,..., m} γ i > 0} 因为 m i=1 γ i = 0 且 γ 1,... γ n 不全为零, 所 以 I 非空 接下来令 我们有 p = m α i s i = i=1 i=1 a = max i I α i/γ i. m α i s i a i=1 m γ i s i = i=1 m (α i aγ i )s i, 即一个至少含有一个零系数的凸组合 这就是说, 当 m > n + 1 时,p 实际上可以被写 为 S 中 m 1 个点的凸组合 重复上述步骤 m n + 1 次, 即可将 p 表示为 S 中 n + 1 个点 的凸组合 定理 6 ( 凸优化问题的最优解判别条件 [15]). 假定一个凸优化问题 ( 即一个以凹函数为 目标函数, 以一个凸集为可行域的最大化优化问题 ) 的目标函数 f(x) 可微 其可行域 为 X 那么 x * X 为 X 上的最优解, 当且仅当 (x x * ) T f(x * ) 0 对于所有的 x X 均成立 ( 图 4.1) 证明 : 2 首先我们用反证法证明命题的充分性 假设对于某个 x * X, 有 (x x * ) T f(x * ) 0, x X, 但 x * 不是最优点, 即 x X, f(x ) > f(x * ) 由 X 为凸集, 得 x * + h(x x * ) X, h [0, 1]. 又由于 f 为凹函数, 我们有 f ( hx + (1 h)x *) h f(x ) + (1 h) f(x * ), h [0, 1] 因此, 1,2 i=1 f ( x * + h(x x * ) ) = f ( hx + (1 h)x *) h f(x ) + (1 h) f(x * ) > h f(x * ) + (1 h) f(x * )f(x * ), 证明可见于标明的文献, 非本研究贡献, 此处出于文章完整性亦给出 32

49 第四章 解决任意约束下的问题 f(x ) x X 图 4.1: x * 为 X 上的最优点 ( 虚线为等值线 ) 这样就出现一个矛盾 : (x x * ) T f(x * ) = x x *f(x* ) ( f x * + h(x x * ) ) f(x * ) = lim h 0 h > 0 所以, 假设不成立,x * 必然是 X 上的最优 接下来, 我们用反证法证明必要性 假设 x * 为最优解, 且存在另一个点 x X 使 得 (x x * ) T f(x * ) > 0 定义以下函数 : Φ(h) = f( x * + h(x x * ) ) f(x * ). h 我们有 lim h 0 Φ(h) = x x *f(x * ) = (x x * ) T f(x * ) > 0 根据局部保号性, 存 在 δ > 0 使得 Φ(h) > 0 对于所有的 0 < h < δ 成立 令 h = 1 2 min{δ, 1}, 我们有 Φ(h ) > 0, 进而 f ( x * + h (x x * ) ) > f(x * ) 由于 X 为凸集, 我们有 x * + h (x x * ) X 因此 这和 x * 为最优点矛盾 因此假设不成立 max f(x) f( x * + h (x x * ) ) > f(x * ), x X 综上所述, 命题成立 利用线性不等式表达约束条件前面已经提到在算法 4 的第 5 行我们需要寻找 S 中满足条件的纯策略 最简单粗暴的办法是将 S 遍历一遍, 直到找到符合条件的纯策略 这种方法适用于所有的约束条件 再根据约束性质进行必要的剪枝可以使效率进一步提高 事实上, 大多数约束条件本身是可以以线性约束的形式给出的, 如本文中列出的所有约束条件 (C1-C5) 在这种情况下, 我们可以将这个步骤形式化为标准的整型线性规划问题 (Mixed-Integer 33

50 中国科学院大学硕士学位论文 基于计算博弈论的出租车市场最优定价研究 Linear Programming), 即如下形式 max (s p * ) T U(p * ) (4.1) s {0,1} n s.t. c 1 s b 1 (4.2) c 2 s b 2 (4.3)... 整型线性规划是一类非常典型的优化问题, 已经有一系列成熟的算法和工具 ( 如本文 实验部分用到的 CPLEX) 可以对其进行求解, 因而关键在于如何将约束条件表示成线 性约束的形式 下面我们详细讲解如何对本文中的约束条件表示成线性约束 C1 与 C2: 如 3.3 节所述, 违反 C1 和 C2 的纯策略分别可以被式 (3.13) 的第三 四部分 筛选掉, 这也就是它们对应的线性约束, 此处不再赘述 C3: 约束 C3 要求连续工作的时间不得少于 ˇn c 个时间段 那么, 所有违背了 C3 的纯 策略中必然至少会出现一段被 0 分隔开的连续的 1, 其长度为 m < ˇn c, 即如下 形式 (..., 0, 1, 1,..., 1, 0,... ) T m 个连续的 1 可以验证, 这种形式的纯策略 s 可以被如下的线性约束排除 ( 当且仅当 -1 对应 s 中 的 0 且 1 对应 s 中的 1 时内积能取到最大值 m): (0, 0, 1, 1, 1,..., 1, 1, 0, 0) s < m m 个连续的 1 注意, 上述列出的形式只针对特定的 m 和一个特定的开始位置 为了排除掉所有 相应于 m = 1,..., ˇn c 1 以及所有可能的起始位置的情况, 我们需要对每个 m = 1,..., ˇn c 1 构造下列线性约束来排除掉所有不满足 C3 的纯策略 : m m s < m m m 个连续的 1 上述约束个数不超过 m(n m) 个 当模型因为划分更细而增大时,m 随 n 成比例增 加, 约束规模即为 O(n 2 ) 34

51 第四章 解决任意约束下的问题 C4: 类似地, 存在长度为 m < ˇn r 的休息时段的纯策略具有如下形式 : (..., 1, 0, 0,..., 0, 1,... ) T m 个连续的 0 我们对每个 m = 1,..., ˇn r 1 定义如下线性约束排除所有违反了 C4 的纯策略 : s < 约束规模为 O(n 2 ) m 个连续的 1 C5: 在高峰时段有交换班行为 ( 由工作状态切换为暂停或停止服务状态 ) 的纯策略 具有如下形式 : (...,..., 1, 0,...,... ) T 高峰时段 我们用下列线性约束排除掉上述形式的违背了 C5 的所有纯策略 : s < 高峰时段 约束总个数不超过高峰时段的长度, 即 O(n) 35

52

53 第五章 实验 本章通过实验对本研究提出的算法进行评估 评估主要包括两方面, 一是检验算法的运行效率, 二是检验对出租车系统优化的效果 实验基于 2011 年北京市交通年报提供的真实数据 [14] 表 5.1 和 5.2 给出了我们所用到的数据 数据覆盖 18 个时长为一小时的子时段, 从上午 5:00 至夜间 11:00 我们使用非线性规划求解工具 KNITRO (8.0.0 版 ) 求解算法中涉及到的所有标准的凸优化问题 ( 如 (3.14)) 用线性规划求解工具 CPLEX( 版 ) 求解所涉及的整型线性规划问题 ( 式 (4.1)) 实验运行平台配置 3.10GHz 四核 CPU 和 4.00GB 内存 5.1 算法运行效率 紧凑表达算法效率测试为测试算法运行效率随问题规模增长的情况, 我们需要将问题划分为不同个数的子时段 我们通过原有的 18 个时段的数据生成其他时段数模型所需的数据 对于 n 个时段的模型, 我们保持优化的时间范围 T = 18 小时不变, 保持约束条件中总工作时间上限 9 小时以及连续工作时间上限 5 小时不变 这样一来,τ = 18/n,ˆn w = 9 τ, ˆn c = 5 τ 我们用线性插值的方法通过 18 时段的数据生成 n 个时段的数据 其他与时段无关的参数保持不变 实验中我们针对高峰时期出租车出勤率低 系统效率严重低下的实际问题对高峰时段 ( 上午 7:00 9:00, 下午 17:00 19:00) 的票价进行优化 其他时段的价格固定不变 图 5.1 展示了 ASM 算法随问题规模扩大的时间和空间开销 我们同时测试了不采用任何紧凑表达法直接求解原优化问题的求解效率 ( 图中标记为 naïve 算法 ) 结果表明, 直接对原优化问题求解的开销增加非常迅速, 在问题规模扩大到 15 个子时段时就由于内存不足而无法运行 而 ASM 算法可以轻松求解 100 个子时段的甚至更大规模的问题 类似地, 图 5.2 展示了 FLORA 算法在 ASM 算法的基础上对求解效率的进一步提升 由此看出,FLORA 算法运行效率极高, 可以很轻松地处理更大规模的问题 另外, 需要指出的是, 实验结果显示通过 ASM FLORA 以及 naïve 方法求出的结果完全相同, 这进一步验证了 ASM 与 FLORA 的正确性 上述每个结果都是 50 次实验的平均值 FLORA-A 算法效率测试由于 FLORA-A 算法处理的约束条件与前面两个算法不同, 它们的运行效率没有直接的可比性 下面我们单独测试 FLORA-A 算法的效率 这里我们同时考虑 C1 C5 五个约束条件 类似地, 我们将约束 C3 和 C4 中的下限固定为 1 个小时, 因而有 ˇn c = 1 τ, 37

54 中国科学院大学硕士学位论文 基于计算博弈论的出租车市场最优定价研究 表 5.1: 与时段无关的参数 参数符号参数值参数描述 N t 出租车总数 N 道路承载力 ( 允许最大行驶车辆数 ) d 7.2 千米平均旅程 τ 1 小时时段长度 n 18 时段数目 ˆn w 9 小时总工作时间上限 ˆn c 5 小时持续工作时间上限 V 0 50 千米 / 小时最高平均时速 β 0.06 需求量敏感度指标 φ 1 20/ 小时旅行时间开销价值 φ 2 40/ 小时候车时间价值 ω 400 出租车服务范围参数 γ 1.5 平均载客数 c g 20/ 小时油耗速率 表 5.2: 与时段相关的参数 (a) 时段 1 9 i 开始时间 Di ( 10 4 ) Nv i ( 10 4 ) 1 05: : : : : : : : : (b) 时段 i 开始时间 Di ( 10 4 ) Nv i ( 10 4 ) 10 14: : : : : : : : :

55 第五章 实验 时间开销 ( 秒 ) Naïve 算法 ASM 算法 问题规模 ( 时段数 ) 内存开销 (MB) Naïve 算法 ASM 算法 问题规模 ( 时段数 ) (a) 时间开销 (b) 空间开销 图 5.1: ASM 算法运行效率随问题规模变化 运行时间 秒 ASM 算法 FLORA 算法 内存使用 MB ASM 算法 FLORA 算法 问题规模 ( 时段数 ) (a) 时间开销 问题规模 ( 时段数 ) (b) 空间开销 图 5.2: FLORA 算法运行效率随问题规模变化 目标函数值 运行时间 秒 FLORA-A 算法 FLORA 算法 迭代次数 (a) 收敛情况 问题规模 ( 时段数 ) (b) 时间开销随问题规模的增长 图 5.3: FLORA-A 算法运行效率 39

56 中国科学院大学硕士学位论文 基于计算博弈论的出租车市场最优定价研究 220 无约束 约束 C1 C2 11 无约束 约束 C1 C2 系统效率 总工作时间 单位里程价格 (a) 系统效率随价格变化 单位里程价格 (b) 总工作时间随价格变化 出勤率 (PoW) 100% 80% 60% 40% 20% 无约束 约束 C1 C2 出勤率 (PoW) 100% 80% 60% 40% 20% 无约束 约束 C1 C2 0% 时段 (c) 优化前的 PoW( 标号加框指高峰时段 ) 0% 时段 (d) 优化后的 PoW( 标号加框指高峰时段 ) 图 5.4: 约束 C1 和 C2 下的优化结果 ˇn r = 1 τ 图 5.3(a) 展示了 FLORA-A 算法收敛的情况 图中的曲线记录了解决规模为 18 个时段的问题的迭代过程中最优值的变化情况 可以看出, 绝大多数测试案例仅需 20 次左右的迭代就已经足够 ( 也就是额外寻找了 20 个新的纯策略 ) 图 5.3(b) 刻画了 FLORA-A 的时间开销 此处我们也附上了 FLORA 的时间开销的增长情况, 虽然二者无直接可比性, 但我们可以看出, 在解决具有简单约束条件的问题时 FLORA 具有极高的运行效率 ;FLORA-A 则以增大时间开销为代价, 换取了普遍的适用性 5.2 优化结果分析本研究的重要目的在于为出租车市场效率的提升提供票价上的优化方案 在前述的实验中, 我们同时也获取了最优化的价格, 在这一节中, 我们对优化的结果进行分析 我们分别对不同约束设置下的结果进行分析 考虑约束 C1 和 C2 以北京市的出租车市场为例, 实验中我们将非高峰期的票价固定为 2.00 并以高峰期票价为优化对象 图 5.4 展示了部分实验结果 图 5.4(a) 展示了系统效率随票价的变化情况 在考虑了 C1 和 C2 的情况下, 系统效率在票价为 2.60 时达到最高 同时我们可以从该图中看到, 如果不考虑任何的约束, 系统效率会随着价格持续增加, 直到越出 40

57 第五章 实验 210 约束 C1 C2 约束 C1-C4 210 约束 C1 C2 约束 C1-C5 系统效率 系统效率 单位里程价格 单位里程价格 (a) 系统效率随价格变化 ( 比较 C3 4) (b) 系统效率随价格变化 ( 比较 C3 5) 出勤率 (PoW) 约束 C1 C2 约束 C1-C5 出勤率 (PoW) 约束 C1 C2 约束 C1-C 时段 时段 (c) 优化前的 PoW( 标号加框指高峰时段 ) (d) 优化后的 PoW( 标号加框指高峰时段 ) 图 5.5: 额外约束条件下的市场情况 合理定价范围 事实上, 这些不切实际的提升是以出租车司机无限制地增加工作时间为条件的 从图 5.4(b) 中我们可以看到, 出租车司机的工作时间在票价达到一定值的时候 ( 约 3.00) 便已经达到上限 若不考虑 C1 和 C2, 他们的工作时间将持续增加并超出合理的范围, 在这种情况下求出的最优票价必然是不合理的 图 5.4(c) 和 5.4(d) 展示了优化前后从 PoW 层面上反映的出租车司机的策略的变化 从图 5.4(c) 可以看出, 优化前无论是否考虑 C1 和 C2 将得到一样的出租车司机的策略 这正是由于当前价格下出租车司机的工作时间未达到上限, 从而约束 C1 和 C2 并未起作用 这也从一个侧面说明了当前出租车系统的运营能力并未完全发挥, 说明了市场优化的必要性 对比图图 5.4(c) 和 5.4(d) 可以看出, 优化之后出租车司机的出勤率在高峰时段有小幅的提升, 证明了通过票价优化提升出租车系统效率的可行性 考虑约束 C3 和 C4 接下来, 我们在上述问题的基础上增加约束条件 C3 和 C4 注意到, 在 18 个时段的问题设置下每个时段长度正好为 1 小时, 所以实际上我们并不需要额外地考虑 C3 和 C4, 因为最短的休息或工作时间都不会短于一个小时 为了检验 C3 和 C4 的效果, 我们此处将模型继续细分为 36 个子时段, 模型中每个子时段持续时间为 0.5 个小时 此时,C3 和 C4 中的下限设置为 ˇn c = 2 以及 ˇn r = 2, 使其对应一个小时的时长 我们用 FLORA-A 算法求解含有 C3 和 C4 的问题 根据实验结果, 考虑 C3 和 C4 对问题的解 41

58 中国科学院大学硕士学位论文 基于计算博弈论的出租车市场最优定价研究 并没有影响 如图 5.5(a), 图中的两条曲线完全重合, 两种约束设置下系统效率随票价变化的情况完全一致 其他结果, 如 PoW 变化情况在两种设置下均完全一致, 图表曲线完全重合, 故此处略去 实验结果表明, 在某些情况下规定 C3 和 C4 意义不大 这一方面是因为出租车司机拥有庞大的策略空间, 即便 C3 和 C4 剔除掉了部分策略, 出租车司机在选择策略时仍然具有很大的灵活性, 能够通过余下的策略去构建最优策略 因而, 在某些条件下我们可以省略 C3 和 C4 从而可以采用更高效的 FLORA 算法求解问题, 换取效率上的提升 考虑约束 C5 最后, 我们通过约束条件 C5 来检验市场约束 ( 高峰时段禁止交接班 ) 的作用 我们仍然采用 18 时段的模型进行测试 同样地, 我们将上午 07:00 09:00 以及下午 17:00 19:00 确定为高峰时段 图 5.5(b) 展示了不同约束设置下系统效率随票价的变化 两条曲线显示出明显的不同, 表明了 C5 对市场的影响 我们看到,C1 5 的曲线更加平缓, 这是因为市场规定约束了出租车司机自由决策的灵活度, 降低了他们对票价的敏感程度 两种情况导出了不同的最优票价 ( 分别为 2.80 和 2.20) 此外, 图 5.5(c) 展示了优化前 PoW 的变化情况 可以看出, 由于高峰期交接班禁令的执行, 高峰期间的低出勤率得到了有效的纠正 图 5.5(d) 则展示了优化后 PoW 的情况 通过图 5.5(c) 和 5.5(d) 的对比不难发现, 市场规定的保障发挥了比价格优化更大的作用 这也说明了当票价提升到一定程度以后, 道路的拥堵代替票价不合理成为出租车市场的主要矛盾 继续提升票价对系统效率的提升不再起作用, 此时若强制执行交接班禁令甚至会对出租车司机产生一定的不公平性 ( 工作却不盈利 ) 最后, 两种约束下的差异也说明在对出租车票价进行优化时, 我们有必要将实际存在的各种约束考虑在内, 否则优化结果可能和客观情况出现较大的偏差 这说明了能够处理任意约束条件的 FLORA-A 算法的重要性 5.3 实验结果讨论通过上述实验结果, 我们可以得到以下几方面的结论 其一, 在算法效率方面, FLORA 算法无论在时间还是空间开销上效率都最高, 是处理一般 TEMP 问题的首选算法 即便在需要考虑某些更细节的约束条件的情况下 ( 如 C3 和 C4),FLORA 算法也能提供很高精度的近似解 ASM 算法的使用范围和 FLORA 一致, 但在效率上不如 FLORA 算法 但是作为一种折衷的紧凑表达法,ASM 能够提供比起 FLORA 更加直观的出租车司机策略的表达法 而对于更为综合的市场情况, 我们需要使用 FLORA- A 对问题进行求解 FLORA-A 以效率为代价换取对更加一般的问题的处理能力 即便如此,FLORA-A 仍然能发挥较好的效率 利用线性约束,FLORA-A 能够轻松地解决实际规模的 TEMP 问题 并且实验结果表明, 当额外的约束条件确实存在时, 不将他们加以考虑会导致优化结果出现较大的偏差 42

59 第六章 结束语 6.1 论文小结本文从多智能体系统研究的角度出发, 采用计算博弈论的思想和方法, 对出租车市场效率优化问题进行研究, 主要有以下贡献 针对出租车系统效率优化这一实际问题, 以及出租车系统非集中式控制的特点, 从多智能体系统研究的角度出发, 对出租车系统进行建模 模型充分考虑了系统中出租车司机作为智能的个体相互竞争 优化运营策略的决策行为, 以及制约这些行为的约束条件 ( 如出租车司机的工作强度及市场规章制度等 ), 在现有交通和经济学研究的基础上融入了对出租车司机这些行为的博弈建模 从该模型中我们导出了出租车系统效率优化问题的形式化表达, 分析且明确了问题求解的难点, 即出租车司机策略空间的组合爆炸 ( 指数增长 ) 造成对应的优化问题规模过大而不可解 就上述难点, 我们采用策略空间紧凑表达法的思路缩减问题规模, 提出两个算法 基于元时间表的 ASM 算法, 以及基于凸多面体表达方式转换的 FLORA 算法 ASM 算法依赖出租车司机行为的基本约束的特点, 将原始策略用元时间表表示, 将问题的规模降至 O(n 2 ), 其中 n 为模型规模 ( 离散的时段数 ) 而 FLORA 算法将混合策略视为纯策略集合的凸包中的点, 进而利用凸多面体顶点表达法到半空间表达法的转换将原策略空间缩减为一个由 O(n) 个线性不等式确定的一个凸多面体空间 对问题的进一步分析表明, 在考虑更加复杂的市场情况下, 除了最基本约束外还存在其他一些额外的约束条件, 如特定的市场规定, 以及策略上的更多细节 前述的 ASM 算法以及 FLORA 算法不能求解带有这些更加复杂的约束条件的问题 为了更加全面地研究这些综合的市场情况, 我们在 FLORA 算法的基础上提出 FLORA-A 算法 该算法能够求解带有任意约束条件的问题 算法利用了混合策略小支持集的特性, 采取搜索有用的纯策略 逐步扩大策略空间的方法, 巧妙地避免了列举所有的 ( 指数多个的 ) 纯策略 此外, 我们还引入了 MILP( 整数线性规划 ) 用于迭代过程中搜索所需的纯策略, 提高了 FLORA-A 的效率 最后, 我们进行了基于真实数据的实验 结果表明 ASM 算法和 FLORA 算法在求解实际问题上具有很高的效率 特别是 FLORA 算法, 能够轻松地求解具有实际规模甚至更大的问题 而虽然 FLORA-A 以普适性为代价牺牲了一定的效率, 但利用 MILP 优化, 仍然能很好地应用于实际规模的问题 实验结果还表明, 在一般情况下, 仅需考虑基本的约束条件便能较为精确地反映市场情况, 此时我们用 ASM 或 FLORA 算法求解能获得很高的效率 而在较为复杂的情况下, 忽略必要的约束条件会导致优化 43

60 中国科学院大学硕士学位论文 基于计算博弈论的出租车市场最优定价研究 结果的明显偏差, 这种情况则有必要使用 FLORA-A 求解问题 实验结果还表明, 就北京市的交通数据而言, 票价优化可以使出租车系统的效率在当前的基础上得到提升 当提升到一定程度后, 道路的拥堵成为出租车系统效率低下的首要原因 为现实的出租车市场管理 政策制定以及优化提供了数据上的有力参考 6.2 未来研究通过计算的手段解决现实问题, 特别是新形势下人类所面临的可持续发展 政策制定 资源分配等为题是当前计算机领域的重要研究方向 本研究作为人工智能 多智能体系统 以及计算博弈论在大型交通系统优化方面的一次尝试和实践对类似的研究起到积极的推动作用 未来的工作包括以下几个方面 其一, 参与者行为的不确定性问题 不确定性一直以来都是对人的智能行为建模时的重要问题 在现实中, 普通人的行为往往都具有一定的非理性, 而即便是理性的行为, 在具体的效用上往往表现出一定的模糊性, 很难精确地刻画 此外, 对最优策略的确定本身是一个复杂的计算过程 ( 如本研究中最优策略的计算 ), 在这种情况下参与者实际所采用的 最优策略 必然与理论的最优有一定的差异, 在这些情况下均衡的实现也是值得探究的一个问题 在本研究中, 出租车司机在策略具体执行的过程中也会面临诸多的不确定性 出租车司机无法确定下一位上车的乘客具体需要多长时间送达, 因而在实际运行过程中往往无法精确地按事先计划的时间表工作 通常来说, 在接近工作结尾时, 出租车司机需要决定是立刻提前切换为非工作 ( 休息 ) 状态还是再多运送一次乘客 ( 若乘客目的地太远, 可能超出预期工作时间 ) 在现实生活中, 出租车司机往往会依据实际距离预想结束时间的时长 当前所处的时段等情况进行判断 而不同的出租车司机往往也会做出不同的判断, 这又涉及到下面一点, 即参与者的差异性问题 其二, 参与者的差异性 当前研究建立在出租车司机的同质性上, 即所有出租车采用同样的策略 这大致上是合理的, 因为大部分城市所有的出租车都是同一档次的车型, 并且采用同样的计价方式 但也有一些例外, 如某些车辆可能由多个司机负责运营, 因而他们的作息习惯有自己的特点 就单个出租车而言, 其工作强度也大于只由单人运营的车辆 另外, 前面已经提到, 不同的人对待策略执行上的不确定性可能会有不同的处理方式 在一些出租车市场也确实存在车型和票价上或大或小的差异, 这些因素都导致单一类型出租车的假设的不合理 如何建模多类型出租车的市场, 如何对这样的问题进行求解, 是未来工作的重点之一 其三, 空间上的差异 当前研究我们从宏观的层面上更多地考虑的是出租车市场在时间上的差异性 事实上, 空间上的差异也是出租车市场的重要特点 从我们的模型中可以看到, 拥堵状况对出租车市场造成很大的影响 实际中并不一定一个城市 ( 特别是特大城市 ) 所有的区域都同时拥堵 这样的情况下有可能出租车司机只是避免 44

61 第六章 结束语 在拥堵地段工作而非完全停止工作 我们需要知道在这些情况下市场状况会发生怎样的变化 其四, 基于更多城市数据的实验 当前的实验仅采用了北京市的交通数据 我们希望能有更多其他城市的数据以进一步验证在不同背景下我们的模型和算法的质量 当然, 这一方面是由于目前这类数据比较缺少, 大部分城市都没有建立完善的数据体系 这方面的工作还需要同交通管理 研究机构密切合作才能更好地完成 最后, 基于移动智能平台的打车服务对市场的影响 近年来智能手机的普及催生了众多新的移动服务 打车手机应用已经普及开来, 使用广泛 打车应用改变了人们打车的习惯, 也改变了出租车司机寻找顾客的方式和策略 乘客打车时通过应用将自己的位置和目的地广播给附近的出租车司机, 出租车司机根据情况自由决定接受与否 这大大地降低了乘客与出租车之间交易的随机性 : 乘客等待不再是盲目地 随机地等待空车的出现, 出租车司机也不再漫游式地寻找顾客, 也能更容易地根据乘客的线路选择接受与否 有媒体报道, 随着这类应用的普及, 在出租车供不应求的时候采用传统方式打车已经变得非常困难 显然, 这类应用对出租车市场的影响已经不可忽视 研究这类应用对出租车市场的影响是一个重要而有趣的课题 45

62

63 参考文献 [1] 郭盛, 林风. 福州的士拒载拼客重罚千元 点禁止交接班 [M]. 东南快报. http: //fj.qq.com/a/ / htm. [2] 史忠植. 智能主体及其应用 [M]. 北京 : 科学出版社. [3] 石小磊. 南京拟禁止出租车在高峰时段交接班 [M]. 东南快报. com.cn/c/ / shtml. [4] 齐介仑. 北京出租车经营模式调查 [J]. 财经国家周刊, 2013: [5] 成熔兴, 李钧, 陈军丽. 武汉今起可电话招出租车晚餐时间禁止交接班 [M]. 湖北日报 htm. [6] 柳妍, 陈宇, 桂莉芬. 合肥出租车上下班时间严禁交接班被举报两次将吊证 [M]. 万家热线. [7] 杨远帆, 白之羽, 曹泽熙. 热点解读 : 北京打车, 没不难的时候 [M]. 人民网. http: //theory.people.com.cn/n/2013/0108/c html. [8] Alshamsi A., Abdallah S., Rahwan I. Multiagent selforganization for a taxi dispatch system[c]//8th International Conference on Autonomous Agents and Multiagent Systems. 2009: [9] An B., Pita J., Shieh E., Tambe M., Kiekintveld C., Marecki J. GUARDS and PRO- TECT: Next generation applications of security games[j]. ACM SIGecom Exchanges, 2011, 10(1): [10] An B., Brown M., Vorobeychik Y., Tambe M. Security games with surveillance cost and optimal timing of attack execution[c]//proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 13). 2013: [11] Au T.-C., Shahidi N., Stone P. Enforcing liveness in autonomous traffic management[c]//proceedings of the AAAI Conference on Artificial Intelligence (AAAI). 2011: [12] Avis D., Bremner D., Seidel R. How good are convex hull algorithms?[j]. Computational Geometry, 1997, 7(5):

64 中国科学院大学硕士学位论文 基于计算博弈论的出租车市场最优定价研究 [13] Bazzan A. L. Opportunities for multiagent systems and multiagent reinforcement learning in traffic control[j]. Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2009, 18: [14] Beijing Transportation Research Center (BTRC). Annual Transportation Report of Beijing (2011)[J] [15] Boyd S. P., Vandenberghe L. Convex optimization[m]. Cambridge university press. [16] Cheng S.-F., Nguyen T. D. Taxisim: A multiagent simulation platform for evaluating taxi fleet operations[c]//proceedings of the 2011 IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology-Volume : [17] DANNINGER-UCHIDA G CARATHéODORY THEOREM[M]//FLOUDAS C, PARDALOS P. Encyclopedia of Optimization.Springer US: doi.org/ / [18] Douglas G. W. Price regulation and optimal service standards: The taxicab industry[j]. Journal of Transport Economics and Policy, 1972: [19] Dresner K., Stone P. A multiagent approach to autonomousintersection management[j]. Journal of Artificial Intelligence Research, 2008, 31: [20] Dresner K. M., Stone P. Sharing the Road: Autonomous Vehicles Meet Human Drivers.[C]//IJCAI. 2007,7: [21] Fleiner T., Kaibel V., Rote G. Upper bounds on the maximal number of facets of 0/1-polytopes[J]. European Journal of Combinatorics, 2000, 21(1): [22] Grunbaum B., Klee V., Perles M. A., Shephard G. C. Convex polytopes[m]. Springer. [23] Jain M., Kardes E., Kiekintveld C., Ordónez F., Tambe M. Security Games with Arbitrary Schedules: A Branch and Price Approach.[C]//Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI 10). 2010: [24] Jain M., Korzhyk D., Vaněk O., Conitzer V., Pěchouček M., Tambe M. A double oracle algorithm for zero-sum security games on graphs[c]//proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 11). 2011: [25] Jain M., An B., Tambe M. An Overview of Recent Application Trends at the AAMAS Conference: Security, Sustainability, and Safety[J]. AI Magazine, 2012, 33(3):