CN101506076B - 使用事先的交通信息的分组电梯调度 - Google Patents

Abstract

一种用于升降机组的接近最佳调度方法使用事先的交通信息。更具体地，事先的交通信息被用来定义目标是为客户改进性能的快照问题。为了求解快照问题，目标函数被变换成一种易于把问题分解为各个座舱子问题的形式。子问题通过使用双层公式被独立地求解，在较高层进行乘客到座舱指定，以及在较低层进行各个座舱的分派。得到接近最佳的乘客选择和各个座舱路线。各个座舱然后通过迭代处理过程进行协调，达到分组控制解，该分组控制解给出对于乘客的接近最佳结果。

Description

使用事先的交通信息的分组电梯调度

相关专利申请的参考

本专利申请要求2005年4月15日提交的美国临时专利申请序列号No.60/671,698的优先权，该专利申请在此引用以供参考。

技术领域

本发明涉及电梯控制领域，具体地，涉及在建筑物中电梯成组运行的调度。

背景技术

成组电梯调度一直被认为是对于运输效率的重要问题。然而，因为混合系统动力学，状态和判定空间的组合激增、时变和不确定的乘客要求、严格的运行约束条件、和对于在线调度的实时计算要求，该问题是困难的。

最近，引用具有目的地输入的电梯系统。在目的地输入系统中，要求乘客在他们得到服务之前登记他们的目的地楼层。因此，更多的信息对于成组电梯调度是可得到的，因为当选定轿厢指定时，乘客目的地现在是已知的。而且，随着信息技术的进步，一个有前景的方向是使用来自各种新的传感器或要求估计技术的事先的交通信息来减小不确定性和大大地改进性能。使用事先的交通信息的接近最佳调度，与不使用事先的交通信息而确定的调度相比较，将导致更好的性能。

发明内容

本发明针对用于使用事先的交通信息的电梯组的调度方法。更具体地，事先的交通信息被用来定义目标是为客户改进性能的快照问题(snapshot problem)。为了解决该快照问题，目标函数被变换成一种易于把问题分解为各个轿厢子问题的形式。子问题通过使用双层公式而独立地解决，在较高层进行乘客到轿厢指定，以及在较低层进行各个轿厢的分派。得到接近最佳的乘客选择和各个轿厢路线。各个轿厢然后通过迭代处理过程进行协调，达到分组控制解，该分组控制解给出对于乘客的接近最佳结果。该方法可以扩展到只有很少的或没有事先信息；电梯的停车操作；和协调的紧急撤离的情形。

本发明提供了用于调度电梯组的方法，该方法包括：对与在预见窗口内的乘客到达时间、到达楼层和离开楼层有关的事先信息进行建模，以便创建快照问题；以及通过根据在快照问题中所有乘客的总服务时间使目标函数最小化来解决快照问题，以确定乘客到轿厢指定和轿厢分派。

本发明提供了用于调度电梯组的方法，该方法包括：接收与乘客到达时间、到达楼层和离开楼层有关的事先信息；根据在预见窗口内所有的未指定的乘客的总服务时间来形成目标函数；把目标函数变换成易于分解快照问题的加法形式；把Lagrangian松弛法施加到变换的目标函数；迭代求解单个轿厢的子问题并更新Lagrangian乘子；以及为每个轿厢选择乘客-轿厢指定和轿厢分派。

本发明提供了用于控制电梯组的运行的方法，该方法包括：接收与乘客到达时间、到达楼层和离开楼层有关的事先信息；根据该事先信息、包括轿厢容量约束条件与轿厢动力学信息的各个轿厢模拟模型、以及作为性能度量的加权和的目标函数，来实时选择乘客到轿厢的指定和轿厢的分派；以及根据所述选择来分派轿厢。

本发明提供了用于控制电梯组的运行的方法，该方法包括：接收事先的交通信息；将事先的交通信息建模成电梯组的当前状态，以创建快照问题，其中快照问题包括需要每个乘客被指定到单个轿厢的乘客指定约束条件；以及通过以下步骤求解快照问题，使目标函数最佳化：放松乘客指定约束条件，以把快照问题变换成放松的问题；把放松的问题分解为独立的轿厢子问题；以及求解所有的独立的轿厢子问题，以生成乘客指定。

附图说明

图1是使用事先的交通信息控制的电梯组的图；

图2是显示在乘客到达时间与离开时间之间的度量的图；

图3是显示双层求解方法的流程图；

图4是显示本地搜索的图；

图5是显示分阶段花费的图；

图6是显示具有75％重叠的非零预见移动窗口的图。

具体实施方式

图1显示由一组四部电梯12提供服务的、具有10层F1-F10的建筑物10。轿厢J1-J4在成组电梯控制14的控制下在电梯12的升降井内移动。轿厢J1-J4的调度是根据代表实际的或预测的服务请求的输入而被协调的。

成组电梯控制14接收要求信息输入，该输入提供有关乘客i的到达时间t_i，乘客i的到达楼层f_i ^a，和乘客i的目的地楼层f_i ^d的信息。事先的交通信息输入的一个源是目的地输入系统，该目的地输入系统具有被放置在离电梯一个距离的键盘，这样，乘客通过在登上电梯之前键入目的地楼层而请求服务。事先的交通信息的其它的源包括引导着陆的在走廊里的传感器、视频照相机、识别卡读取器、和联网到成组电梯控制的计算机系统，以根据预测的要求向特定的目的地楼层提供对于轿厢的事先预订或请求。例如，旅馆会议调度系统可以与成组电梯控制14接口，以提供有关会议何时开始或结束的信息，从而生成对于电梯服务的要求。

