System and method for group elevator scheduling based on submodular optimization

Abstract

Systems and Methods for controlling a movement of cars of an elevator system. A processor determines for each car an individual waiting time of each hall call. Determines for each pair of hall calls assigned for each car, a pairwise delay over the individual waiting time of each hall call in the pair caused by a joint assignment of the car to the pair of the hall calls. Approximate a cumulative waiting time of an assignment of the cars to the hall calls as a sum of individual waiting times for each hall call with the assigned car and a sum of all pairwise delays determined between all pairs of hall calls assigned to the same car. Determine the assignment of the cars using a greedy optimization algorithm that greedily assigns hall calls to the cars to minimize the approximated cumulative waiting time, and control the movement of the cars.

Claims

1. A system for controlling a movement of a plurality of elevator cars of an elevator system, comprising: at least one input interface for accepting a plurality of hall calls requesting service of the plurality of elevator cars to different floors of a building; a processor in communication with the input interface is configured to determine, for each elevator car, an individual waiting time of accommodating each hall call, if the hall call is the only hall call assigned to the elevator car; determine, for each pair of hall calls assigned to each elevator car, a pairwise delay over the individual waiting time of each hall call in the pair caused by a joint assignment of the elevator car to accommodate the pair of the hall calls; approximate a cumulative waiting time of an assignment of the plurality of elevator cars to accommodate the plurality of hall calls as a sum of individual waiting times for accommodating each hall call with the assigned elevator car, and a sum of all pairwise delays determined between all pairs of hall calls assigned to the same elevator car; and determine the assignment of the plurality of elevator cars using a greedy optimization algorithm that greedily assigns the plurality of hall calls to the plurality of elevator cars to minimize the approximated cumulative waiting time; and a controller for controlling the movement of the plurality of elevator cars according to the assignment.

2. The system of claim 1, wherein the greedy optimization algorithm is an algorithmic paradigm that determines at an initial step, an assignment of an unassigned first hall call, based on a locally optimal choice determined at a time of the initial step, then proceeds to the next step or the next successive unassigned hall call.

3. The system of claim 2, wherein the locally optimal choice identifies at each step, a combination of an unassigned hall call from all the remaining unassigned hall calls and an elevator car from the plurality of elevator cars, that results in a least increase in a waiting time for all assigned hall calls including the first hall call, while considering all previous assigned hall calls, then the combination is accepted and the hall call is assigned without further consideration and removed from all the remaining unassigned hall calls.

4. The system of claim 1, wherein the greedy optimization algorithm starts with an empty set of assignments of hall calls needing to be assigned, such that at every step including an initial step which starts with a first hall call, is added to the set of assignments of hall calls needing to be assigned, so as to result in a total of N steps, until all unassigned hall calls are assigned.

5. The system of claim 4, wherein each step in the total of N steps includes a hall call for every passenger to be moved between floors of the building, such that during each step, an unassigned hall call from a passenger is considered sequentially in time, and is initially added to an elevator car of the plurality of elevator cars successively.

6. The system of claim 5, wherein for every combination of the hall call and the elevator car, the greedy optimization algorithm computes a cumulative waiting time of all hall calls assigned at that moment in time, plus the first hall call assigned at the initial step.

7. The system of claim 6, wherein the hall call and the elevator car combination having a least increase in the cumulative waiting time for all assigned hall calls including the first hall call of the initial step, the combination is accepted, and the hall call is assigned and removed from all the remaining unassigned hall calls, then continues to the next step or the next successive unassigned hall call.

8. The system of claim 1, wherein the greedy optimization algorithm is based on optimizing the approximated cumulative waiting time in N steps, where N is a number of unassigned hall calls from passengers waiting to be assigned at a time at each step, such that two sets of coefficients are computed to construct a quadratic Boolean approximation of the cumulative waiting time of all the plurality of hall calls from passengers currently waiting to be assigned at the time of that step.

9. The system of claim 8, wherein the first set of coefficients of the two sets of coefficients includes w.sub.i.sup.c, such that w.sub.i.sup.c is a linear coefficient that is an expected waiting time of a hall call from a passenger h.sub.i, if the hall call is picked by an elevator car c, and no other hall call is picked up by that elevator car.

10. The system of claim 1, wherein the second set of coefficients of the two sets of coefficients includes w.sub.ij.sup.c, such that w.sub.ij.sup.c is a bilinear coefficient that is equal to the pairwise delay between hall calls from passengers h.sub.i and h.sub.j, based on a specific pick-up order of the two hall calls by the elevator car c, such that only one of the two hall calls is causing a delay to the other hall call, and the hall call that is picked-up first causes a delay for the hall call that is picked-up second.

11. A method for scheduling elevator cars of an elevator system, comprising: using at least one input interface for accepting a plurality of hall calls requesting the plurality of elevator cars to different floors of a building; determining independently, using a processor in communication with the input interface, for each elevator car, an independent waiting time of accommodating each hall call, if the hall call is the only hall call assigned to the elevator car; determining, for each pair of hall calls assigned for each elevator car, a pairwise delay over the individual waiting time of each hall call in the pair caused by a joint assignment of the elevator car to accommodate the pair of the hall calls; approximating a cumulative waiting time of an assignment of the plurality of elevator cars to accommodate the plurality of hall calls as a sum of individual waiting times for accommodating each hall call with the assigned elevator car and a sum of all pairwise delays determined for the assigned elevator car between all pairs of hall calls assigned to the same elevator car; determining the assignment of the plurality of elevator cars using a greedy optimization algorithm that greedily assigns the plurality of hall calls to the plurality of elevator cars to minimize the approximated cumulative waiting time; and using a controller for controlling the movement of the plurality of elevator cars according to the assignment.

12. The method of claim 11, wherein the greedy optimization algorithm is an algorithmic paradigm that determines at an initial step, an assignment of an unassigned first hall call, based on a locally optimal choice determined at a time of the initial step, then proceeds to the next step or the next successive unassigned hall call.

