电梯乘客交通分布的混合算法求解

金逸乔

(上海交通大学 电子信息学院，上海 200240)

0 引言

电梯作为垂直交通运输的重要工具，随着文明的不断发展，早已成为了人类生活必不可少的部分。根据国家质量监督检验检疫总局“关于2016年全国特种设备安全状况情况的通报”显示，截至2016 年底，全国在用电梯登记数量为493.69万台，我国电梯保有量、年产量、年增长量均为世界第一。面对如此庞大且复杂的输送能力需求，如何通过改进电梯的配置方案以及服务性能来应对这些需求，一直是电梯行业专家以及各国学者研究的课题。

电梯的交通客流情况，是各项研究的基础数据。通过对客流情况的分析，可以调整和优化电梯的群控系统，可以研究不同建筑的客流特性，可以检验和预测电梯的配置是否合理。电梯交通客流数据包含的内容非常宽泛，理论上来说包含了乘客乘坐电梯发生的交通行为的所有数据。其中“每层进出电梯的乘客数”，能直接反映电梯乘客在建筑中交通状况，同时获取手段也比较多，因此在研究中较为常见。以往的研究中，侧重点通常是电梯群控系统的优化，因此每层进出电梯乘客数能够符合要求。但如要进行电梯配置规划及建筑客流分析，评价方式一般是一个绝对指标，此时就需要讨论电梯及乘客在楼层间的交通情况，即电梯交通分布的信息。

随着电梯远程监控与服务系统的大力发展[1]，每层进出电梯的乘客数已经可以通过该系统记录的电梯称量装置的相关数据来获取，但是电梯交通分布信息难以通过简单的方式大规模获取。鉴于现状，本文以每层进出电梯的乘客数为基础，建立了乘客交通分布求解的模型，然后通过遗传算法(Genetic Algorithm)与列文伯格-马夸尔特算法(Levenberg-Marquardt Algorithm)结合的混合算法来求解模型，最终获得电梯乘客交通分布信息。

1 电梯乘客起讫点矩阵

起讫点是一个在交通运输规划中被广泛提及的概念，其描述的是交通网络中从起点(origin)到终点(destination)的相关信息。而起讫点表，或称OD表，就是一个交通网络中所有起点与终点间产生的交通流量构成的表格，是交通网络的出行分布交通量的直观表达，体现了用户对于交通网络的基本需求。根据起讫点数据表构成的起讫点矩阵是进行进一步的交通规划必不可少的基础数据，是进行交通流量分配的前提，也是进行交通管理与控制优化的重要基础[2,3]。一个存在n个区域(即n个起点，n个终点)的交通网络，其起讫点表如表1所示。

电梯作为垂直运输工具，在许多地方与水平方向的交通运输工具有着相似点。电梯运行产生的乘客交通量同样存在起讫点的概念并形成一定的交通分布，在电梯的运行过程中，电梯运行的楼层是对交通区域的划分，每个交通区域的发生量与吸引量相应的是每一层进入电梯的乘客数与离开电梯的乘客数，乘客通过在起点楼层与终点楼层间的移动构成了一张起讫点表，表的形式与表1一致，由ODij组成的n×n阶的矩阵就是电梯乘客起讫点矩阵。

表1 起讫点表

求电梯乘客交通分布的问题可以作如下描述：在一个服务n层楼的电梯群组中，设Bi表示第i层进入电梯(boarding)的乘客数，Ai表示第i层离开电梯(alighting)的乘客数，xij表示从第i层进入、第j层离开的电梯乘客数，其组成了n×n阶的矩阵X。其简单示意如图1所示。

图1 电梯运行起讫点描述示意

根据起讫点的概念，Bi、Ai与xij具有如下关系如式(1)。

(1)

上述问题中，Bi和Aj是我们通过电梯远程监控与服务系统得到的数据，共有2n个已知量，而xij为未知量，共n2个，式(1)可以组成2n个线性方程，一般情况下，电梯乘客基本不会发生同一楼层进出的情况，即当i=j时xij=0，因此实际问题中未知量的个数可以减小为n(n-1)个，即要求的乘客起讫点矩阵X是个对角矩阵。同时，实际问题中，电梯服务层数超过3(即n>3)时，n(n-1)>2n，因此仅上述条件，无法求得xij。

2 电梯乘客起讫点矩阵的最大熵模型

