Elevator control in an elevator system may enable reallocation of a call after an initial call allocation. This means that, in some cases, it would be beneficial to reassign a new elevator to an already existing call. The situation is, however, different, for example, in elevator systems using immediate call allocation. One example of the immediate call allocation is a destina- tion control system (DCS) . In the immediate call allo ^¬ cation, already allocated calls are not typically be reassigned. This may lead to a situation that after al ^¬ locating a call to a first elevator, it may turn out that it would be more beneficial and optimal to serve the call with a second elevator. But, as already men ^¬ tioned above, it may not be possible to reassign the call of the already allocated call to the first eleva ^¬ tor since in the destination control system the serving (allocated) elevator is signaled to the passengers im- mediately after giving a call.

Further, an elevator may become full before it has served all the calls and passengers assigned to it. This, on the other hand, may result in reduced passen- ger service level especially in destination control systems .

SUMMARY

According to a first aspect of the invention, there is provided a method for computing allocation decisions in an elevator system. The method comprises 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 pas- senger traffic statistics based on the passenger batch journey data; modelling expected calls based on the passenger traffic statistics; and taking the modelled expected call into account in computing subsequent al ^¬ location decisions in the elevator system.

In one embodiment, the method further comprises esti ^¬ mating elevator load in elevators of the elevator system based on the historical passenger traffic statis ^¬ tics; and taking the estimated elevator load into ac- count in computing subsequent allocation decisions in the elevator system.

In one embodiment, alternatively or in addition, the method further comprises 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.

In one embodiment, alternatively or in addition, the modelled expected calls comprise at least one landing and car call pair. In one embodiment, alternatively or in addition, the modelled expected calls comprise at least one destina ^¬ tion call. In one embodiment, alternatively or in addition, the passenger batch journey data comprises building origin- destination matrices formed separately for each day within a predetermined day cycle.

In one embodiment, alternatively or in addition, the elevator system uses immediate call allocation.

According to a second aspect, there is provided an ele- vator control apparatus for computing allocation decisions in an elevator system. The apparatus comprises at least one processor and at least one memory connected to the at least one processor. 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 an origin and a destination floor of the journey, the number of passengers of the journey and the time of the journey; construct historical passenger traffic statistics based on the passenger batch journey data; model expected calls based on the passenger traf ^¬ fic statistics; and take the modelled expected call in ^¬ to account in computing subsequent allocation decisions in the elevator system.

In one embodiment, the at least one memory stores pro ^¬ gram 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 sub ^¬ sequent allocation decisions in the elevator system.

In one embodiment, the at least one memory stores pro- gram 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 simu ^¬ lated service times.

In one embodiment, alternatively or in addition, the modelled expected calls comprise at least one landing and car call pair.

In one embodiment, alternatively or in addition, the modelled expected calls comprise at least one destina ^¬ tion call.

In one embodiment, alternatively or in addition, the passenger batch journey data comprises building origin- destination matrices formed separately for each day within a predetermined day cycle.

In one embodiment, alternatively or in addition, the elevator system uses immediate call allocation.

According to a third aspect, there is provided a com- puter program comprising program code, which when executed by at least one processing unit, causes the at least one processing unit to perform the method of the first aspect.

In one embodiment, the computer program is embodied on a computer readable medium.

According to a third aspect, there is provided an ele ^¬ vator system comprising a plurality of elevators and an elevator control apparatus according to the second as- pect.

BRIEF DESCRIPTION OF THE DRAWINGS

The accompanying drawings, which are included to pro ^¬ vide a further understanding of the invention and con- stitute a part of this specification, illustrate embod ^¬ iments of the invention and together with the description help to explain the principles of the invention. In the drawings: FIG. 1A is a flow diagram illustrating a method for computing allocation decisions in an elevator system.

FIG. IB is a flow diagram illustrating a method for computing allocation decisions in an elevator system.

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

FIG. 3 is a block diagram illustrating an apparatus of operating elevator cars in a multi-car elevator system. DETAILED DESCRIPTION

