Method and system for scheduling elevator cars in a group elevator system with uncertain information about arrivals of future passengers

Abstract

A method schedules elevator cars in a group elevator system in a building by first generating a set of probability distributions for arrivals of future passengers at any floor of the building, wherein the set of probability distributions are characterized by probabilistic variables that specify arrival information of the future passengers, wherein the arrival information includes a probability of service requests by the future passengers and a probability of possible times of the service requests. A schedule for the elevator cars is based on the set of probabilistic distribution. Then, the schedule is provided to a controller of the group elevator system to move the elevator cars according to the schedule.

Claims

1. A method for scheduling elevator cars in a group elevator system in a building, wherein a decision of which an elevator car serves a newly arrived passenger in time is made at a time of arrival of the newly arrived passenger, and not at a later time, comprising steps of: registering a request for service by the newly arrived passenger by a signal at an elevator landing; accessing data from a memory, wherein the data includes arrival information of future passengers, wherein the processor is in communication with the memory, and the processor is configured for: generating a set of probability distributions for arrivals of future passengers at any floor of the building, wherein the set of probability distributions are characterized by probabilistic variables that specify arrival information of the future passengers, wherein the arrival information includes a probability of a number of service requests by the future passengers and a probability of a possible number of times of the service requests; determining a schedule for the elevator cars based on the set of probabilistic distribution using the arrival information by generating multiple continuation sets from some probabilistic variables of the probabilistic variables for arrivals of future passengers, and determining an optimal elevator car assignment for the newly arrived passenger that registered the request for service, by averaging an average waiting time (AWT) of all newly arrived passengers over all continuation sets, after finding assignments for all future passengers in the continuation sets of the multiple continuation sets; and providing the schedule to a controller of the group elevator system to move the elevator cars according to the schedule, wherein the processor is in communication with the controller.

2. The method of claim 1, wherein the probabilistic variables are determined using a statistical distribution including a Gauss-Bernoulli distribution or a Poisson distribution or an another distribution, that is based on historical passenger arrival information.

3. The method of claim 1, wherein the arrival information is based on arrival history information acquired by sensors, such that the arrival history information includes arrival statistics stored in a table in the memory.

4. The method of claim 1, wherein the scheduling is performed in real time.

5. The method of claim 1, wherein the arrival information is based on arrival history information acquired by sensors in the building, such that the sensors include motion detectors.

6. The method of claim 5, further comprising: correlating sensed data with actual service requests via registered requests for service by the newly arrived passengers, such that the sensed data includes a sensed presence of potential passengers in other locations of the building.

7. The method of claim 1, wherein the scheduling minimizes an average waiting time.

8. The method of claim 1, wherein schedule includes passengers that have made requests for service.

9. The method of claim 1, wherein the probability distributions for arrival times of the future passengers are characterized by Gauss-Bernoulli variables.

10. The method of claim 1, wherein the probability distributions for arrival rates of the future passengers are characterized by Poisson variables.

11. The method of claim 1, further comprising: sampling the arrival information to generate multiple continuation sets, wherein each continuation set includes information about assigned waiting passengers, a current requesting passenger, and future passengers, and wherein arrival of future passenger arrivals are sampled from the set of probability distributions.

12. The method of claim 11, wherein a length of the continuation sets vary from minutes to hours, and further comprising: determining an optimal cumulative waiting time for all continuation sets, over all possible assignments of the passengers represented in the multiple continuation sets.

13. The method of claim 11, wherein the current requesting passenger and the future passengers are all scheduled in an immediate assignment mode.

14. The method of claim 11, wherein the current requesting passenger is scheduled in an immediate assignment mode, and the future passengers are scheduled in a reassignment mode.

15. The method of claim 11, wherein the current requesting passenger and the future passengers are all scheduled in a reassignment mode.

