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

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

Описание проблемы

Набор данных

Данные, с которыми я работал, - это данные учета поездок комиссии такси и лимузинов Нью-Йорка, которые доступны по следующему URL-адресу: «https://www1.nyc.gov/site/tlc/about/tlc-trip-record-data. страница." У меня есть ежемесячные данные за 2016 год для желтого такси, зеленого такси и автомобиля для аренды. Набор данных содержит около 1,5 миллиона записей о поездках со следующими 11 атрибутами:

  • id - уникальный идентификатор для каждой поездки
  • vendor_id - код, указывающий на поставщика, связанного с записью поездки.
  • pickup_datetime - дата и время включения счетчика.
  • dropoff_datetime - дата и время отключения счетчика
  • Passenger_count - количество пассажиров в транспортном средстве (введенное водителем значение)
  • pickup_longitude - долгота, на которой был включен счетчик
  • pickup_latitude - широта, на которой был включен счетчик.
  • dropoff_longitude - долгота, на которой счетчик был отключен
  • dropoff_latitude - широта, на которой счетчик был отключен
  • store_and_fwd_flag - этот флаг указывает, хранилась ли запись поездки в памяти транспортного средства перед отправкой поставщику, потому что транспортное средство не было подключено к серверу: Y = сохранить и пересылать и N = не хранить и поездка вперед
  • trip_duration - продолжительность поездки в секундах (также целевая переменная)

Я применил простые методы предварительной обработки данных, такие как удаление дубликатов, проверка границ широты и долготы, удаление очевидных выбросов, преобразование полей данных в разумные единицы и т. Д., Чтобы получить чистый набор данных для моих экспериментов.

Визуализация данных

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

На рисунке 1 показано распределение времени посадки по часам дня. Как видно, самые популярные часы приема - с 18 до 22 часов, при этом совершено более 70 000 поездок. С другой стороны, наименее активные часы посадки - с 2 до 6 утра с менее чем 35 000 рейсов.

На рисунке 2 показано распределение времени посадки по будним дням недели. Кажется, что пятница - самый популярный день для вызова такси, когда совершено около 220 000 поездок, в то время как воскресенье находится на другом конце спектра с приблизительно 165 000 поездками.

Рисунок 3 представляет собой тепловую карту времени приема для результатов, показанных на рисунках 1 и 2. Наиболее активное время приема - с 18:00 до 21:00 с четверга по воскресенье. Наименее активное время посадки - с 14 до 17 часов со среды по воскресенье.

Следующая функция, которую я изучил, - это Продолжительность поездки.

На рисунке 4 показано распределение продолжительности поездки по минутам. Я заметил, что распределение сильно смещено влево: более 75% поездок составляют от 3 до 12 минут. Более 10 000 поездок длятся от 5 до 7 минут.

На рисунке 5 показано сравнение распределения продолжительности поездки по минутам и по широте и долготе. Распределение по долготе также сильно смещено влево с пиком примерно на 1 километре. Распределение по широте более нормальное, с максимумом в 0 километров.

На рисунке 6 показана тепловая карта продолжительности поездки с разбивкой по минутам и часам в день по сравнению с будними днями недели. Самые продолжительные поездки происходят часто с 14 до 16 часов со среды по пятницу. Самые короткие поездки происходят с 8 до 9 утра с понедельника по вторник.

Меня также интересуют Пункты получения и Пункты выдачи.

Я нанес на график пространственную плотность мест посадки и высадки, как показано на рисунке 7. Это немного похоже на изображение, которое вы можете видеть из космоса, где Манхэттен и два аэропорта (LGA и JFK) четко «светятся».

Я пошел еще дальше, чтобы показать типичные поездки на карте на рис. 8. Пурпурные круги - это места посадки, зеленые круги - места высадки, а голубые стрелки - длина поездки. Я вижу неравномерное распределение мест посадки и высадки, так как за пределами Манхэттена гораздо больше мест высадки (Квинс и Бруклин).