FIG. 1A is a flow diagram illustrating a method for computing allocation decisions in an elevator system. 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 pro ^¬ vides historical, realized data about the usage of ele ^¬ vators in the elevator system.

At 102 historical passenger traffic statistics are con- structed 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 sep- arately for each day d, d = 1, 2, D, where D is the number of days in a cycle, and fixed intervals [t _k ,t _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.

A N x N building specific OD matrix can be denoted as Λ* _ω , where N is the number of floors in the building and b, b = 1, 2, ... , B, denotes a batch size (i.e. the num ^¬ ber of passengers) . The element y _U in the building specific OD matrix corresponds to the intensity of pas ^¬ senger batch journeys equal to the batch size b from an origin floor i to a destination floor j within an interval f of a day d.

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.

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 prin- ciple. Then, the route of the elevator through the calls is simulated in that order. The calls can be rep ^¬ resented with nodes. A landing call corresponds to a single origin node and a destination call to an origin and destination node. Let N = [n _lf n _∑ , n _k ] denote the ordered set of nodes. The service time t± of a call ni can be recursively calculated as t _i = t _M + T _t _ , where T _tJ is the time to go from a node n± to a node ri _j , that is, the flight time from the node n± to a node ri _j , plus the stop time at the node n±. A node no is the current location of the elevator, to = 0 and r ₀₁ is the flight time be ^¬ tween the current location of the elevator and the first node ni.

If n± corresponds to a landing call, existing or dummy, a set of dummy car calls that can be assumed to be giv ^¬ en when the landing call n± is served, are modelled and added to the route in right places. Table 1 lists exam- pies of different call types and items that can be mod ^¬ elled .

Table 1

Once the simulation is over, the service time of each call is determined. Then the fitness value of each can ^¬ didate solution, that is, allocation of calls, can be calculated using an objective function. A typical ob- jective function is the average waiting time, the aver ^¬ age journey time or the weighted sum of these two. At 104 expected calls (or "dummy" calls) are modelled based on the passenger traffic statistics. Let

A _kd = _iL _^A _kd denote a matrix containing the intensity of passenger batch journeys for each pair of floors within interval k of day d. An element A _ljkd 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 A ^l _kd , A ² _kd , A ^B _kd . By leaving out the interval and day indices, the time, t± _j , 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

where λ _1} is the intensity of the batch arrivals occur ^¬ ring according to a Poisson process from an origin floor i to a destination floor j in seconds and χ _ϋ is the time since the previous landing or destination call from the origin floor i to the destination floor j.

Because λ _1} is the rate parameter of a Poisson process, is the average time between two successive arri ^¬ vals, i.e. calls. The above equation then implies that even if we assume that the batch arrivals occur accord- ing to a Poisson process, the forgetfulness property of the process is assumed only if the time since the pre ^¬ vious call is longer than the predefined time limit γ . A suitable value for the time limit can be determined, for example, with simulation studies.

When 1/ /L < v.. , 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 in- ter-arrival time, then t„ < 0. In this case, it is natu- ral to assume that the time to the next future call will be very short and thus we set t _!; = 0. If t _!; £

[0, t ] , where t is a predefined time horizon, e.g., ele ^¬ vator 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 _current + t _ijr where t _current is, e.g., the moment of computing a new allocation decision. 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 _tJ £

[0, 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 _tj £ [0 , t ] , the pair for which the arrival time is closest to the current time can be selected. Let li denote this arrival time, i.e. /, = argmu | 0 < t _t] ≤ t} .

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 _tj £ [0, t ] is t _current + 1±.

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 _tj £ [0, t ] are generated.

At 106 at least one modelled expected (or "dummy") call is taken into account in computing subsequent alloca ^¬ tion decisions. This improves the service level of pas- senger since the allocation of elevator cars becomes more optimized.

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

