Программирование, 2019, № 1, стр. 22-42

2.1. Анализ моделей мобильности

Анализ мобильности имеет решающее значение для повышения качества обслуживания транспортных систем. Ряд релевантных показателей можно вычислить из статической информации и обследований. Однако эти методы предполагают дорогостоящие процессы (как по времени, так и по необходимым ресурсам), и они предоставляют только частичную информацию о мобильности граждан. Более эффективным вариантом является применение алгоритмов обработки для извлечения соответствующей информации из необработанных данных, как правило, из современных репозиториев ИТС. Учитывая большой объем доступных данных, для ускорения их обработки применяются техники работы с большими данными и технологии распределенных вычислений. Это позволяет вычислять полезные индикаторы и показатели в режиме близком к реальному времени.

Нами применяется методология, объединяющая методы анализа больших данных и распределенные вычисления для сбора и обработки соответствующих данных из STM. Полезная информация включает в себя: профили спроса, ОН-матрицы, профили использования автобусов, модели мобильности, продажи билетов, характеристики системы общественного транспорта и т.д.

Автобусные компании отправляют информацию городским властям, в том числе геолокацию автобусов и данные о продажах билетов. Сеть автобусов сложна: она имеет 144 маршрута (и несколько вариантов для многих маршрутов) и 4835 остановок [9].

Данные геолокации содержат положение каждого автобуса с частотой от 10 до 30 секунд. Каждая запись GPS содержит следующую информацию:

ID маршрута, код, который идентифицирует маршрут; ID поездки, код, который однозначно идентифицирует поездку для маршрута; широта; долгота; скорость автобуса (в км/ч) временная метка; и ID остановки, если GPS находится рядом с остановкой.

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

Существует два разных способа купить билет: одночасовые билеты, которые позволяют переходить на другую линию в течение одного часа с момента покупки билета; и двухчасовые билеты, позволяющие неограниченные переходы в течение двух часов. Не обязательно использовать карту STM для оплаты билета, но пассажиры, платящие наличными, теряют право на переходы.

Каждая запись продажи, сделанная с или без смарт-карты, содержит следующую информацию:

ID поездки, как и в GPS записи; широта; долгота; ID остановки, как и в GPS записи; количество пассажиров, так как карта позволяет покупать билеты для нескольких пассажиров; и временную метку.

Если продажа осуществляется с помощью смарт-карты, также сохраняется идентификатор смарт-карты, количество транзакций выполненных с одной и той же STM-карты, и последняя оплаченная транзакция. Эти данные позволяют идентифицировать поездку с пересадкой: в этом случае количество транзакций увеличивается, но последняя транзакция не оплачивается.

2.2. Проблема перемещения автобусных остановок

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

Несколько факторов ограничивают возможные конфигурации для перемещения автобусной остановки: i) максимальное количество пассажиров, которые могут одновременно находиться в автобусе, ii) расстояние, на которое пассажир допускает перемещение пешком, iii) расходы на зарплату, топливо и др. Улучшение качества обслуживания заключается в минимизации времени в пути, с учетом времени прибытия, времени ожидания на остановке и продолжительности поездки. Стоимость компаний рассчитывается как разница между прибылью за количество проданных билетов и расходами, необходимыми для организации поездок. В рамках этого проекта предполагается, что расходами являются только затраты на заработную плату водителей и топливо для транспортных средств.

На рисунке 1 представлен пример проблемы для двух маршрутов с одним и тем же пунктом назначения и максимальной загрузкой в 10 пассажиров на автобус. Автобусные остановки идентифицируются кодом в цветном прямоугольнике, соответствующем идентификатору маршрута (первый номер, перед тире) и порядковым номером остановки (второе число после тире). Числовые значения, показанные на каждой остановке, соответствуют количеству пассажиров, желающих сесть (S) и сойти (B) с автобуса. Например, на остановке 1–4 (зеленая линия) четыре человека хотят сесть, но свободное пространство в этот момент составляет всего лишь три места. Однако на остановке 2–2 (синяя линия) четыре человека хотят сесть, при том что в автобусе в этот момент девять свободных мест. Поэтому возможным вариантом является устранение обоих остановок и создание новой в середине между ними, так что оба маршрута могут использовать новую остановку, а человек с маршрута 1, который не смог сесть на автобус 1, сможет сесть на атобус 2.

Рис. 1.

Пример проблемы перемещения автобусных остановок.

Все используемые данные параметризуются, тем самым обеспечивая большую гибкость алгоритмов, чтобы их можно было легко применить в разных сценариях и ситуациях.

Математическая постановка. В математической постановке задачи перемещения остановки автобуса учитываются следующие элементы:

• (непересекающееся) множество зон Z = = $\{ {{z}_{1}}, \ldots ,{{z}_{n}}\} $; каждая зона представляет собой географическую зону, например, район в городе;

• набор возможных локаций для автобусных остановок, $S = \{ {{s}_{1}},\; \ldots ,\;{{s}_{p}}\} $. Каждая локация определяется ее географическими координатами в городе, широтой и долготой $(la{{t}_{s}},lon{{g}_{s}})$. Активные локации представляют собой остановки для одного или нескольких маршрутов. Кроме того, в некоторых локациях потенциально могут быть установлены новые автобусные остановки. Например, новая автобусная остановка может быть определена в новой локации после устранения соседних остановок в окрестности;

