Computing allocation decisions in an elevator system

Abstract

A method and an apparatus for computing allocation decisions in an elevator system is provided. Historical passenger batch journey data relating to the elevator system is obtained, wherein each passenger batch journey includes an origin and a destination floor of the journey, the number of passengers of the journey and the time of the journey. Historical passenger traffic statistics are constructed based on the passenger batch journey data, and expected calls are modelled based on the passenger traffic statistics. The modelled expected call is taken into account in computing subsequent allocation decisions in the elevator system.

Claims

1. A method for computing allocation decisions in an elevator system that uses immediate call allocation, the method comprising the steps of: obtaining historical passenger batch journey data relating to the elevator system, wherein each passenger batch journey comprises historical, realized date about origin and destination floors of past journeys, a number of passengers of the past journeys and time of the past journeys, within a predetermined day cycle; constructing historical passenger traffic statistics based on the passenger batch journey data; modelling expected calls in the future based on the historical passenger traffic statistics; receiving at least one call; and taking at least one modelled expected call into account as a received call in computing allocation decisions for the at least one call in the elevator system.

2. The method according to claim 1, further comprising: estimating elevator load in elevators of the elevator system based on the historical passenger traffic statistics; and taking the estimated elevator load into account in computing subsequent allocation decisions in the elevator system.

3. The method according to claim 2, further comprising: estimating elevator load in elevators of the elevator system separately for each elevator trip based on passenger batch journey intensities and batch size distributions obtained from the historical passenger traffic statistics, and simulated service times.

4. The method according to claim 1, wherein the modelled expected calls comprise at least one landing and car call pair.

5. The method according to claim 1, wherein the modelled expected calls comprise at least one destination call.

6. The method according to claim 1, wherein the passenger batch journey data comprises building origin-destination matrices formed separately for each day within a predetermined day cycle.

7. An elevator control apparatus for computing allocation decisions in an elevator system that uses immediate call allocation, the apparatus comprising: at least one processor; and at least one memory connected to the at least one processor, wherein the at least one memory stores program instructions that, when executed by the at least one processor, cause the apparatus to: obtain historical passenger batch journey data relating to the elevator system, wherein each passenger batch journey comprises historical, realized date about origin and destination floors of past journeys, a number of passengers of the past journeys and time of the past journeys, within a predetermined day cycle; construct historical passenger traffic statistics based on the passenger batch journey data; model expected calls in the future based on the historical passenger traffic statistics; receive at least one call; and take at least one modelled expected call into account as a received call in computing allocation decisions for the at least one call in the elevator system.

8. The elevator control apparatus according to claim 7, wherein the at least one memory stores program instructions that, when executed by the at least one processor, cause the apparatus to: estimate elevator load in elevators of the elevator system based on the historical passenger traffic statistics; and take the estimated elevator load into account in computing subsequent allocation decisions in the elevator system.

9. The elevator control apparatus according to claim 8, wherein the at least one memory stores program instructions that, when executed by the at least one processor, cause the apparatus to: estimate elevator load in elevators of the elevator system separately for each elevator trip based on passenger batch journey intensities and batch size distributions obtained from the historical passenger traffic statistics, and simulated service times.

10. The elevator control apparatus according to claim 7, wherein the modelled expected calls comprise at least one landing and car call pair.

11. The elevator control apparatus according to claim 7, wherein the modelled expected calls comprise at least one destination call.

12. The elevator control apparatus according to claim 7, wherein the passenger batch journey data comprises building origin-destination matrices formed separately for each day within a predetermined day cycle.

13. A computer program embodied on a non-transitory computer readable medium and comprising program code, which when executed by at least one processing unit, causes the at least one processing unit to perform the method of claim 1.

14. An elevator system comprising: a plurality of elevators; and the elevator control apparatus according to claim 7.

15. The method according to claim 2, wherein the modelled expected calls comprise at least one landing and car call pair.

16. The method according to claim 3, wherein the modelled expected calls comprise at least one landing and car call pair.

17. The method according to claim 2, wherein the modelled expected calls comprise at least one destination call.