组电梯控制14是基于计算机的系统，它利用预期的或已知的将来交通要求来决定如何指定乘客到轿厢以及如何分派轿厢搭载和输送乘客。通过使用事先的交通信息，成组电梯控制14提供电梯在服务于乘客方面增强的性能。在对于性能度量的几个可能的选择中的一个选择是减小请求服务的所有乘客的总的服务时间。这个或任何其它目标必须以遵循乘客-轿厢指定约束条件和轿厢容量约束条件以及服从轿厢动力学的方式被满足。

事先的交通信息被成组电梯控制14用来选择来自输入的、落在窗口内的信息。利用每个窗口快照，事先的交通信息用于公式化使客户性能最佳化的目标函数。

在操作电梯组时，如图1所示，电梯12是独立的，而电梯组的各个轿厢J1-J4通过服务于共同的一组乘客而被耦合。对于每个乘客，有且仅一个电梯服务于该乘客。然而，一旦乘客集合被指定到各个轿厢，一个轿厢的分派就与其它的轿厢无关。

这个耦合的但可分开的问题结构被成组电梯控制14用来建立简单但新颖的双层公式化：乘客指定处于较高层，以及单个轿厢分派处于较低层。

电梯分派问题通过放松乘客轿厢指定约束条件而被分解为各个轿厢子问题。然后，对于每个轿厢执行搜索，以选择要由该轿厢提供服务的最好乘客集合。单个轿厢动力学和轿厢容量约束条件被嵌入到单个轿厢模拟模型，以产生对于每个轿厢具有最好性能的最好乘客集合。各个轿厢的结果然后通过更新乘子的迭代过程被协调，以达到对于客户的接近最佳解。以上的方法可以扩展到只有很少的或没有事先信息；电梯停车的操作；和协调的紧急撤离的情形。

预见窗口被使用来对事先的要求信息进行建模，其中考虑在窗口内的已知的或估计的交通。窗口到轿厢指定约束条件被建立为线性不等式约束条件，以及是“耦合的”约束条件，因为各个轿厢通过服务于共同的一组乘客而被耦合。轿厢容量约束条件和轿厢动力学被嵌入在各个轿厢模拟模型内。目标函数在按乘客、按轿厢和按建筑物的测量值，例如乘客等待时间、服务时间或所需要的电梯能量，或在乘客旅程期间经受的轿厢停站的数目的范围内是灵活的。

正如图1所示的例子所显示的，系统是具有F层和J部电梯的建筑物。电梯的参数被给出，包括轿厢动力学和轿厢容量约束条件。电梯组的当前状态，除了轿厢动力学和轿厢容量约束条件以外，包括每部电梯的运行状态：例如，已被指定到轿厢的乘客，在升起路上轿厢的位置，轿厢是否在加速、减速、轿厢方向、轿厢速度。例如，轿厢停止在楼层，门打开，轿厢在楼层之间运动，等等。

事先的交通信息通过预见窗口被建模。假设由到达窗口内的每个乘客1的到达时间t₁ ^a、到达楼层f₁ ^a，和的目的地楼层f₁ ^d规定的事先的交通信息是已知的。事先的交通信息与电梯组的当前状态的区别在于，事先的交通信息涉及到没有被指定到轿厢的乘客。具有不同的事先的交通信息量的情形，诸如从不同的乘客接口或要求估计方法得到的那些事先的交通信息，可以通过调节窗口尺寸而被处理。然后结合窗口使用滚动水平方案，以及快照问题按周期地或按需要被解决。对于快照问题，令S_p表示已被搭载但还没有到达他们的目的地楼层的I_p个乘客的集合，以及S_c表示还没有被搭载的I_c个乘客的集合。总共有I个乘客(I＝I_c+I_p)要传送到他们的目的地楼层。这个方法允许在选择何时提交(commit)指定时的很大灵活性。考虑各种提交策略，乘客量I_c可以在1与I之间变化。一旦问题被解决，成组电梯控制14就在下一个重新调度点之前只提交将被搭载的I_c个乘客的子集的指定，以及将延迟提交其它的乘客。

要考虑的约束条件包括在轿厢之间的耦合约束条件和各个轿厢约束条件。前者包括乘客到轿厢指定约束条件，阐述每个乘客必须被指定到有且仅有一个轿厢，即，

$\underset{j=1}{\overset{J}{\mathrm{\Σ}}}{\mathrm{\δ}}_{\mathrm{ij}}=1,\∀i---\left(1\right)$

其中，δ_ij是零-一指数变量，如果乘客i被指定到轿厢j，它等于1，否则它等于零。对于快照问题，δ_ij，对于所有的i∈I_p(即，已被搭载但还没有到达他们的目的地楼层的乘客)是固定的，以及仅仅δ_ij，对于所有的i∈I_c(即，还没有被搭载和要传送的乘客)要被最佳化。应当指出，各个轿厢被耦合，因为它们必须服务于共同的乘客组。各个轿厢约束条件包括轿厢容量约束条件：

$\underset{i=1}{\overset{I}{\mathrm{\Σ}}}{\mathrm{\ζ}}_{\mathrm{ijt}}\≤C_j,\∀j,t---\left(2\right)$