• набор маршрутов общественного транспорта $R\, = \,\{ {{r}_{1}}, \ldots ,{{r}_{m}}\} $. Каждый маршрут проходит через множество зон, заданных функцией $RZ:R \to Z$. Каждый маршрут имеет фиксированную частоту в минутах, заданную функцией $RF:R \to \mathbb{N}$ (например, автобусы, которые работают на маршруте r_j прибывают на каждую остановку регулярно, каждые $RF({{r}_{j}})$ минут). Каждый маршрут имеет упорядоченный список остановок, заданный функцией $RS:R \to S$ (порядок имеет значение);

• функция спроса пассажиров $D:S \times Z \to N$. $D({{s}_{i}},{{z}_{j}})$, указывающая количество пассажиров, которые осуществляют посадку в автобус на остановке ${{s}_{i}}$ и отправляются в пункт назначения z_j. Функция спроса пассажиров определяется от остановок до зон, потому что пассажиры подтверждают поездку (по смарт-карте или за наличный платеж), когда они садятся на автобус, а не когда они выходят. По этой причине необходимо оценить остановку в пределах зоны назначения z_j, где каждый пассажир выходит из автобуса. Стратегия оценки остановки назначения является частью процесса формирования матрицы OН, описанной в разделе 2.1;

• набор транспортных средств (автобусов) B = = $\{ {{b}_{1}}, \ldots ,{{b}_{q}}\} $. Каждый автобус имеет фиксированную вместительность K, которая определяет максимальное количество пассажиров, которым разрешено перемещаться в автобусе, в соответствии с городскими правилами. Каждое транспортное средство проходит через набор остановок, связанных с маршрутом в определенном порядке, и для завершения каждой поездки требуется определенное время. Время в пути между последовательными остановками связано с географическим расстоянием между ними (в соответствии с маршрутом, определенным для каждого маршрута), дорожными условиями (трафик, максимальная скорость и т.д.) и количеством пассажиров, которые осуществляют посадку и высадку из автобуса на каждой остановке. Время в пути задается функцией $TT:S \times S \to N$, где $TT({{s}_{i}},{{s}_{j}})$ – это время, необходимое для проезда автобуса от остановки ${{s}_{i}}$ до следующей остановки s_j. Каждый раз, когда автобус ${{b}_{h}}$ останавливается на остановке ${{s}_{i}}$, предлагаемая модель различает два случая: i) по меньшей мере один пассажир осуществляет посадку на автобус ${{b}_{h}}$ на остановке ${{s}_{i}}$; тогда время в пути будет увеличено на ${{t}_{s}} + \sum\nolimits_{k = 1}^{k = n} \,D({{s}_{i}},{{z}_{k}} \times {{t}_{b}})$, где t_s – это время, необходимое для остановки автобуса и ${{t}_{b}}$ – время, необходимое одному пассажиру для посадки на автобус; ii) автобус ${{b}_{h}}$ останавливается на остановке ${{s}_{i}}$ только для того, чтобы позволить пассажирам выйти, тогда время в пути будет увеличено на ${{t}_{s}} + {{t}_{a}}$, где ${{t}_{a}}$ – это (постоянное) время необходимое для высадки пассажиров. Модель предполагает, что высадка пассажиров значительно быстрее, чем посадка (т.к. не требуется покупка билетов или проверка карты). Для определения количества пассажиров, которые выходят из автобуса на остановке ${{s}_{i}}$, модель использует оценочную матрицу ОН;

• функция подсчета перемещающихся пассажиров $C:B \times S \to \mathbb{N}$, где $C({{b}_{i}},{{s}_{i}})$ обозначает число пассажиров, которые находятся на борту автобуса ${{b}_{i}}$ на остановке ${{s}_{i}}$. Количество пассажиров на каждом автобусе обновляется каждый раз, когда пассажиры осуществляют посадку или высадку с автобуса на каждой остановке. Число пассажиров не может превышать вместительности $K$;

• функция операционных затрат, связанная с автобусными компаниями, вычисляет стоимость перемещения между автобусными остановками по конкретному маршруту. Она определяется как $BC:S\, \times \,S\, \to \,\mathbb{N}$, где $CC({{s}_{i}},{{s}_{j}})$ = $({{C}_{g}}\, + \,{{C}_{s}})\, \times \,dist({{s}_{i}},{{s}_{j}})$ – это стоимость проезда от ${{s}_{i}}$ до s_j, ${{C}_{g}}$ – это стоимость топлива, а ${{C}_{s}}$ – это зарплата водителя за каждый 1 км.

Также рассматриваются две переменные: ${{x}_{{ij}}}$ – это $i$-я остановка автобуса, определенная на маршруте ${{r}_{j}}$ и $u_{{ij}}^{k}$ (бинарная) обозначает что маршрут k соединяет зоны ${{z}_{i}}$ и z_j.