16. A system for scheduling elevator cars in a group elevator system in a building, wherein a decision of which an elevator car serves a newly arrived passenger in time is made at a time of arrival of the newly arrived passenger, and not at a later time, comprising: a memory having stored data including arrival information of future passengers; a processor in communication with the memory, is configured to: register a request for service by the newly arrived passenger by a signal at an elevator landing; generate probability distributions for arrivals of future passengers at any floor of the building, wherein the probability distributions are characterized by probabilistic variables that specify arrival information of the future passengers, wherein the arrival information includes a probability of a number of service requests by the future passengers and a probability of a possible number of times of the service requests; determine a schedule for the elevator cars based on the probabilistic distributions using the arrival information by generating multiple continuation sets from some probabilistic variables of the probabilistic variables for arrivals of future passengers, and determining an optimal elevator car assignment for the newly arrived passenger that registered the request for service, by averaging an average waiting time (AWT) of all newly arrived passengers over all continuation sets, after finding assignments for all future passengers in the continuation sets of the multiple continuation sets; and a controller of the group elevator system to move the elevator cars according to the schedule.

17. A method for scheduling elevator cars in a group elevator system in a building, wherein a decision of which an elevator car serves a newly arrived passenger in time is made at a time of arrival of the newly arrived passenger, and not at a later time, comprising: registering a request for service by the newly arrived passenger by a signal at an elevator landing; accessing data from a memory, wherein the data includes arrival information of future passengers, wherein the processor in communication with the memory, is configured for: generating a set of probability distributions for arrivals of future passengers at any floor of the building, wherein the set of probability distributions are characterized by probabilistic variables that specify arrival information of the future passengers, wherein the arrival information includes a probability of a number of service requests by the future passengers and a probability of a possible number of times of the service requests; determining a schedule for the elevator cars based on the set of probabilistic distribution using the arrival information by generating multiple continuation sets from some probabilistic variables of the probabilistic variables for arrivals of future passengers; determining an optimal elevator car assignment for the newly arrived passenger that registered the request for service; and providing the schedule to a controller of the group elevator system to move the elevator cars according to the schedule, wherein the processor is in communication with the controller.

18. The system of claim 17, wherein determining the optimal elevator car assignment for the newly arrived passenger that registered the request for service is by averaging an average waiting time (AWT) of all newly arrived passengers over all continuation sets, after finding assignments for all future passengers in the continuation sets of the multiple continuation sets.

19. The method of claim 17, wherein the probabilistic variables are determined using a statistical distribution including a Gauss-Bernoulli distribution or a Poisson distribution or an another distribution, that is based on historical passenger arrival information.

20. The method of claim 17, wherein the arrival information is based on arrival history information acquired by sensors, such that the arrival history information includes arrival statistics stored in a table in the memory.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1A is a block diagram of a method and system for scheduling elevator cars—102 in a group elevator system for passengers;

(2) FIG. 1B is a schematic of a probability distribution model of arrival times of future passengers characterized by probabilistic variables in the form of Gauss-Bernoulli variables;

(3) FIG. 2 is a flow diagram of a method for scheduling passengers in a group elevator system according to embodiments of the invention.

(4) FIG. 3 is a schematic of an exponential probability distribution for arrival times of future passengers not sensed, characterized by a Poisson arrival process according to embodiments of the invention; and

(5) FIG. 4 is a schematic of predictive group elevator scheduling with two continuation sets according to embodiments of the invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

(6) General Scheduling Method

(7) FIG. 1A shows a block diagram of a method and system for scheduling elevator cars 101-102 in a group elevator system 110 in a building having multiple floors 103. A set of probability distributions 120 of realized arrivals of future passengers 140 is estimated 130.

(8) Future passengers are those passengers that have not made a request for service by pressing an UP or DOWN button. At the time of the current request, all future passengers are imagined. The set of probability distribution 120 is characterized by probabilistic variables that specify the uncertain process of future arrivals, e.g., a probability of service requests 121 by the future passengers and a probability of possible times 122 of the service requests. The information can be obtained from sensors 151 or arrival history statistics 152.

(9) The set of probability distribution is stored in an arrival information history table 150. Any time a new current passenger request for service 450 is registered, samples from the probability distributions 120 stored in that table 150 are drawn, and combined with the existing unserved passengers 145 to generate continuation sets that are used to determine 160 a suitable schedule 170 for both existing and potential future passengers. It is understood that the schedule includes passengers whose arrival time is known because an UP or DOWN button has been pressed to make a request for service. The continuation sets are described in greater detail below with reference to FIG. 4.

(10) The method operates continuously and in real time.

(11) Realized Future Arrival Times

