使用分支定界来调度电梯轿厢的方法

摘要

本发明提供了一种使用分支定界来调度电梯轿厢的方法。提供了一种对电梯系统的轿厢进行调度的方法。通过被保持为搜索树中的节点的解矢量来表示层站呼叫集合对轿厢集合的各个可能的分配。利用根据直接策略的ESA－DP处理对各个解矢量进行评价，以确定初始最优解。利用所述初始最优解和所述搜索树对各个解矢量应用分支定界处理，以确定根据再分配策略来调度所述轿厢的全局最优解。

说明书

技术领域

本发明总体上涉及对电梯轿厢进行调度，更具体地说，涉及根据再分配策略进行工作的调度方法。

背景技术

对电梯轿厢进行调度是针对建筑中的电梯组(bank)的实际优化问题。目的是将到来的乘客分配到轿厢以使一个或更多个性能标准最优化，所述性能标准例如有等待时间、总运送时间、等待了长于特定阈值的人的百分比、或者服务的公平性。

由于可能方案(解空间)的数量非常大、由新到来乘客的目的地楼层不明以及未来乘客的到来时间不明而引起的不确定性，电梯轿厢的调度成为困难的组合优化问题。

被最普遍接受的优化标准是到来乘客的平均等待时间(AWT)，G.C.Barney，“Elevator Traffic Handbook”，Spon Press，London，2003；G.R.Strakosch，“Vertical transportation：elevators and escalators”，John Wiley&Sons，Inc.，New York，NY，1998；以及G.Bao，C.G.Cassandras，T.E.Djaferis，A.D.Gandhi和D.P.Looze，“Elevator dispatchers for downpeaktraffic”，Technical report，University of Massachusetts，Department ofElectrical and Determiner Engineering，Amherst，Massachusetts，1994。

另一重要考虑是调度器进行工作所遵守的社会礼节。在某些国家(例如日本)，在到来乘客进行层站呼叫(hall call)时进行各个分配，直到该乘客得到服务才能改变分配。这被称为直接策略。在其他国家(例如美国)，系统会将层站呼叫重新分配给不同的轿厢，如果这会改进调度的话。这被称为再分配策略。当再分配策略增加了调度的计算复杂性时，可以利用附加的自由度来实现对AWT的主要改进。

在实践中，假设乘客的不满作为AWT的函数超线性地增长。当将目标函数最小化时，人们对长时间等待的抱怨要比短时间等待强烈得多，这有助于减少大量的长时间等待，参见M.Brand和D.Nikovski，“Risk-averse group elevator scheduling”，Technical report，MitsubishiElectric Research Laboratories，Cambridge，Massachusetts，2004；以及由Brand等人于2002年6月3日提交的第10/161,304号美国专利申请(＝第2003/0221915号美国专利申请公报)“Method and System for DynamicProgramming of Elevators for Optimal Group Elevator Control”，通过引用将它们都合并于此。

另一方法确定现有乘客和未来乘客的AWT，Nikovski等人，“Decision-theoretic group elevator scheduling”，13^th InternationalConference on Automated Planning and Scheduling，June 2003；以及由Nikovski等人于2003年6月24日提交的第10/602,849号美国专利申请(＝第2004/0262089号美国专利申请公报)“Method and System forScheduling Cars in Elevator Systems Considering Existing and FuturePassengers”，通过引用将它们都合并于此。该方法被称为“通过动态编程清空系统算法(Empty the System Algorithm by Dynamic Programming)”(ESA-DP)方法。

ESA-DP方法确定等待时间的基本精确的估计。该方法考虑了由还未得到服务的乘客或者还未指出其目的地楼层的乘客的目的地楼层不明而引起的不确定性。该方法用离散状态Markov链来表示该系统，并利用动态编程来确定对该系统的所有可能的未来状态进行平均而得到的AWT。尽管状态空间大，但是该方法的性能对于建筑楼层数和井(shaft)数是线性的，并且对于到来乘客的数量是二次的。