13. The method of claim 11, wherein the cumulative waiting time is determined according to $Q (x) B {.Math.}_{i = 1}^{N} {.Math.}_{c = 1}^{C} w_{i}^{c} x_{i}^{c} + {.Math.}_{i = 1}^{N} {.Math.}_{j = i + 1}^{N} {.Math.}_{c = 1}^{C} w_{ij}^{c} x_{i}^{c} x_{j}^{c},$ where is an indicator variable which takes on a value of 1 when the hall call from the passenger i is assigned to the elevator car c, and 0 otherwise, and that all N.Math.C indicator variables are collected in a decision vector x=[x.sub.1.sup.1, x.sub.2.sup.1, . . . , x.sub.N.sup.1, x.sub.1.sup.2, x.sub.2.sup.2, . . . , x.sub.N.sup.2, . . . , x.sub.1.sup.C, x.sub.2.sup.C, . . . , x.sub.N.sup.C].

14. The method of claim 11, wherein the greedy optimization algorithm has complexity O(CN.sup.2) , that is, linear in a number of elevator cars C and quadratic in a number of hall calls by passengers N, and leverages a property of submodularity of an objective function.

15. The method of claim 14, wherein for each step, all remaining unassigned hall calls by passengers are considered sequentially in time, and are initially added to each elevator car successively, and for every combination of a hall call and an elevator car, the SPD of all hall calls assigned, plus the new hall call assigned at the initial step are then calculated, and any combination of the hall call initially added with the elevator car that increases the SPD least, then the hall call is assigned to that elevator car, and removed all the remaining unassigned hall calls, and then continues to the next step.

16. A non-transitory computer readable storage medium embodied thereon a program executable by a computer for performing a method, the method for scheduling elevator cars of an elevator system, the elevator system including a plurality of elevator cars, and a plurality of hall calls, comprising: using at least one input interface for accepting a plurality of hall calls requesting the plurality of elevator cars to different floors of a building; determining independently, using a process in communication with the input interface, for each elevator car, an independent waiting time of accommodating each hall call, if the hall call is the only hall call assigned to the elevator car; determining, for each pair of hall calls assigned for each elevator car, a pairwise delay over the individual waiting time of each hall call in the pair caused by a joint assignment of the elevator car to accommodate the pair of the hall calls; approximating a cumulative waiting time of an assignment of the plurality of elevator cars to accommodate the plurality of hall calls as a sum of individual waiting times for accommodating each hall call with the assigned elevator car and a sum of all pairwise delays determined for the assigned elevator car between all pairs of hall calls assigned to the same elevator car; determining the assignment of the plurality of elevator cars using a greedy optimization algorithm that greedily assigns the plurality of hall calls to the plurality of elevator cars to minimize the approximated cumulative waiting time; and using a controller for controlling the movement of the plurality of elevator cars according to the assignment.

17. The method of claim 16, wherein the greedy optimization algorithm starts with an empty set of assignments of hall calls needing to be assigned, such that at every step including an initial step which starts with a first hall call, is added to the set of assignments of hall calls needing to be assigned, so as to result in a total of N steps, until all unassigned hall calls are assigned.

18. The method of claim 17, wherein each step in the total of N steps includes a hall call for every passenger to be moved between floors of the building, such that during each step, an unassigned hall call from a passenger is considered sequentially in time, and is initially added to an elevator car of the plurality of elevator cars successively.

19. The method of claim 18, wherein for every combination of the hall call and the elevator car, the greedy optimization algorithm computes a cumulative waiting time of all hall calls assigned at that moment in time, plus the first hall call assigned at the initial step.

20. The method of claim 19, wherein the hall call and the elevator car combination having a least increase in the cumulative waiting time for all assigned hall calls including the first hall call of the initial step, the combination is accepted, and the hall call is assigned and removed from all the remaining unassigned hall calls, then continues to the next step or the next successive unassigned hall call.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The presently disclosed embodiments will be further explained with reference to the attached drawings. The drawings shown are not necessarily to scale, with emphasis instead generally being placed upon illustrating the principles of the presently disclosed embodiments.

(2) FIG. 1A is a block diagram illustrating a method for controlling a movement of a plurality of elevator cars of an elevator system, according to an embodiment of the present disclosure;

(3) FIG. 1B is a schematic illustrating the method of FIG. 1A, for scheduling hall calls from passengers regarding controlling movement of the plurality of elevator cars of an elevator system, according to embodiments of the present disclosure;

(4) FIG. 1C is a flow diagram of the method of FIG. 1A, for controlling a movement of a plurality of elevator cars of an elevator system, according to embodiments of the present disclosure;

(5) FIG. 1D is a schematic illustrating the computation of unary and pairwise terms of step 120 of FIG. 1C, according to embodiments of the present disclosure;

(6) FIG. 2 shows the search tree of the greedy optimization algorithm for a reassignment problem with N=3 passengers (1, 2, and 3) and two cars (A and B), where each level of the tree corresponds to one assignment step of the algorithm, according to embodiments of the present disclosure; and

(7) FIG. 3 is a block diagram of illustrating the method of FIG. 1A, that can be implemented using an alternate computer or processor, according to embodiments of the present disclosure.

(8) While the above-identified drawings set forth presently disclosed embodiments, other embodiments are also contemplated, as noted in the discussion. This disclosure presents illustrative embodiments by way of representation and not limitation. Numerous other modifications and embodiments can be devised by those skilled in the art which fall within the scope and spirit of the principles of the presently disclosed embodiments.

DETAILED DESCRIPTION

(9) The following description provides exemplary embodiments only, and is not intended to limit the scope, applicability, or configuration of the disclosure. Rather, the following description of the exemplary embodiments will provide those skilled in the art with an enabling description for implementing one or more exemplary embodiments. Contemplated are various changes that may be made in the function and arrangement of elements without departing from the spirit and scope of the subject matter disclosed as set forth in the appended claims.

