This has always been my favorite interview question for programmers. I ask them to write the steps/algorithm for elevator car movement when there are three cars and five landings, using any programming language or pseudo-code. As they explain, I ask several questions that challenge their suggestions, such as I have listed below.

It’s a great question because even the best programmers cannot provide a deterministic approach in the allotted few (say, 10) minutes of discussion. It really makes you think. I suggest that you try to come up with a solution. If you can make progress on this problem using sound judgement to come up with a practical approach, you would probably be an excellent programmer.

Here are some challenges to get you started:

1. If a wall button is pressed on landing N, while there are cars going UP on N-3, N-2, and N+1, which should be summoned? (basic, obvious, but fundamental)
2. In that same situation, if the second car is stopped for a long time with the doors held open and, meanwhile, the other two cars are at N-2 and N+2, what should be done?
3. Car B is empty on landing N and somebody gets in and presses the button for landing N+1 and the doors close. But that car was already on the way to landing N-3 to pick up somebody. Should the car go down to N-3 first or should it go up to N+1 and a different car be summoned to floor N-3?
4. What if there are many people getting on at landing 1 and going up, filling up every car, and there is somebody on landing 2 who is waiting to go up for a long time but cannot because the cars are always full?
5. What about making the elevators aware of the day of the week and time of the day? When an elevator is idle, should it move to the entry landing that is most often used at that time slot?
6. What if the elevator cars have scales so they can determine whether they are empty or not? How would this impact the movement of the cars?

That is just a small sample of the dozens of scenarios. Now that you have read this far I will give you the bad news: I do not have an answer, only an approach:

The primary thing I have discovered, when thinking about this problem, is that it seems to be a bad idea to actually summon a specific car to a landing and “lock that in as a destination.” Everything works much better if you have rules for balancing the requests and minimizing ride time, then reevaluate those rules every time there is a change in the situation, such as a car reaching a landing or a button being pressed. The decisions should involve the “movement direction” (up or down) of each car rather than the “destination landing.”

I’m not confident that this is the very best approach, mostly because it appears that real elevators don’t always work this way, although it seems that they usually do. But it is a good approach.

This is one of my favorite engineering problems. We learned about this in day 1 of our introduction to Systems Engineering course. Our professor posed the question to us. We generalized it to: "how does one reduce dissatisfaction caused by long wait times for the elevator?"

There are many algorithms and computational techniques one could use. Monte Carlo simulation comes to mind, as the elevator algorithms have to be tested under different types of conditions and different levels of variability come into play. Additionally, queueing theory could prove useful.

Despite all this, our professor proposed a very simple solution (that only now do I see as elegant): install mirrors near the elevators doors on each floor. That way, people can fix their hair and remain pre-occupied while they wait. You don't actually speed up the elevators, but do solve the larger problem of user dissatisfaction.

There is no standard. 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 several 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. (1) 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. (2) If the elevator is moving towards the call, but the call is in the opposite direction, FS = (N + 1) - d. (3) 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.

Frankly there is NO “perfect elevator logic”. I say a commercial high rise office scenario, there are surely “rush time” with people generally going up (say in the morning around start time), at the end of nominal lunch times, and then the load shifts to “down” at the nominal end of lunch times and nominal end of the work day. Even then there is much at least short term performance gains to be achieved by the decisions re how long to wait before “going up? vs waiting for more people to enter the before leaving. Etc etc… All pretty analogous to the problem of how to control street level traffic at stop lights. So LOTS of factors to consider, including in some cases, what type of “elevator traffic” if ANY should get prioirity.

The real questions are how to detect and adapt to the various “service priority concerns”. That implies “AI logic computerization” circa 2025; in “the old days” we just called it “adaptive control” and used it quite effectively if crudely in many applications, personally in regards to making “batches” of glass making ingredient formulas to feed furrnaces that ran 24x7x365 and later re the utilization of robotic pallet transports (think automated forklifts) to deliver empty bottles into an automated warehaose, then on demand to specific bottling lines when needed, and deliveing bottled goods back into the automated warehouse and/or the shipping dock when needed. All very dynamically changing work loads and varying priorities throughout the day and from day to day. The AI we used was called simply “smart adaptive control logic” - some tasks prioritized with allowance for not forgetting any need too long.

It’s NOT easy as pie, BUT doable. More easily doable perhaps with faster computer systems and better sensors.

First, you have to understand that the MTA is not a single, homogeneous authority that runs its subsidiaries directly. It is more like a holding company with executive, administrative and operating redundancies. Why? The New York State Public Authorities Law demands it.

The following is a list of the legal names of the various operating authorities which are owned by the MTA: New York City Transit Authority, Manhattan & Bronx Surface Transit Authority, Staten Island Rapid Transit Operating Authority, MTA Bus Company, Long Island Rail Road, Metro North Commuter Railroad and the Triborough Bridge & Tunnel Authority. Each authority, under NYSPAL, must carry its own set of financial records including budgets. While the MTA has done its best to rationalize operations, unless the State Legislature allows full reorganization into, say, four basic operating divisions (Rapid Transit, Surface Transit, Commuter Rail and Bridges & Tunnels), there is nothing the MTA can legally do to cut its structural redundancy. Most other inefficiencies stem from this basic problem.

