Development of elevator movement algorithm

© Clip "Gangnam Style"

With the increase in the number of floors in our cities, more and more people use elevators every day. But few of us think about how all this lift population manages to more or less effectively deliver a lot of people during the day, especially during rush hours. There are a number of elevator motion algorithms that are based on various conditions, such as minimizing the waiting time for an elevator . But let's think about how you can develop an elevator algorithm.

With all the seeming simplicity of the task, it is rather difficult to create an elevator algorithm for real use in buildings. In addition, such things are considered trade secrets and patented. Therefore, we will try to make a simplified model:

The building on each floor has the same number of people. There are several elevators, no stairs. For simplicity, we assume that the same number of passengers on each floor is waiting for an elevator. We also know that during the day there are several rush hours. We need to come up with an algorithm to minimize the waiting time for all people in the building.

Here it is possible to identify several conditions that impede the solution of the problem:

• Arbitrary number of floors.
• An arbitrary number of elevators.
• There are periods of peak hours.
• The distribution of elevators should be described based on the function of the load and the waiting time.

We will also consider a few more variables and constants:

• The number of people on each floor is 100 people.
• The time it takes for the elevator to pass one floor without stopping is 5 seconds.
• The standing time of the elevator on the floor is 20 seconds.

Of course, in real life, the speed of passage of the floor by an elevator can be non-linear, because it accelerates and slows down. But to simplify the calculations, we discard it. If this seems to you an unnecessary simplification of the task, then you can then enter these conditions into the algorithm yourself.

Note that so far nothing has been said about the lifting capacity of elevators. Here we will also radically simplify our lives - we will assume that the elevator accommodates as many people as you like. Unrealistic, I agree. But then, when we have the first version of the algorithm, it will be easier to enter such conditions:

• If the elevator is full, then it goes down to the floor below.
• After disembarking all passengers, the elevator returns to the previous floor.

Elevator distribution algorithm

As is clear from the figure, each elevator is assigned a certain area of ​​responsibility . This is done in order to average the waiting time on each floor, as well as the load on each of the elevators. Each elevator can go through a cycle "floor 1 -> 2 -> 3 -> 0". Let's calculate how long it takes to complete a cycle:

1. The time of passing one floor is multiplied by the number of floors in the cycle and multiplied by two (because the elevator goes up and then down). In our model it turns out:
   5 * < > * 2.
2. The number of stops from the first to the last floors is multiplied by the duration of the stop. In our model:
   20 * < >.

Combine:
= (5 * < > * 2) + (20 * < >)

Now we calculate the average number of people we transport during one cycle:

= < > * < > * < > / < >

Here:

• <rush hour> is the time to complete one rush hour.
• <number of serviced floors> - the number of floors on which the elevator stops.

Now create two arrays:

1. The array of the building . The number of cells is equal to the number of floors. The contents of the cell indicate the number of people waiting on the floor.
2. Array of elevators . The number of cells is equal to the number of elevators. The contents of the cell denotes the “upper” floor to which this elevator goes. For example, in the array [2, 3, 4] three elevators are described: the first one goes no higher than the second floor, the second one –– not higher than the third, the third –– no higher than the fourth.

Let's start with the fact that the first array is empty, and then every time we add a floor to the array, we will assign an elevator to it. The nature of the addition will change, as we will see below, but in general it is described quite simply. Floors are added to cycles until load capacity becomes a limitation. We introduce a small function:

+ (( / 100) * )

<cycle time> is an integer until it reaches 100 seconds (long enough to stay in the elevator), and then <average elevator loads> are taken into account in the equation. Since our task was described rather vague, there is some ambiguity in the solution. Thus, the function of adding a floor to the area of ​​responsibility of the elevator is rather arbitrary, although it is effective in managing the load. There is probably a better solution.

Implementation of the function of adding a floor (Python):

 # ( * 5 ) + (20  * ( –  )) #    / ,  # (   * 2) +  ,    #  ,   [2]+=1 # e    ( ) def addFloor(e): best = 99999 for i in range(1, len(e)): cirTime, avgCarry = eleLoop(e, i) if cirTime + ((cirTime / 100) * avgCarry) < best: elevatorNumber = i best = cirTime + ((cirTime / 100) * avgCarry) for i in range(elevatorNumber, len(e)): e[i] += 1 return e 

Note: each time elevatorNumber chooses an elevator above the current elevatorNumber value, the size of the elevator array increases:

 for i in range(elevatorNumber, len(e)): e[i] += 1 

In each cycle, we increase by one the maximum floor after the selected elevator. Therefore, in the cycle of the selected elevator, we add another elevator. The eleLoop(e, i) function simply determines the time and average number of passengers carried in a cycle.

