Elevator algorithm for minimum distance

Question

I have a building with a single elevator and I need to find an algorithm for this elevator. We gets a list of objects of this form: {i->j}, where i is the floor that a resident wants to take the elevator from and j is the floor he wants to get down on.

An infinite amount of people can use the elevator at the same time, and it's irrelevant how long people stay in the elevator. The elevator starts from the first floor.

I checked a little on the web and I found the "elevator algorithm" but it doesn't really help me. It says that I should go all the way up and then all the way down. But consider when one resident wants to go from 1 to 100 and another resident wants to go from 50 to 49. Using the above algorithm, it will take a distance of 151 floors. If I instead follow this path: 1->50->49->100, it takes only 102 floors, which is better.

What algorithm should I use?

Answer 1

Here's one way to formulate this problem as a Time-based Integer Program. (It might seem like an overkill to generate all the constraints, but it is guaranteed to produce the optimal solution)

Let's say that elevator takes 1 unit of time to go from floor F to F+1 or to F-1.

The Insight: We use the fact that at any time t, there is only one decision to be made. Whether to go UP or to go DOWN. That is the Decision Variable for our problem. DIR_t = +1 if the elevator moves up at time t, -1 otherwise.

We want to minimize the time when all the passengers reach their destination.

This table makes it clearer

Time    FLOOR_t   Dir_t
1        1          1
2       2           1
3       3           1
4       4           1
...    ...          ...
49      49          1
50      50          -1
51      49          1
52      50          1
...     
100     99          1
101     100         NA

Now, let's bring in the passengers. There are P passengers and each one wants to go from SF to EF (their starting Floor to their ending floor, their destination.)

So we are given (SF_p, EF_p) for each passenger p.

Constraints

We know that the Floor in which the elevator is present at time t is

 F_t = F_t-1 + DIR_t-1

(F0 = 0, DIR_0 = 1, F1 = 1 just to start things off.)

Now, let ST_p be the time instant when passenger p Starts their elevator journey. Let ET_p be the time instant when passenger p ends their elevator journey. Note that SF and EF are input parameters given to us, but ST and ET are variables that the IP will set when solving. That is, the floors are given to us, we have to come up with the times.

   ST_p = t if F_t = SF_p  # whenever the elevator comes to a passenger's starting floor, their journey starts.       
   ET_p = t if F_t = EF_p AND ST_p > 0 (a passenger cannot end their journey before it commenced.)
   This can be enforced by introducing new 0/1 indicator variables.

   ETp > STp # you can only get off after you got on
   

Finally, let's introduce one number T which is the time when the entire set of trips is done. It is the max of all ET's for each p. This is what needs to be minimized.

   T > ET_p for all p # we want to find the time when the last passenger gets off.

Formulation

Putting it all together:

   Min T
   
   T > ET_p for all p
   F_t = F_t-1 + DIR_t-1
   ETp > STp # you can only get off after you got on 
   ST_p = t if F_t = SF_p  # whenever the elevator some to a passenger's starting floor, their journey starts.
   ET_p = t if F_t = EF_p AND ST_p > 0
   ET_p >= 1 #everyone should end their journey. Otherwise model will give 0 as the obj function value.
   DIR_t = (+1, -1) # can be enforced with 2 binary variables if needed.

Now after solving this IP problem, the exact trip can be traced using the values of each DIR_t for each t.

Answer 2

There's a polynomial-time dynamic program whose running time does not depend on the number of floors. If we pick up passengers greedily and make them wait, then the relevant state is the interval of floors that the elevator has visited (hence the passengers picked up), the floor on which the elevator most recently picked up or dropped off, and two optional values: the lowest floor it is obligated to visit for the purpose of dropping off passengers currently inside, and the highest. All of this state can be described by the identities of five passengers plus a constant number of bits.

I'm quite sure that there is room for improvement here.