A recent post on HN got me thinking (and reading) about elevator scheduling algorithms. As it turns out, this is an active area of extensive research. Manufacturers tend to use slightly different algorithms and treat them as trade secrets. But in practice, their algorithms are similar, because the theoretical optimization criteria are roughly the same:
- provide even service to each floor
- minimize how long passengers wait for an elevator to arrive
- minimize how long passengers spend to get to their destination floor
- serve as many passengers as possible
The single elevator case is not very interesting, nor is the case when the passenger can't specify his direction of travel when making the call (one button per floor), so I'll instead discuss only the case where there are multiple elevators, and two buttons on each floor:
There are many criteria to consider in elevator scheduling. For example, people have predictable behavioral patterns that must be addressed, including the uppeak and downpeak---respectively 9AM and 5PM, in many office buildings---which are when elevator efficiency matters the most. There is often a 1-2 hour two-way peak (lunchtime) to address as well. Algorithms should consider whether an elevator is full before assigning it to an elevator call. Sometimes, some blocks of floors have predictably higher interblock or intrablock traffic than other blocks. Often, calls on some floors (executive floors, for example) are given higher priority than others (basements). All of these factors increase the algorithm sophistication.
Still, they tend to be based on the four classic group traffic control algorithms.
Nearest Car (NC)
Elevator calls are assigned to the elevator best placed to answer that call according to three criteria that are used to compute a figure of suitability (FS) for each elevator.If an elevator is moving towards a call, and the call is in the same direction, FS = (N + 2) - d, where N is one less than the number of floors in the building, and d is the distance in floors between the elevator and the passenger call.
If the elevator is moving towards the call, but the call is in the opposite direction, FS = (N + 1) - d.
If the elevator is moving away from the point of call, FS = 1. The elevator with the highest FS for each call is sent to answer it. The search for the "nearest car" is performed continuously until each call is serviced.
Fixed Sectoring Common Sector System (FSO):
The building is divided into as many sectors as there are elevators. Elevators in each sector prefer calls in that sector.Fixed Sectoring Priority Timed System (FS4):
The building is divided into up sectors and down sectors, and elevators only ever treat down calls in down sectors and up calls in up sectors. Each sector has a priority level, which increases the longer the passengers wait. The rate of increase can vary from sector to sector and over time.Dynamic Sectoring System (DS):
Floors are grouped into dynamic sectors. Each elevator is allocated to a sector in the sector definition, and the sectors change size and location based on the position of moving and idle elevators.
Modern control systems do even more than this. Some of them dynamically compute cost functions for passengers waiting on an elevator. Stochastic traffic control systems empirically compute the distribution of response times and try to make it as Gaussian as possible (wait times should be consistent; there shouldn't be some times when elevators respond instantly and others where they take a while). Some advanced techniques use fuzzy logic schedulers (Ho and Robertson 1994), genetic algorithms (Siikonen 2001, Miravete 1999), and neural networks (Barney and Imrak 2001).
Most of this information is paraphrased from UK-based lift consultant Gina Barney's book "Elevator Traffic Handbook: Theory and Practice." A most uplifting read.
This post originated as an answer on Quora.
See discussion on reddit and hackernews.