(12) Following is an example scenario that explains realized future arrival times according to embodiments of the invention. A potential future passenger, with a probability p=0.7 of requesting service, is sensed at a remote location at 10:00:00 am. Suppose that the distance between the remote location and the elevator landing is 20 m, and the average walking speed of passengers is 1 m/s, but due to variations among different people, it can vary by 15%. Then, the time for this passenger to move to the elevator landing is 20 seconds±3 seconds. Under the assumption of normal (Gaussian) distribution of walking speed across the general population, a Gauss-Bernoulli variable for this passenger can be stored in the arrival information table 150, with probability p=0.7, mean μ=20 s, and standard deviation σ=3 s. This means that the expected time of his arrival at the elevator is 10:00:20.

(13) However, there is uncertainty in the expected time, e.g., ±3 seconds. Although, this may seem like a very small amount of time, it is noted that modern elevators can travel at speeds exceeding 15 msec. So the elevator could pass dozens of floors of waiting passengers in that time.

(14) In order to schedule under this uncertainty, we form n=3 continuation sets, by randomly sampling from the Gauss-Bernoulli variable. Suppose that in the first continuation, the arrival time ends up being 10:00:22, in the second continuation it is 10:00:19, and in the third continuation the passenger does not arrive at all. When scheduling the passengers in a continuation set, we order the sets by their sampled (realized, actuated) arrival times. For the passenger in the first continuation case, this would be 10:00:22, and not the expected time 10:00:20.

(15) By implementing the method, when scheduling actual passenger arriving in the near future, their assignment will take into consideration the possible arrival of this sensed passenger around 10:00:20, and this assignment would be robust with respect to the possible variations in this passenger's arrival times, as manifested in the different sampled arrival times in the three continuations.

(16) Sensors

(17) The sensors 151 can be installed in areas from which the future passengers can arrive. For example, the sensors can be motion detectors. Specific types of motion sensor can include cameras, such as surveillance cameras that are commonly located in corridors and hall on the various floors in the building, or proximity sensors that directly detect human motion. The floor can include above or below ground parking level floors.

(18) The sensors can be used to detect the people at multiple locations in a building, and not necessarily only at elevator doors or corridors leading to the elevators. In such a case, when a person is detected at location l, e.g., in a hallway fifty meter away from the elevator landing, the probability p.sub.i that the person will request elevator service can be determined by correlating sensed data with actual service requests.

(19) Historical Information

(20) The historical information obtained from, e.g., from UP and DOWN request at particular floors for specific times of day, days of the week, can be used to adjust the most recently observed actual arrival rates. Such predictive information can result in a reduction of the AWT when used with the predictive scheduler as described herein.

(21) Probabilitic Model

(22) As shown in FIG. 1B, a physical model can also be used to construct a probabilitic model of the probability of possible times of the service requests. Let μ.sub.l=s.sub.l/ν be the time to travel a distance of length s.sub.i between the sensing location l and the elevator door at a velocity ν, for example, 1 meter per second. Then, for any person sensed at location l, a passenger's realized arrival time and request for service can be determined from the probability distribution 120 with probability p.sub.l, in time Δt sampled from a suitable distribution, for example, a Gaussian distribution t:N(μ.sub.l,σ.sub.l.sup.2) with a mean μ. The variance σ.sub.l.sup.2 can also be obtained from data acquired by the sensors.

(23) The probability distribution is used to generate 160 a schedule 170. The schedule can then be provided to a controller 180 of the group elevator system 110 to move the elevators according to the schedule. The steps can be performed by a processor 190 designed to operate the group elevator system using the controller 180. The processor and controller can be connected by a communications link 165.

(24) As an advantage, the invention can schedule the elevators cars for the future passengers so that the arrival of the elevator cars and the future passengers approximately coincide at the various floors to minimize the average waiting times.

(25) Group Elevator Scheduling

(26) One objective of a group elevator scheduling (GES) system is to minimize an average waiting time (AWT) for all passengers that request elevator from a current time and during a future time interval. If the interval is finite, and an exact arrival sequence of the passengers is known, then it is possible, at least in theory, to determine optimal assignments of cars to passengers that minimize the AWT.