Когда остановка ${{s}_{i}}$ удаляется из маршрута r_j, пассажиры, перемещающиеся из ${{s}_{i}}$ в зону ${{z}_{k}}$ распределяются между соседними остановками, которые хотят сесть в автобус, который едет до того же пункта назначения. Например, когда остановка автобуса ${{s}_{i}}$ удаляется из маршрута r_l, пассажиры должны пройти к другой остановке автобуса ${{s}_{h}}$, который проверяет ${{s}_{h}} \in RZ({{r}_{l}})$ и ${{s}_{i}} \in RZ({{r}_{l}})$. Когда доступно более одного варианта, количество пассажиров распределяется обратно пропорционально расстоянию, которое пассажиры должны пройти, чтобы перейти к ближайшей новой остановке. В этом случае пассажирам необходимо перейти на новую остановку, а необходимое время ходьбы определяется функцией $WT\,:\,S\, \times \,Z\, \to \,\mathbb{N}$, где WT(s_i, z_k) определяется WT(s_i, z_k) = $\overline {ws} \, \times \,dist({{s}_{i}},{{s}_{h}})$, где $\overline {ws} $ – это средняя скорость ходьбы для пешеходов и ${{s}_{h}}$ – это ближайшая остановка маршрута r_j, такая что ${{z}_{k}} \in RZ({{r}_{j}})$. Аналогичный подход используется, когда новая остановка добавляется между двумя существующими остановками. В этом случае пассажирам необходимо будет перейти на новую локацию.

Это проблема многокритериальной оптимизации, поскольку она включает одновременную оптимизацию двух функций, находящихся в конфликте друг с другом. Основные задачи – это минимизация времени движения автобуса, что напрямую влияет на качество обслуживания, предлагаемого пассажирам, которое определяется функцией QT (Equation 2.1), одновременно максимизируя прибыль компаний за счет уменьшения стоимости, заданной функцией CT (Equation 2.2). Прибыль определяется как разница между количеством проданных билетов и затратами необходимыми для предоставления услуг. Функция QT учитывает точку зрения пассажиров и администрации города, в то время как функция CT отвечает интересам транспортных компаний, эксплуатирующих автобусные линии.

Сложность проблемы. Предполагая, что в каждом квартале может быть только одна автобусная остановка, количество возможных мест для расположения остановок равно количеству кварталов в городе. Кроме того, каждый маршрут имеет свои собственные остановки, которые должны одновременно использоваться и другими маршрутами. Это является причиной сложности проблемы определения мест для автобусных остановок, которые были бы эффективны с точки зрения системы общественного транспорта. Предполагая что мы имеем набор из $K$ маршрутов и $P$ автобусных остановок, количество возможных комбинаций для их расположения равно ${{K}^{P}}$. Таким образом, проблема распределения имеет вычислительную сложность, которая экспоненциальна по числу остановок ($O({{K}^{P}})$).

При решении больших задач на реальных данных, традиционные точные алгоритмы не применимы для решения проблемы перемещения автобусных остановок за приемлемое время. Использование метаэвристик позволяет получать решения приемлемого качества в разумные сроки выполнения [21]. Метаэвристики – это стратегии высокого уровня, которые объединяют наборы более простых методов обработки (обычно эвристических), чтобы получить более мощную процедуру. В этой статье предлагается применить МКЭА для решения проблемы. Этот подход позволяет получать быстрые кандидатные решения благодаря эффективному изучению пространства решений.

3.1. Анализ мобильности и генерация матрицы ОН

В работе Pelletier et al. [23] рассматривается использование смарт-карт для анализа мобильности в системах общественного транспорта. В ходе исследования были проанализированы основные требования к внедрению решений для оплаты посредством смарт-карт, а также вопросы конфиденциальности и юридические вопросы, возникающие при использовании данных из таких систем. Кроме того, авторы определили основные виды использования этих данных, например, долгосрочное планирование, корректировки предоставляемых услуг и показатели эффективности транспортных систем. Наконец, были представлены примеры реального использования таких данных.

В работе Trépanier et al. [26] представлена модель для оценки мест назначения пассажиров общественного транспорта с использованием смарт-карт. Были рассмотрены две гипотезы, которые используются в других связанных работах: i) происхождение новой поездки – это пункт назначения предыдущей поездки, и ii) в конце дня, пассажиры возвращаются к пункту отправления первой поездки дня. Исходя из этих предположений, метод позволяет исследовать последовательность поездок каждого пользователя в системе. Поездки, для которых сборка последовательности невозможна (например, одна поездка за день для данного пользователя), сравниваются со всеми другими поездками месяца для одного и того же пользователя для того, чтобы найти подобные поездки с известным пунктом назначения. Экспериментальная оценка была проведена с реальной информацией от транзитных властей в городе Гатино, Квебек.

Результаты показали, что существует возможность оценить пункт назначения вплоть до 66% поездок. В статье также показано, что большинство поездок, где пункт назначения невозможно установить, совершаются в часы низкого спроса. Рассматривая только часы с высоким спросом, процент поездок, по которым можно оценить их назначения, составляет 80%. Однако точность не была оценена из-за отсутствия второго источника реальных данных для сравнения.

Группа Wang et al. в статье [27] предложила методологию последовательности путешествий для определения пунктов отправления и назначения пассажиров автобусов с использованием смарт-карт и данных автоматизированной системы сбора местоположения транспортных средств (Automatic Vehicle Location – AVL) в Лондоне, Великобритания. Пункты отправления были точно рассчитаны с использованием временных меток, хранившихся в записях смарт-карт AVL, для определения автобусной остановки. Для оценки пунктов назначения, авторы использовали подход, аналогичный тому, который был представлен в [26], следуя, по возможности, последовательностью поездки. Результаты были сопоставлены с данными лондонского пассажирского опроса, проводимого каждые пять-семь лет для каждого автобусного маршрута и включающего информацию от людей, входящих и выходящих на каждой остановке автобуса. Анализ показал, что пункт отправления может быть оценен более чем в 90% от поездок, тогда как пункт отправления и назначения может быть оценен в 57% от поездок. При сравнении с результатами опроса, разница в оценке пунктов назначения составила ниже 4%. Наконец, были представлены два практических приложения: i) исследование суточного изменения потока для определения местоположений вдоль маршрута автобуса, на которые наблюдается высокий спрос среди пассажиров, а также недоиспользуемые местоположения и ii) анализ времени пересадок, оценка времени, которое пассажиры должны потратить на ожидание пересадки, в зависимости от конечной остановки и данных AVL.