Willumsen提出了的一种在交通运输领域推算起讫点矩阵的模型——最大熵模型。将每个起讫点对的一次出行看作一次随机的事件，每种可能出现的起讫点状态都相应存在一个出现概率，出现概率最高的就是实际存在的起讫点状态[4]。

根据最大熵理论，在一个有n个区域的交通网络中，从起点i到终点j的交通流量Tij就表示第ij个事件的发生次数，而网络的总流量T，即事件的总次数就是式(2)。

(2)

根据特定的排列形成Tij的概率就是式(3)。

(3)

按照最大熵原理的思想，实际存在的Tij是使W(Tij)熵值最大的矩阵。因此，将其存在概率设为目标函数，为方便求解，目标函数设为式(4)。

(4)

根据斯特林公式(Stirling approximation)lnx!≈xlnx-x，式(4)可以化简得式(5)。

(5)

(6)

(7)

Tij≥0

(8)

α=1,2,…,m

(9)

i,j=1,2,…,n

(10)

(11)

(12)

(13)

i≠j

(14)

i,j=1,2,…,n

(15)

其中，Bi是第i层离开电梯人数，Aj是第j层离开电梯人数，在实际问题中，同一层上下电梯的情况可以忽略，因此令i≠j，由xij组成的对角矩阵X就是所要求得的起讫点矩阵。

针对上述基于最大熵模型表述的优化问题，是一个带约束的非线性优化问题，无法直接求解。易知(11)为凸函数，因此利用拉格朗日乘数法(Lagrange Multiplier Method)，构造拉格朗日函数：

(16)

根据库恩-塔克条件(Kuhn-Tucker Condition)，最优解通过计算L(xij,λ)对xij的偏导数，即式(17)。

(17)

可得式(18)。

xij=e-1-λi-λn+j

(18)

根据式(12)，(13)，(14)和(18)，可得式(19)。

(19)

上述方程组是以拉格朗日乘子λ=(λ1,λ2,…λ2n)T为变量，共有2n个未知数的非线性方程组。那么，原问题就可以通过求解拉格朗日乘子，再代入式(4-23)来求得xij和X即起讫点矩阵。

传统的求解方法是迭代法数值求解。以最典型的牛顿法为例，其求解方法如下。建立方程组F(λ)式(20)。

(20)

牛顿迭代格式为式(21)。

λk+1=λk-[J(λk)]-1F(λk)

(21)

其中，k为迭代次数，J(λ)为F(λ)的雅克比(Jacobi)矩阵。迭代的算法如下。

Step1：给定初始值λ0，和精度阈值ε>0，并令k=0；

Step2：计算F(λk)，J(λk)；

Step3：求解线性方程组J(λk)Δλk=-F(λk)，得Δλk;

Step5：计算新的迭代点λk+1,λk+1=λk+Δλk;

Step6：令k=k+1，转至Step2。

3 混合算法求解最大熵模型

求解最大熵模型的传统牛顿法在求解中有着不足：迭代过程中计算矩阵必须是非奇异矩阵。而在实际问题中，其最大的限制是必须给出初值。但考虑到实际的电梯乘客分布问题中，针对每一次采集到的电梯进出人数信息，是无法给出初始分布的，这也就意味着没有办法给出符合实际情况的初值，因此牛顿法包括其他一些改进的牛顿法难以适用。针对这个问题，本文提出一种遗传算法(Genetic Algorithm)与列文伯格-马夸尔特算法(Levenberg-Marquardt Algorithm)结合的混合算法来求解。遗传算法的全局寻优能力强，能够在缺少初值信息的情况下，获得一个较优的数值解[6]。以此较优解为初值，利用列文伯格-马夸尔特算法开始迭代，能够以良好的速度和精度获得最优解。这样混合算法可以避免遗传算法收敛慢的问题，同时能够在实际问题中产生合适的初始值并快速求得模型的解。

遗传算法的各项操作如下：

(1) 目标函数和适应度函数

首先要确定遗传算法的目标函数。本文基于式(19)和式(20)构造目标函数如下式(22)。

(22)

式中，λ=(λ1,λ2,…λ2n)T，且i≠j。

适应度函数为式(23)。

N(λ)=Cmax-M(λ)

(23)

式中，Cmax取一个M(λ)最大估计值，根据实际问题的情况而定。

(2) 编码方式及种群初始化