(27) For a set H of passengers {h.sub.1,h.sub.2, . . . , h.sub.N} arriving during an interval of time, a passenger h.sub.i can be represented by a tuple (t.sub.i, o.sub.i, d.sub.i), where t.sub.i is the arrival time, o.sub.i is the arrival floor, and d.sub.i is the destination floor. An assignment of the N passengers to C cars in a bank partitions the set H into C subsets H.sub.c, such that H=H.sub.1∪H.sub.2∪ . . . ∪H.sub.C, and H.sub.i∩H.sub.j is the null set Ø when i≢j.

(28) A waiting time for a passenger h in a set A assigned to a car c is W.sub.c(h|A) when all passengers in the set A are assigned to the car c. Similarly, a cumulative waiting time for all passengers in the set H is W.sub.c(H|A), when all of those passengers are assigned to car c. The sets H and A are not necessarily the same.

(29) In general, the waiting time W.sub.c(H|A) depends on a predetermined order in which the car c services the passengers in the set H∪A. Most elevator systems use a full collective policy where a car services all requests in one direction in sequence and then reverses and answers all calls in the opposite direction. When the car is empty and stopped, possible UP and DOWN directions are compared, and the one resulting in a shorter AWT is selected. Other possible service sequences that optimize the AWT are also possible. But regardless of the method selected, the resulting waiting time of W.sub.c(H|A) can be completely determined for a given combination of the sets H and A and the position of car c.

(30) For a given full assignment, the total waiting time W(H) for all passengers in the set H can be expressed as

(31) $\begin{array}{cc}W\left(H\right)=\underset{c=1}{\overset{C}{.Math.}}{W}_c\left(H_c.Math.H_c\right)=\underset{c=1}{\overset{C}{.Math.}}\underset{h\epsilon H_c}{.Math.}{W}_c\left(h.Math.H_c\right),& \left(1\right)\end{array}$
and the AWT of the passengers in the set H is W(H)/N. There are C.sup.N possible partitions of the set H into C subsets. With unlimited computational resources and/or a suitable combinatorial optimization method, the optimal assignment could perhaps be determined.

(32) However, even if such a computation was possible, there is a much more severe difficulty resulting from insufficient information. In practice, the GES system has only limited access to arrival information. At the current time t, somewhere within the time interval (t.sub.1<t<t.sub.N), the GES only has information about all request that occurred up to the current time t and states of the C cars in the bank.

(33) The typical conventional art GES system does not have access to future arrival events. In Destination Control (DC) scheduling, the request information for passenger h.sub.i, t.sub.i<t includes the destination floor d.sub.i. For a conventional non-DC systems, that information is not available, and only the desired direction of motion u.sub.i=sign(d.sub.i−o.sub.i) of passenger h.sub.i is available. Moreover, when a passenger arrives at an elevator where other passengers are already waiting, the newly arrived passenger usually does not press the UP or DOWN button if the button has already been selected. This effectively “hides” the arrival of those new passenger from the system.

(34) Passengers Arriving in the Future

(35) As shown in FIG. 2, one way to improve performance of the GES is to predict the intentions of the future passengers 140. Although this is impossible in practice, one can still acquire 210 available passenger information 211. The arrival information can include historical information 152 about assigned waiting passengers, a current requesting passenger, and future passengers 140, e.g., information sensed by sensors 151.

(36) For times t.sub.i<t<t.sub.i+1 between arriving passengers h.sub.i and h.sub.i+1, it is possible to generate 220 n possible continuation sets {hacek over (H)}.sub.j(t) 221, 1≦j≦n of passengers that have arrived and that can possible arrive in the future, see FIG. 3 for detail of passengers and timing.

(37) As defined herein, a continuation set 221
{hacek over (H)}.sub.j(t)≐{h.sub.1,h.sub.2, . . . , h.sub.i,{hacek over (h)}.sub.j,i+1,{hacek over (h)}.sub.j,i+2, . . . , {hacek over (h)}.sub.j,m.sub.j}
includes information 211 about: historically known

(38) assigned passengers h waiting for a car;

(39) current passenger h making a request; and unknown

(40) future passengers {hacek over (h)}.