18. The method according to claim 3, wherein the modelled expected calls comprise at least one destination call.

19. The method according to claim 2, wherein the passenger batch journey data comprises building origin-destination matrices formed separately for each day within a predetermined day cycle.

20. A method for computing allocation decisions in an elevator system that uses immediate call allocation, the method comprising the steps of: obtaining historical passenger batch journey data relating to the elevator system, wherein each passenger batch journey comprises an origin and a destination floor of the journey, the number of passengers of the journey and the time of the journey; constructing historical passenger traffic statistics based on the passenger batch journey data; modelling expected calls in the future based on the historical passenger traffic statistics; receiving at least one call; and taking at least one modelled expected call into account as a received call in computing allocation decisions for the at least one call in the elevator system; estimating elevator load in elevators of the elevator system separately for each elevator trip based on passenger batch journey intensities and batch size distributions obtained from the historical passenger traffic statistics, and simulated service times; and taking the estimated elevator load into account in computing subsequent allocation decisions in the elevator system.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The accompanying drawings, which are included to provide a further understanding of the invention and constitute a part of this specification, illustrate embodiments of the invention and together with the description help to explain the principles of the invention. In the drawings:

(2) FIG. 1A is a flow diagram illustrating a method for computing allocation decisions in an elevator system.

(3) FIG. 1B is a flow diagram illustrating a method for computing allocation decisions in an elevator system.

(4) FIGS. 2A and 2B disclose an example illustrating making an allocation decision in an elevator system.

(5) FIG. 3 is a block diagram illustrating an apparatus of operating elevator cars in a multi-car elevator system.

DETAILED DESCRIPTION

(6) FIG. 1A is a flow diagram illustrating a method for computing allocation decisions in an elevator system.

(7) At 100 historical passenger batch journey data relating to the elevator system is obtained. Each passenger batch journey comprises an origin and a destination floor of the journey, the number of passengers (i.e. the passenger batch size) of the journey and the time of the journey. The passenger batch journey data provides historical, realized data about the usage of elevators in the elevator system.

(8) At 102 historical passenger traffic statistics are constructed based on the passenger batch journey data. The historical passenger traffic statistics may be based on building origin-destination (OD) matrices which in turn may be based on the passenger batch journeys discussed above. A building specific OD matrix may be formed separately for each day d, d=1, 2, . . . , D, where D is the number of days in a cycle, and fixed intervals [t.sub.k, t.sub.k+1], k=1, 2, . . . , K, where K is the number of intervals within a day. For example, if D is set to “7”, the building specific OD matrix covers each weekday.

(9) A N×N building specific OD matrix can be denoted as Λ.sub.kd.sup.b, where N is the number of floors in the building and b, b=1, 2, . . . , B, denotes a batch size (i.e. the number of passengers). The element λ.sub.ijkd.sup.b in the building specific OD matrix corresponds to the intensity of passenger batch journeys equal to the batch size b from an origin floor i to a destination floor j within an interval k of a day d.

(10) In the elevator group control, each candidate solution gives the allocation of the calls for the elevators in the group. In order to calculate the cost or fitness value of a solution, the service order of the calls or passengers for each elevator has to be determined. This can be done for each elevator independently from each other, for example, as follows.

(11) Suppose there exists a given a set of calls, some of which can be dummy calls. First, the service order of the calls is determined by the collective control principle. Then, the route of the elevator through the calls is simulated in that order. The calls can be represented with nodes. A landing call corresponds to a single origin node and a destination call to an origin and destination node. Let N=[n.sub.1, n.sub.2, . . . , n.sub.k] denote the ordered set of nodes. The service time t.sub.i of a call n.sub.1 can be recursively calculated as t.sub.i=t.sub.i−1+τ.sub.i−1,i, where τ.sub.ij is the time to go from a node n.sub.i to a node n.sub.j, that is, the flight time from the node n.sub.i to a node n.sub.j, plus the stop time at the node n.sub.i. A node n.sub.0 is the current location of the elevator, t.sub.0=0 and τ.sub.01, is the flight time between the current location of the elevator and the first node n.sub.1.

