HK1053001B - 用於通過遺傳算法分配乘客的方法和裝置 - Google Patents

Description

用于通过遗传算法分配乘客的方法和装置

技术领域

本发明涉及分配电梯乘客的方法和装置，该方法定义于权利要求1的前序，该装置定义于权利要求8。

背景技术

当乘客希望乘坐电梯时，他/她通过按压安装在该层上的乘坐呼叫键呼叫电梯。电梯群的控制系统接收对于电梯的呼叫，并且试图计算出该电梯群中的哪一个电梯最有可能响应该呼叫。这种行为称为分配(allocation)。通过分配要解决的问题是如何找到一电梯，该电梯将给定的花费因子(castfactor)减至最小。分配的目的是将乘客的等待时间、乘客的乘坐时间、电梯的停止次数或不同方式的多个花费因子的加权组合减至最小。

为了决定电梯中的哪一个适于响应呼叫，传统上通过采用复杂的条件结构对于每一种情况分别进行推理。该推理的最终目的是将描述电梯群的操作的花费因子减至最小，典型的花费因子例如呼叫时间或乘客的平均等待时间。因为电梯群在复杂的状态空间中工作，条件结构也复杂并且有带有间隙的倾向，所以可能不是以最优的方式工作。同样地，将电梯群作为整体考虑是困难的。上述的典型的例子是传统的集中控制(collective control)，其中乘坐呼叫由这样的电梯中的一个响应，该电梯按照与呼叫楼层最近距离的方向，向该呼叫运行。然而，该简单的最优原则导致电梯拥塞，即多个电梯以同一方向向前运行，因此导致电梯群的整体性能下降。

发明内容

本发明的目的是提供一种新方法和装置，该方法和装置用于通过遗传算法(genetic algorithm)分配乘客。本发明的方法的特征如权利要求1的特征部分所述。本发明的装置的特征如权利要求8的特征部分所述。

本发明的方案是关于对于乘客的分配，而非对于乘坐呼叫的分配。因为在乘客分配中每个乘客指出他/她的目的楼层，并且因为基于呼叫输入装置的位置出发楼层是已知的，所以乘客关于系统的意图是确切地已知的。采用该良好的基础数据，电梯群的控制系统可试图发现对于乘客有利的电梯，即，为乘客分配电梯。在传统的分配上/下呼叫中，获得的关于乘客的数据是不完善的，因此，面向呼叫分配而非面向乘客分配，即，系统试图发现对于呼叫有利的电梯。

基于遗传算法进行决策。首先，创建一组可选择的方案，即染色体(chromosome)，并且将该染色体的质量确定为分配决策。其次，通过遗传算法筛选该可选择的方案组，该方法包括为下一代选择代表性的可选择方案和，就父(parent)对子(decendant)而言，子的一代，即，通过将最佳的可选择方案与每个其他的方案杂交和/或通过应用突变，得到新的可选择解决方案，即子的基因的改变。对于每个子，确定质量因子是必要的，根据该质量因子可生成下一代的可选择方案，或者，假如满足结束条件，则将在方案组中的最佳可选择方案作为问题的解决方案输出。遗传乘客分配与上述的较早的遗传方法的不同之处在于：分配明确地与乘客相关，而非传统的上/下呼叫，即，判定哪一个电梯厢体将为每一个乘客提供服务，然而在较早的方法中分配决定确定哪一个电梯厢体为每个乘坐呼叫提供服务。上述的可能性是由于当在出发楼层时，每个乘客通过信号装置给出他的/她的目的楼层，以便在电梯系统中，对于每个单独的乘客的数据是已知的。电梯系统也必须通知每个乘客关于将为他/她提供服务的电梯。一旦乘客获得该信息，为他/她建议使用的电梯一般不应该频繁地改变。

本发明的方案的优点之一是：由乘客分配所提供的精确信息和提供的方法有可能改善提供给乘客的服务的水平。该系统也可以产生客运量统计，该客运量统计在其它的因素中包括：在大楼中的乘客信息和乘客行动，并且可以产生描述乘客服务的参数，例如：在正常工作期间的乘客等待时间。

附图说明