Let’s take purchase of commuter rail cars as an example. The basic electric car purchased for the LIRR & Metro North is the M-7 model. M-7s for the LIRR must have hot shoes that make contact on top of the third rail. M-7S for the Hudson & Harlem lines must have hot shoes that make contact on bottom of the third rail. M-7s purchased for the New Haven line must not only have the underside hot shoe but also pantographs. In addition, the New Haven line is co-owned by the MTA and the Connecticut Department of Transportation. Therefore, it has to be decided how many cars will be bought and owned by the MTA and how many by CDOT. There are plenty more examples of these kinds of complexities throughout the MTA system. Remember, all operating authorities existed before the MTA, particularly the commuter railroads which were inherited from bankrupt private operators (LIRR, Penn Central & NYNH&H). The NY Subway system consisted of two privately operated companies (IRT &BRT/BMT) as well as the publicly owned IND.

This is just the tip of the iceberg but if I went into this in further detail this answer would become a book.

I don’t have an answer to reasoning the elevator problem but I do have a point of appreciation… before there were processors, video sensors, and AI there were machinists, PEOPLE, who designed and built the “brains” for fully mechanized elevator systems.

This is the analog “auto attendant synchronizer” for a 10-story 2-car elevator system from a building I used to work in on Wilshire Blvd in L.A. It’s an amazing and beautiful thing don’t you think?

It did the work after-hours when the elevator operator was off duty. I *think* but don’t know for sure that the dial with the larger set of numbers on it is reading feet and not floors.

So while pondering your high-tech answers or get stuck in one of them IOTA digital lift boxes please have some appreciation for the folks that made this intelligent hunk of metal!

The basic directives that Deepankit Shukla lays out in his answer are a good place to start, and probably the algorithm that most elevator systems rely on. However, there are a number of optimizations to layer on top. I’ll discuss two here: energy optimization and speed optimization.

Consider cases where two elevators are equidistant from the requesting floor, one above and one below. Also assume that the elevators move up and down at the same rate (not necessarily the case, but let’s assume for the sake of argument): Presumably you call the above (using spent energy rather than new energy) to the requested floor. If there is an elevator twenty floors above and another two floors below the requesting floor, maybe you should call the below elevator, and reserve the higher elevator (with more spent/potential energy) for a higher floor request later. Let’s take this scenario: You have two elevators: one on the 3rd floor, and one on the 18th floor. Someone on the 6th floor calls an elevator. It seems that if the 18th floor is going to pick up a passenger on its way down, it will be on the 9th floor, on average. Given that your “expected” value of that elevator is 9 and you’d be spending it on a 6, you’re losing 3 units of energy. Likewise, You’d lose three units of energy traveling upward from the 3rd to the 6th floor. If you factor in convenience to the user (speed), you should call the elevator on the 3rd floor. If this is a low-population building and you only care about energy efficiency, you should still choose the elevator from the 18th floor (since the energy has already been spent). If the call were on the 5th floor, or if the lower elevator were starting off on the 4th floor, you would use the lower elevator (in these cases, it’s more energy efficient and faster).

No. The computers of yore ran at constant speed (when they weren’t halted). With recent PC’s it’s more complex: when the CPU is running at full speed that speed is lower than when it’s idle, but what is the point of a computer being able to run faster at times when it’s not running any processes?

I assume that “algorithm” means “application program”. Application programs don’t alter the speed of the hardware. The performance of the jobs a computer is running is determined by the speed of the hardware, the efficiency of the OS, and the applications. A more efficient algorithm should result in an application taking less time to run or needing less memory.

One of the most effective optimizations to elevator traffic (in a big building, at least) is actually a bit of an overhaul: Replace the "up" and "down" buttons with floor buttons and remove the floor buttons in the elevators. The advantages are obvious: People moving in small increments (1 or 2 floors) can all be put on the same elevator, and an express elevator free of these hoppers takes people long distances without having to make a stop at every floor.

Unfortunately, humans don't like this system. We like to feel in control, and the shock of stepping into an elevator with no button other than "STOP" makes us feel helpless. So nobody uses this kind of system.

