From: chrisman@ucdmath.ucdavis.edu (Mark Chrisman) Newsgroups: sci.math Subject: Re: Elevator Theory? Date: 2 Dec 1994 22:50:39 GMT In article grip@netcom.com writes: > Matthew W. Miller (matt.miller@daytonoh.ncr.com) wrote: > : While waiting for my favorite form of semi-public transportation this morning, I > : was struck by the fact that I am not sure of the algorhythm used for 'sorting' > : passangers. > : I am sure that somewhere in this vast world, someone has worked out a logic for > : determining which elevator goes where. (This question obviously refers to banks > : of elevators selected by a single button.) > > : It HAS occured to me that it may be a simple "if this elevator is passing a > : floor in the correct direction, stop and pick up" for the middle floors. *Is* > : there logic built in to some more sophisticated systems? > > : Even if you're not working on this, and know nothing about it, have you got a > : theory as to how it SHOULD work? > > I doubt that there is any relatively simple algorithm. A program could be > developed with all sorts of checks in it for various conditions. > Certainly a check for an elevator heading in the right direction to pick > up is needed. One could also put in clocks so that in the morning when > most elevators are going up full and down empty, the elevators > automatically head back down when idle. In between they should be parked > at reasonably spaced intervals. If these considerations are parameterized > then each set could be customer dependent. > > One could go farther and keep statistics on use by day and time of day > and automatically adjust the behaviors. > > An interesting programming problem. > > grip I read recently that someone was trying to apply genetic algorithms to the problem. I don't remember the reference. An interesting obstacle to developing a dynamic algorithm is that it's hard for the program to be sure what's really going on. The program "knows" which buttons were pressed, when, and how often, but it doesn't know (for example) how many people got on and off at each stop. So, we should have electric eyes and weight scales to try to count how many people are in the elevator at a given time, and also electric eyes to try to count the number of people waiting at each floor. Also, instead of having "up" and "down" buttons outside the elevator door, it would be more useful (to the elevator program) to have a full array of buttons outside the door. The more the program knows what people want, the better it will perform. Consider the following situations (which are not uncommon): 1. The 6th floor (top floor) is a much more common destination than the 5th (according to the logs of the elevator in a particular building). Ten people enter the elevator on the first floor, and buttons 5 and 6 are pressed. The program estimates that only one of the people wants the 5th floor; the remaining 9 are going to the 6th. The "standard" algorithm says, first stop on the 5th, then continue to the 6th. But a better response (to minimize total waiting/riding time) might be to bypass the 5th floor and let the nine people off on the 6th, then return to the 5th floor for the remaining person. The point here is to give higher priority for the larger group. 2. The ground floor is much more common than the basement. Suppose the elevator is on the third floor, and inside the elevator the "gound" and "basement" buttons are pressed. Suppose also people on the ground floor have pushed the "up" button. The standard algorithm is: first, descend to ground floor, drop off passengers (but flash the "going down" light so people don't get on), descend to basement & drop off passengers, ascend to ground floor and pick up passengers. There are two better ways to handle the situation: (1) go to ground floor, let off passengers AND pick up passengers going up; then go to basement, then ascend WITHOUT stopping on the ground floor again; or (2) go to basement, drop off passengers, ascend to ground floor, drop off passengers and pick up new passengers. The point here is to try to cut down on the number of stops (it's the stops that take up all the time, not the moving up and down). 3. Elevator A starts on the first floor, and will stop on the 8th. Elevator B is also going up (a few seconds behind elevator A) and will stop on the 4nd and 6th. Someone pushes the "up" button on the fourth floor. The standard algorithm will make elevator A stop on the fourth (because A arrives there before B). But it would be better to have A continue on, and have B pick up the passenger (because B was going to stop there anyway). The point here is that the elevator cars should not act independently. Also, it would help if the person on the 4th floor could say something more specific than "up". For example, if that person wanted to go to the 6th floor, he could press a "6" button, and definitely elevator B would stop for him. But maybe he wants to go to the 8th; in that case, it might be better after all for A to stop. One final comment. Logically, the goal should be to minimize the average waiting/riding time. But this leaves open the possibility that one person will end up spending an hour on the elevator because it would be more efficient to transport other people (say, in large groups) first. A common response to this is to try to minimize the average (waiting/riding time)^2, or to put some upper bound on the time. (The standard algorithm has such an upper bound.) But, in real life, it is possible that algorithm A gives a better average than algorithm B, but that A is *perceived* by people to be slower than B. Do we want to maximize actual speed, or perceived speed? Here is another puzzle (one which should be solvable using standard probability techniques). Suppose there is only one elevator car, and that it runs on the standard algorithm, and that all elevator journeys have the ground floor as either starting point or destination (a reasonable assumption). You are on the 5th floor (of 10), and you want to go down to the gound floor. You also have to use the restroom. You can do so here on the 5th floor or on the ground floor. But you want to minimize your wait for the elevator car. Obviously, if you see the elevator doors opening, you should jump in and use the restroom on the ground floor. The question is: what do you do if you don't see the elevator doors opening? What do you do if someone has already pushed the "down" button but the elevator hasn't arrived? -------------------------------------------------------- Mark Chrisman (if your reply is of general interest please post it, don't email it.) ============================================================================== From: dick@silicon.csci.csusb.edu (Dr. Richard Botting) Newsgroups: sci.math Subject: Re: Elevator Theory? Date: 5 Dec 1994 07:21:58 GMT The "lift problem"/"elevator problem" has been used as a case study as nauseum by people researching methods for specifying and designing computer software. There have been dozen's of treatments. It is in M A Jackson's book on Jackson System Development (I think ... it was in his course in 1981). And also some recent Software Engineering texts. The International Workshop on Software Specification and Dessign used it one year ... along with a library and a central heating system as an example... I can send detailed refs. if necessary. To be honest after 14 years of elevators, I'm rather tired of them. A variation of the problem that is important is how to move the head of a disk from track to track, given that a certain subset of tracks are needed to be vissitted... One algorithm is called the elevator algorithm. In My Humble Opinion, the trick for a set of real elevators with real buttons etc. is to have maintain a function that maps each button into a "best" elevator to serve it, *if* it happens to be pressed... As an elevator moves past another elevator it collects all that elevator's buttons that lie in the "same" direction as the overtaking elevator's movement. Perhaps a version for the StarTrek TurboLift (That can move sideways into new shafts...) might be more interesting? -- EMail: dick@csci.csusb.edu=rbotting@wiley.csusb.edu. ftp://ftp.csci.csusb.edu/dick WWW Disclaimer::=`CSUSB may or may not agree with this message`. Copyright(1994)::=`Copy as long as you include this copyright and signature`.