有状态转移方程
s
k
+ 1
=
T
k
(
s
k
,
u
k
)
(1)
需要确定高峰期动态分区时优化的目标函数,
不同的目标函数, 所求的优化策略不同。在上高峰交
通模式下, 把乘客逗留时间作为指标函数, 在略牺牲
候梯时间的情况下, 可降低乘梯时间和电梯停车次
数, 使各个楼层乘客的服务时间均匀化, 减少长候梯
率, 提高服务质量。
一个
n
阶段的电梯高峰期分区决策过程, 从 1
～
n
为分区问题的原过程, 对于任意一个给定的
k
(1
≤
k
≤
n
) , 从第
k
～
n
阶段的过程称为原过程的一个
后部子过程。
V
1, n
(
s
1
,
p
1, n
) 表示初始状态为
s
1
采用策
略
p
1, n
时原过程的指标函数值, 而
V
k
, n
(
s
k
,
p
k
, n
) 表示
在第
k
个阶段、状态为
s
k
采用策略
p
k
, n
时, 后部子过
程的指标函数值。最优指标函数记为
f
k
(
s
k
) , 它表示
从第
k
阶段
s
k
采用最优策略
p
3
k
, n
到过程终止时的最
佳效益值。由上可知,
f
k
(
s
k
) 与
V
k
, n
(
s
k
,
p
k
, n
) 的关系
为
f
k
(
s
k
) =
V
k
, n
(
s
k
,
p
3
k
, n
) =
op t
p
k
, n
∈
P
k
, n
V
k
, n
(
s
k
,
p
k
, n
)
(2)
式中 op t 表示最优化, 即利益最大化 (m ax) 或代价
最小化 (m in)。假设每个阶段经过决策转移到下一
个阶段都有一定的代价, 对于电梯系统来说, 给定乘
客到达率大小及其各楼层的分布, 就可以计算一个
分区方案的乘客平均逗留时间代价或者加权队长代
价。
高峰期动态规划求解分区问题的基本思想应
该是从结束状态 (这里指最后一个分区点
E
) 开始逆
方向逐段递推寻优, 用一个状态到结束状态最优路
径和最优值参与下一阶段的运算, 也就是说, 在每一
个子问题求解时, 都是用它前面子问题的最优结果,
最后一个子问题的最优解, 即为该问题的最优解。由
此得出动态规划的基本方程, 可以表示为
f
k
(
s
k
) =
op t
u
k
∈
D
k
(s
k
)
[
V
k
(
s
k
,
u
k
) +
f
k
+ 1
(
s
k
+ 1
) ]
k
=
n
,
n
-
1, …, 1
f
n
+ 1
(
s
n
+ 1
) = 0
(3)
以图 1 为例, 首先, 求取从
D
～
E
的优化路径。
D
阶段共有 12 个状态, 所以从
D
～
E
有 12 个路径,
每一个状态到
E
只有一条路径, 因此这 12 个路径都
需要参与下一个阶段 (
C
～
E
) 的计算。
C
阶段也有
12 个状态, 必须得出 12 条最优路径参与下一个阶段
的计算, 但是从
C
～
E
有很多路径, 例如, 从
C
1
～
E
共有 12 条可选路径, 这 12 条路径中必然存在一个
代价最小的路径, 选出来参与下一阶段的计算; 同
样, 从
C
2
～
E
共有 11 个可选路径, 选出一个代价最
小的路径参与下一阶段的计算; 以此类推。从
B
～
E
也可以用类似的方法求出 12 条最优路径参与从
A
～
E
的寻优。按此方法, 就可以求出从
A
～
E
的一条
最佳路径, 也就是高峰期的最佳分区点。
考虑到电梯群控的实时性, 如果在上高峰期
间, 交通流的变化较大, 先前采用动态规划划分的分
区点可能就不适应现有交通流, 需要再次进行动态
分区。因此, 如果现有交通流相对于动态分区时的交
通流变化较大时, 需进一步采用动态规划进行动态
分区, 以保证动态分区划分的实时性。
4
动态规划法和穷举法计算量比较
用穷举法 (即搜索法) 计算电梯高峰期的分区
问题, 如图 1 所示, 共有路径数
PN
可以按下式计算
PN
=
∑
12
i
= 1
∑
i
j
= 1
j
=
1
2
∑
12
i
= 1
(
i
2
+
i
) =
1
2
[
1
6
× 12 × (12 + 1) × (2 × 12 + 1) +
1
2
× 12 × (12 + 1)
]
= 364
穷举法需要进行比较的次数为
CN
s
=
PN
-
1 = 363
假设在每一个阶段的代价已经计算出来的情
况下, 穷举法需要进行的加法次数为
A N
s
=
∑
12
i
= 1
∑
i
j
= 1
(2
j
+ 1) = 806
用动态规划的思想求解图 1 的分区问题, 需要
进行的加法次数为
A N
d p
= 2
∑
12
i
= 1
i
+ 12 = 168
需要进行的比较次数为
CN
d p
= 2
∑
11
i
= 1
i
+ 11 = 143
设动态规划的计算量和穷举法的计算量之比
为
Γ, 则有
Γ=
A N
d p
+
CN
d p
A N
s
+
CN
s
=
168 + 143
806 + 363
= 26. 6
◊
上述计算表明, 用动态规划求解高峰期动态分
区问题可大大减少运算量, 提高运算速度, 是一种比
穷举法更快的分区计算方法。
增 刊
宗 群等: 电梯上高峰动态规划分区控制方法的研究
783