本文采用浮点数编码。考虑到二进制编码或格雷码编码的长度较大，计算量会增大，而对于本问题，变量的取值有负数存在，需要搜索的范围较大，因此综合相应的选择、交叉与变异方式，确定采用浮点数编码。初始种群通过随机的方式产生，种群规模需要根据不同情况进行设计，会由于实际问题中电梯的楼层数而改变，但是原则上，考虑到混合算法的目的是通过遗传算法输出一个供LM算法使用的初始值，因此种群规模不宜过小，否则会对全局搜索产生影响。

(3) 适应度计算

算法需要通过个体适应度来判断个体的优劣程度，来决定优秀个体的遗传。适应度比例参数是把适应度函数所返回的适应度值转换为适合于选择函数使用范围的值。本文通过个体适应度值的排列顺序而不是个体适应度值的大小来衡量个体的优劣，最适合个体的排序为1，次最适合个体的排序为2，依此类推，这样可以消除原始适应度值的影响。

(4) 选择

选择运算，又称为复制运算。是在当前群体中选择适应度较高的个体按某种规则或模型遗传到下一代群体中。在本文中采用轮盘赌规则，即与适应度成正比的概率来确定各个体复制到下一代群体中的数量。具体的操作过程是：首先，计算出群体中所有个体的适应度值的总和；其次，计算出每个个体的相对适应度大小，每个个体都会在某个概率区间内，该区间表示个体会被遗传下去的概率大小，所有区间的概率值总和为1；最后，产生一个0～1之间的随机数，通过判断该随机数落在上述哪一片概率区间来确定该各个体所对应的被选中的机率。

(5) 交叉

交叉运算是遗传算法中产生新个体的主要操作过程，它以某一概率相互交换某两个个体之间的部分染色体。本文采用如下交叉的方式：在1到变量个数之间选择两个随机数m和n，在第一个父辈中选择序号小于或等于m的向量项，在第二个父辈中选择序号在m+1到n的向量项，序号大于n的向量项也来自于第一个父辈。这样可以有效提高遗传算法的搜索速度，为尽快得到初始值，转到LM算法做准备。

(6) 变异

变异运算对个体的某一些基因编码串中的基因按某一概率进行改变以产生新的种群，指明了个体在子种群间的遗传。本文采用基本位的方式进行变异。

(7) 算法终止

本文考虑的是通过遗传算法得到LM算法的初始解，避免遗传算法陷入局部过慢的收敛中，因此需要根据实际问题中不同的情况设置算法终止条件，一般通过设置进化代数限制来实现。

综合上述分析，结合LM算法后，整个混合算法的步骤是：

Step1：遗传算法初始化种群；

Step2：遗传算法求解，得到局部最优解及变量值；

Step3：变量作为初始值输入LM算法作为初始迭代点λ0；

Step4：设置LM算法初始步长因子μ0，步长调整因子v>1，精度阈值ε>0，并令k=0；

Step5：计算F(λk)，J(λk)；

Step7：求解方程组(J(λk)TJ(λk)+μkI)Δλk=-J(λk)TF(λk)，得Δλk

Step8：计算F(λk+Δλk)，如果F(λk+Δλk)>F(λk)，则转至Step9，否则转至Step10；

Step9：令μk=vμk，转至Step7；

4 实例分析

通过前文提及的电梯远程监控与服务系统采集了某医院病房大楼电梯的每层进出电梯乘客数，采集时段是一个工作日，从电梯启动到电梯停运为止，如表2所示。

表2 某大楼一天年内进出电梯的乘客数据

使用混合算法求解最大熵模型，遗传算法的相关参数为：种群规模POPSIZE=160，交叉概率PCROSS=0.8，变异概率PMUT=0.15，终止代数MAXGENS=400。400代进化结束后，算法结果如图2所示。

图2 遗传算法结果

以遗传算法的结果作为初始值，开始LM算法。结果如图3所示。

图3 LM算法结果

将LM算法得到的变量值代入，最终求得，大楼的乘客交通分布如表3所示。

表3 电梯乘客交通分布表

5 总结

作为电梯群控系统优化、电梯配置规划和建筑客流分析的基础，电梯乘客交通分布的情况是一个重要的信息。本文在最大熵模型的基础上提出了遗传算法和LM结合的混合算法，求得电梯乘客交通分布，可以作为群控仿真、电梯配置规划的输入数据，无需进行费时费力的人工调查，有着很强的实用性。