Машинное обучение

Следующим этапом моей работы является создание модели машинного обучения для прогнозирования времени в пути между пунктами посадки и высадки. С данными и целью простой линейной регрессии будет недостаточно. Имея несколько случайных выбросов в огромном наборе данных и, возможно, ряд категориальных функций, я решил использовать деревья с градиентным усилением, которые могут легко фиксировать нелинейные отношения, учитывать сложность и обрабатывать категориальные особенности. Были использованы следующие входные функции: пассажира_count, pickup_longitude, pickup_latitude, dropoff_longitude, dropoff_latitude и store_and_fwd_flag. Выходная цель - trip_duration.

Я реализовал эту модель с помощью XGBoost - оптимизированной распределенной библиотеки повышения градиента, разработанной для обеспечения высокой эффективности, гибкости и портативности. Эту модель легко настроить, но ее сложно настроить и интерпретировать. Я использовал среднеквадратичную логарифмическую ошибку в качестве метрики оценки, поскольку она снижает величину ошибки. С помощью этой метрики я произвел выбор различных гиперпараметров и сравнил результаты. Последние параметры, которые я использовал для своей модели XGBoost, следующие: {fbooster = gbtree; цель = линейная; обучение _rate = 0,05; max _depth = 14; подвыборка = 0,9; colsample _bytree = 0,7; colsample _bylevel = 0,7; тихий = 1; feval = rmsleg}.

Полученная нами средняя абсолютная ошибка составила 4,83. Модель XGBoost сохраняется как файл pickle и затем будет использоваться в качестве входных данных для следующего шага: оптимизация.

Предлагаемые решения

Поскольку эта проблема включает в себя минимизацию времени в пути при одновременном посещении каждого места, она аналогична задаче коммивояжера (TSP). Задача коммивояжера - это комбинаторная задача NP-трудной оптимизации. Это означает, что у проблемы нет решения за полиномиальное время. Возможные решения растут с факториальной скоростью по мере добавления новых местоположений. Подход грубой силы к решению этой проблемы включает проверку всех возможных комбинаций местоположений. Если бы я оценил все возможные пути, где n представляет количество местоположений, у него было бы следующее время выполнения: O (n) = [(1/2) (n - 1)!]

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

Оптимизация колонии муравьев

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

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

Где tau представляет собой матрицу феромонов размером n на n, а eta представляет собой матрицу обратных затрат времени в пути размером n на n. Все значения в матрице феромонов сначала инициализируются как 1 / n². Я обнаружил, что инициализация феромонной матрицы с помощью единиц практически не повлияла на мои результаты. Соответствующие показатели alph a и beta используются для контроля влияния феромонов и стоимости времени в пути при вычислении вероятности между двумя узлами. В знаменателе у меня есть сумма этих значений, где h представляет все возможные местоположения, доступные муравью для посещения. Это узлы, которые конкретный муравей еще не посещал. Все эти члены складываются, чтобы вычислить взвешенную вероятность путешествия от узла i к узлу j.

После того, как каждый муравей генерирует соответствующее решение, матрица феромонов обновляется. Как это делается, зависит от используемой стратегии. В этом решении я обновляю каждый край феромона, сначала умножая его на p (остаточный коэффициент). Это скорость, с которой феромоны «испаряются» или уменьшают свое влияние. Затем мы добавляем к краю феромона q / c, где q представляет интенсивность феромона, а C представляет общую стоимость сгенерированного пути. Поскольку в знаменателе указана стоимость времени в пути, вероятность выбора путей с большим временем прохождения будет ниже. Этот процесс повторяется g количество раз, где g представляет количество поколений.

Генетическая эволюция

Генетическая эволюция (ГЭ) - еще одна биологически вдохновленная метаэвристика, которая берет свое начало от процесса эволюции. Он использует функции мутации, кроссовера и отбора в последующих поколениях. Эти поколения составляют совокупность решений. Этот алгоритм оптимизации включает следующие шаги:

  1. Создайте совокупность маршрутов.
  2. Мутировать
  3. Кроссовер
  4. Определите фитнес (время в пути)
  5. Выберите родителя для следующего поколения
  6. Повторите шаг 2