其中C_j是轿厢j的容量，以及ζ_ijt是0-1指数变量，如果乘客i在时间t在轿厢j中，它等于1，否则它等于零(ζ_ijt＝1，如果t_i ^p≤t＜t_i ^d)。在上面，乘客i的搭载时间t_i ^p和离开时间t_i ^d仅仅取决于各个轿厢对于给定的指定如何被分派，以及由分派策略

代表：

其中S_i≡{i′|δ_i′j＝1}和i∈S_j. (3)

鉴于变量{ζ_ijt}的数目是大的，并且函数可能太复杂而不能描述，约束条件(2)和(3)没有明显地表示出，而被嵌入在各个轿厢的模拟模型中。在模拟模型中也使用其它电梯参数，诸如门打开时间、门停留时间(保持门打开的最小时间间隔)、门关闭时间和每个乘客的装载和卸载时间。

成组电梯控制的目标在于，调度将导致较高的客户(乘客或建筑物管理人员)满意度。本方法使能的一个可能性是集中在等待时间的加权和。例如，对于乘客i，等待时间T_i ^W是在乘客i到达时间与搭载时间之间的时间间隔(T_i ^W＝t_i ^p-t_i ^a)，传送时间是在搭载时间与离开时间的间隔(T_i ^T＝t_i ^d-t_i ^p)。服务时间T_i是以上两项的和，或是到达时间与离开时间之间的差(T_i ^S＝t_i ^d-t_i ^a)。时间定义被显示于图2。等待时间是在达时间与搭载时间之间的时间间隔。传送时间是在搭载时间与离开时间的间隔。在本例中，目标是使所有乘客的等待时间和传送时间的加权和最小化，即，

$\underset{\left\{\begin{array}{c}{\mathrm{\δ}}_{\mathrm{ij}},\∀i\∈S_c,\∀j\\ t_i^p,\∀i\∈S_c\∪S_p\end{array}\right\}}{\min }J,$ 其中 $J\≡\underset{i=1}{\overset{I}{\mathrm{\Σ}}}{T}_i,---\left(4\right)$

其中 $T_i=\mathrm{\α}(t_i^p-t_i^a)+\mathrm{\β}(t_i^d-t_i^p)=\mathrm{\α}{T_i}^W+\mathrm{\β}{T_i}^T---\left(5\right)$

上面，α和β是设计者规定的加权因子。应当指出，当α＝β＝1时，T_i＝T_i ^S；以及当α＝1和β＝0时，T_i＝T_i ^W。还应当指出，目标函数可以包括其它性能度量，诸如移动电梯所需要的能量和电梯停靠的数目。目标函数(4)的最佳化受到约束条件(1)，(2)和(3)的限制。这个例子不应当看作为限制其它约束条件的使用。

目标函数的公式化可应用于任何建筑物结构和交通图案，因为对于它们没有进行特定的假设。

如这里所述，耦合的乘客-轿厢指定约束条件(1)是线性不等式约束条件，以及轿厢容量约束条件(2)和轿厢动力学(3)被嵌入在各个轿厢模拟模型内。所以，目标函数(4)首先被变换成易于把问题分解为各个轿厢子问题的形式。然后通过放松导致独立轿厢子问题的耦合的乘客轿厢指定约束条件(1)来开发分解和协调方法。轿厢子问题计算乘客指定到轿厢对系统性能的灵敏度。这是以一系列步骤完成的。第一步骤是决定哪些乘客被指定到特定的轿厢。这个指定步骤可以通过使用本地搜索方法被解决。在一个这样的方法中，首先通过使用启发式法根据次序最佳化概念来快速评估和排名乘客选择，次序最佳化概念是即使用粗略的估算进行排名也是健壮的，正如技术上已知的。利用这个排名信息，通过动态编程使单个轿厢分派最佳化，来为精确的性能评估最高的选择。在代理(surrogate)最佳化框架内，比起以前的选择“更好的”选择对于设置乘子更新方向是“足够好的”。各个轿厢然后通过使用对于接近最佳解的代理最佳化迭代地更新乘子而被协调。这个方法的框架显示于图3。具体的步骤在下面描述。

图3显示用于解决每个快照问题的双层求解方法20。方法在初始化步骤22开始。通过放松耦合的乘客轿厢指定约束条件24创建放松的问题而开发分解与协调方法。放松的问题被分解为轿厢子问题26，这些问题被独立地解决。在轿厢指定问题内的第一步骤28是选择乘客以指定给轿厢。第二步骤使用单个轿厢模型30，以通过使用轿厢动态模型34来识别接近最佳的单个轿厢路线32，随后估计得到的性能36。一旦所有的轿厢子问题都被解决，下一个步骤是构建可行的乘客到轿厢指定38，随后使用停止准则40。准则40确定这个解何时足够接近最佳，以便停止进一步迭代。如果不是的话，在下一个迭代中通过使用来自轿厢子问题26的梯度信息来更新42乘子。

为了把目标函数(4)分解为各个轿厢子问题，目标函数在各个轿厢方面应当是相加的。因此，在公式(4)中的目标函数通过使用(1)被重写为：

$J=\underset{i=1}{\overset{I}{\mathrm{\Σ}}}\left(T_i\underset{j=1}{\overset{J}{\mathrm{\Σ}}}{\mathrm{\δ}}_{\mathrm{ij}}\right)=\underset{j=1}{\overset{J}{\mathrm{\Σ}}}\underset{i=1}{\overset{I}{\mathrm{\Σ}}}\left({\mathrm{\δ}}_{\mathrm{ij}}{T}_i\right)---\left(6\right)$

通过这个相加形式，指定约束条件(1)通过使用非负的Lagrangian乘子{λ₁}被放松：

