Elevator – industrial lift truck – or stationary lift for vehicle – With call registration means – Shared by plural load supports
Reexamination Certificate
2002-06-03
2004-01-06
Salata, Jonathan (Department: 2837)
Elevator, industrial lift truck, or stationary lift for vehicle
With call registration means
Shared by plural load supports
C187S247000
Reexamination Certificate
active
06672431
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to elevator group control, and more particularly to optimizing group elevator scheduling. BACKGROUND OF THE INVENTION
Group elevator scheduling is a well-known problem in industrial control and operations research with significant practical implications, Bao et al., “Elevator dispatchers for down-peak traffic,” Technical Report, University of Massachusetts, Department of Electrical and Computer Engineering, Amherst, Mass., 1994. Given a hall call generated at one of the floors of a building with multiple elevator shafts, the objective of elevator group control is to decide which car to use to serve the hall call.
In some elevator systems, the controller assigns a car to the hall call as soon as the call is signaled, and immediately directs the passenger who signaled the hall call to the corresponding shaft by sounding a chime. While in other systems, the chime is sounded when the assigned car arrives at the floor of the hall call.
That difference influences car assignment in two ways. Making an early assignment to service the hall call impairs the performance of the controller when the assignment is incorrect. That makes the assignment problem harder because the controller has to consider events over a longer time interval. Also, after a decision is made, the decision cannot be changed.
Scheduling policy is subject to constraints arising from passenger expectations, destinations, and elevator movement. The constraints can include passengers arrival rates on all floors, fixed or variable inter-floor travel times, and fixed passenger destinations and/or origins, etc.
While one objective of elevator control is to minimize the cost of operating the system, e.g., the cost measured in terms of waiting and/or travel times of passengers in all types of traffic, several traffic patterns are of special interest because those patterns pose extraordinary demand on the elevator group and its controller. Such traffic patterns are up-peak traffic, which arises at the beginning of the workday in an office building, down-peak traffic, which arises at the end of the workday, and lunch traffic, down first, and up a little later.
Up-peak traffic is characterized by a large number of passengers arriving in the lobby, boarding cars and exiting the cars at the upper floors while, simultaneously, a lesser number of passengers travel between floors other than the lobby. Such a traffic pattern has uncertainty in the destination floors of passengers, while the floor of the car call is most frequently the lobby.
The reverse situation is down-peak traffic, when most passengers board cars at one of the upper floors and exit the car at the lobby, while a lesser number of passengers travel to destinations other than the lobby. Correspondingly, the amount of uncertainty in the case of down-peak traffic is opposite to that of up-peak traffic because there is little uncertainty about the destination floor, i.e., the lobby, but there is greater uncertainty in the call floor.
Lunch traffic combines elements of down-peak and up-peak traffic. The system starts with down-peak traffic and then slowly shifts to up-peak traffic. In addition to having uncertainty in both call and destination floors, the properties of passenger flow shift with time.
Elevator scheduling could be expressed as combinatorial optimization problems. Solutions to these problems are characterized by identifying an optimum solution for transitioning from a current state to a desired state, where the desired state is selected from all possible future states. In principle, combinatorial optimization problems could be solved by evaluating all possible combinations of choices and selecting only that combination that gives the most favorable result.
However, other than for simple problems, the number of possible choices increases exponentially and rapidly becomes so large that, even when digital computers are employed, the solution of a single problem on a single processor may take hours, days, sometimes even months or years, see below. Up to now, prior art elevator scheduling systems and methods have not considered evaluating all possible solutions to find a best solution. Typically, only a subset of solutions are considered, or the operation of the elevators is severely in constrained in some way to make the problem solvable in real-time.
For example, partial solutions have been obtained for the limited case of purely up-peak traffic, and the constraints that all passengers arrive in the lobby at a fixed rate and no other call floors are allowed, see, e.g., Pepyne et al., “Optimal dispatching control for elevator systems during up peak traffic,” IEEE transactions on control systems technology, 5(6):629-643, 1997. In order to make the problem manageable, the service time of elevators is assumed to come from a fixed exponential distribution.
Many prior art controllers used the principle of collective control, see Strakosch et al., “Vertical transportation: elevators and escalators,” John Wiley & Sons, Inc., New York, N.Y., 1983. With collective control, cars are constrained to always stop at the nearest call in their running direction. That strategy ignores the total state of the system and usually results in bunching. Bunching is a phenomenon where several cars arrive at the same floor at about the same time, with all cars but one wasting time, see Hikihara et al., “Emergent synchronization in multi-elevator system and dispatching control,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E80-A(9):1548-1553, 1997. They concluded that the bunching effect occurring in down-peak traffic was due to synchronization between multiple cars.
Another prior art approach constrains operation by zoning, or sectoring. There, the building is divided into zones and each car is assigned a single zone. While that approach avoids bunching, it also ignores the total state of the system.
Other control techniques and heuristics can also be used. Mitsubishi Electric's elevator group control system, “AI-2100N,” is based on an expert system with fuzzy rules. That system relies on expert judgment of humans to prescribe a good assignment of calls. That system cannot determine a solution to a scheduling problem by itself. Rather, that system identifies the problem and employs preprogrammed human derived solutions to the problem, see Ujihara et al., “The revolutionary AI-2000 elevator group-control system and the new intelligent option series,” Mitsubishi Electric Advance, 45:5-8, 1988, and Ujihara et al., “The latest elevator group-control system,” Mitsubishi Electric Advance, 67:10-12, 1994.
The Otis elevator Relative System Response (RSR) method and its variants estimate, for each car, the time it would take to service the already assigned calls when a new call arises, and assigns the car with the lowest remaining service time to that call. The RSR methods are examples of greedy methods They either are constrained to have a predetermined assignment of calls, or never reconsider an assignment.
A more sophisticated group of methods use non-greedy strategies which recompute car assignments after each change of state. As noted, such methods are not applicable to certain elevator groups where reassignments are not allowed. Examples of such methods are Finite Intervisit Minimization (FIM) and Empty the System Algorithm (ESA), see Bao et al. While they have been demonstrated to outperform simpler methods by a margin of 34%, FIM and ESA are limited to down-peak traffic because they presume that the destination of all passengers is constrained to be the lobby. That method is not optimal in real world elevator systems where the lobby is certainly not the only desired destination.
Furthermore, such methods are constrained to assume no new passenger arrivals occur while a call is processed, and find the best strategy to service the existing calls given that simplification. Thus, by failing to take into account the stochastic component of the elevator system, a significant number of potent
Brand Matthew E.
Nikovski Daniel N.
Brinkman Dirk
Curtin Andrew
Mitsubishi Electric Research Laboratories Inc.
Salata Jonathan
LandOfFree
Method and system for controlling an elevator system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for controlling an elevator system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for controlling an elevator system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3187790