下面，参照附图，通过使用本发明的实施例之一，将具体地说明本发明，其中：

图1显示了系统的结构，示出了包括于该系统中的装置。

图2示出了乘客分配操作，和

图3提供一个范例，该范例表示对于乘客进行编码以改变染色体。

具体实施方式

图1显示了系统的结构。当乘客想呼叫电梯时，他/她通过按压安装在他/她的出发楼层的乘坐呼叫输入装置，表达期望的目的楼层。该呼叫输入装置告诉乘客哪一个电梯将为他/她提供服务。下面，将逐步地说明该系统的操作。当通过呼叫输入装置12乘客表示他/她的目的楼层时，呼叫输入装置从该表示产生“新乘客”消息，将该消息发送至电梯群的控制系统。该消息包括下列数据：

设备标识+出发楼层+进入侧+目的楼层+离开侧

在乘客记录单元16中处理该信息，该乘客记录单元保存乘客的记录和乘客数据。该记录单元将明确的乘客标识符、时间和电梯数据包括在到达信息，并且存储这些数据(黑体字)：

乘客标识+出发楼层+进入侧+目的楼层+离开侧+乘客到达出发楼层的时间+乘客进入厢体的时间+乘客到达目的楼层的时间+电梯+厢体+电梯厢体到达出发楼层的估计时间

在这一阶段，以正常字体给出的字段还没有被定义。在保存了该数据之后，乘客记录单元16通过发送“进行分配”的消息，开始乘客分配程序。乘客分配单元18要求乘客记录单元16将系统中的所有乘客和乘客数据一同给出。然后，该乘客分配单元18开始为还没有被分配的乘客搜索以发现电梯厢体。还没有被分配的乘客是还没有被指派电梯厢体的乘客。一旦乘客分配单元决定哪一个电梯厢体将为每个没有被分配的乘客提供服务，该乘客分配单元将发送对于该乘客的“已分配乘客”的消息给乘客记录单元16。该消息包括用于指示该电梯厢体为该乘客提供服务的信息：

乘客标识符+电梯+厢体+电梯厢体到达出发楼层的估计时间

乘客记录单元16更新关于电梯厢体的数据，保留该电梯厢体以为乘客提供服务在考虑之中。这样，在目前阶段，以黑体给出的下面的关于乘客的事实是已知的：

乘客标识符+出发楼层+进入侧+目的楼层+离开侧+乘客到达出发楼层的时间+乘客进入厢体的时间+乘客到达目的楼层的时间+电梯+厢体+电梯厢体到达出发楼层的估计时间

乘客记录单元16向呼叫输入设备12发送“你的运送”消息，该消息通过显示装置14告知乘客将为他/她提供服务的电梯厢体和该电梯到达的可能时间：

设备标识+乘客标识符+出发楼层+进入侧+目的楼层+离开侧+电梯+厢体+电梯厢体到达出发楼层的估计时间

表示哪一个电梯厢体将为该乘客提供服务的数据也被发送到电梯19，该电梯19包括考虑中的厢体。

电梯19保持其自己的关于乘客的记录。该电梯有两个乘客的列表。该列表中的一个包括将进入厢体的乘客，另一个表包括目前在厢体中的乘客。首先将一个新的被分配的乘客加入等待进入厢体的乘客的列表中。同时，将该乘客的出发楼层登记为沿该电梯的路线的停止楼层。当该电梯停在一个楼层时，该电梯检查它的两个乘客列表。假如(a)电梯体停靠的楼层与乘客的出发楼层相同，并且(b)该电梯能够继续向着该乘客的目的楼层的方向行进，则该乘客从等待进入厢体的乘客列表转到当前在厢体的乘客列表。在这种情况下，电梯19将发送“乘客在电梯上”消息：

设备标识+乘客进入厢体的时间

此时，该电梯在它的服务序列中，将刚进入厢体的乘客的目的楼层设为将来停靠楼层。

乘客记录单元根据“乘客在电梯上”消息的数据更新乘客进入厢体的时间。现在关于乘客的已知的事实如下(黑体字)：