$L(\mathrm{\λ},\mathrm{\δ})=\underset{j=1}{\overset{J}{\mathrm{\Σ}}}\underset{i=1}{\overset{I}{\mathrm{\Σ}}}\left({\mathrm{\δ}}_{\mathrm{ij}}{T}_i\right)+\underset{i=1}{\overset{I}{\mathrm{\Σ}}}{\mathrm{\λ}}_i(1-\underset{j=1}{\overset{J}{\mathrm{\Σ}}}{\mathrm{\δ}}_{\mathrm{ij}})$

$=\underset{j=1}{\overset{J}{\mathrm{\Σ}}}\underset{i=1}{\overset{I}{\mathrm{\Σ}}}({\mathrm{\δ}}_{\mathrm{ij}}{T}_i-{\mathrm{\λ}}_i{\mathrm{\δ}}_{\mathrm{ij}})+\underset{i=1}{\overset{I}{\mathrm{\Σ}}}{\mathrm{\λ}}_i.---\left(7\right)$

通过从(7)收集与j有关的所有项，得出对于轿厢j的子问题为：

$\underset{\left\{\begin{array}{c}{\mathrm{\δ}}_{\mathrm{ij}},\∀i\∈S_c,\∀j\\ t_i^p,\∀i\∈S_c\∪S_p\end{array}\right\}}{\min }{L}_j,$ 其中 $L_j\≡\underset{i=1}{\overset{I}{\mathrm{\Σ}}}({\mathrm{\δ}}_{\mathrm{ij}}{T}_i-{\mathrm{\λ}}_i{\mathrm{\δ}}_{\mathrm{ij}}),---\left(8\right)$

受到容量约束条件(2)和轿厢动力学(3)限制。

新颖的和经济的方法被使用来解决对于轿厢j的子问题(8)。轿厢子问题(8)是为给定的乘子集合获得最佳乘客选择和所选择乘客的最佳路线。鉴于所牵涉到的大的搜索空间，很难得到最佳解。无论如何，根据代理次梯度方法，在某些条件下仅仅一个或几个子问题的近似最佳化足以生成适当的方向，从而更新乘子。参阅：X.Zhao，P.B.Luh，和J.Wang，“The Surrogate Gradient Algorithm for Lagrangian RelaxationMethod”，Journal of Optimization Theory and Applications，Vol.100，No.3，March 1999，pp.699-712。通过利用这个特性，目标是获得更好的乘客选择，以及通过使用本地搜索方法来有效地分派选择的乘客。子问题通过使用本地搜索方法结合启发式法和动态编程而被独立地解决。

图3所示的乘客指定28的实施例的例子是图4所示的本地搜索方法50。首先，根据树搜索技术通过一次改变一个乘客而生成乘客选择。对于在本地搜索50中的每个节点(例如，给定了乘客选择δ_ij)，问题是要估计性能，最佳化的单个轿厢分派为如下：

$\underset{\{t_i^p,\∀i\∈S_c\∪S_p\}}{\min }\underset{i=1}{\overset{I}{\mathrm{\Σ}}}{\mathrm{\δ}}_{\mathrm{ij}}{T}_i.---\left(9\right)$

在本地搜索50中，首先快速评估乘客选择，和通过使用启发式法根据次序最佳化概念--即，即使粗略评估排名也是健壮的--进行排名。

然后如图4所示，由单个轿厢模型30，对于精确的性能评估来自本地搜索50的最高候选项。如果它好于原先的选择，则接受它。否则，评估第二好的。如果没有找到更好的选择，则保持原先的选择，并解决下一个子问题。在代理最佳化框架内，好于以前选择的选择是对于设置乘子更新方向是足够好的。

本地搜索程序过程的伪代码显示于表1。

表1

一旦已经定义用于单个轿厢路线的策略，就可以评估从乘客到轿厢的指定的特定选择中得到的性能。这个方法允许单个轿厢路线策略的任何选择。例如，一个流行的单个轿厢路线策略被称为完集(fullcollective)政策，如本领域已知的。

在求解问题(公式9)的一个方法中，单个轿厢模型30作为基于模拟的动态编程(DP)方法被实施，该方法使轿厢轨迹最佳化并评估乘客选择。可以使用单个轿厢模型30的具体的例子具有DP阶段、状态、判定和花费的新颖的定义，以减小计算要求，正如下面描述的。关键概念是对于单向行程，如果给定停止楼层，则轿厢轨迹被唯一地规定。之后，将一个阶段定义为轿厢的单向行程而不改变它的方向。

对于在时间t_k开始的阶段，DP状态包括在t_k的轿厢位置f_j、轿厢方向d_j、和在t_k还没有被传送到他们的目的地楼层的乘客组S_k的状态(乘客i的状态包括到达时间t_i ^a、到达楼层f_i ^a、和目的地楼层f_i ^d)。状态因此由下式代表：

$X_k=(t_k,f_j,d_j,\{t_i^a,f_i^a,f_i^d|\∀i\∈S_k\}).---\left(10\right)$

对于状态的判定包括停靠楼层、轿厢改变其方向的返回楼层、和在当前的阶段要递送的乘客(限于行进在停靠的楼层之间的那些乘客)。判定因此可以由

代表，其中u_i是0-1判定变量，如果乘客I在阶段k被传送到目的地楼层，则等于1，否则等于零。对于在t_k时已经在轿厢j的乘客，u_i总是等于1。对于具有相同的到达和离开楼层的乘客，他们按照先来先服务的法则被搭载。