(10) Specific details are given in the following description to provide a thorough understanding of the embodiments. However, understood by one of ordinary skill in the art can be that the embodiments may be practiced without these specific details. For example, systems, processes, and other elements in the subject matter disclosed may be shown as components in block diagram form in order not to obscure the embodiments in unnecessary detail. In other instances, well-known processes, structures, and techniques may be shown without unnecessary detail in order to avoid obscuring the embodiments. Further, like reference numbers and designations in the various drawings indicated like elements.

(11) Also, individual embodiments may be described as a process which is depicted as a flowchart, a flow diagram, a data flow diagram, a structure diagram, or a block diagram. Although a flowchart may describe the operations as a sequential process, many of the operations can be performed in parallel or concurrently. In addition, the order of the operations may be re-arranged. A process may be terminated when its operations are completed, but may have additional steps not discussed or included in a figure. Furthermore, not all operations in any particularly described process may occur in all embodiments. A process may correspond to a method, a function, a procedure, a subroutine, a subprogram, etc. When a process corresponds to a function, the function's termination can correspond to a return of the function to the calling function or the main function.

(12) Furthermore, embodiments of the subject matter disclosed may be implemented, at least in part, either manually or automatically. Manual or automatic implementations may be executed, or at least assisted, through the use of machines, hardware, software, firmware, middleware, microcode, hardware description languages, or any combination thereof. When implemented in software, firmware, middleware or microcode, the program code or code segments to perform the necessary tasks may be stored in a machine readable medium. A processor(s) may perform the necessary tasks.

(13) Overview

(14) The present disclosure relates to systems and methods for scheduling elevator cars that operate according to a continuous reassignment policy until an actual time of pick up. In particular, controlling a movement of a plurality of elevator cars of the elevator system, wherein the elevator system accepts the plurality of hall calls requesting service of the plurality of elevator cars to different floors of a building.

(15) We realized through experimentation, we needed to solve this combinatorial optimization problem of assigning N multiple passengers to C elevator cars (C.sup.N possible assignments) in the shortest time (<1 s).

(16) During our experimentation, we quickly learned that traditional computation methods did not work, because they incorporated an exhaustive search taking a very long time to compute, i.e. computationally long wait times, that made such solutions impractical when put to use. For example, we explored the Branch-and-Bound and Mixed Integer Programming (MIP) methods, which we learned both had problems because of their worst-case complexity that are exponential in the number of elevator cars and halls calls. What we realized is we needed a combinatorial optimization method with favorable complexity (not exponential, but low-order polynomial) that outperforms known sub-optimal solutions such as the nearest-car and immediate assignment algorithms, among other things.

(17) We further realized that greedy optimization can produce a reasonable solution in a reasonable time, if the optimized cost function has a specific structure, e.g., quadratic, and submodular. In those cases, the greedy optimization has a guaranteed performance. However, the conventional cost function of a total waiting time for passengers is neither quadratic nor submodular. Thus, without realizing the optimized cost function structure (i.e. quadratic and submodular), the greedy algorithm is not going to be effective for optimizing AWT, which is demonstrably a non-submodular function. In particular, conventional greedy optimization methods can produce very suboptimal results when operating on general objective functions. The cost function should be related to a total waiting time for passengers, as according to the present disclosure.

(18) The systems and methods of the present disclosure are based on a greedy optimization algorithm of complexity O(CN.sup.2), that is, linear in the number of cars c and quadratic in the number of passengers N. We discovered that the success of this greedy optimization algorithm depends critically on the property of submodularity of the objective function. In the current context of optimizing average waiting time (AWT), this property is approximately equivalent to the property that when a group of passengers is picked up by the same elevator car, their cumulative waiting time is larger than the sum of their individual waiting times, if they had been picked up by multiple separate cars starting from the same location, one car per passenger. This property, unfortunately, is not strictly always true for waiting times of passengers in elevator banks, due to the intricate interplay between their positions in the pick up schedule of the car.

(19) In order to ensure the submodular property of the objective function, the first step in our method is to construct an approximation of the cumulative AWT of a group of passengers that does possess the submodularity property. To this end, we use the sum of pairwise delays (SPD).

(20) By using the Pairwise Delay Minimization, this converts the optimization problem from a general combinatorial optimization problem without any structure in the objective function to a Quadratic Binary Optimization (QBO) problem that has an objective function with very specific (quadratic) structure that can be leveraged computationally. Moreover, the objective function of the QBO problem is submodular, which allows the application of fast greedy optimization methods. We note that there is no reason to apply the greedy algorithm to minimize the pairwise approximation, or even think about making such a combination, since this is not known. In fact, without having the knowledge of submodularity, there is no reason to put together the greedy algorithm and our specific disclosed pairwise approximation.

(21) The second step of the algorithm is to optimize the SPD by greedily assigning passengers to cars in a manner that minimizes the SPD at every step. The algorithm starts with an empty set of assignments. At every step, a new passenger is added to the set of assignments, until all passengers are assigned. This results in exactly N steps, one for every passenger. During a given step, all remaining unassigned passengers are considered in turn, and are tentatively added to each car, again in turn. For every combination of a passenger and a car, we compute the SPD of all passengers assigned so far plus the new passenger being assigned at the current step. The passenger/car combination that increases the SPD the least is chosen, the passenger is assigned to this car and removed from the list of unassigned passengers, and the algorithm proceeds with the next step.

(22) Some embodiments of the present disclosure include using an input interface for accepting a plurality of hall calls requesting service of a plurality of elevator cars to different floors of a building. A processor is configured to determine, for each elevator car, an individual waiting time of accommodating each hall call, if the hall call is the only hall call assigned to the elevator car. Along with determining, for each pair of hall calls assigned for each elevator car, a pairwise delay over the individual waiting time of each hall call in the pair caused by a joint assignment of the elevator car to accommodate the pair of the hall calls.

(23) Followed by approximating a cumulative waiting time of an assignment of the plurality of elevator cars to accommodate the plurality of hall calls, as a sum of individual waiting times for accommodating each hall call with the assigned elevator car, and a sum of all pairwise delays determined between all pairs of hall calls assigned to the same elevator car. Then, determine the assignment of the plurality of elevator cars using a greedy optimization algorithm that greedily assigns the plurality of hall calls to the plurality of elevator cars to minimize the approximated cumulative waiting time. Finally, use a controller for controlling the movement of the plurality of elevator cars according to the assignment.