В работе [18] представили подход, аналогичный подходу группы [27] для оценки OН-матриц в мультимодальной транспортной системе Сантьяго, Чили. В этом случае пассажиры могли использовать свои смарт-карты для оплаты билетов в метро, автобусах и на автобусных остановках.

В различных исследованиях применялись распределенные вычисления для обработки больших объемов данных трафика, хотя очень немногие работы касались оценки спроса или OН-матриц с использованием распределенных вычислений.

Ранние работы применяли распределенные вычисления для сбора данных о трафике. В работе Sun [24] была предложена клиент-серверная модель, реализованная на основе CORBA, для сбора информации о трафике в реальном времени и использования ее для динамического построения матриц спроса.

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

В статье [25] комбинируются различные источники информации (т.е. записи звонков сотовых телефонов, переписи и опросы) для расчета полезных показателей общественного транспорта и вывода матриц OН. Несколько существующих алгоритмов были объединены для создания OН-матриц, назначения поездок для определенных маршрутов и для расчета показателей качества использования маршрутов. Кроме того, было реализовано веб-приложение, предоставляющее дружественный интерфейс для просмотра данной информации. Это исследование страдает отсутствием информации о применяемых методов параллельных вычислений.

В работе Melleg å rd [17] предложена реализация, использующая Hadoop для создания массивов OН при сохранении конфиденциальности пользователей посредством синтетического мобильного сбора данных (симуляции). Однако показатели производительности не сообщаются, поэтому преимущества применения Hadoop не ясны.

В работе Massobrio et al. [16] представлен анализ использования распределенных вычислительных технологий для анализа данных GPS с автобусов. Представлен подход с использованием MapReduce для обработки исторических данных для изучения показателей для оценки качества обслуживания транспортных систем в Монтевидео, Уругвай. Авторы использовали стратегию расчета средней скорости автобусов и выявления проблемных зон движения в соответствии с задержками и отклонениями при прибытии на каждую остановку. Параллельное развертывание масштабируется должным образом при обработке больших объемов данных.

3.2. Эволюционные подходы к оптимизации общественного транспорта

Командой Johar et al. [13] представлен исчерпывающий обзор, касающийся проектирования и планирования сетей общественного транспорта. Авторы классифицировали проблемы транспортной сети на четыре больших блока: маршрутизация, планирование, комбинированная маршрутизация и планирование, а также интеграция планирования общественного транспорта. Большая часть работ была посвящена оптимизации общей стоимости маршрута с учетом как пользователя, так и поставщика услуг. Авторы предложили использовать эволюционные алгоритмы (ЭА) вместо классических алгоритмов оптимизации для решения таких проблем, из-за сложности и количества переменных, необходимых для принятия решения.

В работе Deb и др. [5] представлен ЭА для оптимального планирования расписаний и маршрутов автобусов или поездов. В работе также представлено его сравнение с классическими подходами (например, с методом ветвей и границ). Методология основана на минимизации общего времени, учитывая как время в пути, так и время, необходимое пассажирам для прибытия в пункт отправления и посадки в транспортное средство. Экспериментальная оценка проводилась на основе модели, основанной на некоторых предположениях. Как и Johar et al. [13], авторы предлагают использовать ЭА для планирования коллективных транспортных систем из-за количества переменных, которые необходимо учитывать при принятии решений и вычислительных ресурсов, необходимых для нахождения оптимального решения.

Król [14] представил ЭА для решения проблемы проектирования транспортной сети и проблемы настройки частоты, используя в качестве информации матрицу OН и информацию о существующих маршрутах. Экспериментальный анализ проводился в сети общественного транспорта Бельско-Бяла в Польше, которая имеет 46 маршрутов, которые обслуживают около 90 тысяч человек в день. Работа не предоставляет подробной информации о том, как была создана матрица OН.

В работе Bielli et al. [1] предложен ЭА для улучшения автобусной сети, путем оптимизации количества транспортных средств. Экспериментальный анализ был проведен в четырех сетях общественного транспорта: реальной сети в Парме (Италия) с 22 маршрутами и 459 остановками и тремя синтетическими сценариями, определенными авторами. Предлагаемый метод позволил достигнуть улучшение 90% показателей относительно исходной сети.

Xiong et al. [28] предложили использование ЭА для обучения нейронной сети для получения решений проблемы проектирования дискретной транспортной сети, что является NP-сложной проблемой. Предлагаемый метод, обозначенный кумулятивным генетическим алгоритмом (cumulative genetic algorithm – CGA), обнаруживает особей с большей пригодностью, которые будут использоваться в сочетании с новым поколением при воспроизведении. Нейронная сеть обучается у CGA. Сеть имеет три уровня, в общей сложности 62 нейронов и 1261 связи. Для обучения сети использовалось 2500 случайно выбранных решений, вычисляющих их затраты с помощью алгоритма Флойда–Варшалла. Экспериментальный анализ проводился по сценариям, определенным авторами, с 20 различными моделями сети общественного транспорта и матрицей фиксированного спроса. Никаких числовых результатов не сообщается.

