基于非合作博弈的应急车辆调度与再配置.docVIP

基于非合作博弈的应急车辆调度与再配置 华 南 理 工 大 学 学 报 （自 然 科 学 版 ） Journal of South China University of Technology (Natural Science Edition) Vol. 4 4 No. 3 M a r 7c h 2 0 1 6 文章编号：l〇〇〇-565X (2016)03-0110-08 基于非合作博弈的应急车辆调度与再配置 赵建东 1 段晓红 1 宋守信 2 (1.北京交通大学机械与电子控制工程学院，北京100044;.北京交通大学经济管理学院，北京100044) 摘 要 ：多事故多救援站点的应急车辆调度问题中，在处置当前事故时，若将空闲车辆再 配置于救援站点，有利于对潜在事故的快速响应.文中采用双层规划理论和非合作博弈理 论建立应急车辆调度与再配置模型.上层模型在事故需求和救援时间窗约束下，最小化当 前事故响应时间；下层模型将各救援站点视为非合作博弈的局中人,综合考虑车辆再配置 时间和救援站覆盖区域潜在风险，确定局中人的收益函数，将优化再配置策略转化为寻求 非合作博弈的纳什均衡.然后，提出一种层次混合蛙跳算法，其中上层算法用于求解约束 单目标规划问题，下层算法用于求解非合作博弈模型.求解事故算例证明了应急车辆调度 与再配置模型的合理性和层次混合蛙跳算法的有效性. 关键词：应急车辆;调度算法;资源配置;博弈论 中图分类号：X951 doi： 10.3969/j . issn. 1000-565X. 2016.03.016 高速公路里程和路网密度的迅速增加、交通出 行量和交通事故发生频率的急剧上升、交通安全形 势的日趋严峻，对快速高效的事故应急救援能力提 出了迫切需求.科学合理地调度有限的应急车辆是 应急救援的关键问题，可有效减少事故损失. 目前，应急车辆调度研究主要集中在调度建模 方法和调度求解算法.调度建模方面，Y a mada[1]提 出仅考虑当前事故救援需求，应急资源调度决策可 转化为路网最短路的求解，以选择事故最近出救点. 何建敏等[2]针对单事故下多出救点选择问题，引入 时间最短的概念，提出了单目标、多目标等多种组合 优化模型.戴更新等[3]将单资源调度扩展到多资源 调度，以救援起始时间最早为目标，建立了多资源调 度数学模型.Cartel??等[4]指出考虑未来事故需求，选 择离事故点最近的出救点不一定是最优策略. Sherali等[5]将资源调度总成本定义为当前事故救援 收稿日期：2015-05-11 * 基金项目：国家科技支撑计划项目（2011BAG07B05-2) 成本和潜在事故救援机会成本的总和，建立了应急 车辆调度的机会成本法模型.O z b a y等[6]针对潜在 事故资源需求的随机性，引入服务质量概念，建立了 一种带有概率型约束的整数规划模型，用以解决交 通事故响应和资源调配问题.Z h a o等[7]针对机会成 本模型中车辆速度和潜在事故概率的不确定性问 题，引入削弱救援车速系数概念，修正了机会成本模 型中的速度参数.杨继君等[]研究了在应急资源有 限条件下的多灾点资源调度问题，考虑到各灾点利 益的冲突性，建立了基于非合作博弈的应急资源调 度模型.Y a n g等[9]建立了带区域覆盖约束的应急优 化车辆调度模型，通过将空闲车辆重新配置于各救 援站点的方法避免对潜在事故的救援延迟. 调度求解算法方面，C h a n g等[10]提出一种基于 贪婪有哪些信誉好的足球投注网站的多目标遗传算法，自动生成多种可行的 应急物资调度策略.I c h o a等[11]应用并行禁忌有哪些信誉好的足球投注网站 F o u n d a t i o n i t e m： Supported by the National Key Technology Research and Development Program of the Ministry of Science and Technology of China(2011BAG07B05-2) 作者简介：赵建东(1975-)，男，博士，副教授，主要从事交通安全与控制研究.E-mailzhaojdt^ btu. edu cn 第3 期 赵建东等：基于非合作博弈的应急车辆调度与再配置 111 算法，分别求解了基于静态和动态参数的车辆调度 模型.刘芹等[12]设计了一种混合粒子群算法来实现 车辆调度模型的求解.杨仁法等[13]运用蚁群算法把 时间窗约束转化为惩罚函数形式，求解了带时间窗 约束的配送中心车辆调度问题. 综述文献，国内外学者在应急车辆调度建模时 已考虑车辆再配置.笔者在文献[1 ]中提出将救援 站覆盖区域潜在风险作为关键约束，建