(24) FIG. 1A is a block diagram of a method for controlling a movement of a plurality of elevator cars of an elevator system, according to an embodiment of the present disclosure. The method 100 includes step 110 of using at least one input interface for accepting a plurality of hall calls requesting the plurality of elevator cars to different floors of a building. Such an interface is located at every elevator landing in the building. It is contemplated that the plurality of hall calls may be accepted. The most typical user interface includes an up button and a down button, which are used by the passenger to request transportation in the respective direction. A more novel user interface, known as a destination panel, includes buttons for all possible destination floors. A combination between the two types of interfaces is also possible, for example a full destination panel at the lobby of the building and a simpler two-button interface at other floors.

(25) Step 115 of FIG. 1A includes determining independently, using a processor 112 in communication with the input interface, for each elevator car, an independent waiting time of accommodating each hall call, if the hall call is the only hall call assigned to the elevator car. In practice, this determining is done by means of an internal simulator that simulates the path of the car if it has to pick up this passenger only. Note that any outstanding car calls places by passengers already in the car must be included in the simulation. For example, if the car is at the 3.sup.rd floor, and the hall call is at the 8.sup.th floor, but there is an outstanding car call to the 5.sup.th floor, the stop at the 5.sup.th floor must be simulated, too.

(26) Step 120 of FIG. 1A includes determining, for each pair of hall calls assigned for each elevator car, a pairwise delay over the individual waiting time of each hall call in the pair caused by a joint assignment of the elevator car to accommodate the pair of the hall calls. In practice, this determining is done by means of an internal simulator that simulates the path of the car if it has to pick up these two passengers only, according to the preferred pick-up order for this elevator bank. The usual method of deciding the pick-up order is the group collective policy, where the car picks up all passengers in front of it in its current direction of motion, going in the same direction, then reverses direction to pick up all passengers going in the opposite direction, and finally reverses direction again to pick up passengers going in its original direction, but behind its starting floor. Other pick-up sequencing policies are also possible, and can be simulated similarly. After the simulation is complete, the increase in waiting times of the two passengers are computed with respect to their individual waiting times determined in step 115. The sum of these increases is the pairwise delay between the two hall calls. Note that in all cases, only one of these increases is greater than zero, and the other one is always zero.

(27) Step 125 of FIG. 1A includes approximating a cumulative waiting time of an assignment of the plurality of elevator cars to accommodate the plurality of hall calls as a sum of individual waiting times w.sub.i.sup.c for accommodating each hall call i with its assigned elevator car c, and a sum of all pairwise delays w.sub.ij.sup.c between all pairs of hall calls (i,j) assigned to the same elevator car c, according to the formula

(28) $Q (x) = {.Math.}_{i = 1}^{N} {.Math.}_{c = 1}^{C} w_{i}^{c} x_{i}^{c} + {.Math.}_{i = 1}^{N} {.Math.}_{j = i + 1}^{N} {.Math.}_{c = 1}^{C} w_{ij}^{c} x_{i}^{c} x_{j}^{c},$
where the indicator variable x.sub.i.sup.c=1 if hall call i is assigned to car c, and x.sub.i.sup.c=0 otherwise.

(29) Step 130 of FIG. 1A includes determining the assignment of the plurality of elevator cars using a greedy optimization algorithm that greedily assigns the plurality of hall calls to the plurality of elevator cars to minimize the approximated cumulative waiting time.

(30) As noted above, the greedy optimization algorithm has a complexity O(CN.sup.2), that is, linear in the number of cars c and quadratic in the number of passengers N. Such that the success of this greedy optimization algorithm depends critically on the property of submodularity of the objective function. Further, when optimizing average waiting time (AWT), this property is approximately equivalent to the property that when a group of passengers is picked up by the same elevator car, their cumulative waiting time is larger than the sum of their individual waiting times, if they had been picked up by multiple separate cars starting from the same location, one car per passenger.

(31) Step 135 of FIG. 1A includes using a controller for controlling the movement of the plurality of elevator cars according to the assignment. Once the schedule has been determined, each car starts serving the hall calls assigned to it, according to the accepted sequence discussed above.

(32) FIG. 1B is a schematic illustrating the method of FIG. 1A, for scheduling elevator cars 101-102 in a group elevator system 111 in a building having multiple floors 103, according to embodiments of the present disclosure. The controller keeps track of all requests for service, in the form of a table of hall calls 155. When a hall call is served by a car that picks up the passenger or passengers that initiated the call, that hall call is removed from the table 155. When a new hall call 150, is registered, it is added to the table 155. At regular intervals, or at specific events, such as new hall calls or starts/stops of cars at floors, the scheduler 160 is executed. It produces a schedule 170 in the form of a full assignment of all outstanding hall calls to cars. The controller 180 continuously executes the current schedule 170, according to the preferred service policy, for example the group collective service policy, also known as the selective collective principle, or some other policy, Tanaka, Uraguchi, and Araki, Dynamic optimization of the operation of single-car elevator systems with destination hall call registration: Part I. Formulation and simulations, European Journal of Operational Research 167.2 (2005), pp 550-573

(33) FIG. 1C is a flow diagram of the method of FIG. 1A, for controlling a movement of a plurality of elevator cars of an elevator system, according to embodiments of the present disclosure. The controller collects information about hall calls 109 from the up/down button interfaces 112 located at each elevator landing, and car calls 109 from button panel interfaces 112 located in each car; determines (step 120) independent waiting time of accommodating each hall call, and pairwise delays between pairs of passengers constructs (step 125) an approximate cumulative waiting time 126 in the form of a quadratic Boolean function; determines (step 130) the assignment of the plurality of elevator cars using a greedy optimization algorithm by executing N assignment steps, such that at each step the marginal increase in waiting time 131 among all passengers that are not assigned yet is minimized 132; and executes the current schedule according to the current assignment, until the next reassignment step. Finally, step 135 includes using a controller for controlling the movement of the plurality of elevator cars according to the assignment.