(12) If n.sub.i corresponds to a landing call, existing or dummy, a set of dummy car calls that can be assumed to be given when the landing call n.sub.i is served, are modelled and added to the route in right places. Table 1 lists examples of different call types and items that can be modelled.

(13) TABLE-US-00001 TABLE 1 Call type Modelled items Existing landing call A set of car calls that will be given by the passengers behind the call Dummy landing call 1. The time when the dummy call will be given 2. A set of car calls that will be given by the passengers behind the call Existing destination A set of car calls that will be given by the call, car call buttons passengers behind the call Dummy destination The time when the dummy call will be given call, no car call buttons Dummy destination 1. The time when the dummy call will be call, car call buttons given 2. A set of car calls that will be given by the passengers behind the call

(14) Once the simulation is over, the service time of each call is determined. Then the fitness value of each candidate solution, that is, allocation of calls, can be calculated using an objective function. A typical objective function is the average waiting time, the average journey time or the weighted sum of these two.

(15) At 104 expected calls (or “dummy” calls) are modelled based on the passenger traffic statistics. Let Λ.sub.kd=Σ.sub.b=1.sup.BΛ.sub.kd.sup.b denote a matrix containing the intensity of passenger batch journeys for each pair of floors within interval k of day d. An element λ.sub.ijkd is the intensity of journeys from an origin floor i to a destination floor j. It is also assumed herein that the batch journeys occur according to a Poisson process. Furthermore, the batch size distributions for each pair of floors may be defined by the matrices Λ.sub.kd.sup.1, Λ.sub.kd.sup.2, K, Λ.sub.kd.sup.B. By leaving out the interval and day indices, the time, t.sub.ij, to the next pair of a dummy landing and car call, or a dummy destination call from an origin floor i to a destination floor j, can be defined as