为了说明起见而集中于等待时间和传送时间性能矩阵，给定X_k和U_k，通过单个轿厢模拟，来获得在阶段k递送的乘客的搭载时间t₁ ^p和离开时间t₁ ^d以及阶段k+1的开始时间t_k+1。应当指出，对于每个乘客，等待时间或传送时间在每个阶段(即，每个单向行程)在他/她的延时上是相加的。所以，在(9)中的目标函数--所有乘客的等待时间和传送时间的加权和值--可以如下地被划分成阶段。

图5是对于分阶段花费的示意图。阶段k在时间t_k开始，和在时间t_k+1结束。对于在阶段k被递送的任何乘客(u₁＝1)，在阶段k的等待时间是t_j ^p-max(t_k，t_i ^a)，以及传送时间是t_j ^d-t_j ^p。对于在阶段k没有被传送的任何乘客(u₁＝0)，在阶段k的等待时间是t_k+1-max(t_k，t_i ^a)，以及传送时间是0。目标函数

因此可被合并到以下的分阶段花费中：

通过以上的定义，通过使用正向动态编程来获得对于单个分派的最佳轨迹。

根据代理次梯度法，在某些条件下仅仅一个或几个子问题的近似最佳化足以生成更新乘子的适当方向。首先，所有的子问题应当在初始迭代时被最小化。初始化乘子的快速方式是基于观察：当

时，对于所有的子问题的最佳解是

(见表2的伪代码)。

和{δ_ij}⁰的初始值因此可以容易地得到。给定在第k次迭代时当前的解

代理对偶是

${\tilde{L}}^k=\tilde{L}\left(\right\{{\mathrm{\λ}}_i^k\},\{{\mathrm{\δ}}_{\mathrm{ij}}^k\left\}\right)=\underset{j=1}{\overset{J}{\mathrm{\Σ}}}\underset{i=1}{\overset{I}{\mathrm{\Σ}}}\left({\mathrm{\δ}}_{\mathrm{ij}}^k{T}_i^k\right)+\underset{i=1}{\overset{I}{\mathrm{\Σ}}}{\mathrm{\λ}}_i^k(1-\underset{j=1}{\overset{J}{\mathrm{\Σ}}}{\mathrm{\δ}}_{\mathrm{ij}}^k)$ (12)

$=\underset{j=1}{\overset{J}{\mathrm{\Σ}}}\underset{i=1}{\overset{I}{\mathrm{\Σ}}}({\mathrm{\δ}}_{\mathrm{ij}}^k{T}_i^k-{\mathrm{\λ}}_i^k{\mathrm{\δ}}_{\mathrm{ij}}^k)+\underset{i=1}{\overset{I}{\mathrm{\Σ}}}\left({\mathrm{\λ}}_i^k\right).$

Lagrangian乘子按照下式被更新

${\mathrm{\λ}}_i^{k+1}={\mathrm{\λ}}_i^k+s^k{\tilde{g}}_i^k,---\left(13\right)$

其中代理次梯度的分量是

${\tilde{g}}_i^k=(1-\underset{j=1}{\overset{J}{\mathrm{\Σ}}}{\mathrm{\δ}}_{\mathrm{ij}}^k),---\left(14\right)$

其中步长尺寸s^k满足

$0<s^k<(L^{*}-{\tilde{L}}^k)/\underset{i=1}{\overset{I}{\mathrm{\&Sigma;}}}{\left({\tilde{g}}_i^k\right)}^2.---\left(15\right)$

为了估计最佳对偶L^*，每五次迭代构建一个可行的{δ_ij}^k，以及评估可行的花费。在第k次迭代，接着将P^k定义为目前获得的最小的可行的花费。鉴于P^k是L^*的上限并且代理对偶是L^*的下限，最佳对偶被如下地估计，

${\hat{L}}^{*}=(P^k+{\tilde{L}}^k)/2.---\left(16\right)$

对于估计的最佳对偶花费，步长尺寸是

$s^k=\mathrm{\&rho;}({\hat{L}}^{*}-{\tilde{L}}^k)/\underset{i=1}{\overset{I}{\mathrm{\&Sigma;}}}{\left({\tilde{g}}_i^k\right)}^2,$ 其中0＜ρ＜1.                (17)

给定

通过使用本地搜索结合启发式法和DP(见表2)，而选择轿厢子问题j(j＝k模J)和执行“近似最佳化”获得这样，

满足

L_j({λ_i ^k+1}，{δ_ij ^k+1})＜L_j({λ_i ^k+1}，{δ_ij ^k}).        (18)

因此，获得对于轿厢j(j＝k模J)的

同时对于其它轿厢的保持为它们的最新的可用值。对于更新的值

和{δ_ij}^k+1，处理过程重复。

如果对偶间隙小于

或已经达到最大迭代次数，则算法停止。对于具有大的时间窗口的情形，迭代次数的上限被去除。原因在于这种情形是用于离线最佳化，以及主要关心的是解的最佳性，而不是CPU时间。

如果算法由于不可行的解而停止，则使用启发式法规则来如下地构建可行的解，

·识别具有违例指定的任何乘客，即，

$\underset{j=1}{\overset{J}{\mathrm{\&Sigma;}}}{\mathrm{\&delta;}}_{\mathrm{ij}}\&NotEqual;1$

·生成在1与J之间的随机数j’

·把这个乘客指定到轿厢j’，这样，δ_ij’＝1，和δ_ij’＝0，对于

表2