(34) FIG. 1D is a schematic illustrating the computation of unary and pairwise terms of step 120 of FIG. 1C, according to embodiments of the present disclosure. In FIG. 1D, the individual waiting times (unary terms) and mutual delays (pairwise terms) are computed for two passengers 141 and 142 to be picked up by the same car 140 (C1, currently at the 5.sup.th floor, and moving up). In FIG. 1D-a, the car will reverse its direction and quickly pick up 143 the first passenger from the floor below. The resulting waiting time will be the unary term 131 for the first passenger 141. This time can be computed by means of forward simulation of what the car will do when picking up that passenger. In FIG. 1D-b, through a similar simulation, it will be determined that the car will continue its direction of motion and pick up 144 the second passenger 142. The resulting waiting time of that passenger 142 will be his unary term 132. Finally, in FIG. 1D-c, it is determined that if the car 140 is to pick up both passengers 141 and 142, following the principle of group collective control, it will first pick up 144 the second passenger 142, as in FIG. 1D-b, and only then will it reverse direction to come down 145 and pick up the first passenger 141. As a result, the first passenger 141 will wait much longer for service than if he was picked up alone, as in FIG. 1D-a. This difference in the waiting time of passenger 141 between cases 1D-c and 1D-a is the delay the second passenger 142 would cause to passenger 141, and is equal to the pairwise delay term 133 between these two passengers. Note that for each pair of passengers, only one of them is delaying the other, but not vice versa; in FIG. 1D, passenger 142 is delaying passenger 141, but passenger 142 is not delayed by passenger 141, specifically for this car 140 in its current direction of motion. For a different car, the delay might be different.

(35) FIG. 2 shows the search tree of the greedy optimization algorithm for a reassignment problem with N=3 passengers (1, 2, and 3) and two cars (A and B), where each level of the tree corresponds to one assignment step of the algorithm. The root node of the tree 200 corresponds to the initial stage of the algorithm, when no assignments have been made yet. Six tentative assignments 210 are made of the three unassigned calls to the two available cars. For each of them, the marginal increase in waiting time 131 is computed and the minimum 132 is determined. In this example, this minimum 132 is achieved for the pair 220 of call 2 and car B (2B). Passenger 2 is assigned to car B, all other tree nodes at this level are ignored, and the children nodes of node 2B (220) are expanded at the next level, with the remaining four possible assignments 225 between the remaining unassigned passengers 1 and 3 and the two available cars A and B. The marginal increase in waiting time 130 is computed for each of these tentative assignments, keeping in mind that passenger 2 has already been assigned to car B, so any other passenger assigned to car B would either delay or be delayed by passenger 2, according to the respective pairwise term 133. At this level, the assignment 1B 230 is determined to increase the waiting time the least, so it is chosen among the four 225. At the next, final stage 235, the only remaining passenger 3 is assigned analogously 240 to car A, because it results in a lower marginal increase in waiting time than the alternative, 3B.

(36) The algorithm has two main stages: the first one is the computation of the approximation of AWT based on the sum of pairwise delays (SPD), and the second one is the greedy optimization algorithm for optimizing the SPD in N steps, where N is the number of passengers still waiting to be picked up at the time of reassignment.

(37) Stage 1: Quadratic Boolean Approximation

(38) During the first stage, two sets of coefficients w.sub.i.sup.c and w.sub.ij.sup.c are computed to construct a quadratic Boolean approximation of the cumulative waiting time of the entire set of passengers currently waiting for service at the time when reassignment is performed, in the form:

(39) $\begin{matrix} Q (x) = {.Math.}_{i = 1}^{N} {.Math.}_{c = 1}^{C} w_{i}^{c} x_{i}^{c} + {.Math.}_{i = 1}^{N} {.Math.}_{j = i + 1}^{N} {.Math.}_{c = 1}^{C} w_{ij}^{c} x_{i}^{c} x_{j}^{c}, & (1) \end{matrix}$
where x.sub.i.sup.c is an indicator variable which takes on a value of 1 when passenger i is assigned to car c, and 0 otherwise. All N.Math.C indicator variables can be collected in a decision vector x=[x.sub.1.sup.1, x.sub.2.sup.1, . . . , x.sub.N.sup.1, x.sub.1.sup.2, x.sub.2.sup.2, . . . , x.sub.N.sup.2, . . . , x.sub.1.sup.C, x.sub.2.sup.C, . . . x.sub.N.sup.C]. The procedure is detailed in U.S. Pat. No. 7,546,905, Nikovski et al., System and method for scheduling elevator cars using pairwise delay minimization, incorporated herein and thereafter in its entirety. The procedure is repeated below using a slightly different notation.

(40) Let H be the set of N passengers {h.sub.1, h.sub.2, . . . , h.sub.N} still waiting. A single passenger h.sub.i is described by the tuple (t.sub.i, o.sub.id.sub.i), where t.sub.i is the arrival time, o.sub.i is the arrival floor, and d.sub.i is the indicated direction of movement, or the desired destination floor, if known. A full assignment of the N passengers to the C cars in a bank would be a partition of H into C subsets H.sub.c, such that H=H.sub.1H.sub.2 . . . H.sub.C, and H.sub.iH.sub.j= if ij. Let also W.sub.c(h|A), where h is a passenger and A is a set of passengers, denote the expected waiting time of passenger h if assigned to car c (as it is in its current position), and also all passengers in the set A are assigned to the same car c , too. Note that this waiting time reflects all constraints that already exist for car c , including stops requested by passengers who are already inside the car, and have indicated their destination floor by pressing one of the buttons on the destination panel inside the car.

(41) The expected waiting time W.sub.c(h|A) can be computed relatively easily by performing a forward simulation of the path of car c until the time it picks up passenger h , while also stopping to unload passengers already in it, or picking up other passeners in the set A that need to picked up before passenger h. Such a simulation supposes that a specific predetermined order of servicing hall and car calls will be followed by the schedule execution system of the elevator bank. The usual order adopted by most actual elevator systems, commonly called the group collective policy, is to service all car and hall calls in the current direction of motion of the car, then reverse its direction, and repeat the procedure in alternating directions indefinitely. However, in practice, any order can be followed, as long as it is known in advance, fixed, and can be simulated in software.

