Patent Publication Number: US-9834405-B2

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

Description:
FIELD OF THE INVENTION 
     The invention relates generally to scheduling elevator cars in a group elevator system, and more particularly to assigning elevator cars to passengers with the help of uncertain information about arrivals of future passengers. 
     BACKGROUND OF THE INVENTION 
     Group elevator scheduling (GES) is a combinatorial optimization problem for a bank of two or more elevators. The most common instance of this problem deals with assigning elevator cars to passengers requesting an elevator car by means of an UP or DOWN button. In response to receiving the requests, a scheduler assign a car to each passenger so that a performance metric, for example an average waiting time (AWT) for all passengers, is minimized. The AWT is defined as a time interval from the moment a passenger makes the request until a car arrives, averaged over many requests. A large number of scheduling methods are known. However, there are significant obstacles to achieving an optimal AWT. 
     The first obstacle is the combinatorial complexity of the scheduling problem. If a building has an elevator bank with C cars and N passengers must be assigned to the cars, then there are C N  possible assignments, each resulting in a different AWT. Even for a small number of cars and passengers, determining an optimal assignment by an exhaustive search of all C N  assignments is not feasible, particularly given the relative short response times required. For this reason, multiple heuristic and approximate methods have been developed, see Nikovski U.S. Pat. No. 7,546,905, “System and method for scheduling elevator cars using pairwise delay minimization,” U.S. Pat. No. 7,484,597, “System and method for scheduling elevator cars using branch-and-bound,” U.S. Pat. No. 7,014,015, “Method and system for scheduling cars in elevator systems considering existing and future passengers, and U.S. 20030221915, “Method and system for controlling an elevator system.” In U.S. Pat. No. 7,014,015, Nikovski describes a scheduling method where future requests are predicted at the main floor, and the waiting times for such future requests are included in the decision process. A shortcoming of that method is that only future requests at the main floor are considered. 
     The second obstacle to minimizing the AWT is due to incomplete, untimely and inaccurate information. For example, most hall call requests do not include a destination floor, but only an UP or DOWN direction. Typically, the destination floor is only indicated after the passenger enters the car. One approach of dealing with this problem is to assume a particular destination, for example, the last floor in the requested direction. A different approach determines the AWT for all possible destinations using a method to reduce the AWT with respect to arbitrarily selecting a single destination floor, see Nikovski et al., “Method and system for controlling an elevator system, U.S. Pat. No. 6,672,431. However, that method still cannot compensate for the lack of precise information. More advanced signaling mechanisms have been considered, including direct specification of the destination floor by means of an input panel outside the elevator for Destination Control (DC) scheduling. As a significant disadvantage, this increases the cost of the system, and is typically only used at the main floor, if at all. 
     A third obstacle is the inability to predict future requests and destinations. Typically, the scheduler can only service known requests and destinations. As a result, most schedulers use an empty-the-system algorithm (ESA), see Bao et al., “Elevator dispatchers for down-peak traffic,” Technical report, University of Massachusetts, 1999. In ESA schedulers, all future passenger arrivals are ignored, which is an obvious inaccuracy with respect to what will actually happen to the elevator system. A major problem with the ESA is its inability to predict future requests. In effect, the ESA makes a schedule that can result in all cars being positioned in only one small part of the building, leaving large parts uncovered. The reason for this is that all terminal positions of the cars are considered equally good, as long as no passengers are waiting so there is no reason to prefer one position over another. 
     Conventional GES systems typically deal with the lack of information and limited computing resources by simplifying the optimization problem. Several simplification can be used. 
     In one method, mutual delays due to the assignment of two or more passengers h to the same car are ignored. The selected car is c*=argmin c W c (h|Ø), where W c  is a function that expresses the waiting time of one or more passengers given that another set of zero or more passengers are also assigned to the same car, and Ø is the null set. This simplification reduces the scheduling problem to selecting the car that minimizes the waiting time W for passenger h, regardless of whether other passengers have been or will be assigned to the same car. That method ignores the delays that existing passengers assigned to the same car would cause to the current passenger, as well as the delays the current passenger making the request and to be scheduled would cause to the existing passengers. 
     The most common scheduling method used in conventional GES systems accounts for interdependence of assigned passengers, but ignores future passengers. That method determines the best possible assignment for passengers that have requested service, but have not boarded a car yet. Because AWT minimization reduces to finding an assignment that would load the existing passengers into cars as fast as possible, this kind of methods are also known as empty-the-system-methods (ESA). Let H(t) represent the set of passengers who have arrived by time t, but have not been served yet and are still waiting. Then, the goal is to find assignments for the passengers in H(t) that minimizes their cumulative waiting time W (H(t)) . 
     In an immediate assignment mode, the assignment for the current passenger h is made immediately and never reconsidered. In this mode, it is sufficient to determine a marginal waiting time
 
