Разработка алгоритма движения лифтов

© Клип "Gangnam Style"

С ростом этажности наших городов всё больше людей ежедневно пользуется лифтами. Но мало кто из нас задумывается о том, как всё это лифтовое поголовье умудряется более-менее эффективно развозить в течение дня уйму людей, особенно в часы пик. Существует ряд алгоритмов движения лифтов, которые исходят из разных условий — например минимизации времени ожидания лифта. Но давайте подумаем, как можно разработать лифтовый алгоритм.

При всей кажущейся простоте задачи довольно сложно создать лифтовый алгоритм для реального применения в зданиях. К тому же такие вещи считаются коммерческими тайнами и патентуются. Поэтому попробуем сделать упрощённую модель:

В здании на каждом этаже живёт одинаковое количество людей. Есть несколько лифтов, лестниц нет. Для простоты будем считать, что на каждом этаже одинаковое количество пассажиров ждёт лифт. Также мы знаем, что в течение дня есть несколько часов пик. Нужно придумать такой алгоритм, чтобы минимизировать время ожидания всех людей в здании.

Здесь можно выделить несколько затрудняющих решение задачи условий:

• Произвольное количество этажей.
• Произвольное количество лифтов.
• Есть периоды часов пик.
• Распределение лифтов должно описываться на основе функции от нагрузки и времени ожидания.

Также будем учитывать ещё несколько переменных и констант:

• Количество людей на каждом этаже — 100 человек.
• Время, за которое лифт проходит один этаж без остановки, — 5 секунд.
• Время стояния лифта на этаже — 20 секунд.

Конечно, в реальной жизни скорость прохождения этажа лифтом может быть нелинейной, ведь он разгоняется и тормозит. Но для упрощения расчётов мы это отбросим. Если вам это покажется излишним упрощением задачи, то можете потом самостоятельно ввести эти условия в алгоритм.

Заметим, что пока ничего не сказано о грузоподъёмности лифтов. Здесь мы тоже радикально упростим себе жизнь — будем считать, что лифт вмещает сколько угодно людей. Нереалистично, согласен. Но зато, когда у нас появится первая версия алгоритма, будет проще ввести такие условия:

• Если лифт полон, то он опускается на этаж ниже.
• После высадки всех пассажиров лифт возвращается на предыдущий этаж.

Алгоритм распределения лифтов

Как понятно из рисунка, каждому лифту присваивается определённая зона ответственности. Это сделано для того, чтобы усреднить время ожидания на каждом этаже, а также нагрузку на каждый из лифтов. Каждый лифт может проходить цикл «этаж 1 -> 2 -> 3 -> 0». Давайте посчитаем, сколько времени занимает полное прохождение цикла:

1. Время прохождения одного этажа умножаем на количество этажей в цикле и умножаем на два (потому что лифт идёт вверх, а потом вниз). В нашей модели получается:
   5 секунд * <максимальное количество этажей> * 2.
2. Количество остановок c первого по последний этажи умножаем на продолжительность остановки. В нашей модели:
   20 секунд * <количество обслуженных этажей>.

Объединим:
время прохождения цикла = (5 * <максимальное количество этажей> * 2) + (20 * <количество обслуженных этажей>)

Теперь посчитаем усреднённое количество людей, которых мы перевезём в течение одного цикла:

усреднённая загрузка лифта = <Время прохождения цикла> * <количество обслуженных этажей> * <количество людей на этаже> / <час пик>

Здесь:

• <час пик> — это время завершения одного часа пик.
• <количество обслуженных этажей> — количество этажей, на которых останавливается лифт.

Теперь создадим два массива:

1. Массив здания. Количество ячеек равно количеству этажей. Содержимое ячейки обозначает количество ожидающих на этаже людей.
2. Массив лифтов. Количество ячеек равно количеству лифтов. Содержимое ячейки обозначает «верхний» этаж, до которого ездит данный лифт. Например, в массиве [2, 3, 4] описаны три лифта: первый ездит не выше второго этажа, второй — не выше третьего, третий — не выше четвёртого.