(42) Then, the coefficients in the quadratic Boolean approximation shown in Equation 1 can be computed as follows:
w.sub.i.sup.c=W.sub.c(h.sub.i|{h.sub.i}) (2)
w.sub.ij.sup.c=[W.sub.c(h.sub.i|{h.sub.i, h.sub.j})W.sub.c(h.sub.i|{h.sub.i})]+[W.sub.c(h.sub.i|{h.sub.i, h.sub.j})W.sub.c(h.sub.j|{h.sub.j})]. (3)

(43) Per Equation 2, the linear coefficient w.sub.i.sup.c is simply the expected waiting time of passenger h.sub.i, if that passenger is picked by car c, and no other passenger is picked up by that car. In order to compute the N.Math.C linear coefficients w.sub.i.sup.c, a total of N.Math.C forward simulations must be performed, from the current position of each car to the floor of each passenger. These simulations are very simple and usually very fast.

(44) Per Equation 3, the bilinear coefficient w.sub.ij.sup.c is equal to the mutual delay between passengers h.sub.i and h.sub.j. For a specific pick-up order of passengers by car c, only one of the two passengers is causing a delay to the other. (The passenger who will picked up first causes a delay for the passenger who will be picked up second.) In order to compute this delay, we compute the two differences W (h.sub.i|{h.sub.i, h.sub.j})W.sub.c(h.sub.i|{h.sub.i}) and W.sub.c(h.sub.i|{h.sub.i, h.sub.j})W.sub.c(h.sub.j|{h.sub.j}), only one of which is zero. In practice, the two values W(h.sub.i|{h.sub.i, h.sub.j}) and W.sub.c(h.sub.i|{h.sub.j}) can be computed by means of only one forward simulation, where car c picks up both passengers h.sub.i and h.sub.j, and their respective waiting times are calculated. The other two values, W.sub.c(h.sub.i|{h.sub.i, h.sub.j}) and W.sub.c(h.sub.j|{h.sub.j}), have been computed during the calculation of the linear coefficients, and could be stored during that step for reuse. In total, the computation of the N(N1)C/2 bilinear coefficients requires an equal number of forward simulations, one for every car and every pair of passengers. These simulations are also relatively simple and very fast.

(45) Stage 2: Greedy Optimization of Approximated Waiting Time

(46) After the coefficients of the approximation Q(x) have been computed, the optimal assignment x* must be computed as x*=argmin.sub.xQ(x), subject to the constraints that the decision variables are Boolean (i.e., they assume values of only 0 or 1), and exactly one decision variable is equal to 1 for a given passenger (.sub.c=1.sup.Cx.sub.i.sup.c=1).

(47) Equation 1 can be recognized as a quadratic expression in the decision variables x.sub.i, which, along with the requirement for these variables to assume Boolean values, turns the minimization task into a Quadratic Boolean Optimization (QBO) problem. Even though the problem possesses a certain mathematical structure, it is well known that it is NP-complete, that is, finding its truly optimal solution will still have exponential complexity O(C.sup.N) using any known optimization algorithm. However, the particular version of the problem we are considering has an additional property. Let us define the set function (S)=Q(x), whose argument is one of the possible subsets of all assignments (h.sub.i.fwdarw.c) of passengers to cars, (including incomplete assignments where not all passengers are assigned), such that x.sub.i.sup.x=1 if (h.sub.i.fwdarw.c)S, and x.sub.i.sup.c=0, otherwise. Then, it can be proven that the function (S) is submodular, that is, for two sets of assignments S.sub.1.Math.S.sub.2, and an element (assignment) s.Math.S.sub.2 it is true that
(S.sub.1s)(S.sub.1)(S.sub.2s)(S.sub.2).

(48) This is true because the function is the negative of the function Q, and adding a passenger to a larger set of passengers already assigned to the same car would result in a larger increase in cumulative waiting time in comparison to the case when the same passenger is added to a smaller set of passengers. The latter is true because more mutual delays exist in a larger group of passengers than in a smaller one.

(49) Because the function is the negative of the function Q, maximizing is equivalent to minimizing Q, which is our goal. But, when a function is submodular, a type of greedy optimization algorithm can be applied to maximize it, with provable performance guarantees, Nemhauser, G. L.; Wolsey, L. A.; and Fisher, M. L. 1978. An analysis of the approximations for maximizing submodular set functions, Mathematical Programming, pp. 265-294. That is, the algorithm has a very favorable computational complexity (O(N.sup.2C)), while the minimal value it returns is guaranteed to be within double the true minimum. (In practice, the suboptimality is often much smaller.)

(50) The algorithm has exactly N steps, and at every step, one passenger is assigned to a car. The algorithm starts with an empty set of assignments. At every step n, n=1, . . . , N, all remaining Nn+1 unassigned passengers in the set H.sub.n.sup. are tentatively assigned to one of the C cars. If passenger h.sub.i is being tentatively assigned to car c, the increase Q(i,c) of the total waiting time of all passengers, including the new passenger h.sub.i, can be defined and computed as

(51) $Q (i, c) = Q (.Math., x_{i}^{c} = 1, .Math.) - Q (.Math., x_{i}^{c} = 0, .Math.) = w_{i}^{c} + {.Math.}_{j = i + 1}^{N} w_{ij}^{c} x_{j},$
that is, we tentatively set the value of x.sub.i.sup.c to 1, and compute the increase in Q(x), while keeping all other assignments as they currently are. This increase will include the time w.sub.i.sup.c it would take the car c to pick up passenger h.sub.i if it had no other passengers to pick up, plus the marginal increase of waiting times for all passengers already assigned to the same car, caused by the new passenger, or the marginal time those passengers would cause to the new passenger, if only they and the new passengers are being transported by the same car. Clearly, the waiting times of passengers assigned to other cars would not be affected by this tentative assignment.