Now we will write the function of passing through the floors and creating the floors themselves. Please note: in our case the number of people on the floors is considered the same. If you solve this problem, then it will be quite easy to take into account the different number of people on the floors.

 #  . # Elevator[]    . def elevatorAllocation(building, elevatorCount): elevator = [] for i in range(elevatorCount + 1): elevator.append(0) for i in range(1, floorCount): elevator = addFloor(elevator) printeleLoop(elevator) 

That is quite enough. The decision is relatively straightforward, so much can be improved here.

Python implementation

Now we will assemble the different parts of the algorithm together, add several functions for data output and create a small simulator .

Variables:

• 10 floors.
• 3 elevators.
• 1 rush hour
• 5 seconds to pass the floor.
• 20 seconds standing elevator on the floor.
• 100 people per floor.

 #  ,    def fillBuilding(): building = [] for i in range(floorCount - 1): building.append(peoplePerFloor) return building #    (cirTime), #     ,   . #  e —  ,     #  .  i —   e. def eleLoop(e, i): floorsServiced = e[i] - e[i-1] + 1 cirTime = timePerFloor * e[i] * 2 cirTime += timePerWait * floorsServiced avgCarry = cirTime * peoplePerFloor / rushHour * floorsServiced return cirTime, avgCarry # ( * 5 ) + (20  * ( –  )) #    / ,  # (   * 2) +  ,    #  ,   [2]+=1 # e    ( ) def addFloor(e): best = 9999 for i in range(1, len(e)): cirTime, avgCarry = eleLoop(e, i) if cirTime + ((cirTime / 100) * avgCarry) < best: elevatorNumber = i best = cirTime + ((cirTime / 100) * avgCarry) for i in range(elevatorNumber, len(e)): e[i] += 1 return e #        . def printApprox(building): str = '[ ' for i in range(len(building)): str += '%06.3f ' % building[i] str += ']' print str #  (-)    def printeleLoop(e): print '' print e print '' for i in range(1, len(e)): floorsServiced = e[i] - e[i-1] + 1 curr = timePerFloor * e[i] * 2 curr += timePerWait * floorsServiced avgCarry = curr * peoplePerFloor / rushHour * floorsServiced str = ' #%d,   %d , ' % (i, curr) str += '   ' str += '%3.2f ' % avgCarry print str print '' #  . # Elevator[]    . def elevatorAllocation(building, elevatorCount): elevator = [] for i in range(elevatorCount + 1): elevator.append(0) for i in range(1, floorCount): elevator = addFloor(elevator) printeleLoop(elevator) return elevator #   ,     def simulate(e, building): str = '[ ' for floor in range(len(building)): str += 'floor%2d ' % (floor + 1) str += ']' print str eCircuit = [] for i in range(len(e)): curr, avgCarry = eleLoop(e, i) eCircuit.append(float(curr)) emptyFloors = 0 iteration = 0 finalFloor = 0 while emptyFloors < len(building): emptyFloors = 0 iteration += 1 for i in range(1, len(e)): for j in range(e[i-1], e[i]): if building[j] > 0.0: persons = eCircuit[i] * peoplePerFloor / rushHour building[j] = building[j] - persons if 0 >= building[j]: building[j] = 0.0 emptyFloors += 1 finalFloor = j printApprox(building) print '' #     ,   for i in range(len(e)): if e[i] > finalFloor: iteration = eCircuit[i] * iteration / 60 print ' : %d \n' % () # ___ MAIN ____ building = fillBuilding() elevator = elevatorAllocation(building, elevatorCount) simulate(elevator, building) 

Output:

[0, 4, 7, 9]

Lift number 1, cycle time - 140 seconds, on average 19.44 people are transported
Elevator number 2, the duration of the cycle - 150 seconds, an average of 16.67 people transported
Lift number 3, cycle time - 150 seconds, an average of 12.5 people transported

Total time: 65 minutes

The average number of people per floor as elevators pass:

As you can see, the algorithm works well, but not perfect (for our conditions). You can improve it yourself.

Run time

The running time of the algorithm depends on three factors:

• k: longest cycle, number of people
• n: the initial number of people on the serviced floor of the longest cycle
• m: total number of floors

Run time: O(m * (n/k))

n/k defines the maximum number of iterations performed by elevators within the cycle (s). m used because we need to go through each floor during the iteration. In this case, we neglect the “setting”, which is the filling of the “building array” that describes the number of people on each floor, because this is not the main condition for the run (m * (n / k) + m).

The amount of memory for running the algorithm depends on:

• e: on the number of elevators
• f: on the number of floors

Memory capacity: O(e + f)

Final word

Of course, the algorithm was not perfect, but quite working. Suggest your improvements. The movement of elevators is an interesting application that is similar to the allocation of computer resources.