Δ W   c ( h )≐ W   c ( h∪H   c ( t )| h∪H   c ( t ))− W   c ( H   c ( t )| H   c ( t ))
 
for each car c, and assign h to the car with the shortest marginal waiting time ΔW c (h). That is, the scheduler tentatively assigns the passenger h to each car in turn, and selects the car that marginally increases the waiting time. The marginal increase in the waiting time can be written as
 
Δ W   c ( h )= W   c ( h|H   c ( t ))+Σ g∈H     c     (t)   [W   c ( g|H   c ( t )∪ h )− W   c ( g|H   c ( t ))],
 
where g ranges over all passengers in the set H c .
 
     The first term in the marginal increase is the time needed to serve the passenger h with car c. It also accounts for stops that car has to make due to other passengers in the set H c (t) already assigned to car c. The remaining terms in the sum account for the increase in waiting time passenger h causes to the passengers already in the set H c (t), when also assigned to c. 
     In a reassignment mode, any passenger&#39;s assignment could be reassigned at any time when new information is received, including, but not limited to, new arrivals. Effectively, the total waiting times W(H(t)) for every possible assignment is predetermined, but for the passengers in the set H(t), ignoring past and future passengers. Although the resulting set is much smaller than the set H, an exhaustive search is still rarely feasible. 
     Some methods consider future arrivals at the main floor. Even this limited consideration of future arrivals can result in considerable reduction of the AWT during, for example, a peak up traffic time in the morning, see U.S. Pat. No. 7,014,015, “Method and system for scheduling cars in elevator systems considering existing and future passengers.” As a limitation, that method only considers future arrivals at a single (main) arrival floor, such as a building lobby. 
     Another practically beneficial method for consideration of future arrivals is described by Suzuki et al. in U.S. 20130186713. An elevator system parks empty cars at floors having a high frequency of use. The system includes a remote call device to perform a hall call registration at a distance from the elevator. The time for moving the elevator car from the parking floor is compared with the walking time to elevator. A determination is made whether or not to perform a standby operation based on the result of the comparison of the times. 
     Suzuki et al., “Elevator supervisory control system with cars cooperative method,” Proceedings of the ELEVCON&#39;06 World Elevator Congress, pp. 338-346, 1206, simulate an imaginary additional request at each floor for each real request, and the best schedule that can handle both real and imaginary requests, even for a most unfavorable floor for the imaginary request, is selected. While that method significantly improves over the ESA methods, the method still considers only one future request, and the time of the imaginary and actual requests are coincident. 
     In U.S. Pat. No. 8,220,591, Attala et al. describe a scheduling method for a group of elevators using advance traffic information. The advance traffic information is used to define a “snapshot” problem to improve performance for passengers. To solve the snapshot problem, an objective function is transformed to facilitate the decomposition of the problem into individual car subproblems. The subproblems are independently solved using a two-level formulation, with passenger to car assignment at a higher level, and the dispatching of individual cars at a low level. The primary disadvantage of that method is that future arrivals are assumed to occur with complete certainty, e.g., requests are made on a keypad located at a distance from the elevators, cameras or other sensors in corridors leading to the elevators detest approaching passengers, identification card readers or a hotel conference schedule system supply arrival information at an increased costs. However, complete certainty still cannot be reasonably expected in an actual practical system. 
     It is desired to provide an optimal scheduling strategy for group elevator systems that takes advance information about uncertain future passenger arrivals into consideration. 
     SUMMARY OF THE INVENTION 
     The embodiments of the invention provide a method and system for scheduling elevator cars in a group elevator system of a building, and more particularly to assigning elevator cars to passengers using uncertain information about arrival times of future passengers at any floor of the building. It is an objective of the invention to determine a schedule for the elevator cars that optimizes a performance metric, for example, an average waiting time (AWT) for all passengers. Furthermore, it is desired to perform the scheduling in real time. 
     The embodiments use information about expected arrivals of future passengers, and consider the uncertainty in that information. The invention can also operate in an immediate assignment mode. This means that every time a request for an elevator car is received, the car that services the passenger is determined immediately, and the request is not reconsidered. The scheduling also considers arrival information stored in a table. The arrival information can include data acquired by sensors located in the building, and arrival statistics such as the probability of service requests by the future passengers and the probability of possible times of the service requests. 
     The possible arrival times of the future passengers are represented by probabilistic variables, e.g., using a statistical distribution such as a Gauss-Bernoulli distribution, a Poisson distribution, a Weibull distribution, or another appropriate distribution. The probabilistic variables can be based on past passenger arrival information, as well sensed presence of potential passengers in other parts of the building. The probabilistic variables can be parameterized by a probability distribution of arrival floor and time of arrival. This probability distribution can have a specific parametric form, such as a Gaussian distribution, a Weibull distribution, etc. Passengers who have not been sensed, but could arrive within a future time interval, are characterized by an arrival rate, under the assumption of a Poisson arrival process, where the times between arrivals come from an exponential distribution. 
     Based on the arrival information, the scheduler can generate multiple possible continuation sets, e.g., by drawing samples from the Gauss-Bernoulli or Poisson variables for the future passengers. Then, the scheduler determines the optimal car assignment for the passenger that has just arrived by averaging the AWT of all passengers over all continuation sets, after finding suitable assignments for all future passengers in the continuation sets. 
     For a recently arrived passenger, the car assigned to the passenger is the same over all continuation sets, but for future arrivals, a passenger sampled from the same entry in the table of arrival times of future passengers does not necessarily have to be assigned to the same car over all continuation sets. 
     In the preferred embodiment, future passengers are assigned to cars using an immediate assignment mode, where every passenger is assigned in the order of arrival, and assignment takes into consideration passengers arrived so far, but ignores passengers who arrive later in the continuation set. In another embodiment, all future passengers are assigned jointly, such that every passenger&#39;s assignment takes into consideration assignments of all other passengers, regardless of whether the other passengers arrived before or after that passenger. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1A  is a block diagram of a method and system for scheduling elevator cars— 102  in a group elevator system for passengers; 
         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; 
         FIG. 2  is a flow diagram of a method for scheduling passengers in a group elevator system according to embodiments of the invention. 
         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 
         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 
     General Scheduling Method 
       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 . 
     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 . 
     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 . 
     The method operates continuously and in real time. 
     Realized Future Arrival Times 
     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. 
     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. 
     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. 
     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&#39;s arrival times, as manifested in the different sampled arrival times in the three continuations. 
     Sensors 
     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. 
     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 i  that the person will request elevator service can be determined by correlating sensed data with actual service requests. 
     Historical Information 
     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. 
     Probabilitic Model 
     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 μ l =s l /ν be the time to travel a distance of length s 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&#39;s realized arrival time and request for service can be determined from the probability distribution  120  with probability p l , in time Δt sampled from a suitable distribution, for example, a Gaussian distribution t:N(μ l ,σ l   2 ) with a mean μ. The variance σ l   2  can also be obtained from data acquired by the sensors. 
     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 . 
     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. 
     Group Elevator Scheduling 
     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. 
     For a set H of passengers {h 1 ,h 2 , . . . , h N } arriving during an interval of time, a passenger h i  can be represented by a tuple (t i , o i , d i ), where t i  is the arrival time, o i  is the arrival floor, and d 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 c , such that H=H 1 ∪H 2 ∪ . . . ∪H C , and H i ∩H j  is the null set Ø when i≢j. 
     A waiting time for a passenger h in a set A assigned to a car c is W 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 c (H|A), when all of those passengers are assigned to car c. The sets H and A are not necessarily the same. 
     In general, the waiting time W 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 c (H|A) can be completely determined for a given combination of the sets H and A and the position of car c. 
     For a given full assignment, the total waiting time W(H) for all passengers in the set H can be expressed as 
                       W   ⁡     (   H   )       =         ∑     c   =   1     C     ⁢           ⁢       W   c     ⁡     (       H   c     ❘     H   c       )         =       ∑     c   =   1     C     ⁢       ∑     h   ⁢           ⁢   ε   ⁢           ⁢     H   c         ⁢       W   c     ⁡     (     h   ❘     H   c       )               ,           (   1   )               