(41) Here, {hacek over (h)}.sub.j,i+k is the k.sup.th future passenger in continuation set {hacek over (H)}.sub.j(t). The number m.sub.j of passengers in each continuation sets can be different. Note that the existing passengers in all continuation sets are identical, that is, all continuations share the same past, but have different futures.

(42) Depending on computational resources and passenger arrival rates, a length l of time of the continuation sets can vary, e.g., from minutes to hours. Then, for each continuation set {hacek over (H)}.sub.j(t), it is possible to determine 230 an optimal cumulative waiting time (CWT) 231 similarly to equation (1):

(43) $\begin{array}{cc}W\left[{\stackrel{.Math.}{H}}_j\left(t\right)\right]=\underset{c=1}{\overset{C}{.Math.}}{W}_c\left({\stackrel{.Math.}{H}}_{\mathrm{jc}}\left(t\right).Math.{\stackrel{.Math.}{H}}_{\mathrm{jc}}\left(t\right)\right)=\underset{c=1}{\overset{C}{.Math.}}\underset{h\epsilon {\stackrel{.Math.}{H}}_{\mathrm{jc}}}{.Math.}{W}_c\left(h.Math.{\stackrel{.Math.}{H}}_{\mathrm{jc}}\left(t\right)\right),& \left(2\right)\end{array}$
where {hacek over (H)}.sub.jc(t) denotes the set of passengers in continuation set {hacek over (H)}.sub.j(t)assigned to car c. The AWT for that assignment can be determined 240 as
Σ.sub.j=1.sup.nW[{hacek over (H)}.sub.j(t)]/m.sub.j)/n241.   (3)

(44) Although this computation is over n continuation sets, as opposed to only one set of passengers as in equation (1), it would not necessarily take more time. Equation (2) involves the entire arrival stream, possibly over a very long interval of time. However, the duration of the n continuation sets can be adjusted according to the available computational resources.

(45) Special care is taken that in all n continuation sets, the passengers h.sub.i with arrival times t.sub.i<t are assigned to the same car in every continuation set. Outside of this consideration, any practical method for minimizing the AWT, e.g., an empty-the-system method, can be used Immediate assignment and reassignment modes can be used.

(46) Immediate Assignment

(47) In this mode, the current passenger h is tentatively assigned 250 to car c with a marginal waiting time (MWT) 251
ΔW.sub.c(h)≐W.sub.c(h|H.sub.c(t))+Σ.sub.g∈H.sub.c.sub.(t)[W.sub.c(g|H.sub.c(t)∪h)−W.sub.c(g|H.sub.c(t))],   (4)
where g ranges over all passengers tentatively assigned to car c.

(48) Note that future passengers are ignored in the first term. However, this assignment has an effect on the waiting time of future passengers {hacek over (h)}.sub.j,i+k, when their marginal waiting times are determined as

(49) $\Delta W_c\left({\stackrel{.Math.}{h}}_{j,i+k}\right)\doteq W_c\left({\stackrel{.Math.}{h}}_{j,i+k}.Math.{\stackrel{.Math.}{H}}_{\mathrm{jc}}\left(t_{i+k-1}\right)\right)+\underset{g\epsilon {\stackrel{.Math.}{H}}_{\mathrm{jc}}\left(t_{i+k-1}\right)}{.Math.}\left[W_c\left(g.Math.{\stackrel{.Math.}{H}}_{\mathrm{jc}}\left(t_{i+k-1}\right).Math.{\stackrel{.Math.}{h}}_{j,i+k}\right)-W_c\left(g.Math.{\stackrel{.Math.}{H}}_{\mathrm{jc}}\left(t_{i+k-1}\right)\right)\right)],$
where Ĥ.sub.jc(t.sub.i+k−1) denotes the set of future passengers that have arrived before time t.sub.i+k, and have already been assigned to car c.

(50) Then, the current passenger h is tentatively assigned to one of the continuation sets {hacek over (H)}.sub.jc(t.sub.i+k−1), and one can account for the mutual effects between known passenger h and the unknown future passenger {hacek over (h)}.sub.j,i+k.

(51) This assignment mode has a relatively low complexity, compared to exhaustive searches, is linear in the number of future arrivals, but does not necessarily determine the most optimal assignment for all passengers in the continuation set, because this mode only considers passengers that have arrived at times t.sub.i+k before assigning passenger {hacek over (h)}.sub.j,i+k. Due to the low complexity, this is the preferred embodiment of the invention.