ESA-DP方法的运行时间对于现代微控制器是完全可能的，并且当与其他调度方法相比时，ESA-DP方法的解的质量导致明显改进。然而，该方法没有利用根据再分配策略进行工作的电梯系统的附加潜力。

发明内容

本发明提供了一种调度电梯系统的轿厢的方法。由保持为搜索树中的节点的解矢量来表示层站呼叫集合对轿厢集合的各个可能的分配。利用根据直接策略的ESA-DP处理对各个解矢量评价，来最初确定最优解。利用所述初始最优解和所述搜索树对各个解矢量应用分支定界(branch-and-bound)处理，来确定根据再分配策略对轿厢进行调度的全局最优解。

附图说明

图1是根据本发明实施例的分支定界处理所使用的搜索树的图；

图2是根据本发明实施例的对电梯轿厢进行调度的系统和方法的框图；

图3示出了根据本发明实施例的方法的伪代码；以及

图4示出了枚举层站呼叫的所有可能子集的伪代码。

具体实施方式

本发明的实施例提供了一种对根据再分配策略进行工作的电梯系统中的电梯轿厢进行调度的方法。

可以用未分配的层站呼叫的集合H来表示电梯调度问题，其中集合H中的各个层站呼叫h是定义到达楼层f和期望方向d(向上或向下)的元组(f，d)。层站集合要分配给电梯系统的轿厢集合。

根据轿厢c的当前位置、速度、方向、搭乘乘客的数量以及层站呼叫集合(其约束轿厢的运动)来确定轿厢c的状态。因此，对于一具体轿厢c，用＜_c来表示层站呼叫的固有顺序(轿厢c可按该顺序对乘客进行服务)，即，当且仅当在呼叫h_i在呼叫h_j之前被轿厢c服务时，h_i＜_ch_j。

通常，存在轿厢可服务于n个未分配层站呼叫的n！个不同的顺序。公知的是，即使对于单个轿厢，对应的调度问题的难度也为NP。然而，我们遵循广泛使用的假设：轿厢总是沿其当前方向保持移动，直到请求该方向上的服务的所有乘客都得到服务为止。在轿厢变空之后，它可以调转方向。

对于各个层站呼叫h，用W_c(h)来表示轿厢c为了服务于层站呼叫h而花费的等待时间。该时间取决于轿厢c的当前状态、以及电梯系统的具体运动(例如，加速度、最大速度、门的开关时间、以及启动延迟)。假设调度器已知所有这些参数从而能够充分精确地预测行进时间。

此外，乘客的等待时间严重依赖于分配给同一轿厢的其他层站呼叫。调度器还必须考虑这些层站呼叫。由于新到来乘客的目的地楼层不明而引起的不确定性，无法对等待时间进行精确预测。因此，用等待时间的统计期望来代替延迟。

对于层站呼叫H的任何子集R，RH，如果子集R中的层站呼叫也被分配给轿厢c，则用W_c(h|R)来表示层站呼叫h对轿厢c的预期等待时间。因为另外的层站呼叫只会使轿厢变慢，所以W_c(h|R)≥W_c(h|)为真，并且如果h＜_cg，其中g是已分配层站呼叫，则W_c(h|R∪{g})＝W_c(h|R)，这是因为如果层站呼叫g在层站呼叫h之后被轿厢c服务，则层站呼叫g不会使层站呼叫h的乘客变慢。

利用通过引用而合并于此的ESA-DP方法，可以有效地确定W_c(h|R)。然而，如果单独给出W_c(h|R₁)和W_c(h|R₂)的个别期望，则不能容易地确定W_c(h|R₁∪R₂)。

将层站呼叫的集合H分配给m个轿厢就是将层站呼叫的集合H划分成m个不同子集{H₁，H₂，...，H_m}，使得对于i≠j以及 $>sup>>\cup >>i>=>1>>m>>>H>i>>=>H>,>>>H$_i∩H_j＝。对于给定的轿厢分配，将分配给层站呼叫h的轿厢表示为c(h)。