3.3. Резюме

При обзоре литературы можно выделить большой интерес к изучению различных подходов к анализу сетей общественного транспорта. В некоторых исследованиях были использованы аналогичные предложения, представленные в этой статье для оценки OН-матриц. Однако ни один из них не использовал распределенный подход для генерации их из данных местоположения GPS и проданных билетов. Многие подходы, которые ищут улучшения при проектировании и планировании сетей общественного транспорта, используют ЭА. Тем не менее, не было обнаружено никакой предыдущей работы о многокритериальном перемещении автобусных остановок. В существующих статьях основное внимание уделяется оптимизации общего времени в пути, в основном с помощью однокритериальных методов оптимизации. В отличие от представленных работ, мы предлагаем многокритериальный подход для предоставления набора эффективных решений, которые представляют собой различные компромиссы между общим временем и транспортными расходами.

4.1. Многоцелевые эволюционные алгоритмы

Эволюционные алгоритмы – это недетерминированные методы, которые эмулируют естественную эволюцию для решения задач оптимизации, поиска и смежных проблем [20]. За последние тридцать лет, ЭА были успешно применены для решения задач оптимизации, лежащих в основе многих реальных приложений высокой сложности.

ЭА – итеративный метод (каждая итерация называется поколением), который работает, применяя стохастические операторы на множестве индивидуумов (популяции P), чтобы улучшить их приспособленность, то есть меру, связанную с целевой функцией, которая оценивает, насколько это решение хорошее. Каждый индивидуум в популяции является кодированной версией кандидата решения для проблемы. Первоначальная популяция генерируется случайным методом или с использованием определенной эвристики для проблемы. Функция оценки присваивает значение приспособленности каждому индивидууму, указывая на его пригодность для решения проблемы. Поиск основан на вероятностном выборе наилучшего метода (как для родителей, так и для потомства) для предварительных решений более высокого качества. Итерационно, решения модифицируются вероятностным применением операторов вариации, в том числе рекомбинацией частей из двух особей или случайных изменений (мутаций) в их содержании, которые применяются для создания новых решений во время поиска. Эволюционный алгоритм возвращает лучшее решение, когда-либо найденное в итерационном процессе, с учетом функции приспособленности.

Многокритериальные эволюционные алгоритмы (МКЭА) [2, 4] – это специальные ЭА предназначенные для решения проблем с двумя или более противоречивыми целями. МКЭА оказались эффективными в решении сложных проблем оптимизации в реальном времени во многих областях исследований. МКЭА предназначены для одновременного выполнения двух целей: i) обеспечивают аппроксимации границы Парето, используя эволюционный поиск на основе Парето и ii) поддерживают разнообразие, а не сходятся к определенному участку границы Парето, используя методы, также применяемые при оптимизации мультимодальных функций (например, посредством совместного использования или переполнения).

Нами предлагается использовать Недоминируемый Генетический Алгоритм Сортировки, версии II (Non-dominated Sorting Genetic Algorithm, version II – NSGA-II) [4] для решения проблемы многокритериального перемещения автобусных остановок. NSGA-II – это современный МКЭА, который успешно применяется во многих областях.

Алгоритм 1 представляет псевдокод NSGA-II. Расчет приспособленности основан на доминировании Парето, построении границ не доминирующих решений. Основными особенностями NSGA-II являются: i) не доминирующая элитарная сортировка, которая снижает сложность проверки доминирования; ii) метод переполнения для сохранения разнообразия; и iii) назначение приспособленности, которое учитывает значения расстояния переполнения.

Algorithm 1. Псевдо-код NSGA-II

Require: N, размер популяции

1: t ← 0        $ \triangleright $ счетчик поколения

2: offspring $ \leftarrow $ $\not {0}$

3: initialize($P$(0))  $ \triangleright $ инициализация популяции

4: while not критерий_остановки do

5:  evaluate($P$($t$)) $ \triangleright $ оценка популяции

6:  R $ \leftarrow $ $P$ ($t$) $ \cup $ потомки

7:  границы $ \leftarrow $non-dominated sorting(R))

8:  $P$($t$ +1) $ \leftarrow $ $\not {0}$; $i$ $ \leftarrow $ 1

9:  while $P(t + 1) + $границы(i)$ \leqslant N$ do

10:   расстояние переполнения (границы (i))

11:   P(t + 1) ← P(t + 1) $ \cup $ границы(i)

12:   $i$ $ \leftarrow $ $i$ +1

13:  end while

14:  сортировка по расстоянию (границы(i))

15:  P(t + 1) ← P(t + 1) $ \cup $ границы(i) [1:(N – |P($t$ + 1)|)]

16:  выбранные $ \leftarrow $ выборка ($P$ ($t$ + 1))

17:  потомки $ \leftarrow $ операторы вариации (выбранные)

18:  $t$ $ \leftarrow $ $t$ + 1

19: end while

20: return вычисленная граница Парето

4.2. Кодирование решения