(52) Immediate Assignment of the Current Passenger with Reassignment for Future Passengers

(53) The immediate assignment mode requires that the assignment for the current passenger is made immediately and never reconsidered. However, there is no such restriction of assignments for the future passengers. This makes it possible, at least in principle, to reconsider the assignment. However, this can lead to a significant increase in computation, and also might not correspond to the way scheduling is performed.

(54) For example, suppose that one of the n continuation sets actually occurs in the future, even though this is not very probable, but not impossible. In that case, the assignments for requests are performed in the immediate mode, and reassignment is not allowed. So, if a good partitioning has been determined in the reassignment mode, then it can be missed in the immediate assignment mode, and that is why reassignment should probably not be used when scheduling future passengers.

(55) Reassignment Mode

(56) When a computationally efficient procedure is available to determine the optimal assignment of an entire continuation set of passengers, it can also be effectively used for Monte Carlo evaluation on the expanded continuation sets {hacek over (H)}.sub.j(t) with an associated increase in the computational time.

(57) Regardless of which mode is used, the Monte Carlo scheduling method operates in a rolling horizon manner. After passenger h.sub.i has been assigned (temporarily or permanently) at time t.sub.i, using the n sets {hacek over (H)}.sub.j(t.sub.i), when the next passenger h.sub.i+1 arrives at time t.sub.i+1, new continuation sets {hacek over (H)}.sub.j(t.sub.i+1) are generated from an information vector I(t.sub.i+1).

(58) A number of options are possible for the format of the information vector I(t) depending on the type of sensing information. A general format that can be used for generation of the Monte Carlo continuation sets is independent of the sensors. This format is a matrix of stochastic processes, specifying an arrival process for each pair of origin and destination floors.

(59) Time-Dependent Poisson Processes

(60) In its simplest form, the information I(t) available at time t includes the most recent estimates of the arrival rates λ.sub.i(t) for each floor i. These estimates can be obtained by estimating the number of people boarding cars at particular floors using the sensors 151. The sensor can be a weight sensor in the elevator, a motion sensor at the elevator door, or a camera with a view of the door. To obtain arrival rates λ.sub.ij(t) for pairs of origin-destination floors, disembarkation rates can also be determined from sensor statistics and iterative proportional fitting. After the arrival rates λ.sub.ij(t) have been determined and the arrival process is assumed to have a Poisson distribution 300, then it is possible to generate a probability distribution 120 for arrival rates of future passengers characterized by Poisson variables for the continuation set from any starting time 301 as shown in FIG. 3.

(61) Scheduling Passengers using Continuation Sets

(62) FIG. 4 is a schematic of predictive group elevator scheduling with two continuation sets 401-402 according to embodiments of the invention. It is understood that there can be any number of continuation sets. In FIG. 4, the arrival time t 410 runs down. The time is partitioned into a time interval 411 for passengers whose requests have been served, a time interval 412 for passengers with assignments that have not yet been served, a current time 413, and a future time interval 415. The solid UP 421 and DOWN 422 symbols indicate request made by already arrived passengers, and the dashed symbols 431 and 432 indicate potential requests by future passengers. The letters A 441 and B 442 represent cars, two in this case. In the time interval 411 the consecutive choice of cars is arranged as a decision tree. During the future time interval 415, it is preferred that requests are fulfilled in immediate assignment mode.

(63) The AWT over all continuation sets is computed for each tentative assignment of the current passenger request 450 (in this case, to either car A or car B), and then the car choice with the shortest AWT is used to make the assignment for the current passenger request 450 at the current time 413. In other words, the scheduler compares how long the existing passenger and a set of possible future passengers would wait, across all possible options (cars) available at the current point in time. The multiple number of continuations ensures that this calculation considers not only one, but many more possible future realizations of the passenger arrival stream, arising from the uncertainty in future arrivals.

(64) Although the invention has been described by way of examples of preferred embodiments, it is to be understood that various other adaptations and modifications can be made within the spirit and scope of the invention. Therefore, it is the object of the appended claims to cover all such variations and modifications as come within the true spirit and scope of the invention.