在一具体确定步骤中将AWT最小化等价于将当前正被服务的所有乘客的剩余等待时间之和最小化。因此，可将给定分配集合{H₁，H₂，...，H_m}的目标函数F定义为

$>>F>>(>\{>>H>1>>,>>H>2>>,>.>.>.>,>>H>m>>\}>)>>:>=>>\Sigma >>c>=>1>>m>>>\Sigma >>h>\in >H>>>>W>c>>>(>h>|>>H>i>>)>>->->->>(>1>)>>>>$

期望将该目标函数最小化以找到该调度问题的最优解。

分支定界

分支定界(B&B)是一种利用搜索树来系统地解决困难优化问题的处理。在贪婪搜索法和动态编程无效时，B&B是有用的。B&B类似于宽度优先搜索。然而，不是搜索树的所有节点都扩展为子节点。而是用预定标准来确定扩展哪个节点以及何时找到最优解。丢弃比当前最优解差的部分解，参见A.H.Land和A.G.Doig的“An Automatic Method forSolving Discrete Programming Problems”，Econometrica，vol.28，pp.497-520，1960，通过引用将其合并于此。

使用B&B处理来解决电梯调度的大规模组合优化问题。虽然解的数量的指数级增长通常使得无法进行显式枚举，但是B&B处理对部分问题空间进行搜索的能力常常隐式地导致大小实际的问题的精确解。

B&B处理保持问题空间的尚未探索子集的池以及到当前为止所获得的最优解。通常将问题空间的未探索子集表示为动态生成的搜索树的节点。最初，B&B处理使用具有表示所有可能分配的单个根节点的搜索树以及初始最优解。每次迭代都处理搜索树的一个具体节点，并且可以分为三个主要部分：选择要处理的下一节点、定界、以及分支。

B&B处理是一通用范例(paradigm)，对于这些步骤中的每一个都存在各种可能性，并且对于它们的顺序也存在各种可能性。例如，如果节点选择基于子问题的定界，则分支是选择要处理的下一节点之后的第一个操作，即，“急切策略(eager strategy)”。作为另一选择，可以在选择节点之后确定界限并且如果必要的话随后进行分支，即，“懒惰策略(lazystrategy)”。

根据优化问题的类型，定界的任务是要针对整个子集确定目标函数值的下界。如果所考虑的子集不包括优于当前最优解的解成立，则丢弃整个子集。

分支通常通过将当前解的一个或更多个分量分配给特定值，从而将当前搜索空间分成多个非空子集。用搜索树中的节点来表示各个新创建的子集，并将新创建的子集添加到未解子集的池。当该池由单个解组成时，将该单个解与最优解进行比较。保留这两个解中较好的一个，并丢弃另一个。当不再有未解的子问题剩余时，分支定界终止。此时，找到的最优解保证为全局最优解。

图1和2示出了根据本发明实施例而保持的示例B&B搜索树100。该树具有表示所有可能分配的顶层根节点101、一个或更多个具有表示部分分配的子节点103的中间父节点102、以及表示完全分配的底层叶子节点104。要注意，最初，顶层节点既是根节点也是叶子节点。按自顶向下的顺序处理这些节点。在任意叶子处，对节点进行评价以确定当前解。如果针对子树中的任意轿厢分配，当前解无法改进最优解，则丢弃该节点和其下的整个子树；否则，通过生成子节点来扩展该节点，从而树进一步向下延伸(descending)。

用矢量(c₁，c₂，...，c_n)110来表示n个层站呼叫h的集合H对轿厢c_i的各个可能的分配，即，将可能的分配划分为m个不同子集。将可能的解矢量保持为B&B树100。对于已分配层站呼叫，向轿厢c_i分配1≤c_i≤m范围内的值，并且对于未分配层站呼叫，向轿厢c_i分配-1。每一个完全解矢量对应于一个有效分配，即，对于所有1≤i≤n，轿厢c_i＞-1。因此，解空间的大小是指数的；更精确地说，其大小为mⁿ。