结合窗口来使用滚动水平方案。周期性地重新解决快照问题。

图6说明当预见窗口具有有限的持续时间时的情形。在图6上，显示75％重叠的非零移动窗口。窗口尺寸是T，重新调度时间间隔是0.25T，以及重新调度点是t₁和t₂。假设当前的时刻是t₂。假设给出在t₂与t₂+T之间的所有的交通信息。具有不同层的事先交通信息的情形因此可以通过适当地调节T而被建模。

(具有很少的或不具有将来的交通信息的情形)

对于通过具有小的或零时间窗口被建模的、具有很少的或不具有将来的交通信息的情形，以上的快照问题的最佳化是“近视的”，以及总的性能可能是不好的。例如，假设在大堂内有四部电梯以及具有不同的目的地楼层的四个乘客在高峰交通时大约同时到达大堂。对于这个快照问题的“最好的”判定(例如以使总的服务时间最小化)是为每个乘客分派一部电梯。然而，这导致电梯的“群聚(bunching)”，即，电梯互相靠近地移动。比起第四个乘客稍微晚一点到达的乘客必须等待，直至一部电梯返回到大堂为止，导致差的总性能。群聚对于具有足够的将来的信息的情形不太成问题。

另一个关心的问题是对于具有低的乘客到达和只有很少的或没有将来信息的双向交通情形，减小乘客等待时间。已经表明，通过把电梯预先“停靠”在多半可能需要电梯的楼层，可以改进性能。我们在以上给出的方法被扩展成以相干的方式解决这两个问题。

(用于高峰的最佳化统计方法)

为了克服对于只有很少的或没有将来信息的高峰的快照解的近视困难，考虑乘客用给定的目的地楼层分布以时变的速率到达的静态模型。根据统计分析，已经表明，对于这样的高峰交通，通过以相等的时间间隔从大堂释放电梯，可以达到良好的稳态性能，假设电梯容量足以容纳在电梯的“离开间时间(inter-departure time)”内新的到达者。这个离开间时间被计算为单个电梯的往返时间除以电梯数，往返时间取决于交通统计值。

根据以上说明，上面提出的方法通过除了在时间窗口内可得到的那些信息以外合并在线统计信息并通过采用离开间时间概念而被加强。所得到的用于高峰的最佳化统计方法是把两个“电梯释放条件”加到电梯从大堂离开的距离变动公式。具体地，对于均匀的乘客流动，电梯被保持在大堂，和在每次离开间时间τ被释放，即，

t^m+τ≤t^m+1，                    (19)

其中t^m和t^m+1是接连的电梯离开时间。对于(19)，电梯等待将来的乘客到达。在不存在稳态的假设下，离开间时间τ需要在线地计算。这是通过使用在时间窗口内可得到的到达和目的地以及除了时间窗口以外的统计信息而扩展该方法完成的，后者是根据每个楼层的最近乘客到达和他们的目的地统计地得到的。为了覆盖爆发到达，当电梯容量的某个百分数被填充时，电梯被释放，即，

$\underset{t^m\&le;t_i^p<t^{m+1}}{\mathrm{\&Sigma;}}{\mathrm{\&delta;}}_{\mathrm{ij}}>v{C}_j,---\left(20\right)$

其中v是给定的电梯容量百分数。

为了解决这个问题，使用以上给出的分解和协调方法，以及当解决在代理最佳化框架内的各个子问题时，以上的两个条件(19)和(20)被用来触发大堂处的电梯的释放。具体地，当解决特定的电梯子问题时，其它子问题以它们最近可得到的数值进行判定，并且在本地搜索过程内合并这两个释放条件。

(对于具有低的到达速率的双向的停靠策略)

为了开发对于具有很少或没有将来信息的双向交通的停靠策略，我们的思想是把建筑物划分成多个非重叠“区域”，每个区域包含一组相邻的楼层。下一个乘客到达各个区域的概率被估计，以及没有进行乘客指定的“空的”电梯停靠在多半需要它们的区域。为了避免电梯的过多的运动，在同一个区域中的楼层不进行区分。

具体地，假设电梯变为空的，使空的电梯的总数是J’，其中1≤J’≤J。根据最近到达的信息在统计上估计下一个乘客到达楼层f的概率P^f，以及下一个乘客到达区域n的概率是

在区域n处停靠的想要的电梯的数目然后被计算为

(截断的整数)。通过比较和在各个区域已停靠的电梯的数目，来识别需要空电梯的区域。新的空电梯然后停靠在这些区域的附近的一个区域。这种停靠策略被嵌入在我们的最佳化统计方法中，形成单个算法，以及当电梯变为空的时被调用。

(在紧急模式下的调度)

除了在正常操作期间良好的性能以外，分组电梯调度在由国家安全事件驱动的快速疏散时具有新的重要性。在高层建筑物中，楼梯对于紧急撤离是低效的，因为它们变为拥挤阻塞的，在从顶部楼层到地面的长度距离期间人们慢慢地下来，以及老年人和残疾人完全不能使用楼梯。H.Hakonen，“Simulation of Building Traffic and Evacuation byElevators”，Licentiate Thesis，Department of Engineering Physics andMathematics，Helsinki University of Technology，2003。使用安全电梯用于撤离的潜力在诸如检测到化学或生物试剂或在建筑物的一翼发生火灾的某些情形下已得到展示。J.Koshak，“Elevator Evacuation inEmergency Situations”，Proceedings of Workshop on Use of Elevators inFires and Other Emergencies，Atlanta，Georgia，March，2004，pp.2-4。协调的紧急撤离是关键的疏散方法，其中在每个楼层内的人员以协调的和有次序的方式撤离。作为关键的疏散方法，这里考虑协调的紧急撤离，其中在每个楼层内的居住者以协调的和有次序的方式撤离。根据预定的计划，假设在电梯与楼梯之间交通是平衡的，以使总的疏散时间最小化。电梯疏散时间T_e被定义为对于撤离被指定到电梯的所有乘客所需要的时间，即，假设包括到达时间、到达楼层和目的地楼层(即，大堂)的交通信息是在时间窗口内已知的，以及居住者遵循乘客到电梯指定判定。然后，给定电梯的位置和方向，问题是使电梯疏散时间T_e最小化，即，