乘客标识符+出发楼层+进入侧+目的楼层+离开侧+乘客到达出发楼层的时间+乘客进入厢体的时间+乘客到达目的楼层的时间+电梯+厢体+电梯厢体到达出发楼层的估计时间

以相同的方法对于乘客的目的楼层进行处理。当一电梯停靠在一个楼层时，该电梯检查它的乘客在电梯上的列表。假如停靠楼层与该乘客的目的楼层相同，则从该列表中删除该乘客。该乘客现在以到达他/她的目的楼层，并且发送“乘客在目的楼层”的消息：

乘客标识符+乘客到达目的楼层的时间

乘客记录单元使用“乘客在目的楼层”消息的数据更新乘客到达目的楼层的时间。最后，乘客记录单元从它自己的列表中删除该乘客，并且以“已对乘客提供服务”消息的方式向用于搜集统计的单元发送关于该乘客的信息，这样该信息包括完整的关于乘客的数据：

乘客标识符+出发楼层+进入侧+目的楼层+离开侧+乘客到达出发楼层的时间+乘客进入厢体的时间+乘客到达目的楼层的时间+电梯+厢体+电梯厢体到达出发楼层的估计时间

基于该关于单独的乘客的信息，可生成针对大楼的客运量统计11，该客运量统计一般按照当天的时间说明在不同楼层之间乘客的客运量。这在传统的系统中是困难的，在传统的系统中仅能估计从/向上和下方向到达和离开的客运量因素，而不能精确地估计在楼层之间的客运量。同样地，使用乘客数据可生成确切的基本特性13，该基本特性通常通过时间描述电梯群的服务的质量：乘客的等待时间、乘坐时间和运输时间。在传统的控制系统中，这些数据也是不精确的。

图2显示了乘客分配系统的运行。首先，将所有乘客的数据读入20特定的本地数据存储器22。其次，对乘客进行分类23为已分配的24和未分配的26乘客。对于已分配的乘客，已保留一个电梯厢体，即，系统知道哪一个电梯厢体将对于每个乘客提供服务，然而，对于未分配的乘客，还没有保留电梯厢体。两种类型的乘客数据都被输入电梯群模型28，该模型包括电梯的运行规则和基本信息，如速度、厢体大小、电梯数目等。基本思想是：当向该模型输入时，每个乘客有指定给他/她的电梯，并且该电梯模型努力做到质量30，例如：按照乘客的等待时间、乘坐时间或运输时间，或者上述的组合。因为乘客分配系统知道单个的乘客，所以在该电梯模型中上述特性可非常精确地计算出。

这样，当应用该电梯群模型时，每个乘客有分配给他/她的电梯厢体。对于已分配的乘客，电梯已明确地固定并且不能改变，然而，对于未分配的乘客，遗传算法提供不同的可选择的电梯厢体，并且通过按照该遗传算法的规则为每个未分配的乘客寻找一个电梯厢体，该电梯厢体将为该乘客提供服务。包含于遗传算法中的编码单元34将对于每个未分配乘客的一个基因加入该遗传算法的染色体结构中。此时，通过检查对于停靠和厢体呼叫的锁定状态的设定，并且向不同的控制功能的控制单元发送请求，该遗传算法检查关于出发和目的楼层的任何服务限制33。当加入一个基因时，编码单元34也填写密码本35，该密码本告知基因的类型。例如，需要对于没有人乘座的电梯保持方向。事先决定电梯的出发方向，以使对于分配给该电梯的乘客的服务更有利，是一件困难的事情。该问题通过引入染色体得以解决，在空闲的电梯的情况下，基因36代表方向并且使遗传搜索得以建立，该方向是对于电梯的有利的出发方向。在对于为电梯模型所理解的形式进行搜索期间，解码单元32使用密码本减少由该遗传算法生成的染色体。当完成该遗传搜索时，执行单元从GA(遗传算法)内核38取来方案染色体，并且使用解码功能。结果，解码单元将由这样生成的方案所指定的电梯厢体设定到未分配的乘客的电梯数据字段。最后，对于每个未分配的乘客，如前面的段落所述，执行单元39发送“分配的乘客”消息。基因位于染色体中的位置定义乘客的身份，并且基因的值定义被指派为乘客提供服务的电梯。可对于空闲电梯的方向基因进行编码，例如：与在染色体的末端的乘客基因相邻。因为密码本说明基因的类型和特性，所以基因序列本身并没有意义。直到在电梯模型中，厢体才与电梯相关。

