I have a skyscraper with N floors and an elevator. When people arrive on a floor they push the button of their desired destination. So in real time the elevator robot keeps a list of orders, each entry having an origin floor, a destination floor, a time stamp, and a flag telling the robot if the person has been picked up and is now a passenger. I need a good strategy for bringing many people to their destinations fast. But not too complicated at first. It should be memoryless, i.e. the decision should only depend on the current list of orders.
If the time now is t and the elevator is at floor x(t) it must decide whether to go up one floor or down one floor. When it arrives at a floor it stops and opens the door if and only if somebody has ordered that floor as an origin and is not a passenger or destination and is a passenger. But regardless it reconsiders where to go next.
Is a good strategy known? Not to say optimal? The criterion of optimality? It should complete the greatest number of orders in the shortest amount of time.
My only idea so far is to use center of gravity: If xi is the origin and yi the destination of order i, and pi the passenger flag, let z = 1/n sum( (1-pi)xi + piyi ). Then if z < x(t) we go down one floor, otherwise up. But I worry that this could result in a deadlock, perpetually going up and down between floors x and x+1.
Edit. One more thought. One should consider the age of an order. If ti is the time stamp of order i, one should put greater weight on this order if (t - ti) is large. So a weighed center of gravity? Let ai = t - ti and a = sum(ai). Then z = 1/a sum( ai((1-pi)xi + piyi) ).
Edit 2. One should also consider inertia. If the elevator is on its way up the decision might differ from that when it's going down. But I don't know how to take this into account. An inertia strategy might be to never reconsider where to go until the elevator has stopped on a floor. And it only does so if somebody is getting on or off.
Edit 3. Another consideration is load. The elevator doesn't know how many people are on board, but it knows the current load. If that load approaches max it should give priority to bringing people to their destinations rather than picking up more. But how exactly?