Проблема перемещения автобусных остановок имеет несколько особенностей, которые требуют специальных методов решений. Поскольку определение проблемы основано на наборе маршрутов, предлагаемая кодировка использует список маршрутов. Каждый маршрут имеет список остановок, упорядоченных от пункта отправления до пункта назначения. Пример этой кодировки показан на рисунке 2 для маршрутов 116, 117 и 121. Пример решения показывает соответствие между набором маршрутов и их остановками с их соответствующим представлением. Ограничение проблемы состоит в том, что начальные и конечные остановки каждого маршрута должны оставаться неизменными.

Рис. 2.

Пример кодировки.

4.3. Входные данные

В предлагаемом МКЭА используются данные из реальных сценариев. Эти данные используются в качестве входных данных для алгоритма и предоставляют информацию о расходах и доходах от поездок, требуемом времени, скоростях и других значениях, находящихся в файле параметров. Это позволяет сделать алгоритм более гибким и расширить возможности его применения к другим исходным данным. Соответствующие входные данные описаны в таблице 1.

4.4. Эволюционные операторы

Инициализация популяции. Популяция инициализируется механизмом, который учитывает реальную информацию о системе общественного транспорта в Монтевидео в 2015 году и матрицу OН, рассчитанную на предыдущем этапе.

Чтобы обеспечить разнообразие для первоначальной популяции, выполняются случайные изменения базового решения, например, путем изменения местоположения остановок автобусов и количества пассажиров, осуществляющих высадку и посадку на автобус в случайно выбранных остановках. Пассажиры перераспределяются на остановки непосредственно рядом с изменяемой остановкой. Расположение выбранных остановок также изменяется. Они перемещаются на переменное расстояние (максимум 500 метров) от их первоначального местоположения. Исходные и конечные остановки не перемещаются, поскольку они определяют каждый маршрут и не могут быть изменены.

Отбор. Используется стандартный турнирный отбор, который включен в первоначальное предложение NSGA-II. Результат предварительного анализа, выполненный на небольшом сценарии, показал, что турнирный отбор обеспечивает необходимое давление выбора.

Рекомбинация. Для рекомбинации маршрутов двух решений использовался оператор одноточечного кроссовера (Single point crossover – SPX). Решения, которые нарушают установленные ограничения (например, те, которые превышают вместительность автобуса), просто отбрасываются. Рисунок 3 показывает пример рекомбинации для упрощенного экземпляра проблемы с тремя маршрутами и их соответствующими остановками.

Рис. 3.

Пример оператора рекомбинации.

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

Рисунок 4 показывает пример мутации для экземпляра проблемы с тремя маршрутами и их соответствующими остановками. Для каждого маршрута показано одно из возможных действий: остановка 4042 маршрута 116 остается неизменной, остановка 579 маршрута 117 устраняется, а остановка 576 маршрута 121 перемещается в новое место.

Рис. 4.

Пример предлагаемого оператора мутации.

Корректирующая функция. Во время эволюционного поиска некоторые из решений, возникающих после применения эволюционных операторов, могут включать бесполезную информацию; например, они могут иметь маршруты с остановками, где пассажиры не производят посадку в автобус. Была реализована корректирующая функция: если есть две последовательные остановки, где пассажиры не производят посадки на автобус, то обе остановки объединяются в одну остановку посередине между ними. Исходные и конечные остановки исключаются в этом процессе поиска, потому что они должны оставаться неизменными для всех маршрутов.

5.1. Модели мобильности, тепловые карты и другая полезная информация о системе общественного транспорта

Несколько показателей были рассчитаны при анализе больших данных, выполненном над информацией из системы общественного транспорта в Монтевидео.

Гистограммы на рисунках 5–6 представляют четыре примера соответствующих показателей, рассчитанных для рабочих дней в мае 2015 года.

Рис. 5.

Транзакции по карте, 2015.

Рис. 6.

Ног на поездку, 2015.

Анализ показал, что большинство людей использовали смарт-карту для трансферных поездок. Сегодня ситуация может поменяться, так как в 2017 году власти Монтевидео начали программу поощрения использования смарт-карт, предложив снижение цен. Что касается транзакций по карте (рисунок 5), анализ показал, есть два четких максимума в двух и четырех случаях, что соответствует одной или двум поездкам, которые большинство людей делают в рабочие дни.

Анализ количества перегонов на поездку (Рисунок 6) показал, что почти все пассажиры используют смарт-карту поотдельности, как указано численно в таблице 2. 98.13% всех оплат по картам соответствует только одному пассажиру, тогда как всего 1.76% соответствуют двум или более лицам, путешествующим вместе. Этот результат свидетельствует о том, что граждане не знают о возможностях карты STM оплачивать сразу несколько билетов.

Что касается транзакций на автобус (Рисунок 7), анализ показал, что некоторые автобусы имеют значительно большее количество проверок смарт-карт, что, возможно, указывает на то, что общая длина каждого маршрута довольно велика (ситуация, которая признана аналитиками дорожного движения), а также некоторые линии с небольшими количествами валидаций карт указывают на меньшее количество пассажиров и, возможно, на недоиспользование ресурсов.

Рис. 7.

Транзакции на автобус, 2015.

Наконец, в отношении транзакций в час (рисунок 8) анализ показал, что в рабочие часы спрос несколько меняется и что можно выделить 3 основных пика в часы высокой загрузки транспорта (7:00–8:00, 12:00–13:00 и 17:00–18:00). Анализ также позволил определить часы, в которых выполняется самое низкое количество транзакций (3:00–4:00). Этот час использовался как точка разрезания для метода оценки конечной остановки, применяемого при построении матрицы OН.

