Список работ

Оптимизация расписания движения трамваев

Ефремова Н. Г., A-13-13

Содержание

Аннотация

Исследуется возможность применения генетического алгоритма для оптимизации расписания движения трамваев. Рассмотрены критерии оптимизации расписания. Предложены операции скрещивания и мутации генетического алгоритма.
Задача решается на упрощенной модели, в которой минимизируется среднее время ожидания пассажиров на остановках маршрута.
Реализовано приложение, генерирующее начальное множество расписаний и находящее затем расписание, существенно превосходящее по принятому критерию оптимизации лучшее расписание исходной популяции.
Ключевые слова: расписание движения, оптимизация, генетический алгоритм.

Цель работы

Исследовать на достаточно простой модели возможность применения генетического алгоритма для решения задачи оптимизации расписания движения трамваев.
Упрощение модели состоит в следующем:

  1. Пассажиров перевозят трамваи одного маршрута, например, маршрута 29.
  2. Многофакторная задача оптимизации расписания редуцируется до однофакторной.
  3. На всех остановках площадки высадки и посадки пассажиров совпадают.

Комментарий упрощений:

  1. В общем случае от остановки А до остановки Б можно добраться на трамваях разных маршрутов, например, в Москве от остановки Техникум до остановки Метрогородок можно добраться на трамваях маршрутов 2, 13, 29 и 36.
  2. Качество расписания можно оценить по нескольким показателям, такими, как время ожидания трамвая, время достижения пункта назначения, число трамваев, осуществляющих перевозки пассажиров, наполняемость салонов трамваев и др. В работе расписание оценивается одним показателем – средним временем ожидания трамвая пассажирами на остановках маршрута.
  3. Имеются остановки с двумя площадками – первая для высадки пассажиров, вторая для посадки.

Решаемые задачи

Формулируется критерий оптимальности расписания и затем средствами генетического алгоритма выполняется поиск расписания, отвечающего наименьшему значению критерия.
Искомое расписание будем называть «хорошим», поскольку в общем случае генетический алгоритм позволяет лишь приблизится к оптимуму целевой функции, не находя последнего.
Поиск «хорошего» расписания выполняется специально разработанным для этой задачи C#-приложением.
Задача поиска «хорошего» расписания решается отдельно для рабочих дней, выходных и праздников.

Задание расписания

Расписание задается в виде следующего массива:

S = {t1, t2, …, tm},

где
ti – время отправления рейса i с начальной (конечной) остановки маршрута;
m – суточное число рейсов на маршруте.
В этом массиве неизменными являются значения t1 и tm – соответственно время первого и последнего рейса. Прочие элементы могут в процессе решения задачи изменяться, но при этом получаемое расписание должно быть допустимым: время между соседними рейсами должно находится в пределах заданного временного интервала.
Значение m определяет размерность решаемой задачи. В случае одного маршрута, если t1 = 5 и tm = 24 и среднее время между рейсами составляет 3 мин, то m = 380.
Увеличение числа маршрутов усложняет вычислительный алгоритм, в том числе и за счет роста размерности задачи.

Критерий оптимизации

Минимизируется среднее время ожидания пассажирами трамвая. Оно рассчитывается по следующей формуле:

T = Σni = 1Ti / Σni = 1Ni

где
n – число остановок на маршруте;
Ti – среднее время ожидания трамвая на остановке i;
Ni – число пассажиров, севших в трамвай на остановке i.
В свою очередь, расчет Ti ведется по следующей формуле:

Ti = Tij – Tij – 1,

где
Tij – время отправления рейса j с остановки i.
Время отправления рейса j с остановки i есть сумма времени прибытия рейса j на остановку i и времени посадки (или высадки) пассажиров, ожидающих на остановке трамвай этого рейса.
Время высадки берется в том случае, если оно превышает время посадки.
Время посадки пассажиров в прибывший трамвай оценивается следующим образом:

TOij = to * Nij

где
to – среднее время посадки одного пассажира;
Nij – число пассажиров, севших в трамвай рейса j на остановке i.
Аналогично рассчитывается и время высадки пассажиров из трамвая.
Посадка заканчивается в одном из двух следующих случаев:

Диаграмма прихода/выхода пассажиров