图3提供一个范例，该范例表示在乘客分配进程中染色体及其基因的生成。在该附图中所采用作为例子的大楼有十层和四个独立厢体的电梯，在每个起卸口的上方表明该电梯的标识号和方向。在各自的起卸口的电梯的位置如下：电梯1在底层的一楼、电梯2在四楼、电梯3在七楼并且电梯4在十楼。由上述的位置给出的乘客和目的楼层按照运输的方向显示在电梯群的左侧或右侧。将给出下行呼叫的乘客描绘在电梯群的左侧。在该范例中，该乘客的数目是四。从顶层10楼发出呼叫的乘客想乘电梯到底层一楼。从八楼输入两个呼叫，一个对于五楼，并且另一个对于一楼。五楼的乘客想乘电梯到一楼。在相应的模式中，将目的是上楼的乘客描绘在电梯群的右侧。在三楼，有一个目的是七楼的乘客。在五楼，两个乘客想乘电梯到十楼，十楼也是在八楼的乘客的目的。该范例包括未分配和已分配的乘客。在下行方向上，五楼的乘客已经被分配给电梯3。其它的乘客未被分配。同样地，在已经发出上行呼叫的乘客中，在三楼的乘客已被分配给电梯1，而其他人未被分配。

生成染色体的首要原则是：从楼层已发出呼叫的每个乘客相当于基因，并且基因的值，即，等位基因，决定哪一个电梯将为每个单独的乘客提供服务。此外，在相同的楼层等待的并有相同的目的的乘客可作为一个单独的基因对待，即，作为一个特定的乘客群基因。正如表示单个乘客的基因(乘客基因)的值涉及被指定的为他/她提供服务的电梯厢体，可能的乘客群基因的值同样表示将未该乘客群提供服务的电梯厢体。乘客群基因的例子参见五楼，其中乘客群基因包括两个具有相同的目的十楼的乘客。假如在一层楼有具有相同的目的的乘客，则可形成乘客群。

在该范例中，在电梯群的下面表示染色体的形成。从在不同的楼层的乘客和从五楼的乘客群发出的箭头指向该染色体中的相应的基因的位置。在该染色体中，等待下行乘坐的乘客按照出发楼层的降序排列，该等待下行乘坐的乘客被安排在等待上行乘坐的乘客之前，该等待上行乘坐的乘客按照出发楼层的升序排列。这样，在十楼的乘客由染色体中的第一基因表示，该基因的后面是表示在八楼的、目标是下行方向的基因。因为不同的目的，所以在八楼的这两个乘客不能形成群基因(group gene)。第四基因表示在五楼的想向下乘坐的乘客。第五基因是在三楼的、目的是上行的乘客。第六基因是乘客群基因，该乘客群基因将两个在五楼的乘客包括在一个单一的基因中，该两个乘客的目的是十楼。该乘客群基因之后是第七基因，该基因表示在八楼的、以上行为目的的乘客。因为在染色体中的基因可随意地编码加以区别，所以基因的彼此相对的次序的关系本身并没有意义。

根据如何对于在五楼的、具有相同的目的的乘客进行处理，和根据在染色体结构中是否包括分配的乘客，在图3中的基因的数目可从5变化至8。在五楼的、想乘坐到十楼的两个乘客可组合为一个单一的乘客群基因，或者另一种情况每个乘客也可以单独处理，在后一种情况下，染色体结构将包括相应于这两个乘客中的每一个的分离的基因。按照被选择的处理模式，在染色体结构中将有一个或者两个基因相应于这两个乘客。

