第44卷第3期
2016年3月
华 南 理 工 大 学 学 报 （自 然 科 学 版 ）
Journal of South China University of Technology
(Natural Science Edition)
Vol. 4 4 No. 3
M a r c h 2 0 1 6
文章编号：l〇〇〇-565X (2016)03-0110-08
基于非合作博弈的应急车辆调度与再配置
赵建东 1 段晓红 1 宋守信 2
(1.北京交通大学机械与电子控制工程学院，北京100044;.北京交通大学经济管理学院，北京100044)
摘 要 ：多事故多救援站点的应急车辆调度问题中，在处置当前事故时，若将空闲车辆再
配置于救援站点，有利于对潜在事故的快速响应.文中采用双层规划理论和非合作博弈理
论建立应急车辆调度与再配置模型.上层模型在事故需求和救援时间窗约束下，最小化当
前事故响应时间；下层模型将各救援站点视为非合作博弈的局中人,综合考虑车辆再配置
时间和救援站覆盖区域潜在风险，确定局中人的收益函数，将优化再配置策略转化为寻求
非合作博弈的纳什均衡.然后，提出一种层次混合蛙跳算法，其中上层算法用于求解约束
单目标规划问题，下层算法用于求解非合作博弈模型.求解事故算例证明了应急车辆调度
与再配置模型的合理性和层次混合蛙跳算法的有效性.
关键词：应急车辆;调度算法;资源配置;博弈论
中图分类号：X951 doi： . issn. 1000-565X.
高速公路里程和路网密度的迅速增加、交通出
行量和交通事故发生频率的急剧上升、交通安全形
势的日趋严峻，对快速高效的事故应急救援能力提
出了迫切需求.科学合理地调度有限的应急车辆是
应急救援的关键问题，可有效减少事故损失.
目前，应急车辆调度研究主要集中在调度建模
方法和调度求解算法.调度建模方面，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 ]中提出将救援
站覆盖区域潜在风险作为关键约束，建立了应急车
辆调度与再配置的多目标规划模型.接着，在文献
[15]中分析了应急车辆调度和再配置两类目标间
的层级关系，建立了双层规划模型.模型以当前事故
响应时间最短为上层目标，应急车辆再配置时间最
短为下层目标.进一步分析文献[8 ]、16-17 ]发现，
非合作博弈理论在求解资源限制条件下的多灾点应
急资源调度、作业车间任务调度及出租车调度等竞
争问题时均体现了考虑各局中人之间利益冲突的优
点.因此，在文献[4-15]的研究基础上，文中提出应
用非合作博弈理论求解下层应急车辆再配置过程中
的冲突问题.通过将各个救援站视为博弈模型的局
中人，可能的车辆再配置方案映射为策略集，从而将
应急车辆再配置问题转化为对非合作博弈模型的纳
什均衡点求解.此外，还设计了一种层次混合蛙跳算
法实现模型求解.
1 问题描述
如图 1 所示，区域 C 内共有/(/^2 )个救援站.
某一时刻，/(/^ 2 )起事故同时发生为事故集合，
事 故 e £， = 1，2 ,…，7 ) 的应急车辆需求量
% >〇;应急车辆总数为尺，且 乙 ％ < K 当前事故
与路网内交通风险因素耦合作用，易引发潜在事故，
导致新的救援需求，救援站^(^ e 5 , = 1，，••，/)
覆盖区域A 的潜在风险可量化为兄，为救援站集
合.在考虑当前事故救援的同时，根据再配置时间和
救援站覆盖区内潜在风险情况，将车辆进行优化再
配置，从而提高路网整体救援能力.应急车辆集合为
K 车辆& (^ e = 1，2 ，…，，〇到达事故^及救援
站\的在途时间分别为 4^ 0 及 《彡0 .
2 模型构建
路网内应急车辆储备有限，导致当前事故救援
需求和潜在事故储备之间存在着竞争关系.应急车
辆应优先调度至事故点，以救援当前事故.当前事故
救援策略可指导以保证潜在事故资源储备为目标的
应急车辆再配置决策.同时，应急车辆调度决策也需
图1 多事故多救援点应急车辆调度问题
Fig. 1 Emergency vehicle scheduling problem with multiple
accidents and multiple rescue sites
兼顾考虑车辆再配置选择.据此，文中将当前事故救
援问题作为上层问题，应急车辆再配置问题作为下
层问题，建立双层规划模型.
2 .1 上层模型构建
2 . 上层目标函数
事故响应时间是调度决策的关键因素，事故响
应时间由调度决策时间与车辆在途时间构成[]，上
层目标函数用于最小化车辆在途时间：
m i = ( )j 左
其中，f 为上层目标函数， 为上层决策变量，若车
辆&前往处理事故、则 = 1，否则 4 = 〇.
2 . 上层约束条件
(〇事故需求约束
前往事故的车辆总和与事故&.的需求％.相
一致：
E 4 = % ， V . e E (2)k
(2 )救援时间窗约束
应急救援的时间敏感性要求应急车辆必须在时
间窗[ n ^ n a 内到达事故点：
C x ^ max， C X = m a X { 4 4 .}， V . E E ⑶
4mrn ^ n mrn， 4mm = m i { 4 kj4kj } ， V . E E (4 )
2 .2 下层模型构建
在路网内应急车辆有限的情况下，各个救援站
所需资源是相互冲突的，各方利益相互影响，一方利
益的增加必然导致其他救援站利益的减少.从博弈
112 华 南 理 工 大 学 学 报 （自然科学版 ) 第44卷
论角度来看，各救援站间潜在事故对应急车辆的需
求可认为是非合作博弈的，博弈的目的是尽量为自
身争取更合理的效用，即以更少的成本获得更多的
资源.
(1 ) 策略集
区域 P 内的/(/ > 2 )个救援站构成一个/人非
合作博弈G = (G i , G 2，…,G , ; i，2,…，〜），救援站
以 1矣^/)的策略集为 G ,= ( ， ，…，？），其中
是局中人i的策略总数.策略集G ,包括救援站s,
所有可能的再配置策略.
定义下层决策变量为4 ，表示车辆％是否再配置
于救援站V 若车辆^再配置于救援站S ，则：4 = 1，否
则 ：4 =〇.则将局中人i的策略g丨（矣 表 示 为
d ，…，4 , …，，4) ⑶
(2 ) 效用函数
局中人 i选 择 策 略 的 效 用 为
u ， = ^ ( )
t = 1 lu
其中，4 ,表示局中人z选择策略g 时车辆^ ( 1矣k
K )是否再配置于救援站s ，若车辆^再配置于救援
站 s ，则 4 , = 1，否则4 , = 〇.
2 . 下层目标函数
定义 1 策略组合尤21!是/人非合作博弈的一
个纳什均衡解，如果X 2 4满足：
u,(X 21 g \) ^ u,(X 2* ) ， i =1,2,…，/ (7)
其中，X 21 g 表示只有局中人i用 g 替换策略组合
X 2*中自己的策略，其他局中人的策略不变.
在应急车辆再配置问题中，每一个救援站V 从
其策略集G 中选取某一种策略，组成/人博弈的策
略组合X 2.根据纳什均衡定义，下层目标函数为
/
min/ = Z 腿 X {u (x 2 llg) - u (x 2 )， 1, =i = 1
1 2 ,…，m } ( )
当策略组合X 2*为纳什均衡时，对于每一个局
中人 i，单独将自身策略变为g ( = 1 ，，… ，m )时均
不能获得更多收益，此时目标函数取最小值〇.
2 . 下层约束条件
应急车辆〜可以派往当前事故点或者再配置
于救援站点，且只能处于两种状态之一：
H 4 + Z 4 = 1 e V (9)j i
3 基于层次混合蛙跳算法的车辆调度
模型求解
混合蛙跳算法（S F L A )是一种模因元启发式算
法，采用混合进化算法（S C E )的全局寻优策略和粒
子群算法（P S O )的局部迭代规则.算法基于族群内
个体模因进化和种群中全局信息交流，将青蛙种群
分为多个族群，各族群内青蛙通过信息交换实现局
部深度进化.一段时间后，将各子族群混合，使信息
在整个种群内得到交流.各子族群内局部寻优和全
局信息融合往复执行至达到指定进化代数.
该算法数学模型为：由只青蛙组成算法种群
八 每 只 青 蛙 的 位 置 = [“ … ，P ] T代表一个
可行的决策向量，》为决策向量维数.每个决策向量
对应一个与优化目标相关的适应度函数值K f f P).
将只青蛙根据其适应度函数值从大到小的顺序
排列，并将其分配到《个族群，每个族群包含6 只青
蛙. 分配策略为
牧 = {及 +a(-1) e P | 1矣/办}， 1矣〇矣《
(10)
其中，M 。表示第。个族群.
根据式（1)及（1 2)，各子族群中的最差青蛙位
置 w 跟随族群内最优青蛙位置r 或种群最优青蛙
位置 Z 进行局部更新，直到完成指定迭代次数a .
b = { m i n[I N T(r(F - W ))，]， Y - W ^ 0 (1)
i m a x [I N T(K r - W ))，- 5 ]， Y - W <0 ( )
W n ew = W 〇ld + P (12)
其中，为一随机数且r e [0 ，1 ]，;S 表示青蛙个体的
调整矢量，表示最大调整步长，W dd和W n „分别为
更新前、后的最差青蛙位置.
完成局部搜索的各族群重新混合，排序后执行
下一次分组及局部搜索，直至完成指定的外层迭代
次数 n
3 . 1 求解非合作博弈模型的混合蛙跳算法
求解非合作博弈模型的混合蛙跳算法中，每只
青蛙的位置g = ( 1，2,… ，/ ) e G ,，1 d 矣/ ,代
表 /人博弈的一个策略组合.青蛙群体在策略组合
空间中寻找最优位置，青蛙位置的优劣由适应度函
数反应，当青蛙处于最优位置时对应的适应度函数
到达最大.与目标函数相一致，应急车辆再配置问题
的适应度函数定义为
K x2) = - Z m a {u (X 2 llgi) - u (X 2 )，i = 1
0 I l = 1 ,2 ，*-*,m i } (13)
第 3期 赵建东等：基于非合作博弈的应急车辆调度与再配置 113
3 .2 求解双层规划问题的层次混合蛙跳算法
采用与文献[15 ]相同的双层架构，设计求解应急
车辆调度与再配置的层次混合蛙跳算法.该架构集成
了两个基本混合蛙跳算法模型SFLA_U 及 SFLA_D .
上层的S F L A_U 采用基于权重的混合蛙跳算法
模型，用来求解应急车辆调度问题，上层决策向量
X 1 E {0 , I f ' 由元素 4 , = 1 2 ,…，X , = 1 ,2 ,…,
组成;下层的S F L A _D 采用求解非合作博弈的混合
蛙跳算法模型，用来求解应急车辆再配置问题，下层
决策向量X 2 E {0，1}KX/，由元素4 ，a = i ，2,…，X ，
h 1，2 ，…，/组成.算法遵循双层规划问题的决策规
则，算法步骤为：
步骤 1 上层决策者在搜索空间内随机生成少
个决策向量X >= ( Xj>，X i )，</) = 1，2 ，..，0 ;
步骤2 对于每一个< ( < / ) = 1，2 ,…，少），下层决
策者将 X 作 为 参 数 ，在 下 层 搜 索 空 间 仏 =
{1 2 |1 2 £ {〇，1 }£></}内 随 机 生 成 0 个决策向量
X # = (X ;，X ^ )， = 1，2，…，0 .基于 S F L A _D ，以下
层适应度函数为指导，0 只青蛙在约束域内反复搜
索，使最优青蛙的位置不断逼近下层博弈模型的纳
什均衡解X 2/ ;
步骤3 以（X k X j ；)为参数，基于 S F L A _U ，上
层决策者获得符合自身目标的最优解(X 1 *，X 2* ).
编码方案设计
混合蛙跳算法中青蛙的位置代表了问题的一个
可行解.采用整数编码方式将双层规划模型的决策
变量映射到混合蛙跳算法的决策空间.由此，两类决
策变量4 和4 被转换为整型表达4 ，％代表对第&
( = 1 ，2 ，〜^)辆车的调度策略，每辆车可以去往
事故点e1、2,…，ej■或救援站点h ，2,… 的可
行域为{ 1，2 ,…，1/，1/ + 1，…，_/ + /}.基于此编码方
式，在初始种群产生和进化的全过程中，决策变量均
满足方程(9).第;X 个青蛙的位置可以表示为
X (( ，：) = [4,1，4,2,…，4 ，，…，4 x ] (I4 )
为便于识别，在计算下层适应度函数值时将4
解码为4 和 4 .
3 . 2 . 2 适应度函数设计
对于上层算法 S F L A _ U ，采用罚函数的方法考
虑约束条件，则上层算法的适应度函数K (X )由上
层目标函数及各关键约束未满足的惩罚组成：
k (x 1) = - Z Z 4 4j k Zj
^■ max { 0 yN - - Z 4 } -k
y .
j
， a X {0，min - 4 i } -
y 7t jmsa m a X { 0，Jma - TJt niax } (5)
叫 ==i (16)
兀,- = 驗 , _1 (17)
7ljmax b / (18)
式中， 分别表示事故e 的现场疏散能力及事故
严重程度.同文献[15 ]，，定义见表 1.对应于事故
由轻微到严重的4 个等级，^的取值依次为40、60、
80、100.
表 1 时间窗约束惩罚
T able 1 P unish m ent for time w indow constraints
被影响车道数目 sj min 被影响车道数目
8 3 4
2 6 >3 2
下层混合蛙跳算法S F L A_U 用来求解基于非合
作博弈论的应急车辆再配置模型，其适应度函数
K (X 2)为
/
K ( 2) 二 -工 m ax
i = 1
0 I，= 1，2,…，％} (19)
4 算例分析
采用文献[ 5 ] 中的两个算例1、、1验证文中双
层模型和求解算法的有效性.具体算例为：区域 0
内共有4 个救援站•?1、2、3、4,救援站覆盖区域潜
在风险如表2 所示;算例 I 中同时发生2 起事故 e1
和 e2，算例 II中同时发生3 起事故 e1、2 和 e3，事故
参数如表3 所示；区域内共有5 辆应急车辆，算例 I、
II中应急车辆^到达事故 e 和求援站&的在途时
间 4 和 4 如表4 所示.
表2 救援站参数
T able 2 R escue site param eters
算例 & h 算例 i^
I 25 I 17
I 21 h I 27
I 22 I 10h2 I 24 I 10
表3 当前事故参数
Table 3 C urrent accident param eters
e 算例 N ft Tm T；min max 71j .min
I 2 60 4 15 5 60 60
e II 1 40 8 10 0 40 40
I 1 40 8 8 0 40 40
e2 I 1 60 6 20 10 60 60
I
e3 I 1 80 4 15 6 80 80
114 华 南 理 工 大 学 学 报 （自然科学版 ) 第44卷
表 4 车辆在途时间
Table 4 Travel time matrix
应急车辆算例 已2 e3 ^1 2^ 4^
^1
I 8 10
0 10 5 14
II 6 8 12
v2
I 12 6
10 0 12 8
I 12 8 14
^3
I 6 12
11 11 6 14
I 7 13 13
I 7 15
13 12 0 9
I 9 16 7
v5
I 13 10
16 6 15 5
I 15 14 9
根据决策变量规模大小，层次混合蛙跳算法参
数选择如表5 所示.运行层次混合蛙跳算法，经过寻
优过程，获得两个算例的最优解如表6 所示.表中包
含有文献[15]原模型的最优解数据.并分别采用层
次混合蛙跳算法（S F L A )和文献[18 ]中的层次粒子
群算法（P S O )对两个算例进行求解，结果见表7.
表 5 层次混合蛙跳算法参数设置
Table 5 Selection of parameters of integrated bi-level shuffled
frog-leaping algorithm
算例 上层种
群规模
上层族
群数
上层组内
迭代次数
上层全局
迭代次数
上层最大
调整步长
I 300 20 15 5 [6,6,6,6,6]
I 500 25 20 10 [7,7 , , , ]
编号 下层种 下层族 下层组内 下层全局 下层最大綱号 群规模 群数 迭代次数 迭代次数 调整步长
I 150 15 10 5 [6,6,6,6,6]
I 150 15 10 5 [ , , , , ]
表 6 算例最优解
Table 6 Optimal solutions of examples
上层目标最优值下层目标最优值 最优解
算例——
本模型原模型文中模型原模型文中模型 原模型
4 . 1 算 例 I 的结果分析
文中模型获得的最优解均为[3，2，1，1，4 ]，和
原模型一样.最优调度与再配置策略如图2 所示，表
示应急车辆〃 1前往救援站^，应急车辆〃2 前往事故
点 ^ ，应急车辆〃3和〃4前往事故点^，应急车辆％
前往救援站^最优策略分析如下.
I 19 46 11 3,2，1，1，4 3,2，1，1，4
I 28 5 15 4,5,13,2 15,2,3,6
图 2 最优调度与再配置策略
Fig. 2 Optimal scheduling and reallocation strategy
表 7 层次混合蛙跳算法与层次粒子群算法的对比
Table 7 Comparison of integrated bi-level shuffled frog-leaping
algorithm and particle swarm optimization algorithm
算例
最优解 平均迭
代次数
求解时
间/s
1 次运行中获得
最优解的比例/ %
SFLA PSO SFLA PSO SFLA PSO SFLA PSO
I 3,2，1，1，4 90 50
I 4,5,13,2 90 50
对于事故^的应急车辆调度策略
事故^的应急车辆需求为2,将 5 辆车到达事
故点 ^的在途时间升序排列为（％:6 m i n )，（％:
7 m in)，（ ％ :8 m i n)，（ z;2 :12 m in)和（z;5:13 m i n).若将
车辆〃3和〃4派往事故^，则满足使应急车辆在途时
间最小的上层目标.然而，在满足事故点^应急车
辆需求的同时，还应考虑事故点^的需求及对各救
援站的车辆再配置.假设选择次优策略，应急车辆〃 1
第 3期 赵建东等：基于非合作博弈的应急车辆调度与再配置 115
代替％或&被派往事故^，则增加了车辆在途时间
的同时，也使对救援站^的再配置时间延长了至少
10 min.可见，将应急车辆％和 ^派 往 事 故 ei 是合
理的.
4 . 1 . 2 对于事故^的应急车辆调度策略
事故 e2 的应急车辆需求为1，将 5 辆车到达事
故点 e2 的在途时间升序排列为（d2:6 m i n )，（巧：
10 m in)，（u5 :10 mi n)，（u3 :12 m in)和（u4 :15 m in).若
将车辆2 2派往事故^ ，则满足使应急车辆在途时间
最小的上层目标.假设选择次优策略，将车辆 2 1派
往事故 ^，则车辆在途时间增加了 4 m i n，为保证对
当前事故e2 的快速救援，应将车辆22 派往事故e2.
应急车辆再配置策略
由于应急车辆22、3 和 2 4前往救援当前事故，
空闲车辆为2 1和 25.为分析下层模型的有效性，计
算所有可能再配置策略对应的目标函数值，结果如
表 8 所示.
表8 再配置策略下层目标函数值
Table 8 Performance function value of the second level of pos
sible strategies
可能策略 下层目标函数值 可能策略 下层目标函数值
[3,2，1，1，3] 8 [5,2，1，1 ，3]
[3,2，1，1，4] [5,2，1，1 ，4]
[3,2，1，1，5] [5,2，1，1 ，5]
[3,2，1，1，6] [5,2，1，1 ，6]
[4,2，1，1，3] [6,2，1，1 ，3]
[4,2，1，1，4] [6,2，1，1 ，4]
[4,2，1，1，5] [6,2，1，1 ，5]
[4,2，1，1，6] 0 . 1 8 0 [6,2，1，1 ，6]
由表可见，策略[3,2，1，1，4 ]的下层目标函数
值最小，该策略更符合应急车辆调度与再配置模型
的优化目标.
4 . 2 算 例 I I的结果分析
文中模型求得的最优解为[4，5，1，，]，而原
模型的最优解为[1，5,2,3,6]，如表9所示，将最优解
解码并进行比较.最优调度与再配置策略如图2 所
示，表示应急车辆2 1前往救援站^，应急车辆 2 2前
往救援站^，应急车辆 2 3前往事故点^，应急车辆
2 4前往事故点^，应急车辆2 5前往事故点
4 . 2 . 1 对于当前事故的应急车辆调度策略
事故^的应急车辆需求为1 将 5 辆车到达事
故点 e 1的在途时间升序排列为（21 :6 m i n ) , (23 :
7 m in) , (24 :9mi n) , (22 :12m in)和(25 :15m i n).若将
车辆 2 1派往事故^，则满足使应急车辆在途时间最
小的上层目标.假设选择次优的策略，应急车辆 23
代替 2 i被派往事故ei，则当前事故ei的救援时间仅
延长 1 m i n，而对具有最高潜在风险的救援站^的再
配置时间缩短了 1 0 m i n，可见，应该将应急车辆2 3派
往事故点ep
同理，可证明对事故点^和^的调度策略是合
理的.
4 . 2 . 2 应急车辆再配置策略
由表9 可知，文中模型求得最优策略的目标函
数值较原模型优化了 5 6 % ，说明策略[4，5，1，3，2 ]
的整体效用比[1，5,2,3,6]高，因此文中模型获得
的策略更加合理.
表9 算例II两种最优策略对比
Table 9 Comparison of two optimum strategies of example II
模型 最优解 最优策略 车辆在途 时 间 /min
时间窗约束
惩罚
当前事故
需求惩罚
潜在事故 改进模型下层 车辆再配置
需求惩罚 目标函数值 时 间 /min
2 -
->•52
文 中 模 型 4,5,1,3,2 2 - )e1 28 0 0 — 0 . 9 0 0 0
2 - )e3
2
2 - )e1
原 模 型 1,5,2,3,6 2 - 26 0 0 31 15
2 - )e3
% -
116 华 南 理 工 大 学 学 报 （自然科学版 ) 第44卷
4 .3 算法性能分析
表 7 中 2 个算例数据表明，层次混合蛙跳算法
和层次粒子群算法在1 0次运行后均能获得最优解，
层次混合蛙跳算法平均求解时间大约为层次粒子群
算法的1/3 ;前者10次运行中获得的最优解比例高
于后者.
5 结 语
事故发生后，调度应急车辆对当前事故进行有
效救援的同时，综合考虑救援站覆盖区域潜在风险
情况，对应急车辆进行统筹再配置，可以有效缩短对
潜在事故的响应时间.文中基于应急车辆调度与再
配置双层规划模型，考虑各救援站点对于有限资源
的竞争关系，将各救援站点视为非合作博弈的局中
人，定义了与再配置时间和救援站覆盖区潜在风险
相关的收益函数，通过寻求多人非合作博弈的纳什
均衡解获得优化的再配置策略;设计了一种层次混
合蛙跳算法完成了模型的求解，上层算法采用基于
权重的混合蛙跳算法模型，下层采用求解非合作博
弈的混合蛙跳算法模型.模型的算例验证结果表明：
文中双层规划模型符合应急车辆调度与再配置问题
的决策规则;下层模型综合考虑应急车辆再配置时
间和区域潜在风险，符合下层问题的决策目标;基于
双层规划问题及非合作博弈问题求解思想设计的层
次蛙跳算法，能较好地求解应急车辆调度与再配置
模型，且在求解速度和准确度方面均优于层次粒子
群算法.
参考文献：
[ 1 ] Y A M A D A Takeo. A network flow approach to aci t y
emergency evacuation planning [ J ]. International Jour
nal of Systems Science, 1 9 9 6,27 ( 1 0) ： 931-936.
[ ] 何建敏，刘春林，尤海燕.应急系统多出救点的选择问
题 [J ]. 系统工程理论与实践，2 0 0 1，21 ( 1 1) :89-93.
H E Jian-min, L I U Chun-lin, Y O U Hai-yan. Selection of
multi-depot in emergency systems [ J ]. Systems Engi
neering—Theory and Practice,2001 ,2 1 ( 1 1 ) ：89-93.
[ ] 戴更新，达庆利. 多资源组合应急调度问题的研究
[ ] . 系统工程理论与实践，2 0 0 0 , 2 0 ( 9) :52-55.
D A I Geng-xin, D A Qing-li. T h e study of combinatorial
scheduling problem in emergency systems [ J ]. Systems
Engineering—Theory and Practice,2 0 0 0 , 2 0 ( 9 ) ：52-55.
[ 4 ] C A R T E R G M ，C H A I K E N J M ，I G N A L L E. Response
area for two emergency units [ J ]. Operations Research，
1 9 7 2 , 2 0(3 ) ：571-594.
[5] SHERALI H D , SUBRAMANIAN S. Opportunity cost-
based models for traffic incident response problems [ J ].
Journal of Transportation Engineering, 1999, 125 ( 3 )：
176-185.
[6] OZBAY Kaan,XIAO Weihua. Probabilistic programming
models for response vehicle dispatching and resource allo
cation in traffic incident management [ C ] // Proceedings
of the 83rd Annual Meeting Compendium of Papers C D-
R O M . Washington D C ： Transportation Research Board，
2004.
[7] Z H A O Jiandong，DU A N Xiaohong，Z H A N G Lina，et al.
Traffic emergency resources dispatch based on opportuni
ty cost method with GA-BP optimization model [ J]. Ad
vances in Information Sciences and Service Sciences，
2013,5(9) ：301-309.
[ ] 杨继君，许维胜,黄武军，等.基于多灾点非合作博弈
的资源调度建模与仿真[ ] . 计算机应用，2008,28
(6) ： 1620-1623.
Y A N G Ji-jun, X U Wei-sheng, H U A N G W u -jun, et al.
Modeling and analyzing of simulation based on non-coope
rative games for multiple emergency locations in resources
scheduling [ J ]. Computer Applications, 2008,28 (6 )：
1620-1623.
[9] Y A N G Saini,HAMEDI Masoud, HAGHANI Ali. Online
dispatching and routing model for emergency vehicles
with area coverage constraints [ J ]. Transportation Re
search Record, 2005,1923 ： 1 -8.
[10] C H A N G Fu-Sheng，W U Jain-Shing，LEE Chung-Nan，et
al. Greedy-search-based multi-objective genetic algo
rithm for emergency logistics scheduling [ J ]. Expert
Systems with Application,2014,41 (6) ：2947-2956.
[11] ICHOUA Soumia，GEN D R E A U Michel，POTVIN Jean-
Yves. Vehicle dispatching with time-dependent travel
times [J]. European Journal of Operational Research，
2003,144(2) ：379-396.
[12] 刘芹,史忠科.混合粒子群算法求解交通路网中的车
辆调度问题[ ] . 控制与决策,2006,21 (11)1284-
1288.
LIU Qin，SHI Zhong-ke. Hybrid particle swarm algo
rithm for vehicle routing problem in road networks [ J ].
Control and Decision,2006,21 (11) ：1284-1288.
[ 1 3 ] 杨仁法，龚延成.带时间窗车辆调度问题的蚁群算法
[ ] .交通运输工程学报,2009,9(4)71-74.
Y A N G Ren-fa,GONG Yan-cheng. Ant colony algorithm
of vehicle scheduling problem with time windows [ J ].
Journal of Traffic and Transportation Engineering, 2009，
9(4) ：71-74.
[14] DUANXiaohong，SONGShouxin，ZHAOJiandong，et al.
第 3期 赵建东等：基于非合作博弈的应急车辆调度与再配置 117
Emergency vehicle dispatching based on shuffled frog
leaping algorithm [ J ]. Journal of Computational Infor
mation Systems,2013,9(24) ：9875-9884.
[15] D U A N Xiaohong, SONG Shouxin, Z H A O Jiandong.
Emergency vehicle dispatching and redistribution in
highway network based on bi-level programming [ J ].
Mathematical Problems in Engineering, 2015 , 2015 ：
1-12.
[ 1 6 ] 周光辉，王蕊,江平宇，等.作业车间调度的非合作博
弈模型与混合自适应遗传算法[] .西安交通大学学
报,2010,44(5) :35-39.
Z H O U Guang-hui，W A N G Rui，JIANG Ping-yu，et al.
Non-cooperation game model and hybrid adaptive genetic
algorithm for job-shop scheduling [J]. Journal of Xi ’ an
Jiaotong University,2010,44(5) ：35-39.
[17] BAI RB,LI J W,Atkin J A D,et al. A novel approach
to independent taxi scheduling problem based on stable
matching [ J ]. Journal of the Operational Research
Society,014,5(10) ：1501-1510.
[ 1 8 ] 赵志刚，顾新一,李陶深.求解双层规划模型的粒子
群优化算法[J] .系统工程理论与实践，2007,27
(8) ：92-98.
Z H A O Zhi-gang, G U Xin-yi, LI Tao-shen. Particle
swarm optimization for bi-level programming problem
[J]. Systems Engineering—Theory and Practice,2007,
27(8)92-98.
Emergency Vehicle Scheduling and Reallocation on the Basis of
Non-Cooperative Game
ZHAO Jian-dong1 D U A N Xiao-hong1 SONGShou -xin2
( 1. School of Mechanical and Electronic Control Engineering, Beijing Jiaotong University, Beijing 100044, China；
2. School of Economics and Management, Beijing Jiaotong University, Beijing 100044, China)
Abstract ： W h e n an emergency vehicle scheduling problem involving multiple accidents and multiple rescue sites
occurs , the response time of potential accidents can be shortened by redistributing idle emergency vehicles on res
cue sites , in addition to optimizing the scheduling of vehicles for current accidents. This paper presents an improved
model of emergency vehicle scheduling and reallocation on the basis of bi-level programming and non-cooperative
g ame. The upper level of the model is established under the constraints of accident requirements and accident rescue
window to minimize the response time for current accidents , while in the lower level of the model , each rescue site
is treated as a participant in a non-cooperative game , the payoff function of each participant is determined after tak
ing into account the reallocation time of the vehicle and the potential risks within the coverage area of each rescue
site , so that the optimal reallocation strategy is transferred into Nash equilibrium in a non-cooperative game. After
wards , an integrated bi-level shuffled frog-leaping algorithm is proposed , which contains an upper-layer algorithm
for single-objective programming and a lower-layer algorithm for solving the non-cooperative game. Several illustra
tive examples verify the rationality of the proposed model and the effectiveness of the integrated bi-level shuffled
frog-leaping algorithm.
K e y words ： emergency vehicles; scheduling algorithms; resource allocation ； game theory