其中 $J_e\&equiv;T_e^2,---\left(21\right)$

受到乘客到电梯指定约束条件和各个电梯约束条件限制。

在(21)中的目标函数在电梯方面不是相加的。所以，不能直接应用以前描述的分解和协调方法，来解决这个问题。无论如何，令T_cj是对于电梯j撤离被指定到它的所有的乘客所需要的时间，即，

通过对于所有的j要求T_cj小于或等于疏散时间T_e，目标函数可以以相加的形式被写出，加上以下的线性不等式“疏散时间约束条件”，每个电梯一个：

$T_{\mathrm{cj}}\&le;T_e,\&ForAll;j.---\left(22\right)$

对于(22)，应用最佳化-统计方法。通过放松具有非负的乘子{λ_i}的指定约束条件和具有非负的乘子{μ_j}的疏散时间约束条件获得加法的Lagrangian函数，即：

$L(\mathrm{\&lambda;},\mathrm{\&delta;})=T_e^2+\underset{i=1}{\overset{I}{\mathrm{\&Sigma;}}}{\mathrm{\&lambda;}}_i(1-\underset{j=1}{\overset{J}{\mathrm{\&Sigma;}}}{\mathrm{\&delta;}}_{\mathrm{ij}})+\underset{j=1}{\overset{J}{\mathrm{\&Sigma;}}}{\mathrm{\&mu;}}_j(T_{\mathrm{cj}}-T_e)$

$=(T_e^2-\underset{j=1}{\overset{J}{\mathrm{\&Sigma;}}}{\mathrm{\&mu;}}_j{T}_e)+\underset{j=1}{\overset{J}{\mathrm{\&Sigma;}}}({\mathrm{\&mu;}}_j{T}_{\mathrm{cj}}-\underset{i=1}{\overset{I}{\mathrm{\&Sigma;}}}\left({\mathrm{\&lambda;}}_i{\mathrm{\&delta;}}_{\mathrm{ij}}\right))+\underset{i=1}{\overset{I}{\mathrm{\&Sigma;}}}{\mathrm{\&lambda;}}_i.---\left(23\right)$

电梯子问题然后被构建和解决，以及引入对于T_e的新的“疏散时间子问题”，正如下面给出的。

通过从(23)收集与电梯j有关的所有项，获得对于电梯j的子问题为：

其中 $L_i\&equiv;{\mathrm{\&mu;}}_j{T}_{\mathrm{cj}}-\underset{i=1}{\overset{I}{\mathrm{\&Sigma;}}}\left({\mathrm{\&lambda;}}_i{\mathrm{\&delta;}}_{\mathrm{ij}}\right),---\left(24\right)$

受到各个电梯约束条件限制。这个子问题可以通过使用如前所述的基于次序最佳化的本地搜索来解决，其中搜索树的节点首先通过使用“三趟(three passage)启发式法”被粗略地评估和排名。最高排名节点然后通过使用DP被精确地最佳化，其中T_cj由以下的分阶段花费表示：

g_k(x_k，u_k)＝t_k+1-t_k.            (25)

通过从(23)收集与T_e有关的所有项来获得附加的疏散时间子问题：

$\underset{\{T_e\&GreaterEqual;0\}}{\min }{L}_{J+1},$ 其中 $L_{J+1}\&equiv;T_e^2-\underset{j=1}{\overset{J}{\mathrm{\&Sigma;}}}{\mathrm{\&mu;}}_j{T}_e.---\left(26\right)$

鉴于它的具有非正的线性系数的二次项，这个子问题可以容易地解决。在第n次迭代时被使用来更新{μ_k}的代理次梯度的分量是

${\tilde{g}}_j^n=T_{\mathrm{cj}}^n-T_e^n.---\left(27\right)$

乘子更新迭代遵循以前对于接近最佳解描述的内容。

本发明提供建模和改进使用事先的交通信息的成组电梯控制的一致方式。在窗口内的交通信息是已知的以及窗口外部的信息被忽略的情况下，首先引入预见窗口，以建模事先的交通信息。具有不同层的事先的交通信息的情形可以通过适当地调节窗口尺寸而被建模。成组电梯调度的关键特性被使用来建立创新的双层公式，在较高层进行乘客到轿厢指定，以及在较低层进行各个轿厢的分派。这个公式可应用于不同的建筑物结构和交通图案，因为对于它们没有作出具体的假设。单个轿厢动力学的细节被嵌入在各个轿厢模拟模型内。公式因此是可灵活地合并不同的策略，用于单个轿厢分派，包括基于模拟的动态编程方法。