(52) Then, the algorithm selects the assignment with the smallest increase in cumulative waiting time:
[i, c]=argmin.sub.i,cQ(i,c).

(53) After the last, N-th step of the algorithm, a full assignment of passengers to cars has been constructed.

(54) FIG. 2 shows the search tree of this algorithm, for the case when 3 passengers, 1, 2, and 3, need to be assigned to 2 cars, A and B . The algorithm starts with an empty set of assignments 200. During the first step, all three passengers are yet to be assigned. The six possible assignments 1A, 1B, 2A, 2B, 3A, and 3B are tentatively tested. Since no passengers have been assigned previously, the increases in marginal waiting times are simply the respective times it would take for the car to pick up the passenger alone. It turns out that passenger 2 will be picked up by car B the fastest, so this is the assignment 220 chosen at this step. Note that this is a greedy assignment, and will never be revised later.

(55) During the second step, the two remaining passengers, 1 and 3 are tentatively assigned to the two cars A and B. If they are assigned to car B, which has already been determined to transport passenger 2, the mutual delay between the new passenger and passenger 2 needs to be added to the increase in cumulative waiting time, too. In this example, it is concluded 230 that it is actually less expensive to assign passenger 1 to car B, too, even if the mutual delay between passengers 1 and 2 must be added, rather than assign this passenger to car A, or assign passenger 3 to either car. This could be because passengers 2 and 1 are unusually close to car B.

(56) And, in the last step, the remaining passenger 3 is assigned 240 to car A, because it would result in lower waiting time than if the passenger was assigned to car B. This assignment is quite logical, because by this stage, car B is already scheduled to pick up passengers 1 and 2, and if it were to also pick up passenger 3, the entire system would have to incur the mutual delay between each pair of passengers, while car A would be idle; clearly, this is not likely to be the most optimal solution.

(57) Note that the order of assignment of passengers to cars is not fixed, and that is the main difference of the proposed algorithm with respect to the immediate assignment method, where the order of assignment is fixed and identical to the chronological order of arrival of passengers. The computational cost of the proposed method is slightly higherat each one of the N steps, on the order of N remaining passengers are tentatively assigned to the C cars, for a computational complexity of O (N.sup.2C). This is one polynomial degree higher than the complexity of the immediate assignment method (O(NC)), but still very much within the computational power of most modem microcontrollers.

(58) FIG. 3 is a block diagram of illustrating the method of FIG. 1A, that can be implemented using an alternate computer or processor, according to embodiments of the present disclosure. The computer 311 includes a processor 340, computer readable memory 312, storage 358 and user interface 349 with display 352 and keyboard 351, which are connected through bus 356. For example, the user interface 349 in communication with the processor 340 and the computer readable memory 312, acquires and stores the data (i.e., data relating to controlling movement of the elevator cars or elevator systems, elevator system operational historical data, elevator system optimization related data related to assigning halls calls to elevator cars of a similar elevator system), in the computer readable memory 312 upon receiving an input from a surface, keyboard surface, of the user interface 357 by a user.

(59) Contemplated is that the memory 312 can store instructions that are executable by the processor, historical data, and any data to that can be utilized by the methods and systems of the present disclosure. The processor 440 can be a single core processor, a multi-core processor, a computing cluster, or any number of other configurations. The processor 340 can be connected through a bus 356 to one or more input and output devices. The memory 312 can include random access memory (RAM), read only memory (ROM), flash memory, or any other suitable memory systems.

(60) Still referring to FIG. 3, a storage device 358 can be adapted to store supplementary data and/or software modules used by the processor. For example, the storage device 358 can store historical data and other related data such as manuals for the devices of the elevator system or similar types of elevator systems, wherein the devices can include sensing devices capable of obtaining data as mentioned above regarding the present disclosure. Additionally, or alternatively, the storage device 358 can store historical data similar to the data. The storage device 358 can include a hard drive, an optical drive, a thumb-drive, an array of drives, or any combinations thereof.

(61) The system can be linked through the bus 356 optionally to a display interface (not shown) adapted to connect the system to a display device (not shown), wherein the display device can include a computer monitor, camera, television, projector, or mobile device, among others.

(62) The computer 311 can include a power source 354, depending upon the application the power source 354 may be optionally located outside of the computer 311. Linked through bus 356 can be a user input interface 357 adapted to connect to a display device 348, wherein the display device 348 can include a computer monitor, camera, television, projector, or mobile device, among others. A printer interface 359 can also be connected through bus 356 and adapted to connect to a printing device 332, wherein the printing device 332 can include a liquid inkjet printer, solid ink printer, large-scale commercial printer, thermal printer, UV printer, or dye-sublimation printer, among others. A network interface controller (NIC) 334 is adapted to connect through the bus 356 to a network 336, wherein measuring data or other data, among other things, can be rendered on a third party display device, third party imaging device, and/or third party printing device outside of the computer 311.

(63) Still referring to FIG. 3, the data or other data, among other things, can be transmitted over a communication channel of the network 336, and/or stored within the storage system 358 for storage and/or further processing. Further, the measuring data or other data may be received wirelessly or hard wired from a receiver 346 (or external receiver 338) or transmitted via a transmitter 347 (or external transmitter 339) wirelessly or hard wired, the receiver 346 and transmitter 347 are both connected through the bus 356. The computer 311 may be connected via an input interface 308 to external sensing devices 344 and external input/output devices 341. The computer 311 may be connected to other external computers 342. An output interface 309 may be used to output the processed data from the processor 340.

(64) According to aspects of the present disclosure, the greedy optimization algorithm is an algorithmic paradigm that determines at an initial step, an assignment of an unassigned first hall call, based on a locally optimal choice determined at a time of the initial step, then proceeds to the next step or the next successive unassigned hall call. According to aspects of the present disclosure, the locally optimal choice identifies at each step, a combination of an unassigned hall call from all the remaining unassigned hall calls and an elevator car from the plurality of elevator cars, that results in a least increase in a waiting time for all assigned hall calls including the first hall call, while considering all previous assigned hall calls, then the combination is accepted and the hall call is assigned without further consideration and removed from all the remaining unassigned hall calls.