Число пассажиров, ожидающих трамвай, и число пассажиров, его покидающих, – это случайная величина, для работы с которой используются диаграммы прихода/выхода пассажиров.
Диаграммы формируются для каждой остановки на основе статистических данных отдельно для рабочих дней, выходных и праздников.
Пример диаграммы показан на рис. 1.

Диаграмма прихода/выхода пассажиров

Рис. 1. Диаграмма прихода/выхода пассажиров

Каждый временной интервал диаграммы показывает, сколько пассажиров пришло на остановку в этот интервал. Так, на временном промежутке, который начинается в 1080 мин., вплоть до следующего интервала на остановку пришло 30 человек.
Диаграмма позволяет найти число пассажиров, пришедших на остановку в промежуток между двумя соседними рейсами. Если этот промежуток принадлежит интервалу диаграммы, то это число равно:

NCij = NTij * (Tij– T ij – 1) / ΔT

где
ΔT – длина временного интервала диаграммы;
NTij – показание диаграммы (число пассажиров, приходящих на остановку в рассматриваемый интервал).
Если же промежуток между двумя соседними рейсами принадлежит нескольким интервалам диаграммы, то при вычислении числа пришедших пассажиров учитывается вклад каждого интервала.
Аналогично оценивается и число пассажиров, выходящих из трамвая.
В работе диаграммы прихода/выхода генерируются автоматически. Программа их построения описана в [1].

Генетический алгоритм

Генетический алгоритм состоит в применении операций скрещивания, мутации и селекции, [2]. Применительно к решаемой задаче генетический алгоритм записывается следующим образом:

  1. Задать предельное число итераций.
  2. Сформировать H – начальное множество расписаний. Каждое расписание множества содержит одинаковое число рейсов, и оно должно быть допустимым.
  3. Вычислить для каждого расписания множества H значение критерия оптимальности.
  4. Упорядочить расписания по возрастанию значения этого критерия.
  5. Отобрать в подмножество B k лучших (первых) расписаний.
  6. Выполнить m раз операцию скрещивания, выбирая из отобранного подмножества B каждый раз свежую пару расписаний. Добавить в популяцию потомок (результат) скрещивания, если он лучше своих родителей, и удалить при этом из H худшее расписание. (При скрещивании каждый рейс потомка определяется как среднее арифметическое соответствующих рейсов предков.)
  7. Если же m скрещиваний не дают прогресса, то применить n операций мутации, меняя случайным образом произвольное расписание множества H. Мутация принимается, если новое расписание является допустимым, и оно лучше своего предка.
  8. Завершить вычисления если нет улучшения в результате выполнения скрещиваний и мутаций или если достигнуто предельное число итераций. (Под улучшением понимается получение расписание, превосходящего по качеству лучшее расписание текущей популяции.)

Заметим, что скрещивание и мутация отвергаются, если в результате получается недопустимое расписание.

Результаты

Реализованное C#-приложение содержит базу данных, хранящую сведения о маршрутах, расписаниях и диаграммах прихода/выхода. Расчетный модуль, оперируя этими данными и параметрами модели, формирует исходную популяцию и улучшает ее средствами генетического алгоритма.
Главная форма приложения показана на рис. 2.

Главная форма приложения

Рис. 2. Главная форма приложения

В результате применения генетического алгоритма к популяции из 60 расписаний удалось почти в 3 раза снизить среднее время ожидания (время ожидания лучшего расписания исходной популяции составило 7 мин 10 с, а оптимизированного расписания – 2 мин 43 с).
Это и другие испытания позволяют надеяться, что генетический алгоритма будет эффективен и при решении задачи оптимизации расписания на модели, реально отвечающей практике.

Список литературы

  1. Ефремова Н. Г. Построение диаграммы прихода пассажиров на остановку. 100 байт. 2010. 24 янв. http://100byte.ru/stdntswrks/cshrp/chart.html. (Дата обращения 06.07.2017).
  2. Genetic algorithm. Wikipedia. The free encyclopedia. 2001. 15 янв. https://en.wikipedia.org/wiki/Genetic_algorithm. (Дата обращения 06.07.2017).

Список работ

Рейтинг@Mail.ru