Начнём с того, что первый массив пуст, а затем при каждом добавлении этажа в массив мы станем приписывать к нему лифт. Характер добавления будет меняться, как мы увидим ниже, но в целом он описывается довольно просто. Этажи добавляются в циклы до тех пор, пока грузоподъёмность не станет ограничением. Введём маленькую функцию:

время прохождения цикла + ((время прохождения цикла / 100) * усреднённая загрузка лифта)

<время прохождения цикла> — это целое число, пока оно не достигнет 100 секунд (достаточно долго для пребывания в лифте), а затем в уравнении начинают учитываться <усреднённые загрузки лифтов>. Поскольку наша задача была описана довольно расплывчато, то и в решении есть некоторая неясность. Таким образом, функция добавления этажа в зону ответственности лифта довольно условна, хотя и эффективна при управлении нагрузкой. Вероятно, есть и более хорошее решение.

Реализация функции добавления этажа (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

Обратите внимание: каждый раз, когда elevatorNumber выбирает лифт выше текущего значения elevatorNumber, увеличивается размер массива лифтов:

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

В каждом цикле мы на единицу увеличиваем максимальный этаж после выбранного лифта. Поэтому в цикл выбранного лифта мы добавляем ещё один лифт. Функция eleLoop(e, i) просто определяет время и среднее количество перевозимых в цикле пассажиров.

Теперь напишем функцию прохождения по этажам и создания самих этажей. Обратите внимание: в нашем случае количество людей на этажах считается одинаковым. Если решить эту задачу, то потом будет достаточно легко учитывать и разное количество людей на этажах.

# Распределение лифтов.
# 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)

Этого вполне достаточно. Решение относительно прямолинейное, так что здесь многое можно улучшить.

Реализация на Python

Теперь соберём разные части алгоритма вместе, добавим несколько функций для вывода данных и создадим маленький симулятор.

Переменные:

• 10 этажей.
• 3 лифта.
• 1 час пик.
• 5 секунд на прохождение этажа.
• 20 секунд стояния лифта на этаже.
• 100 человек на этаж.

# Настраиваем здание, заполняем этажи людьми
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)

Выходные данные:

[0, 4, 7, 9]

Лифт № 1, продолжительность цикла — 140 секунд, в среднем перевозится 19,44 человека
Лифт № 2, продолжительность цикла — 150 секунд, в среднем перевозится 16,67 человека
Лифт № 3, продолжительность цикла — 150 секунд, в среднем перевозится 12,5 человека

Общее время: 65 минут

Среднее количество людей на этаже по мере прохода лифтов:

Как видите, алгоритм работает неплохо, но не идеально (для наших условий). Вы можете улучшить его самостоятельно.

Время прогона

Время прогона алгоритма зависит от трёх факторов:

• k: самый длинный цикл, количество людей
• n: начальное количество людей на обслуживаемом этаже самого длинного цикла
• m: общее количество этажей

Время прогона: O(m * (n/k))

n/k определяет максимальное количество итераций, совершаемых лифтам в пределах цикла(-ов). m используется потому, что нам нужно пройти по каждому этажу в ходе итерации. В этом случае мы пренебрегаем «настройкой», представляющей собой заполнение «массива здания», описывающего количество людей на каждом этаже, потому что это не является основным условием для прогона (m*(n/k) + m).

Объём памяти для прогона алгоритма зависит:

• e: от количества лифтов
• f: от количества этажей

Объём памяти: O(e + f)

Заключительное слово

Конечно, алгоритм получился не идеальный, но вполне рабочий. Предложите свои улучшения. Движение лифтов — это интересная прикладная задача, которая аналогична распределению ресурсов компьютера.

Автор: pushtaev

Источник