Рис. 8.

Транзакций в час, 2015.

Профили загрузки. Профили загрузки полезны для определения областей, которые чрезмерно либо недостаточно используются в рамках определенного маршрута. Например, на Рисунке 9 представлено число людей, путешествующих по маршруту 121 (вариант 2399) с 17:00 до 19:00 часов (час пик) на неделе 16–20 Марта. Максимальная емкость линии представлена оранжевым цветом (32 пассажира сидят и 25 стоят), а количество пассажиров, которые садятся в автобус по маршруту, представлено синим. Средняя частота – один автобус каждые пять минут, согласно администрации города [12].

Рис. 9.

Профиль загрузки для маршрута 121 с 17:00 до 19:00, 16–20 марта 2015 года.

Рисунок 10 показывает профиль загрузки для маршрута 121 между 13:00 и 17:00 часами в ту же неделю марта 2015 года. Результаты показывают, что этот маршрут не используется чрезмерно, потому что, хотя автобус близок к максимальной загрузке в пиковое время, заполнение автобуса не превышает вместительность в каждой из зон. Это может быть связано с тем, что он имеет относительно короткий маршрут, поскольку он использует только 30 остановок через центр города.

Рис. 10.

Профиль загрузки маршрута 121 между 13:00 и 17:00 часами 16–20 марта, 2015.

Рисунок 11 показывает профиль загрузки для маршрута 300 (вариант 2065) с 13:00 до 17:00 и с 17:00 до 19:00, в мае 2015 года. Эта линия имеет более длинный маршрут, чем маршрут 121, с 74 остановками. Средняя частота этой линии составляет один автобус каждые 10 минут.

Рис. 11.

Профиль загрузки маршрута 300 между 13:00 и 17:00 и между 17:00 и 19:00 часами 11 мая.

Результаты показывают, что маршрут 300 используется с 13:00 до 19:00 часов с более высокой потребностью в час пик. Этот паттерн повторяется на протяжении всех недель. В отличие от маршрута 121, маршрут 300 перемещается по более чем в два раза большему количеству районов и имеет частоту, уменьшенную наполовину, что приводит к избытку пассажиров.

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

Тепловые карты. Тепловые карты – это визуальный инструмент, позволяющий анализировать спрос на определенные линии. Рисунки 12 и 13 показывают тепловые карты для районов города и Старого города, с 17:00 до 19:00 в марте 2015 года. Тепловые карты показывают, что наибольшие требования предъявляются в точках, где сосредоточено большое количество офисов или рабочих мест, например, вблизи площади Независимости. Количество пассажиров уменьшается в противоположном направлении. Кроме того, на улицах с большим количеством маршрутов число пассажиров также увеличивается из-за того, что люди возвращаются в свои дома после рабочего дня, например, на автобусных остановках на проспекте 18 июля.

Рис. 12.

Тепловая карта для центра города.

Рис. 13.

Тепловая карта для центра города.

5.2. Матрицы спроса и отправления-назначения

Предлагаемая методология оценки спроса и ОН-матриц с использованием анализа больших данных и распределенных вычислений была применена для системы общественного транспорта Монтевидео.

Время выполнения предлагаемого метода исследовалось при различном количестве вычислительных ресурсов (ядер) и различных рабочих нагрузках, назначенных каждому процессу в процессе выполнения, при реализации модели портфеля задач (Bag-of-Tasks – BoT).

Анализ эффективности представлен в таблицах 3 (матрица спроса) и 4 (матрица отправления-назначения, основанная на основных результатах, опубликованных в наших предыдущих работах [6, 15, 22]). Значения ускорения – это оценка улучшения времени выполнения, полученного распределенным алгоритмом, по сравнению с последовательной реализацией с использованием только одного вычислительного ресурса.

Результаты показывают, что использование распределенного подхода значительно повышает эффективность обработки данных. Было достигнуто значительное улучшение времени выполнения: ускорение до 12.8 для прямых поездок и 16.4 для трансфертных поездок (матрица спроса) и ускорение до 17.1 (матрица OН). Размер портфеля задач также влияет на время выполнения алгоритма. В обоих случаях лучшие результаты эффективности были получены с использованием портфеля задач в 5000 поездок и 24 ядер.

6.1. Методика

Мультиобъективные показатели оптимизации. В существующей литературе предложено несколько показателей для оценки результатов полученных МКЭА [4, 2 ]. В этой статье рассматриваются несколько релевантных показателей для оценки предлагаемого МКЭА для проблемы перемещения автобусных остановок:

• генерационное расстояние (Generational Distance – GD): (нормированная) сумма расстояний между не доминируемыми решениями на границе Парето, найденными алгоритмом (P) и набором равномерно распределенных точек $\text{v}$ на истинной границе Парето (P*) (уравнение 6.1). Меньшие значения GD означают лучшее приближение к границе Парето

• интервал (spacing): метрика, которая оценивает дисперсию неосновных решений в вычисленной границе Парето, определяемых уравнением 6.2;

• Распределение (spread): в отличие от интервала метрика распределения включает в себя информацию о крайних точках истинной границы Парето, чтобы вычислить более точное значение распределения, как показано в уравнении 6.3 [4]. Меньшие значения метрики распределения означают лучшее распределение неориентированных решений в вычисленной границе Парето, а метрика принимает значение нуль для идеального равнораспределенного распределения

