This is a multiple-elevator system sim that is primarily meant to run in the browser.
This is a React project made with Vite, so after installing dependencies with yarn you can run either
yarn dev
to start the Vite server in development mode with hot module reloading, or
yarn build && serve ./dist
to make a production build and serve it locally.
(all related code in directory src/lib/.)
The task at hand is to:
- manage a discrete-time system of elevators;
- dispatch pick-up requests at any point in time to the optimal elevator and go-to requests when a passenger first enters one;
- maintain appropriate movement for each elevator in the system.
Seeing this, we can deduce that there's two main parts to the problem; dispatching requests to elevators and actually moving them.
Defined in lib/ElevatorSystem.ts, the function dispatch contains the logic for picking out the "optimal" elevator to assign a pick-up request to. This is how it's done:
First, we look if there are any idle elevators, i.e. ones that have no requests/stops left. We assign the request to the one closest to its origin.
Otherwise, we look for elevators going in the direction of the request and whose direction is the same as that of the request (i.e. "the button pressed on the wall", or the sign of <goal floor number> - <origin floor number>). We assign the request to the one closest to its origin and least busy (in that order of priority).
At last, in the pessimistic case, there are no elevators that are either idle or going in the direction of the request. We simply assign the request to the elevator closest and least busy. This is not too great of a worry because it's a pretty improbable scenario (in real-life conditions) either way.
This entire approach is not proven to be the one most optimal or efficient but it's intuitive and does not make simple mistakes to suboptimally pile tasks on one elevator, trying to make the most of the distributed system we're working with.
The second part of the problem is actually moving the elevators. We do that every step — defined, again, in lib/ElevatorSystem.ts.
A naïve solution to the elevator problem is to make each elevator instance hold:
- a request queue,
- a current floor destination.
Every stop the elevator could pop one request from the queue and set it as its destination. One can quickly see, though, that that's very unperformant...
Say an elevator at F0 (for the purposes of this example, an only elevator in a system) has received a pick-up request at F1. While going there, it received another pick-up request, this time at F10. Now the queue is simply [ 10 ] (1 was popped in the initial stop state).
As the F1 passenger gets in, they put in F2 as their destination. Now the queue is [ 10 2 ] The elevator, stopped at F1, pops the 10 from the queue and goes there, when it could've let out the first passenger at F2 on the way there!
The first passenger is forced to ride the elevator for an unnecessarily long time, same as the other passenger: when they get in, they put in F11 as their destination. This time the elevator turns back, going down to let out the initial passenger. The second passenger is forced to ride through |10 - 2| + |11 - 2| = 17 floors, when their destination was just one floor away!
We aid this by using a different kind of data structure to keep track of an elevator's requests, namely a boolean array with one index for each floor.
When a request is dispatched to floor i, the ith value of the array is set to true. Each time it stops, the elevator checks if there are any true values further down its path in the current direction. If there are, it continues, stopping on each floor whose value is set to true, exchanging passengers there, marking the floor in the array as false, and once again updating its direction.
If there are no stops scheduled down the current direction, an elevator turns back, performs the same check and moves if it should. Otherwise it stays idle.
This kind of logic (defined in lib/Elevator.ts) allows for picking up and letting off passengers "on the way" and making the least number of direction changes, figuratively "sweeping" the building up and down. It is not hard to see our previous example is rendered optimally when operating in this manner.
There's a couple of tricks this algorithm does not use and opinionated approaches it makes.
One of the latter is on-the-way pickups. If someone is going from floor 1 to floor 5 and, in the meantime, a pick-up request is made at floor 3, if there's an idle elevator available on any floor, the system makes it so that the request will be dispatched to it, not to the moving elevator. On one hand this is less time-efficient but on the other it disperses passengers across more elevators, which is beneficial both formally and socially — elevator rides with strangers are never not awkward.
A trick some commercial elevator systems appear to use (speaking from personal experience) is sending elevators which have been idle for a set amount of time to the ground floor — making use of the observation that it is generally the most picked-up-from floor. We don't utilise this strategy, though it's entirely possible.
On the code side, a bummer is that there is no actual declaration file for the library.
The frontend for this system is written in client-side React, with the help of Vite. Component logic and styles are all in the src/components/ directory.
In this panel, you can view the state of every single elevator at once. The Play and Pause buttons control a one-second step interval. A red status light indicates an elevator is stopped (though not necessarily idle) and a green one that it is moving in the direction shown below the light.
Clicking on an elevator will log detailed info about its passengers in the Console.
All pick-up requests are logged here; both randomly generated ones and user-generated ones. The generation of the latter can be controlled via the buttons at the top. A new request is made every 2 seconds only if both "Randomly generate passengers? Yes" and "Play" are pressed.
By choosing origin and destination floors, you can make your own pick-up-and-go-to requests. Your choice is limited between 0 and FLOOR_COUNT, a constant defined in src/lib/util.ts which you can modify (as well as ELEVATOR_COUNT and the DEBUG flag which logs all elevators' statuses to the browser console) as you wish before serving. Randomly generated requests are always between two different floors but you are free to make a same-floor request — though its execution is not too interesting to view in action.
You can utilise the Wizard together with Play/Pause to test any kind of edge-case possible.
Most importantly, this interface is fully functional, straightforward and uncluttered visually; however, there's quite many things in it that could be improved upon:
- maybe we should log more info to the Console;
- the design is not super responsive and sadly not too usable on mobile;
- in connection with the above, a feature idea: when viewed on mobile, the interface could change to one similar to a real-life elevator button array along with a segment display on top;
- we could easily keep track of each passenger's iterations spent both waiting for an elevator as well as inside it and calculate and show average waiting/riding times.
On the code side, state logic in the App component is somewhat messy. Perhaps it could be simplified.