Начальная популяция создается путем случайного создания n путей. Операции мутации и кроссовера основаны на скорости мутации m и скорости кроссовера c. Оба эти значения находятся в диапазоне от 0 до 1 включительно. При итерации по каждому пути в текущей популяции я случайным образом выбираю другой путь и видоизменяю его. Мутация выполняется путем перебора каждого места в пути и случайной замены его местами предыдущего индекса. Этот случайный обмен взвешивается коэффициентом мутации m.

После того, как я создал мутанта, я начинаю кроссовер. Я перебираю каждый индекс как в моем текущем, так и в мутантном пути и выбираю местоположение на основе скорости кроссовера c:

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

Когда у меня есть последний путь потомка, я могу оценить его пригодность по сравнению с текущим путем. Если у него меньшее время в пути, он выбирается в качестве родительского для следующего поколения, заменяя текущий маршрут. Этот процесс повторяется g количество раз, где g представляет количество поколений.

Результаты экспериментов

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

Результаты ACO

Для испытаний оптимизации колонии муравьев я использовал следующие значения: альфа = 1,0, бета = 10,0, p = 0,5 и q = 10,0, в то время как я варьировал количество муравьев и поколений g.

Графики ниже были получены с 10 муравьями и g = 100. Как видно из графика средней стоимости одного поколения, ACO не застрял на локальном минимуме. Он продолжал изучать другие возможные решения. Об этом свидетельствует большой разброс средней стоимости.

Результаты GE

Для испытаний оптимизации генетической эволюции я использовал следующие значения: скорость мутаций m = 0,5, скорость кроссовера c = 0,7, при этом я варьировал размер популяции p и количество поколений g. По результатам я вижу, что чем больше поколений и чем больше население, тем лучшее решение найдет алгоритм. Однако по сравнению с оптимизацией колоний муравьев это решение все еще хуже.

Обсуждение

Из результатов экспериментов ясно, что оптимизация муравьиной колонии - лучший алгоритм для оптимизации нашей задачи, которая аналогична задаче коммивояжера. Независимо от того, какие параметры я использовал для популяции p, скорости мутации m или скорости кроссовера s в моей программе генетической эволюции, он не смог найти пути с затратами не ниже ACO. Я считаю, что это вызвано множеством факторов.

Во-первых, рассмотрим, как генерируются пути решения в обоих алгоритмах. В колонии муравьев затраты времени в пути n_ij учитываются при каждом решении, которое принимает муравей. Это связано с тем, что обратная матрица времени прохождения используется при вычислении вероятности для определения того, какое место муравей должен посетить следующим. Генетическая эволюция оценивает затраты только после того, как применила операцию мутации и скрещивания. Стоимость проезда не влияет на этот стохастический компонент генетической эволюции. Мутации и кроссоверы выполняются случайным образом и, несмотря на влияние кроссовера и скорости мутаций, не учитывает, дают ли эти изменения нам более низкое значение. Только на этапе отбора я проверяю, имеет ли потомство лучшую ценность.

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

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

Заключение

Хотя проблема коммивояжера сама по себе может быть давней, ее применение в современных сервисах, таких как Uber и Lyft, напоминает мне о ее актуальности и уродливом факториальном времени работы. Благодаря недавним достижениям в области алгоритмов оптимизации, основанных на биологии, я все еще могу находить возможные решения, не имея решения за полиномиальное время.

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

Примечание. Вы можете просмотреть полный код этого проекта в репозитории GitHub: https://github.com/khanhnamle1994/trip-optimizer

— —

Если вам понравилась эта статья, вы можете найти мой собственный код на GitHub, а другие мои работы и проекты на https://jameskle.com / . Вы также можете подписаться на меня в Twitter, написать мне напрямую или найти меня в LinkedIn.