and the AWT of the passengers in the set H is W(H)/N. There are C 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.
 
     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 1 &lt;t&lt;t 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. 
     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 i , t i &lt;t includes the destination floor d i . For a conventional non-DC systems, that information is not available, and only the desired direction of motion u i =sign(d i −o i ) of passenger h 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. 
     Passengers Arriving in the Future 
     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 . 
     For times t i &lt;t&lt;t i+1  between arriving passengers h i  and h i+1 , it is possible to generate  220  n possible continuation sets {hacek over (H)} 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. 
     As defined herein, a continuation set  221 
 
{hacek over (H)} j ( t )≐{ h   1   ,h   2   , . . . , h   i   ,{hacek over (h)}   j,i+1   ,{hacek over (h)}   j,i+2   , . . . , {hacek over (h)}   j,m     j   }
 
includes information  211  about:
         historically known       

     assigned passengers h waiting for a car; 
     current passenger h making a request; and
         unknown       

     future passengers {hacek over (h)}. 
     Here, {hacek over (h)} j,i+k  is the k th  future passenger in continuation set {hacek over (H)} j (t). The number m 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. 
     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)} j (t), it is possible to determine  230  an optimal cumulative waiting time (CWT)  231  similarly to equation (1): 
                       W   ⁡     [         H   ⋓     j     ⁢     (   t   )       ]       =         ∑     c   =   1     C     ⁢       W   c     ⁡     (           H   ⋓     jc     ⁡     (   t   )       ❘         H   ⋓     jc     ⁡     (   t   )         )         =       ∑     c   =   1     C     ⁢       ∑     h   ⁢           ⁢   ε   ⁢           ⁢       H   ⋓     jc         ⁢       W   c     ⁡     (     h   ❘         H   ⋓     jc     ⁡     (   t   )         )               ,           (   2   )               