如图2所概略示出的，并且利用图3中的对应伪代码，针对我们的调度方法，将ESA-DP 210处理与B&B处理220相结合，以根据再分配策略将n个层站呼叫的集合211分配给m个轿厢的集合212。在每一次迭代中选择第一个未分配层站呼叫，确定其目标函数值的界限，并且如果必要的话进行分支。通过将呼叫分配给轿厢之一，来将剩余的搜索空间划分成m个大小相等的子问题，从而生成m个子节点102。

首先通过将乘客对各个轿厢的等待时间进行累加，使用根据直接策略的ESA-DP处理对解矢量201进行评估，从而确定(210)解矢量的初始最优解s₁ 202。

使用栈S来保持未解子问题的集合。最初，在根节点101处将空分配x＝{-1}n压入(301)栈S。使用根据直接分配策略的ESA-DP方法来确定(210)部分解201的最优解202。

每当遇到(302)叶子节点104(即，每一个层站呼叫被分配给具体轿厢)时，确定对于该分配的平均等待时间的期望。仅在当前分配的解更优时，才用当前分配代替(303)所找到的最优解。

通过确定(304)下界b，来对部分分配进行评价。将该下界与最优解进行比较(305)。如果下界b大于目标函数F到当前为止的最优解，则停止对该节点的进一步处理，以有效地丢弃从栈中弹出的叶子节点。

否则，通过将第一个未分配层站呼叫分配给可用轿厢之一并将所述分配压入(307)栈中，来生成(306)m个子节点。因为要处理的下一节点总是在栈S的顶部，所以该方法对应于深度优先的懒惰B&B策略。

在实践中，根据到发起层站呼叫的楼层的距离按照从头至尾的顺序将对层站呼叫的轿厢分配进行排序，并按相反顺序将这些分配压入栈，从而先处理位于栈顶部的更有希望的轿厢分配。

B&B处理的成功主要由如下两个因素实现：(a)在优化处理中可以较早得到良好的解；和(b)确定各个分支节点的紧密(tight)界限的手段。将紧密界限定义为充分接近被优化的(即，在该应用中被最小化的)变量的最优值的下界。

通过使用用于直接策略的ESA-DP方法以及对最有希望的分配的深度优先评价，来实现(a)。

对紧密界限的确定是非平凡的(nontrivial)。确定部分解的下界b的一种方式是忽略未分配层站呼叫并应用ESA-DP处理。然而，该方法没有考虑两个重要问题。各个层站呼叫不可避免地被分配给轿厢之一，必须考虑由于该分配而导致的其他乘客的等待时间的增加。各个层站呼叫可能将延迟引入到稍后服务的层站呼叫，在其等待时间的统计期望中必须考虑这一点。

可以总是通过min_cW_c(h|)(即，假设对同一轿厢没有分配其他层站呼叫，任意轿厢到达具体楼层所需的最少时间)而使任意未分配层站呼叫h处于不利地位。然而，该界限不允许在没有显式枚举的情况下就丢弃大部分搜索树。这是基于W_c(h|H_c)≥W_c(h|)这一事实，其为更一般性的不等式W_c(h|Q∪R)≥W_c(h|R)的特殊情况，其中集合Q包含未分配层站呼叫，并且是空集。

用H_c来表示对轿厢c的已知分配的集合。可以将以上方法归纳为W_c(h|H_c)≥max_RW_c(h|R)，而R包括层站呼叫的整个集合H_c。在实践中，考虑所有子集是不可行的。相反，仅对|R|≤p的子集R预先确定W_c(h|R)。这里，p是一小整数，例如1、2或3，因为基数为p的所有可能子集的数量随着p指数级地增长。现在可以通过下式确定由部分分配 $>>H>=sup>>\cup >>i>=>1>>m>>>H>i>>>>导致的对呼叫h(hH)的惩罚P(h)，$

$>>P>>(>h>)>>:>=>>>min>c>>>max>>R>\subseteq >>H>c>>,>|>R>|>\le >p>>>>W>c>>>(>h>|>R>)>>->->->>(>2>)>>>>>$

