Что, если бы в приложении службы такси на вашем мобильном телефоне была кнопка, позволяющая указать, что вы готовы разделить поездку с другим пассажиром? Насколько радикально совместное использование такси могло бы сократить трафик, стоимость проезда и выбросы углекислого газа?
Авторитетный ответ на этот вопрос требует анализа огромных объемов данных, что невозможно с вычислительной точки зрения традиционными методами. Но в сегодняшнем выпуске Proceedings of the National Academies of Sciences исследователи из Массачусетского технологического института, Корнельского университета и Института информатики и телематики Итальянского национального исследовательского совета представляют новую технику, которая позволила им исчерпывающе проанализировать 150 миллионов записей о поездках, собранных из более чем 13 000 такси Нью-Йорка в течение года.
Их выводы: если бы пассажиры были готовы терпеть задержки не более чем на пять минут на поездку, почти 95 процентов поездок можно было бы разделить. Оптимальная комбинация поездок сократила бы общее время в пути на 40 процентов с соответствующим сокращением эксплуатационных расходов и выбросов углекислого газа.«Конечно, никого нельзя заставлять делить автомобиль», — говорит Карло Ратти, профессор практики Департамента городских исследований и планирования Массачусетского технологического института (DUSP) и один из соавторов газеты. «Тем не менее, наше исследование показывает, что произошло бы, если бы люди использовали возможность совместного использования в качестве опции.
Это больше, чем теоретическое упражнение, с такими службами, как Uber Pool, которые воплощают эти идеи в жизнь».Чтобы найти оптимальную комбинацию поездок, необходимо заранее знать время начала поездки: например, 30-минутная поездка протяженностью Манхэттен может быть объединена с 10-минутной поездкой, начинающейся на 15 минут позже.
Но такое заблаговременное планирование маловероятно, если пассажиры используют приложения для мобильных телефонов. Таким образом, исследователи также проанализировали данные, исходя из предположения, что можно объединить только поездки, начинающиеся в пределах одной минуты друг от друга. Даже тогда общее время в пути сократилось на 32%.
«Мы думаем, что с потенциалом 30-процентного снижения эксплуатационных расходов есть много возможностей для перераспределения этих преимуществ среди клиентов, потому что мы должны предлагать им более низкие тарифы; водителям, потому что мы должны стимулировать их к участию в этом системы; компаниям; и, конечно, это приносит пользу сообществу », — говорит Паоло Санти, приглашенный ученый из DUSP и первый автор статьи.На самом деле, говорит Санти, результаты анализа его и его коллег были настолько поразительны, что они попросили корнельского математика Стивена Строгаца пересмотреть их методологию. Строгац является соавтором статьи, так же как и Ратти и постдок Станислав Соболевский, оба из Senseable City Lab Массачусетского технологического института. Завершают список авторов Майкл Сзелл, который был постдоком в лаборатории Senseable City, когда работа была сделана и сейчас находится в Северо-Восточном университете, и Джованни Реста, исследователь в Институте информатики и телематики, где родился Санти.
При анализе данных такси на предмет возможности совместного использования поездок «Обычно применяемый подход представлял собой разновидность так называемой« проблемы коммивояжера », — объясняет Санти. «Это основная алгоритмическая структура, а также есть расширения для совместного использования».Задача коммивояжера спрашивает, существует ли, учитывая набор городов и время в пути между ними, маршрут, который позволил бы коммивояжёру добраться до всех из них в течение некоторого времени. К сожалению, задача коммивояжера также является примером — на самом деле, пожалуй, самым известным примером — NP-полной проблемы, а это означает, что даже для наборов данных среднего размера она не может (насколько известно) быть решенным в разумные сроки.
Поэтому Санти и его коллеги использовали другой подход. Во-первых, они характеризуют каждую поездку на такси по четырем параметрам: время и GPS-координаты места посадки и высадки.
Затем для каждой поездки их алгоритм определяет набор других поездок, которые перекрываются с ней — тех, которые начинаются до ее завершения. Затем он определяет, может ли рассматриваемая поездка быть объединена с любой из этих поездок без превышения порога задержки.
В среднем на любую поездку можно «поделиться» примерно с 100 другими поездками.Затем алгоритм представляет в виде графика возможность совместного использования всех 150 миллионов поездок в базе данных.
Граф — это математическая абстракция, состоящая из узлов, обычно изображаемых как круги, и ребер, обычно изображаемых как линии между узлами. В этом случае узлы представляют поездки, а ребра — их совместное использование.Само графическое представление было ключом к анализу исследователей. Имея это под рукой, известные алгоритмы могут эффективно находить оптимальные соответствия, чтобы либо максимизировать совместное использование, либо минимизировать время в пути.
Исследователи также провели эксперименты, чтобы убедиться, что их алгоритм сопоставления будет работать в реальном времени, если он будет работать на сервере, используемом для координации данных с мобильных телефонов, на которых запущено приложение для совместного использования такси. Они обнаружили, что даже при запуске на одном компьютере с Linux он может находить оптимальные соответствия примерно для 100 000 поездок за десятые доли секунды, тогда как данные GPS показывают, что в среднем каждую минуту в Нью-Йорке совершается около 300 новых поездок на такси.
Наконец, разработанное Szell онлайн-приложение HubCab позволяет людям самостоятельно исследовать данные о такси, используя карту Нью-Йорка в качестве интерфейса.