where {hacek over (H)} jc (t) denotes the set of passengers in continuation set {hacek over (H)} j (t)assigned to car c. The AWT for that assignment can be determined  240  as
 
Σ j=1   n   W[{hacek over (H)}   j ( t )]/ m   j )/ n 241.   (3)
 
     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. 
     Special care is taken that in all n continuation sets, the passengers h i  with arrival times t i &lt;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. 
     Immediate Assignment 
     In this mode, the current passenger h is tentatively assigned  250  to car c with a marginal waiting time (MWT)  251 
 
Δ W   c ( h )≐ W   c ( h|H   c ( t ))+Σ g∈H     c     (t)   [W   c ( g|H   c ( t )∪ h )− W   c ( g|H   c ( t ))],   (4)
 
where g ranges over all passengers tentatively assigned to car c.
 
     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)} j,i+k , when their marginal waiting times are determined as 
                   Δ   ⁢           ⁢       W   c     ⁡     (       h   ⋓       j   ,     i   +   k         )         ≐         W   c     ⁡     (         h   ⋓       j   ,     i   +   k         ❘         H   ⋓     jc     ⁡     (     t     i   +   k   -   1       )         )       +       ∑     g   ⁢           ⁢   ε   ⁢           ⁢         H   ⋓     jc     ⁡     (     t     i   +   k   -   1       )           ⁢           ⁢     [         W   c     ⁡     (     g   ❘           H   ⋓     jc     ⁡     (     t     i   +   k   -   1       )       ⋃       h   ⋓       j   ,     i   +   k             )       -       W   c     ⁡     (     g   ❘         H   ⋓     jc     ⁡     (     t     i   +   k   -   1       )         )         )           ]     ,         
where Ĥ jc (t i+k−1 ) denotes the set of future passengers that have arrived before time t i+k , and have already been assigned to car c.
 
     Then, the current passenger h is tentatively assigned to one of the continuation sets {hacek over (H)} jc (t i+k−1 ), and one can account for the mutual effects between known passenger h and the unknown future passenger {hacek over (h)} j,i+k . 
     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 i+k  before assigning passenger {hacek over (h)} j,i+k . Due to the low complexity, this is the preferred embodiment of the invention. 
     Immediate Assignment of the Current Passenger with Reassignment for Future Passengers 
     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. 
     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. 
     Reassignment Mode 
     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)} j (t) with an associated increase in the computational time. 
     Regardless of which mode is used, the Monte Carlo scheduling method operates in a rolling horizon manner. After passenger h i  has been assigned (temporarily or permanently) at time t i , using the n sets {hacek over (H)} j (t i ), when the next passenger h i+1  arrives at time t i+1 , new continuation sets {hacek over (H)} j (t i+1 ) are generated from an information vector I(t i+1 ). 
     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. 
     Time-Dependent Poisson Processes 
     In its simplest form, the information I(t) available at time t includes the most recent estimates of the arrival rates λ 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 λ 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 λ 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 . 
     Scheduling Passengers using Continuation Sets 
       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. 
     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. 
     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.