(16) $t_{\mathrm{ij}}=\{\frac{\max \left\{\frac{1}{{\lambda }_{\mathrm{ij}}}-{\gamma }_{\mathrm{ij}},0\right\}{\gamma }_{\mathrm{ij}}\le \hat{\gamma }}{\frac{1}{{\lambda }_{\mathrm{ij}}}\mathrm{otherwise}}$
where λ.sub.ij is the intensity of the batch arrivals occurring according to a Poisson process from an origin floor i to a destination floor j in seconds and γ.sub.ij is the time since the previous landing or destination call from the origin floor i to the destination floor j.

(17) Because λ.sub.ij is the rate parameter of a Poisson process, 1/λ.sub.ij is the average time between two successive arrivals, i.e. calls. The above equation then implies that even if we assume that the batch arrivals occur according to a Poisson process, the forgetfulness property of the process is assumed only if the time since the previous call is longer than the predefined time limit {circumflex over (γ)}. A suitable value for the time limit can be determined, for example, with simulation studies.

(18) When 1/λ.sub.ij<γ.sub.ij, i.e., there is a lot of traffic from the origin floor i to the destination floor j, and the time since the previous call is longer than the average inter-arrival time, then t.sub.ij<0. In this case, it is natural to assume that the time to the next future call will be very short and thus we set t.sub.ij=0. If t.sub.ij∈[0,{circumflex over (t)}], where {circumflex over (t)} is a predefined time horizon, e.g., elevator cycle time, a pair of a dummy landing and car call, or a dummy destination call is generated from an origin floor i to a destination floor j with the arrival time equal to t.sub.current+t.sub.ij, where t.sub.current is, e.g., the moment of computing a new allocation decision.

(19) There can be several destination calls per origin floor, and thus, all dummy destination calls from an origin floor i to a destination floor j such that t.sub.ij∈[0,{circumflex over (t)}] are generated. Because there can be only one landing call per direction on an origin floor i at a time, among all pairs of dummy landing and car calls to the same direction such that t.sub.ij∈[0,{circumflex over (t)}], the pair for which the arrival time is closest to the current time can be selected.

(20) Let l.sub.i denote this arrival time, i.e. l.sub.i=arg min{t.sub.ij|0≤t.sub.ij≤{circumflex over (t)}}.

(21) Hence, the arrival time of the next dummy landing call on an origin floor i to the direction defined by the dummy car calls j such that t.sub.ij∈[0,{circumflex over (t)}] is t.sub.current+l.sub.i. Further, for example, if there is an existing landing call at the origin floor i, then only the dummy car calls to destination floors j such that t.sub.ij∈[0,{circumflex over (t)}] are generated.

(22) At 106 at least one modelled expected (or “dummy”) call is taken into account in computing subsequent allocation decisions. This improves the service level of passenger since the allocation of elevator cars becomes more optimized.

(23) FIG. 1B is a flow diagram illustrating a method for computing allocation decisions in an elevator system. The embodiment illustrated in FIG. 1B is similar to the one illustrated in FIG. 1A that already illustrates steps 100, 102 and 104.

(24) At 108 load in elevators is modelled based on the historical passenger traffic statistics. For each dummy car call discussed in more detail in FIG. 1A and its description, the intensity at which passengers travel from an origin floor i to a destination floor j within interval k of day d is estimated as
μ.sub.ijkd=λ.sub.ijkdt.sub.iE└Y.sub.ijkd┘
where t.sub.i is the serving time of the landing call on a floor I, and t.sub.i becomes defined during route simulation. E[Y.sub.ijkd] is the expected number of passengers related to each arrival, in other words, the expected batch size which is estimated using the batch size distribution defined by the matrices Λ.sub.kd.sup.1, Λ.sub.kd.sup.2, K, Λ.sub.kd.sup.B, as already illustrated earlier. λ.sub.ijkd is the intensity of batch arrivals from an origin floor i to a destination floor j, that is, an element in the matrix defined as Λ.sub.kd=Σ.sub.b=1.sup.BΛ.sub.kd.sup.b.

(25) The intensities are estimated similarly as for dummy calls, as already illustrated in the description of FIG. 1A. Furthermore, if there is an existing car or destination call to a floor ahead a floor where an existing or dummy landing call is served, the intensity for this pair of floors may also be estimated. The reason is that the passengers who board the elevator at the landing call floor may also be travelling to the floor defined by an existing car or destination call, not only to the floor defined by the dummy calls.

(26) The estimated intensities with their origin and destination floor numbers may be stored in a memory. For existing car and destination calls that the elevator will actually serve, the intensities may be kept in the memory as long as they are not served at the destination floor. For dummy car and destination calls, the intensities may be kept in memory as long as it would still be possible to decelerate to the destination floor defined by the intensity. The destination floors of the estimated intensities can be represented with nodes.

(27) When the simulation of an elevator route is over, all the destination nodes of the estimated intensities are iterated through in the order defined by the route. In course of the iteration, two rules may be used to separate the route into successive elevator trips. An elevator trip ends to the current destination node if: 1. The smallest origin node number of the intensities associated to the next destination node, if any, is larger (smaller) or equal to the largest (smallest) destination node number encountered so far when the elevator running direction is up (down). 2. The elevator changes its running direction at the node.

(28) In one embodiment, the following steps are performed: 1. During the simulation of the route defined by the existing calls, dummy landing, car and destination calls are generated and the intensities are estimated based on the passenger batch journey statistics for the existing and dummy car and destination calls. 2. The destination nodes defined by the intensities are iterated through in their service order and the elevator route is divided into successive elevator trips using the two rules.

(29) After the above two steps, the intensities related to each elevator trip are used to define the origin and destination floors of the elevator trip.

(30) In one embodiment, next the load of the elevator is estimated for each elevator trip individually as follows.

(31) Let x.sub.ij denote the number of individual passenger arrivals from a node i to a node j. Assuming that the arrivals occur according to a Poisson process, x.sub.ij follows a Poisson distribution with the rate parameter μij. The number of passengers in the elevator after a stop at a node k must not exceed the capacity of the elevator. Mathematically this is can written as follows:
Σ.sub.i=1.sup.kΣ.sub.j=k+1.sup.Px.sub.ij≤Q
where Q is the elevator capacity and P is the number of nodes on the elevator trip.

(32) Next, since x.sub.ij may not be accurately known, the uncertainty related to them is taken into account by requiring that the probability of exceeding the elevator capacity Q after a stop at the node k is smaller than some predefined small probability α. Assuming that x.sub.ij are independent, this can be expressed as follows:

(33) $\mathrm{Prob}\left(\underset{i=1}{\overset{k}{.Math.}}\underset{j=k+1}{\overset{P}{.Math.}}{x}_{\mathrm{ij}}>Q\right)\le \alpha$$1-\mathrm{Prob}\left(\underset{i=1}{\overset{k}{.Math.}}\underset{j=k+1}{\overset{P}{.Math.}}{x}_{\mathrm{ij}}\le Q\right)\le \alpha$$1-\underset{q=0}{\overset{Q}{.Math.}}\frac{e^{-u}{\mu }^q}{q!}\le \alpha$
where μ=Σ.sub.i=1.sup.kΣ.sub.j=k+1.sup.Pμ.sub.ij. The final equation above can be considered as a penalty term since the smaller the left hand side is, the more probable is that the elevator capacity will not be exceeded during the elevator trip. The penalty term for a single elevator trip can be written as follows:

(34) $\mathrm{\beta max}\left\{0,1-\underset{q=0}{\overset{Q}{.Math.}}\frac{e^{-u}{\mu }^q}{q!}-\alpha \right\}$
where β is a scaling factor whose value can be determined, for example, with computational experiments. It follows that the penalty term for the whole route is the sum of the above penalties for the individual elevator trips. The penalty term for the whole route may thus be used when is added to an objective function used. A typical objective function is the average waiting time, the average journey time or the weighted sum of these two.

(35) At 110 the at least one modelled expected (or “dummy”) call and the modelled load is taken into account in computing subsequent allocation decisions. An elevator group control is then able to construct and use historical passenger traffic statistics based on passenger batch journeys to estimate load of an elevator during its route through the calls allocated to it which, when taken into account in computing the allocation decisions, help to improve passenger service level.

(36) FIGS. 2A and 2B disclose an example illustrating making an allocation decision in an elevator system. The example assumes that a destination control system is used in a building with eight floors and two elevators, 200 and 202. It is also assumed that one of the elevators is at the top most floor, the floor 9, and the other one is at the bottom most floor, the floor 1.

(37) In addition, it is assumed that two destination calls, one 204 from the floor 8 to the floor 2 and the other one 206 from the floor 5 to the floor 1, occur about the same time and that, based on minimizing the average waiting time, the first one is allocated to the first elevator 200 and the second one is allocated to the second elevator 202. Next, it is assumed that after about 5 seconds, when the elevators 200, 202 have started to move to serve the destination calls, a new destination call 208 is given from the floor 4 to the floor 6. This has been illustrated in FIG. 2B.

(38) Now, from the average waiting time point of view, the best allocation would be to reassign the destination call from the floor 5 to the floor 1 for the first elevator 200 and to give the new destination call 208 to the second elevator 202. Normally, however, this would not be possible since in the destination control system the serving elevator is signaled to the passengers immediately after giving a call. However, as illustrated in the embodiment of FIG. 1A, this problem can be overcome when the new destination call is taken into account as a predicted or dummy destination call when allocating the first two calls. Therefore, in this case, the first and the second destination calls would be allocated to the first elevator 200 in the first place, and the second elevator 202 would then serve the subsequent new destination call 208.

(39) FIG. 3 illustrates a block diagram of an elevator control apparatus 300 for computing allocation decisions in an elevator system. The apparatus 300 comprises at least one processor 302 connected to at least one memory 304. The at least one memory 304 may comprise at least one computer program which, when executed by the processor 302 or processors, causes the apparatus 300 to perform the programmed functionality. The apparatus 300 may also comprise input/output ports and/or one or more physical connectors, which can be an Ethernet port, a Universal Serial Bus (USB) port, IEEE 1394 (FireWire) port, and/or RS-232 port. The illustrated components are not required or all-inclusive, as any components can deleted and other components can be added.

(40) The elevator control apparatus 300 may be an elevator control entity configured to implement only the above disclosed operating features, or it may be part of a larger elevator control entity, for example, a group controller.

(41) The exemplary embodiments of the invention can be included within any suitable device, for example, including, servers, workstations, personal computers, laptop computers, capable of performing the processes of the exemplary embodiments. The exemplary embodiments may also store information relating to various processes described herein.

(42) Example embodiments may be implemented in software, hardware, application logic or a combination of software, hardware and application logic. The example embodiments can store information relating to various methods described herein. This information can be stored in one or more memories, such as a hard disk, optical disk, magneto-optical disk, RAM, and the like. One or more databases can store the information used to implement the example embodiments. The databases can be organized using data structures (e.g., records, tables, arrays, fields, graphs, trees, lists, and the like) included in one or more memories or storage devices listed herein. The methods described with respect to the example embodiments can include appropriate data structures for storing data collected and/or generated by the methods of the devices and subsystems of the example embodiments in one or more databases.

(43) All or a portion of the example embodiments can be conveniently implemented using one or more general purpose processors, microprocessors, digital signal processors, micro-controllers, and the like, programmed according to the teachings of the example embodiments, as will be appreciated by those skilled in the computer and/or software art(s). Appropriate software can be readily prepared by programmers of ordinary skill based on the teachings of the example embodiments, as will be appreciated by those skilled in the software art. In addition, the example embodiments can be implemented by the preparation of application-specific integrated circuits or by interconnecting an appropriate network of conventional component circuits, as will be appreciated by those skilled in the electrical art(s). Thus, the examples are not limited to any specific combination of hardware and/or software. Stored on any one or on a combination of computer readable media, the examples can include software for controlling the components of the example embodiments, for driving the components of the example embodiments, for enabling the components of the example embodiments to interact with a human user, and the like. Such computer readable media further can include a computer program for performing all or a portion (if processing is distributed) of the processing performed in implementing the example embodiments. Computer code devices of the examples may include any suitable interpretable or executable code mechanism, including but not limited to scripts, interpretable programs, dynamic link libraries (DLLs), Java classes and applets, complete executable programs, and the like.

(44) As stated above, the components of the example embodiments may include computer readable medium or memories for holding instructions programmed according to the teachings and for holding data structures, tables, records, and/or other data described herein. In an example embodiment, the application logic, software or an instruction set is maintained on any one of various conventional computer-readable media. In the context of this document, a “computer-readable medium” may be any media or means that can contain, store, communicate, propagate or transport the instructions for use by or in connection with an instruction execution system, apparatus, or device, such as a computer. A computer-readable medium may include a computer-readable storage medium that may be any media or means that can contain or store the instructions for use by or in connection with an instruction execution system, apparatus, or device, such as a computer. A computer readable medium can include any suitable medium that participates in providing instructions to a processor for execution. Such a medium can take many forms, including but not limited to, non-volatile media, volatile media, transmission media, and the like.

(45) While there have been shown and described and pointed out fundamental novel features as applied to preferred embodiments thereof, it will be understood that various omissions and substitutions and changes in the form and details of the devices and methods described may be made by those skilled in the art without departing from the spirit of the disclosure. For example, it is expressly intended that all combinations of those elements and/or method steps which perform substantially the same function in substantially the same way to achieve the same results are within the scope of the disclosure. Moreover, it should be recognized that structures and/or elements and/or method steps shown and/or described in connection with any disclosed form or embodiments may be incorporated in any other disclosed or described or suggested form or embodiment as a general matter of design choice. Furthermore, in the claims means-plus-function clauses are intended to cover the structures described herein as performing the recited function and not only structural equivalents, but also equivalent structures.

(46) The applicant hereby discloses in isolation each individual feature described herein and any combination of two or more such features, to the extent that such features or combinations are capable of being carried out based on the present specification as a whole, in the light of the common general knowledge of a person skilled in the art, irrespective of whether such features or combinations of features solve any problems disclosed herein, and without limitation to the scope of the claims. The applicant indicates that the disclosed aspects/embodiments may consist of any such individual feature or combination of features. In view of the foregoing description it will be evident to a person skilled in the art that various modifications may be made within the scope of the disclosure.