(65) According to aspects of the present disclosure, the greedy optimization algorithm starts with an empty set of assignments of hall calls needing to be assigned, such that at every step including an initial step which starts with a first hall call, is added to the set of assignments of hall calls needing to be assigned, so as to result in a total of N steps, until all unassigned hall calls are assigned. Wherein each step in the total of N steps includes a hall call for every passenger to be moved between floors of the building, such that during each step, an unassigned hall call from a passenger is considered sequentially in time, and is initially added to an elevator car of the plurality of elevator cars successively. Wherein for every combination of the hall call and the elevator car, the greedy optimization algorithm computes a cumulative waiting time of all hall calls assigned at that moment in time, plus the first hall call assigned at the initial step. Wherein the hall call and the elevator car combination having a least increase in the cumulative waiting time for all assigned hall calls including the first hall call of the initial step, the combination is accepted, and the hall call is assigned and removed from all the remaining unassigned hall calls, then continues to the next step or the next successive unassigned hall call.

(66) According to aspects of the present disclosure, wherein the greedy optimization algorithm is based on optimizing the approximated cumulative waiting time in N steps, where N is a number of unassigned hall calls from passengers waiting to be assigned at a time at each step, such that two sets of coefficients are computed to construct a quadratic Boolean approximation of the cumulative waiting time of all the plurality of hall calls from passengers currently waiting to be assigned at the time of that step. Wherein the first set of coefficients of the two sets of coefficients includes w.sub.l.sup.c, such that w.sub.i.sup.c is a linear coefficient that is an expected waiting time of a hall from a passenger h.sub.i, if the hall call is picked by an elevator car c, and no other hall call is picked up by that elevator car.

(67) According to aspects of the present disclosure, wherein the second set of coefficients of the two sets of coefficients includes w.sub.ij.sup.c, such that w.sub.ij.sup.c is a bilinear coefficient that is equal to the pairwise delay between hall calls from passengers h.sub.i and h.sub.j, based on a specific pick-up order of the two hall calls by the elevator car c, such that only one of the two hall calls is causing a delay to the hall call, and the hall call that is picked-up first causes a delay for the hall call that is picked-up second.

(68) According to aspects of the present disclosure, wherein the cumulative waiting time is determined according to

(69) $Q (x) B {.Math.}_{i = 1}^{N} {.Math.}_{c = 1}^{C} w_{i}^{c} x_{i}^{c} + {.Math.}_{i = 1}^{N} {.Math.}_{j = i + 1}^{N} {.Math.}_{c = 1}^{C} w_{ij}^{c} x_{i}^{c} x_{j}^{c},$
where x.sub.i.sup.c is an indicator variable which takes on a value of 1 when the hall call from the passenger i is assigned to the elevator car c, and 0 otherwise, and that all N.Math.C indicator variables are collected in a decision vector x=[x.sub.1.sup.1, x.sub.2.sup.1, . . . , x.sub.N.sup.1, x.sub.1.sup.2, x.sub.2.sup.2, . . . , x.sub.N.sup.2, . . . , x.sub.1.sup.C, x.sub.2.sup.C, . . . , x.sub.N.sup.C].

(70) According to aspects of the present disclosure, Wherein the greedy optimization algorithm includes a O(CN.sup.2), that is, linear in a number of elevator cars C and quadratic in a number of hall calls by passengers N, and includes a property of submodularity of an objective function. Wherein for each step, all remaining unassigned hall calls by passengers are considered sequentially in time, and are initially added to each elevator car successively, and for every combination of a hall call and an elevator car, the SPD of all hall calls assigned, plus the new hall call assigned at the initial step are then calculated, and any combination of the hall call initially added with the elevator car that increases the SPD least, then the hall call is assigned to that elevator car, and removed all the remaining unassigned hall calls, and then continues to the next step.

(71) According to aspects of the present disclosure, historical elevator system data originates from a user, and is stored in a memory in communication with the processor. The historical elevator system data can be data relating to elevator systems including similar elevator systems of the present disclosure, as well as instructional data

(72) According to aspects of the present disclosure, further comprising: initiating to start to implement the method by accepting the hall call data and to be received by the input interface is by a user input provided on a surface of at least one user input interface in communication with the processor and received by the processor

(73) According to aspects of the present disclosure, further comprising: using a user input provided on a surface of at least one user input interface both in communication with the processor and received by the processor via the input interface for controlling movement of the plurality of elevators based upon an abnormal event. The abnormal event can include an event that disrupts operation of the plurality of elevators causing an unsafe environment to cargo and passengers on the elevators

(74) The above-described embodiments of the present disclosure can be implemented in any of numerous ways. For example, the embodiments may be implemented using hardware, software or a combination thereof. Use of ordinal terms such as first, second, in the claims to modify a claim element does not by itself connote any priority, precedence, or order of one claim element over another or the temporal order in which acts of a method are performed, but are used merely as labels to distinguish one claim element having a certain name from another element having a same name (but for use of the ordinal term) to distinguish the claim elements

(75) Although the present disclosure has been described with reference to certain preferred embodiments, it is to be understood that various other adaptations and modifications can be made within the spirit and scope of the present disclosure. Therefore, it is the aspect of the append claims to cover all such variations and modifications as come within the true spirit and scope of the present disclosure.

System and method for group elevator scheduling based on submodular optimization

Assignee

Inventors

Cpc classification

Classification Explorer

B66B2201/20

PERFORMING OPERATIONS; TRANSPORTING

Classification Explorer

B66B2201/211

PERFORMING OPERATIONS; TRANSPORTING

Classification Explorer

B66B1/2458

PERFORMING OPERATIONS; TRANSPORTING

Classification Explorer

B66B1/2433

PERFORMING OPERATIONS; TRANSPORTING

Classification Explorer

B66B2201/00

PERFORMING OPERATIONS; TRANSPORTING

International classification

Classification Explorer

B66B1/24

PERFORMING OPERATIONS; TRANSPORTING

Abstract

Claims

Description