在附图中所说明的范例中，在前一个分配的循环期间，有两个已被分配电梯厢体的用户，但是，在这种情况下，仍需为其他的乘客寻找合适的电梯。为五楼的乘客分配了电梯3。相似地，为三楼的乘客分配了电梯1。因此，相应于这些乘客的基因只有一种可能的值，其中对于五楼的乘客来说意味着电梯3，并且对于三楼的乘客来说意味着电梯1。因为其它的乘客没有被分配电梯厢体，所以相应于该乘客的基因有四种可能的电梯选择，即，电梯1、2、3和4。因为对于在三楼和五楼乘客提供服务的电梯已知，并且在决策制订的进程中没有改变，所以该乘客不必包括在最终的染色体结构中；然而，可将该乘客作为有关的电梯的路线的一部分直接地代入电梯模型中。尽管没有将被考虑的基因包括于实际的染色体的结构中，但是有这样的效果：仍然将这些在三楼和五楼乘客考虑到决策制订的进程中。

因为染色体结构涉及电梯厢体，所以该方法也适用于电梯群，该电梯群可包括单一的厢体和/或多厢体电梯。

本发明不局限于上述的本发明的实施例的范例；在权利要求确定的范围内允许多种修改。

Claims (11)

1.用于对于电梯群中的乘客进行分配的方法，包括：

-接收由每个乘客通过呼叫装置给出的有关乘客目的楼层的消息，从而确定该乘客的出发和目的楼层，

-将该电梯的路线编码到可选择的染色体中，关于乘客和电梯厢体的所需的数据存储在该染色体的基因中，

-通过使用遗传算法，形成可选择的染色体，并且在该染色体中选择最佳的染色体，

-将由该染色体所表示的乘客引导到由该染色体所代表的电梯厢体中；和

-引导由最佳染色体所表示的电梯厢体对于记录在该染色体中的乘客提供服务。

2.如权利要求1所述的方法，其特征在于该染色体以如下形式构成：由基因位于该染色体中的位置定义乘客的身份，并且其值，即该基因的等位基因定义为向乘客提供服务的电梯厢体。

3.如权利要求1-2中任何一个所述的方法，其特征在于就遗传算法的运算而言，该基因带有多个等位基因的选择。

4.如权利要求1-2中任何一个所述的方法，其特征将在前一个分配循环期间固定给乘客的电梯厢体作为基因记录在该染色体中，该基因的等位基因是不变的，并且表示已分配给乘客的厢体。

5.如权利要求1-2中任何一个所述的方法，其特征在于遗传分配在GA的内核中进行，执行单元从该GA的内核中得到为乘客所选择的电梯厢体，将该乘客带入带有该厢体的电梯中，该乘客称为分配的乘客。

6.如权利要求1-2中任何一个所述的方法，其特征在于一旦遗传算法停止，执行单元调用解码功能，于是从GA的内核中获得相应于最优染色体的电梯，并将该电梯置于未分配乘客的电梯数据字段中。

7.如权利要求1-2中任何一个所述的方法，其特征在于可将两个或多个乘客一同作为单一的乘客群基因对待。

8.用于对于属于电梯群的乘客进行分配的装置，以便由该电梯群中的一个电梯厢体对于每个乘客提供服务，其特征在于，该装置包括：

每层都有的输入装置，用于输入每个乘客的目的楼层；

用于基于电梯模型执行计算的装置；

用于生成定义乘客和为该乘客提供服务的厢体的基因的装置，该用于生成基因的装置适配为将乘客目的楼层数据记录在基因中；

用于运行遗传算法的装置；和

编码装置，用于填写密码本和指定每个基因的类型，并且通过使用密码本，将基因搜索期间由该用于运行遗传算法的装置生成的染色体解码为电梯模型所理解的形式，

并且该装置包括根据所选择的基因对于乘客提供服务的装置。

9.如权利要求8所述的装置，其特征在于该装置包括执行单元，该执行单元为每个未分配的乘客，向带有已分配乘客厢体的电梯发送“分配的乘客”消息。

10.如权利要求8或9所述的装置，其特征在于该电梯将被分配的乘客的出发和目的楼层作为将停靠的楼层加入该电梯线路中。

11.如权利要求8或9所述的装置，其特征在于该装置包括统计单元，该统计单元从单个的乘客构建了对于大楼的客运量矩阵，即在每两个楼层之间的客运流量，并且该统计单元编制了对于乘客服务的质量的统计，该乘客服务的质量由乘客等待时间、乘坐一个厢体的次数和运输时间表示。