Elevator algorithm for minimum distance

Question

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

An infinite number of people can use the elevator at the same time, and it does not matter how long people stay in the elevator. The elevator starts from the first floor.

I checked a bit on the Internet and I found the "elevator algorithm", but it really doesn't help me. It says that I have to go all the way, and then all the way down. But think about it, when one resident wants to go from 1 to 100, and the other resident wants to go from 50 to 49. Using the above algorithm, he will occupy the 151 floor. If I follow this path instead: 1-> 50-> 49-> 100, it only takes 102 floors, which is better.

Which algorithm should I use?

Answer 1

Here is one way to state this problem as an Integer Time Program. (This may seem redundant to generate all the restrictions, but it is guaranteed to provide the optimal solution)

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

Insight: We use the fact that at any time t only one decision must be made. Do go or go down. This is Variable Variable for our problem. DIR_t = +1 if the elevator rises at time t, -1 otherwise.

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

This table simplifies

 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 me bring the passengers. There are P passengers, and everyone wants to switch from SF to EF (their ground floor to end floor, their destination.)

Thus, we give (SF_p, EF_p) for each passenger p .

Limitations

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 to start all.)

Now let ST_p be the time when passenger p begins his journey through the elevator. Let ET_p be the point in time when passenger p finishes the elevator ride. Note that SF and EF are the entered parameters, but ST and ET are the variables that IP will set when solving. That is, the floors are given to us, we must come up with time.

  ST_p = t if F_t = SF_p # whenever the elevator comes to a passenger 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, we introduce one number t , which is the execution time of the entire set of trips. This is the maximum of all ET 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. 

Composition

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 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 problem with IP, precise tracking can be tracked using the values ​​of each DIR_t for each t .

Answer 2

There is a dynamic program with polynomial time, the operating time of which does not depend on the number of floors. If we greedily collect passengers and make them wait, then the corresponding state is the interval of floors that the elevator visited (therefore, the passengers are raised), the floor on which the elevator was recently lifted or reset, and two optional values: the lowest floor, which he is obliged to visit in order to reset passengers inside and of the highest level. All this state can be described by identifiers of five passengers plus a constant number of bits.

I am absolutely sure that there is room for improvement.

Answer 3

Your question reflects voice head scheduling algorithms.

Check out the shortest search time at the start of vs scan, cscan, etc. .

There are times when sstf wins, but what if it was from 50 to 10, and you also had from 2 to 100, from 3 to 100, from 4 to 100, from 5 to 100, from 6 to 100, etc. d. You may notice overhead for all other people. In addition, if incoming requests have a shorter search time, starvation can occur (similar to process scheduling).

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

Answer 4

In the comments on CB, the OP response comments: "the requests are static, at the beginning I get a complete list." I would welcome counter examples and / or other reviews, since it seems to me that if we are given all the trips in advance, the problem can be dramatically reduced if we consider the following:

• Since the elevator has unlimited bandwidth, any trips going up this end are lower than the highest floor that we will visit are not related to our calculations. Since we guarantee the transfer of all these pickups and exits on the way to the highest point, we can put them on our schedule after considering the top-down trips.

• Any trips “contained” in other trips in one direction are also irrelevant, since we will transfer these pickups and departures during the “most external” trips and can be accordingly planned after consideration.

• Any overlapping downstream trips can be combined for some reason, which will soon become apparent.

• Any downward trips occur either before or after reaching the highest point (except that the top floor has reached the pickup). The optimal schedule for all downstream trips that we have defined in order to happen to the highest point (considering only the types of “external container” and two or more overlapping trips as one trip), one after the other, when we go up as we are on the way anyway.

How to determine which downstream trips should occur after the highest point?

We carry out our calculation on one point, TOP . Let me name a trip that includes the top floor reached by H and the top floor reached HFR . If HFR is a pickup, H decreases and TOP = H_dropoff . If HFR is dropoff, H increases and TOP = HFR .

The lowering trips that must be planned after the top floor is visited are members of the largest group of neighboring downstream trips (considering only the types of “external containers” and two or more overlapping trips as one trip) that we can collect, starting from the next lower descending departure after TOP and continuing down, where their combined individual distances double, more than the total distance from TOP to their last fall. That is, where (D1 + D2 + D3...+ Dn) * 2 > TOP - Dn_dropoff

Here's a rude attempt at 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 ab = 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(\ab -> compare ba) 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 (\ab -> compare ba) 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]