层站呼叫的集合H∪Q的下界是F(H)+∑_h∈QP(h)，其中，H为已知分配，并且集合Q中的元素为未知分配。因为按特定顺序(h₁，h₂，...，h_n)，h_i∈H来处理层站呼叫，所以通过忽略在h_i之后处理的h_j(即，j≥i)，可以进一步加速用于确定W_c(h_i|R)的预处理过程。每当对h_i的界限感兴趣时，那些层站呼叫还未分配给具体轿厢并且无法用于确定P(h_i)。因此，ESA-DP 210针对单个层站呼叫h_i的所需调用的次数可以从显著减少到

如果h_i＜_ch_j，则将层站呼叫h_j分配给轿厢之一不影响层站呼叫h_i。对于单个轿厢c，最好严格按照由＜_c所给出的顺序来处理层站呼叫，因为各个层站呼叫对在优化处理中稍后处理的呼叫引入了延迟，并且可成功地提高界限。然而，通常，该顺序对于不同的轿厢是不同的，并且在下述实施例中是启发式地确定的。

因此，可以使用其下界∑_h∈QP(h)来代替F(H)的确定。这既减少了确定界限所需的时间，也减小了下界的紧密性。结果，搜索空间被更低效并且增量更小地裁剪。

如果忽略未来的乘客，则两个版本的B&B处理都会以这样的分配终止，该分配在所有可能的分配的集合之中具有最小期望AWT。然而，该方法的复杂性是显著的，并且对于中等大小的建筑会变得不可行。此外，该方法根据电梯系统中的传感器所提供的现实世界的“快照”进行工作，随着时间流逝或者系统变化(例如新乘客到来或者轿厢在它们以前可以停靠的具体楼层不再能够停靠)，解的值减小。

将描述可以用来代替对AWT直接最小化的不同的代理标准(proxycriteria)。该代理标准通过对界限的增量计算，使得能够进行更高效的B&B过程。

不是考虑对各个层站呼叫的所有约束，而是通过限制对分配给同一轿厢的p个最差层站呼叫的延迟，来有意忽略某些约束。在某种意义上，这是对用于确定W_c(h|)的传统最近轿厢启发的扩展。

用下式来代替对给定分配H＝H_i的等待时间的估计，

$>>>\Sigma >>c>=>1>>m>>>\Sigma >>h>\in >>H>c>>>>max>>max>>R>\subseteq >>H>c>>|>R>|>\le >p>>>>W>c>>>(>h>|>R>)>>,>>>$

即，在确定等待时间时不是考虑所有层站呼叫，而是使用有界基数的子集R。通常，该过程会低估等待时间，通过增大p，可以期望获得更好的结果。然而，该式的关键特征是可以在B&B搜索树向下延伸的同时增量地确定等待时间。这意味着针对搜索树中的较高节点而确定的等待时间可以用来确定较低节点的等待时间。

如图4中的伪代码所示，按如下方式枚举(400)基数为p的层站呼叫的所有可能的子集R：可将这些子集分为子集S_i(i＝1，...，n)，以使S_i仅包含由层站呼叫h_i组成的子集R和已在h_i之前处理过的层站呼叫的子集R’，即，|R’|＜p。从空集S₀开始(401)，依次处理各个层站呼叫(402)。对于各个层站呼叫，首先形成(403)在先前的迭代期间产生的所有集合S_j(j＝1至i-1)的并集T。然后，对T中的基数严格小于p的所有那些子集R’进行迭代(404)，将新的层站呼叫h_i加入(405)R’。

此外，对于B&B搜索树中的每个节点，保持有一矩阵A。假定该节点的固定分配最初为W_c(h|)，则该矩阵的元素A_c，h包含基数高至p的任何子集R针对分配给轿厢c的层站呼叫h所引起的最大延迟。

每当通过将层站呼叫h_i分配给轿厢之一而将新节点插入B&B搜索树中时，确保了矩阵A_c，g针对c≠c(h_i)保持不变。通过针对所有已分配层站呼叫g确定

$>>max>>(>>A>>c>>(>h>)>>,>g>>>,>>max>>R>\in >>S>i>>>>>W>>c>>(>h>)>>>>>(>g>|>R>)>>)>>>>$