为了根据事先的交通信息实现接近最佳乘客到轿厢指定和用于该指定的接近最佳的各个轿厢路线，通过放松耦合乘客轿厢指定约束条件使用分解和协调方法。轿厢子问题独立地被解决。在本地搜索时，首先通过使用启发式法快速评估和排名乘客选择。通过这个排名信息，接着通过用改进单个轿厢路线的阶段、状态、判定、和花费的新颖定义进行动态编程来对于精确的性能评估最好选择。然后通过使用接近最佳解的代理最佳化通过Lagrange乘子的迭代更新来协调各个轿厢。

虽然本发明是参照例子和优选实施例描述的，本领域技术人员将会看到，可以在形式和细节上作出改变而不背离本发明的精神和范围。

Claims (21)

1.一种用于调度电梯组的方法，该方法包括：

对与在预见窗口内的乘客到达时间、到达楼层和离开楼层有关的事先信息进行建模，以便创建快照问题；以及

通过根据在快照问题中所有乘客的总服务时间使目标函数最小化来解决快照问题，以确定乘客到轿厢指定和轿厢分派。

2.权利要求1的方法，其中解决快照问题包括：

为每个电梯轿厢选择可选的乘客到轿厢指定；以及

通过使用轿厢模拟模型根据所选择的乘客到轿厢指定来确定各个轿厢的最佳分派。

3.权利要求1的方法，其中目标函数包括所有乘客的等待时间和传送时间的加权和。

4.权利要求2的方法，其中所有乘客I的加权和是

以及对于乘客i，T_i＝αT_i ^w+βT_i，其中α和β是加权因子，T_i ^w是等待时间，以及T_i ^T是传送时间。

5.权利要求1的方法，其中使目标函数最小化包括：

把目标函数变换成一种易于分解快照问题的形式；

把Lagrangian松弛法施加到变换的目标函数和耦合的乘客到轿厢指定约束条件，以形成Lagrangian对偶函数；以及

在代理最佳化框架内求解Lagrangian对偶函数。

6.权利要求5的方法，其中求解Lagrangian对偶函数包括重复进行以下步骤，直至满足停止准则为止：

通过放松乘客到轿厢指定约束条件，获得各个轿厢子问题；

通过使用本地搜索方法来独立地求解子问题；

通过使用代理最佳化来迭代更新乘子，从而协调各个轿厢；以及

如果在停止乘子更新迭代时违反了乘客到轿厢指定约束条件，则通过使用接近最佳解的启发式法来构建可行的指定。

7.权利要求6的方法，其中本地搜索方法包括：

通过使用启发式法来评估和排名乘客选择；以及

根据排名，通过使用动态编程来评估对于精确性能的最高选择。

8.权利要求7的方法，其中在代理最佳化期间，优于以前的选择的选择被用来设置乘子更新方向。

9.权利要求6的方法，其中通过使用接近最佳解的代理最佳化，来迭代地更新乘子。

10.权利要求9的方法，其中在初始迭代时所有的乘子被设置为零，以及通过选择没有乘客，来使所有的子问题最小化。

11.一种用于调度电梯组的方法，该方法包括：

接收与乘客到达时间、到达楼层和离开楼层有关的事先信息；

根据在预见窗口内所有的未指定的乘客的总服务时间来形成目标函数；

把目标函数变换成易于分解快照问题的加法形式；

把Lagrangian松弛法施加到变换的目标函数；

迭代求解单个轿厢的子问题并更新Lagrangian乘子；以及

为每个轿厢选择乘客-轿厢指定和轿厢分派。

12.权利要求10的方法，其中目标函数包括所有乘客的等待时间和传送时间的加权和。

13.权利要求12的方法，其中所有乘客I的加权和是

以及对于乘客i，T_i＝αT_i ^w+βT_i，其中α和β是加权因子，T_i ^w是等待时间，以及T_i ^T是传送时间。

14.一种用于控制电梯组的运行的方法，该方法包括：

接收与乘客到达时间、到达楼层和离开楼层有关的事先信息；

根据该事先信息、包括轿厢容量约束条件与轿厢动力学信息的各个轿厢模拟模型、以及作为性能度量的加权和的目标函数，来实时选择乘客到轿厢的指定和轿厢的分派；以及

根据所述选择来分派轿厢。

15.权利要求14的方法，其中对于每个轿厢，最佳化包括：

作出乘客指定的最佳选择；以及

对于每个乘客指定，确定轿厢性能。

16.权利要求14的方法，其中目标函数包括所有乘客的等待时间和传送时间的加权和。

17.权利要求16的方法，其中所有乘客I的加权和是

以及对于乘客i，T_i＝αT_i ^w+βT_i，其中α和β是加权因子，T_i ^w是等待时间，以及T_i ^T是传送时间。

18.一种控制电梯组的运行的方法，该方法包括：

接收事先的交通信息；

将事先的交通信息建模成电梯组的当前状态，以创建快照问题，其中快照问题包括需要每个乘客被指定到单个轿厢的乘客指定约束条件；以及

通过以下步骤求解快照问题，使目标函数最佳化：

放松乘客指定约束条件，以把快照问题变换成放松的问题；

把放松的问题分解为独立的轿厢子问题；以及

求解所有的独立的轿厢子问题，以生成乘客指定。

19.权利要求18的方法，还包括：

用统计信息补充事先的交通信息；以及

根据与电梯的离开间时间和电梯容量的填充百分比有关的电梯释放约束条件，来释放电梯。

20.权利要求18的方法，还包括：

把建筑物楼层划分成区域；

识别其中很可能需要电梯的区域；以及

把电梯停靠在识别的区域。

21.权利要求18的方法，还包括：

把疏散时间子问题包括在目标函数内。

Images