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

In the comments to C.B.'s answer, the OP comments: "the requests are static. in the beginning i get the full list." I would welcome counter examples and/or other feedback since it seems to me that if we are given all trips in advance, the problem can be drastically reduced if we consider the following:

1. Since the elevator has an unlimited capacity, any trips going up that end lower than the highest floor we will visit are irrelevant to our calculation. Since we are guaranteed to pass all those pickups and dropoffs on the way to the highest point, we can place them in our schedule after considering the descending trips.

2. Any trips 'contained' in other trips of the same direction are also irrelevant since we will pass those pickups and dropoffs during the 'outer-most' trips, and may be appropriately scheduled after considering those.

3. Any overlapping descending trips may be combined for a reason soon to be apparent.

4. Any descending trips occur either before or after the highest point is reached (excluding the highest floor reached being a pickup). The optimal schedule for all descending trips that we've determined to occur before the highest point (considering only 'outer-container' types and two or more overlapping trips as one trip) is one-by-one as we ascend, since we are on the way up anyway.

How do we determine which descending trips should occur after the highest point?

We conduct our calculation in reference to one point, TOP. Let's call the trip that includes the highest floor reached H and the highest floor reached HFR. If HFR is a pickup, H is descending and TOP = H_dropoff. If HFR is a dropoff, H is ascending and TOP = HFR.

The descending trips that should be scheduled after the highest floor to be visited are all members of the largest group of adjacent descending trips (considering only 'outer-container' types and two or more overlapping trips as one trip) that we can gather, starting from the next lower descending trip after TOP and continuing downward, where their combined individual distances, doubled, is greater than the total distance from TOP to their last dropoff. That is, where (D1 + D2 + D3...+ Dn) * 2 > TOP - Dn_dropoff

Here's a crude attempt in Haskell:

import Data.List (sort,sortBy)

trips = [(101,100),(50,49),(25,19),(99,97),(95,93),(30,20),(35,70),(28,25)]

isDescending (a,a') = a > a'

areDescending a b = isDescending a && isDescending b

isContained aa@(a,a') bb@(b,b') = areDescending aa bb && a < b && a' > b'

extends aa@(a,a') bb@(b,b') = areDescending aa bb && a <= b && a > b' && a' < b'

max' aa@(a,a') bb@(b,b') = if (maximum [b,a,a'] == b) || (maximum [b',a,a'] == b')
                              then bb
                              else aa

(outerDescents,innerDescents,ascents,topTrip) = foldr f ([],[],[],(0,0)) trips where
  f trip (outerDescents,innerDescents,ascents,topTrip) = g outerDescents trip ([],innerDescents,ascents,topTrip) where
    g [] trip (outerDescents,innerDescents,ascents,topTrip) = (trip:outerDescents,innerDescents,ascents,max' trip topTrip)
    g (descent:descents) trip (outerDescents,innerDescents,ascents,topTrip)
      | not (isDescending trip) = (outerDescents ++ (descent:descents),innerDescents,trip:ascents,max' trip topTrip)
      | isContained trip descent = (outerDescents ++ (descent:descents),trip:innerDescents,ascents,topTrip)
      | isContained descent trip = (trip:outerDescents ++ descents,descent:innerDescents,ascents,max' trip topTrip)
      | extends trip descent = ((d,t'):outerDescents ++ descents,(t,d'):innerDescents,ascents,max' topTrip (d,t'))
      | extends descent trip = ((t,d'):outerDescents ++ descents,(d,t'):innerDescents,ascents,max' topTrip (t,d'))
      | otherwise = g descents trip (descent:outerDescents,innerDescents,ascents,topTrip)
     where (t,t') = trip
           (d,d') = descent

top = snd topTrip

scheduleFirst descents = (sum $ map (\(from,to) -> 2 * (from - to)) descents)
                       > top - (snd . last) descents

(descentsScheduledFirst,descentsScheduledAfterTop) =
  (descentsScheduledFirst,descentsScheduledAfterTop) where
    descentsScheduledAfterTop = (\x -> if not (null x) then head x else [])
                           . take 1 . filter scheduleFirst
                           $ foldl (\accum num -> take num sorted : accum) [] [1..length sorted]
    sorted = sortBy(\a b -> compare b a) outerDescents
    descentsScheduledFirst = if null descentsScheduledAfterTop
                                 then sorted
                                 else drop (length descentsScheduledAfterTop) sorted

scheduled = ((>>= \(a,b) -> [a,b]) $ sort descentsScheduledFirst) 
         ++ (if isDescending topTrip then [] else [top])
         ++ ((>>= \(a,b) -> [a,b]) $ sortBy (\a b -> compare b a) descentsScheduledAfterTop)

place _      []             _    _     = error "topTrip was not calculated."
place floor' (floor:floors) prev (accum,numStops)
  | floor' == prev || floor' == floor = (accum ++ [prev] ++ (floor:floors),numStops)
  | prev == floor                     = place floor' floors floor (accum,numStops)
  | prev < floor                      = f
  | prev > floor                      = g
 where f | floor' > prev && floor' < floor = (accum ++ [prev] ++ (floor':floor:floors),numStops)
         | otherwise                       = place floor' floors floor (accum ++ [prev],numStops + 1)
       g | floor' < prev && floor' > floor = (accum ++ [prev] ++ (floor':floor:floors),numStops)
         | otherwise                       = place floor' floors floor (accum ++ [prev],numStops + 1)

schedule trip@(from,to) floors = take num floors' ++ fst placeTo
  where placeFrom@(floors',num) = place from floors 1 ([],1)
        trimmed = drop num floors'
        placeTo = place to (tail trimmed) (head trimmed) ([],1)

solution = foldl (\trips trip -> schedule trip trips) scheduled (innerDescents ++ ascents) 

main = do print trips
          print solution

Output:

*Main> main
[(101,100),(50,49),(25,19),(99,97),(95,93),(30,20),(35,70),(28,25)]
[1,25,28,30,25,20,19,35,50,49,70,101,100,99,97,95,93]

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.

Answer 3

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 4

Your question mirrors disk-head scheduling algorithms.

Check out shortest seek time first vs scan, cscan, etc.

There are cases where sstf wins, but what if it was 50 to 10, and you also had 2 to 100, 3 to 100, 4 to 100, 5 to 100, 6 to 100 etc. You can see you add the overhead to all of the other people. Also, if incoming requests have a smaller seek time, starvation can occur (similar to process scheduling).

In your case, it really depends on if the requests are static or dynamic. If you want to minimize variance, go with scan/cscan etc.