可以更新矩阵的行c(h_i)。在A_c(g)，g中可以得到具有已知分配的各个层站呼叫g的界限，并且可以通过min_cA_c，h来确定未分配层站呼叫h的界限。虽然该方法也适用于上述定界过程，但是现在还可以通过∑_h∈HA_c(h)，h来确定目标函数在叶子节点处的值，并且在B&B处理期间可以省略对ESA-DP过程的调用。

然而，该预处理过程的计算复杂性随着p指数级地增长，对于小的p，会明显低估剩余等待时间。

成对(pairwise)延迟最小化

在本发明的另一实施例中，直接将分配给同一轿厢的层站呼叫之间的成对延迟之和最小化。用ΔW_c(h|g)(即，ΔW_c(h|g)＝W_c(h|g)-W_c(h|))来表示在层站呼叫h的基础上分配层站呼叫g所引入的延迟。现在得到目标函数

在该目标函数中，指示层站呼叫h的乘客在被分配给轿厢c的情况下将经历的真正等待W_c(h|H_c)由于H_c中的所有其他乘客也被分配给同一轿厢而被总和代替，该和由这些乘客中的每一个将对h而引起的个体成对延迟构成。

然而，该替换并不总是准确的，并且由于许多原因并不对应于等待时间的准确估计。当在分配给轿厢的两个连续层站呼叫之间该轿厢达到其最大速度时，该替换总是准确的。在这种情况下，个体层站呼叫独立起作用，并且其联合延迟等于其个体延迟之和。

然而，更典型的是，在两个连续呼叫之间(例如，当这些呼叫发起于两个相邻楼层时)，轿厢无法达到其最大速度。在这种情况下，根据层站呼叫之间的位置和交互作用，G({H₁，H₂，...，H_m})要么是F({H₁，H₂，...，H_m})的高估要么是F({H₁，H₂，...，H_m})的低估，并且无法用作分支定界处理中所使用的严格下界。然而，在本发明的该实施例中，将G({H₁，H₂，...，H_m})直接用作进行最小化的目标函数，下面描述如何有效地确定该目标函数的紧密下界。

此外，加速分支定界处理算法的实际运行时间。通过利用如下事实可以有效地预先确定值W_c(h|g)：ΔW_c(h|g)和ΔW_c(g|h)中仅有一个是非零的。还可以在B&B处理期间增量地确定该目标函数并利用中间结果作为目标函数的紧密下界。除了预处理过程之外，在B&B评价期间不需要对ESA-DP处理进行另外的调用。

为了确定目标函数(式(3))，针对搜索树的每个节点都保持一个矩阵W，该搜索树的根节点101用W_c(h|)进行了初始化。在优化处理的各个实例中，W_c，h包含W_c(h|)与到当前为止分配给轿厢c的所有层站呼叫的个体延迟之和。

因此，可以根据各个节点的父节点来传递(propagate)该节点的矩阵W，并且当将层站呼叫h分配给轿厢c(h)时，可以通过将ΔW_c(h)(h|g)添加到各个元素W_c(h)，g来更新所传递的行W_c(h)。实质上，利用该步骤，当将层站呼叫h分配给轿厢c时，已考虑了该层站呼叫将会对先前分配给同一轿厢的所有层站呼叫引起的延迟。

设H＝P∪Q、P∩Q＝为任意部分分配，其中P是固定轿厢，Q中的元素是未知分配。可以定义

并且通过∑_h∈Hw(h)来确定中间节点的下界以及目标函数在叶子节点处的值。

虽然已通过优选实施例的示例描述了本发明，但是应该理解，在本发明的精神和范围内可以进行各种其他改编和变型。因此，所附权利要求书的目的是要覆盖落入本发明的真正精神和范围内的所有这种改变和变型。

本发明与题目为“System and Method for Scheduling Elevator CarsUsing Pairwise Delay Minimization”的第11/390,508号美国专利申请相关，Nikovski等人于2006年3月27日同时提交了该申请与本申请。