В уравнениях 6.2 и 6.3, d_i обозначает расстояние между i-м решением в вычисленной границе Парето и его ближайшем соседе, тогда как $\bar {d}$ – это среднее значение для всех d_i. В уравнении 6.3 $d_{h}^{e}$ – это расстояние между крайним значением $h$-й функции в истинной границе Парето и ближайшей точкой в вычисленной границе Парето;

• относительный гиперобъем (Relative hypervolume – RHV): отношение объема (в пространстве объективных функций), покрытого вычисленной границей Парето, и объемом, покрытым реальной границей Парето.

В экспериментальном анализе истинная граница Парето – которая неизвестна для изученных экземпляров проблемы – была аппроксимирована путем сбора недоминированных решений, найденных в 30 независимых исполнениях, выполненных для каждого экземпляра проблемы.

Экземпляры проблемы. Предложенный МКЭА для перемещения автобусных остановок был оценен на основе реальных случаев указанной проблемы. Информация, полученная из разных источников, использовалась для создания реалистичных сценариев. Статическая информация о точках высадки, маршрутах и автобусных остановках была публично получена с помощью Открытого каталога данных в Intendencia de Montevideo [11]. Матрица ОН была сгенерирована посредством методологии, описанной в разделе 5. Для того, чтобы определить функции времени в пути, были рассмотрены три периода для создания разных случаев: утром (с 07:00 до13:00), днем (с 13:00 до 19:00) и ночью (с 19:00 до 7:00) с учетом различных условий движения в городе.

Всего было создано 30 экземпляров проблемы:

• 11 – малые экземпляры, в том числе 10 строк с указанием точек отправления и конечных станциях в населенных районах Монтевидео и использованием матрицы OН для января 2015 года;

• 9 – средние экземпляры: между 30 и 60 маршрутов с точками отправления в соседних окрестностях Монтевидео и пунктах назначения в каждом другом районе с использованием матрицы OН в период с января по май 2015 года;

• 10 – большие экземпляры: в том числе более 100 маршрутов из разных районов Монтевидео с использованием матрицы OН за весь 2015 год.

Все сведения о экземплярах проблем общедоступны на веб-сайте проекта www.fing.edu.uy/inco/grupos/cecal/hpc/IOTU.

Вычислительная платформа. Экспериментальный анализ был выполнен на сервере HP Proliant DL385 G7 с 2 процессорами AMD Opteron 6172 на частоте 2,66 ГГц, по 12 ядер каждый и на 72 ГБ оперативной памяти от кластера FING, платформы HPC в Universidad de la República, Уругвай [19].

Статистический анализ. Из-за стохастической природы ЭА, разные результаты могут быть получены для разных запусков одного и того же экземпляра проблемы. Для получения значимых результатов, для каждого экземпляра проблемы было произведено 30 независимых запусков.

6.2. Настройка параметров

Был выполнен анализ конфигурации для определения наилучших значений для каждого соответствующего параметра в предлагаемом МКЭА. Анализ параметров был выполнен на трех малых экземплярах проблемы, которые отличались от тех, которые использовались в экспериментальной оценке, чтобы избежать смещения.

В экспериментах изменялся размер популяции ($\# P$, значениями кандидатов 50, 100 и 150), вероятность рекомбинации (${{p}_{R}}$, значения кандидата 0.6, 0.75 и 0,9) и вероятность мутации (${{p}_{M}}$, значения кандидата 0.001, 0.01 и 0.05). Для каждой комбинации параметров выполнялось 30 независимых запусков из 5000 поколений. Чтобы выбрать наилучшую конфигурацию, была исследована метрика относительного гиперобъема, так как она учитывает как дисперсию найденных решений, так и близость к границе Парето.

В таблице 5 представлены полученные результаты, из которых можно сделать вывод, что использование размера популяции 100, вероятности рекомбинации 0.9 и мутации 0.05 позволяет найти наилучшие решения для оцениваемых экземпляров проблемы.

6.3. Численные результаты

В таблицах 6–8 приведены численные результаты для мультиобъективных показателей оптимизации. Среднее, стандартное отклонение и наилучшее значение (в скобках), рассчитанное в 30 независимых исполнениях предлагаемого МКЭА, представлено для каждого экземпляра проблемы.

Таблица 9 суммирует полученные результаты, сгруппированные по размеру экземпляра.

Результаты показывают, что значения расстояний поколений (GD) очень малы, что говорит о хорошей сходимости к реальной границе Парето. Достигнутые значения распространения также малы, что свидетельствует о хорошем распределении не доминирующих решений на границе Парето. Наконец, достигнутые значения RHV подтверждают хорошую конвергенцию и разнообразие найденных решений.

Очень важный результат вытекает из сравнения решений МКЭА с реальной ситуацией. Это сравнение выполняется для каждого экземпляра проблемы с номером 1, который соответствует реальным данным и сценариям в 2015 году.

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

Результаты показывают, что предлагаемый МКЭА способен находить решения, которые улучшают время в пути до 16.70% и прибыль до 33.92% от реальной ситуации.

Для небольших экземпляров, где есть несколько маршрутов для изменения, процент улучшения значительно выше. Эти результаты могут быть объяснены тем, что чем больше количество маршрутов, перемещение одной остановки автобуса, оказывает большее влияние на остальные маршруты. В этом случае МКЭА может сосредоточиться на соответствующих улучшениях для сети общественного транспорта.