At 108 load in elevators is modelled based on the his- torical 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 where t _± is the serving time of the landing call on a floor I, and t _± becomes defined during route simulation. E[Yij _kd ] 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 A ^l _kd , A ² _kd , A ^B _kd , as already illus ^¬ trated earlier. A _ljkd is the intensity of batch arrivals from an origin floor i to a destination floor j , that is, an element m the matrix defined as A _kd = A _kd .

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 ex- isting or dummy landing call is served, the intensity for this pair of floors may also be estimated. The rea ^¬ son 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.

The estimated intensities with their origin and desti ^¬ nation 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 destina ^¬ tion 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 .

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 sepa ^¬ rate the route into successive elevator trips. An ele ^¬ vator trip ends to the current destination node if:

1. The smallest origin node number of the in ^¬ tensities 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 .

In one embodiment, the following steps are performed:

1. During the simulation of the route defined by the existing calls, dummy landing, car and destina ^¬ tion calls are generated and the intensities are esti ^¬ mated based on the passenger batch journey statistics for the existing and dummy car and destination calls.

2. The destination nodes defined by the inten- sities are iterated through in their service order and the elevator route is divided into successive elevator trips using the two rules.

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. In one embodiment, next the load of the elevator is es ^¬ timated for each elevator trip individually as follows.

Let x _± j denote the number of individual passenger arri- vals from a node i to a node j. Assuming that the arri ^¬ vals occur according to a Poisson process, x _± j follows a Poisson distribution with the rate parameter pij . 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: where Q is the elevator capacity and P is the number of nodes on the elevator trip.

Next, since x _± j may not be accurately known, the uncer ^¬ tainty related to them is taken into account by requir ^¬ ing that the probability of exceeding the elevator ca- pacity Q after a stop at the node k is smaller than some predefined small probability a. Assuming that x _± j are independent, this can be expressed as follows:

Q e ¹¹ μ ,ft

<a

⁰ q\

where μ = ∑ ^F _ _{k+l y} · 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: 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 ele ^¬ vator 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 wait ^¬ ing time, the average journey time or the weighted sum of these two.

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 histor ^¬ ical 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 deci- sions, help to improve passenger service level.

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.

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.

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 ele ^¬ vator 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 im ^¬ mediately after giving a call. However, as illustrated in the embodiment of FIG. 1A, this problem can be over- come when the new destination call is taken into account as a predicted or dummy destination call when al ^¬ locating the first two calls. Therefore, in this case, the first and the second destination calls would be al ^¬ located to the first elevator 200 in the first place, and the second elevator 202 would then serve the subse ^¬ quent new destination call 208. 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 add- ed.

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 .

The exemplary embodiments of the invention can be included within any suitable device, for example, includ- ing, 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.

Example embodiments may be implemented in software, hardware, application logic or a combination of soft- ware, hardware and application logic. The example em ^¬ bodiments 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) in- eluded 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 ex- ample embodiments in one or more databases.

All or a portion of the example embodiments can be con ^¬ veniently 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 appre ^¬ ciated by those skilled in the software art. In addi ^¬ tion, the example embodiments can be implemented by the preparation of application-specific integrated circuits or by interconnecting an appropriate network of conven- tional component circuits, as will be appreciated by those skilled in the electrical art(s) . Thus, the exam ^¬ ples 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. Com ^¬ puter 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 .

As stated above, the components of the example embodi ^¬ ments may include computer readable medium or memories for holding instructions programmed according to the teachings and for holding data structures, tables, rec ^¬ ords, and/or other data described herein. In an example embodiment, the application logic, software or an in ^¬ struction set is maintained on any one of various con- ventional 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, ap- paratus, 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, trans ^¬ mission media, and the like. 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 ex ^¬ pressly intended that all combinations of those ele ^¬ ments 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 dis- closed 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 cov ^¬ er the structures described herein as performing the recited function and not only structural equivalents, but also equivalent structures. The applicant hereby discloses in isolation each indi ^¬ vidual feature described herein and any combination of two or more such features, to the extent that such fea ^¬ tures 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 fea ^¬ tures or combinations of features solve any problems disclosed herein, and without limitation to the scope of the claims. The applicant indicates that the dis ^¬ closed aspects/embodiments may consist of any such in ^¬ dividual 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.