The closest we can come to this, then, is just to have an algorithm that prioritizes direction first (you don't want to schedule an elevator heading up to pick someone up who wants to go down) and then just doesn't make stops if it's heading up many floors until it gets close to its destination.

Many early elevators just had a 'call' button on each floor; only when you entered the elevator could you direct it to a particular floor. Eventually, designers changed this to 'call to ascend' and 'call to descend', as this allows an elevator that is already going downwards to skip someone waiting to go upwards, for example.

I believe a sensible progression is to allow the user to select the floor they wish to go while waiting. Behind the scenes, this data could permit a more efficient routing algorithm, and even more so in multi-elevator scenarios. There are several drawbacks to this however, including the cost of the additional buttons or more sophisticated interface, the difficulty of defining the algorithm in a generic way across different buildings, etc.

Finally, concepts from machine learning could be employ to build models of the likely collection and destination floors required at certain times, since human behaviour is surprisingly regular in this regard.

Most, or all of the features you talk about are available for elevators, but they are often not purchased by the builder of the building. For example, for a good anti-nuisance feature operation, (the cancelling of excessive calls being entered for no reason) you need a load weighing device in the elevator to compare the number of calls with the number of occupants. This adds initial costs and maintenance complexity and costs to keep it calibrated.
Door open buttons are occasionally temporarily disconnected by elevator technicians who cannibalize the button parts or electronic parts to keep other features running.

Elevator cars take time to reach certain floors, depending on all sorts of dynamics of a given situation, including such items as:

• the distance from the beginning to the end of a trip
• the direction that a specific car is already moving when it is summoned
• the overall time-of-day elevator loading (such as lunchtime overloading)
• the trip interruptions, such as by those annoying people who want to get on or off in the middle of your own trip
• the relative health of each car (for example, if two cars in a bank of elevator cars are currently out of service for purposes of maintenance, then all of the remaining cars will have sub-optimum performance due to the overload)
• unexpected glitches or unusual passenger behaviours in operations
• the overall algorithm governing the elevator system operations (for example, if the “home” location for cars is mid-height of the building, then the times to reach top or bottom would be similar, whereas bottom or top homes would result in widely different timings).

Numerous other factors could alter the observed timings. Further, it is not individual timings that are important, but average timings during peak loads, time of day, and so on.

Some algorithms can be helpful for average times. For example, during the morning rush for employee arrivals, the system could be biased so that the elevator cars tend to have a home location at the building’s ground floor lobby, whereas at the end of the day, when employees leave, the home location could be at mid building height.

So far I have only addressed business elevators. Different algorithms might be applicable for residential buildings.

Elevator system design, and especially elevator user interaction models, is one of my amateur interests during my retirement. See, for example, my book Making Products Obvious, sometimes available from online book retailers. One of the things that I advocate in that book is replacing the two buttons “Open Door” and “Close Door” by only one single button “DOOR”. That DOOR button would toggle the current state of an elevator car door: if the door is closed or closing, pressing the DOOR button would cause the door to start opening; if the door is open or opening, it would start closing. Pressing and holding the DOOR button would cause the door to remain in its current state. I advocate such a design for all elevator manufacturers, along with many other design improvements, such as double-pressing a floor button should cancel a mistaken previous selection.

SCAN scheduling algo. is used in elevators. SCAN is a disk scheduling
algorithm to determine the motion of the disk's arm and
head in servicing read and write requests.
This algorithm is named after the behavior of a building
elevator , where the elevator continues to travel in its
current direction (up or down) until empty, stopping only
to let individuals off or to pick up new individuals
heading in the same direction.
From an implementation perspective, the drive maintains
a buffer of pending read/write requests, along with the
associated cylinder number of the request. Lower cylinder
numbers indicate that the cylinder is closest to the
spindle, and higher numbers indicate the cylinder is
farther away.
Description:••
When a new request arrives while the drive is idle, the
initial arm/head movement will be in the direction of the
cylinder where the data is stored, either in or out . As
additional requests arrive, requests are serviced only in
the current direction of arm movement until the arm
reaches the edge of the disk. When this happens, the
direction of the arm reverses, and the requests that were
remaining in the opposite direction are serviced, and so
on

The NYC may be old, but it is far from unreliable. As someone who has been taking it for more than 25 years, I can tell you that it’s reliability has gotten better, not worse. If you have facts to support your contention that it’s getting worse, I’d like to see them. I’d also point out that NYC has a far better public transportation system (as far as it’s ability to get you anywhere you need to go in Manhattan and a good chunk of the other boros quickly and cheaply) than any other major US city, and operates it on a far, far greater scale.

EDIT 1/31/2018: Since originally writing this answer, I’ve seen additional statistics regarding subway on-time rates and other reliability measures have been showing a clear decrease. That’s not to say the subway isn’t overall reliable, but things definitely are not going in the right direction. There are a number of reasons for this, tied up in politics, money and societal choices, which are too complex to get into here. But suffice it to say that I would amend my original answer if I were to write it today.

That depends completely on the programme. However, it is relevant to understand the objectives of the programme. Mainly, you need to consider two different notions of 'efficient', when it comes to an efficient programme. The first is bandwidth, the other is latency. The first is 'how many people per hour', the second is 'how long do people wait after pressing the button'. In a crowded office building or mall, the former is more important (if the bandwidth is insufficient, the elevator queues of people will form faster than the elevator can serve them). In a residential flat, the latter is typically more important (queues are unlikely to form).

Thus, different circumstances require different programmes. In fact, some elevators are programmed to have 'rush hour' and 'after hour' programmes.