Наверное, сейчас очень мало людей, которым ни разу не приходилось пользоваться услугами такси, тем более, что последнее время популярность этого вида транспорта растет, а цена неуклонно падает. На личном опыте могу сказать, что это удобный способ, например, съездить с маленьким ребенком в поликлинику.
А Вы когда-нибудь задумывались, за что мы в таких случаях платим?
Без сомнения, основную часть составляет плата за время водителя и издержки на автомобиль, однако было бы довольно опрометчиво считать, что эта плата распространяется только на то время, пока Вы в пути. Кода таксисту приходится долго ждать очередного заказа, кто заплатит за его время и простой машины? — в конечном итоге мы с вами. Таксист по праву не согласится на вознаграждение за день ниже его стоимости на трудовом рынке, выполняй он при этом в среднем пять заказов или двадцать пять. Мне стало интересно, каково время не выгодного никому простоя и как его можно уменьшить. Ниже я хотел бы поделиться с вами результатами собственного исследования этого вопроса.
Как работает современный таксист?
Получает заказ от диспетчера или через приложение для таксистов, отвозит пассажира до нужного ему места, и чаще всего дожидается очередного заказа неподалеку от места высадки.
Чем плоха такая политика?
Может приводить к ситуации, когда в некоторых районах города скапливается слишком много таксистов, которым приходится подолгу стоять в очереди на следующий заказ, в то время как
в других районах возникает дефицит свободных машин и часть заказов поэтому оказываются потерянными. В наиболее острой форме описанная проблема возникает в результате суточных миграций: утром таксисты вместе с потоком работающего населения "утекают" из жилых районов, где в это время к тому же повышенный спрос на их услуги, и скапливаются в центре, где плотность заказов наоборот понижена, и особенно мало желающих вернуться домой.
Являются ли предыдущие выводы правдоподобными рассуждениями или они как-то проверены на практике?
Когда я об этом подумал впервые, я опирался исключительно на здравый смысл и небольшой опыт общения с подвозившими меня таксистами. Однако, в тот момент, когда у меня появился первый эскиз оптимизирующего работу службы такси алгоритма, мне конечно же захотелось проверить свои гипотезы и оценить эффективность полученного решения. По понятным причинам ни один из крупных игроков рынка, вроде Uber, Gett, или "отечественного" Яндекс.Такси не пожелал бы открыть нужную мне информацию. К счастью, администрация далекого Чикаго уже давно собирает и выкладывает в открытый доступ данные обо всех поездках значительной части служб городского такси.(подробнее смотрите "Примечания о данных")
Какого же положение дел было в Чикаго за 2016 год?
Согласно моим оценкам (об их методике подробнее в "Примечаниях об оценках времени обслуживания"), из проведенного всеми таксистами на рабочем месте времени в лучшем случае только 46% от него занимало выполнение заказов. Что касается негативного проявления эффекта суточной миграции, то в среднем число доступных машин внутри административных районов на 30% больше либо меньше числа поступающих заказов в это время.
Что и как можно улучшить?
Само собой напрашивается два очевидных направления действий:
1) Организовать переброску машин из районов, где их слишком много, в районы, где в них наблюдается или ожидается дефицит.
2) Поддерживать в каждом районе оптимальным число ожидающих заказа машин.
Конечно, можно поставить более общую задачу максимизации прибыли, и в ходе ее решения даже отказаться от обслуживания части "невыгодных" маршрутов, однако такая стратегия чревата для компании потерей приверженности в целом выгодных ей пользователей, если по "невыгодным" маршрутам их будет обслуживать конкурирующий игрок. Учитывая такую возможность, достаточно разумной выглядит попытка обслужить все доступные заказы, но с наименьшими издержками.
Какие требования стоит предъявить к хорошему алгоритму перераспределения трафика?
Здесь, по моему мнению, желательно выполнение следующих условий:
а) Общее время, затраченное на переброску, поскольку оно не оплачивается пассажирами, желательно сделать как можно меньшим( В написанной мною программе, например, для этого используется специальные минимизирующие алгоритмы на графах, но о них позже);
b) Так как достаток водителей чаще всего напрямую зависит от объема выполненных ими заказов, то желательно, чтобы накладные издержки времени на реализацию алгоритма ложились на каждого из них в равной мере. Следует также учесть, что водитель, получивший предписание перемещаться в другой район, скорее выполнит его, если на это уйдет 15 минут, и скорее проигнорирует, если — 50.
с) Степень дефицита числа свободных машин в каждом районе меняется в течении суток, поэтому алгоритм должен устранять дисбаланс с достаточной оперативностью и при планировании потоков переброски рассчитывать их с учетом ситуации в будущем.
d) Вычислительная сложность алгоритма должна давать возможность реализовать его на практике.
Маленькая хитрость, сильно упрощающая дело.
Представьте себе двадцать солдат, стоящих перед вами в шеренгу. Как добиться, чтобы место перед первым стало занятым, а место последнего освободилось? Один из способов — попросить стоящего последним перейти вперед. Другой способ сделать то же самое, но в двадцать раз быстрее — попросить всех солдат сдвинуться всего на одну позицию. Эта идея, примененная к машинам такси, означает следующее: вместо их переброски из профицитного района А непосредственно в удаленный от него дефицитный район В можно "сдвинуть" автомобили всего на одну позицию вдоль цепочки районов, ведущей из А в В. Такое решение, с одной стороны, позволяет практически мгновенно, по сравнению со скоростью изменения дефицита на карте, устранить дисбаланс, с другой, требует от водителей тратить на "сдвиги" каждый раз не более 15-ти минут.
Каков математический метод реализации алгоритма перераспределения трафика?
(Здесь я подробно опишу технические подробности разработанного мною алгоритма, читатель, интересующийся только результатами может пропустить эту часть статьи.)
Давайте попытаемся свести проблему к хорошо известной задаче на графах отыскания в сети производства-потребления потока снабжения минимальной стоимости. Поскольку спрос на машины такси и их распределение по городу зависят от времени суток и дня недели, построим отдельный граф описанным ниже способом для каждого дня недели и интервала времени длинною в час. Вершинами графа будут выступать административные районы. Те из них, в которых ожидаемое число I освободившихся после выполнения заказа машин превышает предполагаемое число заказов U, займут роль центров производства с мощностью S = I — U, остальные — роль центров потребления с мощностью — S = U — I. Величину S назовем дисбалансом вершины (района). Будем считать, что из района А в район В есть ребро, если (и только если) из А в В можно добраться в среднем за время t, не превышающее 15-ти минут, при этом t есть стоимость этого ребра (подробнее смотрите "Примечания об оценке времени пути между районами"). В классической задаче о сети производства-потребления ограничения на пропускаемую величину потока имеют ребра графа, однако в рассматриваемом случае трудно предположить, что одни только таксисты могут вызвать затор на шоссе, а вот дважды в одном промежутке между заказами "сдвигать" водителя было бы дурным тоном с нашей стороны. В силу последнего замечания "сдвиговый" поток из вершины не должен превышать I.
Есть ли способ так трансформировать граф, чтобы можно было применить алгоритмы для стандартной задачи поиска потока минимальной стоимости?
Давайте выберем любую вершину и заменим ее двумя новыми так, чтобы при этом в первую входили все ребра, входившие в исходную, а из второй — выходили все, из исходной выходившие.Осталось соединить эти две новые вершины единственным ребром с нулевой стоимостью и пропускной способностью I и приписать первой дисбаланс S, а второй — ноль. Проделав такое преобразование с каждой вершиной исходного графа, вы переведете его к виду, стандартному для задачи о потоке минимальной стоимости, но это еще не все.
Чтобы задача поиска потока, удовлетворяющего потребности всех "центров потребления" и реализующего мощности всех "центров производства" вообще была разрешима, суммарный дисбаланс всех вершин, очевидно, должен быть равен нулю. Можно ли выполнения последнего свойства ожидать для графов обслуживания такси? Выглядит весьма правдоподобным, что в графах построенных для утренних часов, когда потребность в машинах такси растет, суммарный дисбаланс будет отрицательным, а для вечерних — наоборот. Давайте представим, как с этой проблемой может справляться служба такси: разумным было бы введение такого графика работы для таксистов, при котором число задействованных машин всегда адекватно соответствовало бы спросу. Чтобы учесть это, в своем алгоритме я добавил к графу дополнительную вершину "дом" с ребрами большой стоимости (40 минут), идущими в каждый район, и незначительной, идущими обратно.
Кстати, если Вам понадобится когда-нибудь численно решать задачу поиска потока минимальной стоимости, крайне не советую прибегать к сомнительным источникам вроде Википедии или различных форумов, советующих устаревшие для этого алгоритмы Форда-Беллмана или потенциально зацикливающийся сетевой симплекс-метод. Хорошие с точке зрения времени работы алгоритмы можно найти в этой статье.
"Под капотом" прилагаемых к статье программ работает мой вариант алгоритма Эдмондса — Карпа.
Каковы сравнительные издержки времени реализации алгоритма перераспределения в городе Чикаго?
В среднем за неделю на выполнение заказов в Чикаго таксисты вместе тратят 275 млн. секунд, простаивают в ожидании 315 млн. секунд, в то время как алгоритм перераспределения отнимал бы у них всего 30 млн секунд.
Можно ли считать, что все издержки времени при идеальной организации перевозок это время выполнения либо заказов, либо предписаний алгоритма перераспределения трафика?
К сожалению, нет! Пусть, к примеру, в некотором районе в понедельник между 9-ю и 10-ю утра ожидается 25 заказов, 15 освободившихся после высадки пассажиров машин и еще 10, дополнительно переброшенных из профицитных районов. Казалось бы, число свободных и требующихся машин находится за этот период находится в балансе, стоит ли тогда рассчитывать суметь выполнить все заказы? Даже если ожидаемые числа совпадут с реальными, порядок, в котором будут поступать свободные машины и заявки на них, вообще говоря, произвольный. Чтобы гарантировать на момент поступления заказа наличие свободной машины, последних придется всегда держать небольшой запас. Запас машин, который с большой вероятностью не истощится за время задержки в их перераспределении (порядка 15-ти минут), есть (пуассоновский характер распределений) приблизительно два квадратных корня из ожидаемого числа заказов за этот период.
Довольно неожиданно, что время, теряющееся в таких очередях, куда больше времени затраченного на выполнение алгоритма перераспределения и составляет примерно 114 млн секунд в неделю. Можно ли его как-то сократить?
Кое-что придумать можно. Одна из идей заключается в следующем: если машины такси, доставляющие пассажиров в некоторый район, прибывают со средним интервалом в минуту, то от очередного заказа не стоит отказываться, даже когда свободных машин на момент его поступления и вовсе нет: самое большее через три минуты хотя бы одна такая наверняка появится. Правда, у этой выжидательной стратегии есть один минус — увеличивается "время подачи" автомобиля. В моем алгоритме я уменьшил размер очереди в каждом районе на среднее количество прибывающих туда за 5 минут автомобилей. Такая мера должна лишь в редких случаях увеличить "время подачи" на пять минут, а вот суммарные потери на простое в очередях по расчетам должны сократиться более чем в двое, сведя их до 50 млн секунд в неделю.
Каков итоговый результат?
**Для Чикаго в соответствии с расчетами (их программы вы найдете но ссылкам ниже) использование алгоритма перераспределения свободных машин в комбинации с управлением размера их очередей в каждом отдельном районе позволили бы увеличить долю времени приходящуюся на транспортировку пассажиров с 46% до 77%. Если расчеты верны, то их внедрение в Чикаго позволило бы экономить примерно 15 млн $ в год, а в городах размера Москвы около 100 млн $ — деньги, которые сейчас просто остаются лежать на дороге и не приносят пользу никому.
Проекты кода, относящиеся к этой задаче доступны по ссылке
Примечания о данных.
В расчетах я использовал данные за весь 2016 год. Два месяца назад полей в датасете было побольше и среди них было много информации о точных координатах и об оплате заказа. Видимо, часть из них были скрыты в коммерческих интересах служб такси, а часть из за проблем с личной жизнью. Мне не нужны были все имеющиеся на тот момент поля, и файл с которым я в итоге начал работу можно найти по ссылке. Одна запись в нем состоит из:
шифра номера заказа,
шифра номера машины,
даты и времени посадки и высадки, округленных до ближайших отметок на часах, кратных 15 минутам,
длинны пути в милях,
времени выполнения заказа в секундах,
административных зон Чикаго, в которой была произведена посадка и соответственно высадка,
примерные геокоординаты места посадки и места высадки.
Этот файл имеет размер почти в восемь гигабайт, причем добрые две трети из них занимают неуместно длинные шифры. Чтобы мне было удобнее работать с данными, я заменил шифры на их порядковый номер при словарном упорядочивании, некоторые цифры перевел из текстового формата в числовой и сохранил записи как объекты пользовательского класса "дата юнит". По ходу дела я выбросил незначительное количество записей с совсем не реалистичными данными. Компактная упаковка позволила сократить место под тот же объем информации до 750 мегабайт. Последний файл также можно найти по ссылке, а формат хранения например в этой программе.
Примечание об оценке времени обслуживания.
Среднее время выполнения заказов за неделю я получил, просуммировав времена выполнения заказов, указанных в записи о каждой поездке и разделил на 52. Как видите никакого волшебства. Чтобы найти время простоя, сначала я сформировал упорядоченный по времени список выполненных заказов для каждой машины и вычитая из времени начала следующего заказа в списке время завершения предыдущего я получил новые списки так называемых "таймаутов". Тут возникло две трудности. Как я уже упоминал в примечаниях о данных, записи о времени посадки и высадки — это не настоящие времена, а их округления до ближайших отметок на циферблате, кратных 15-ти минутам. Вторая трудность состояла в том чтобы не учитывать перерывы между рабочими сменами в качестве простоя. Вторую я решил выгрузив распределение "таймаутов" случайных 30 машин, откуда было видно, что времена ожидания порядка 15-45 минут — характерное явление, причем достаточно часто бывают и часовые простои. Из этого всего я сделал вывод включать в расчет времени простоя только "таймауты" меньше полутора часов, а остальные игнорировать. Первую трудность я обошел просто просуммировав все принимаемые в расчет "таймауты". Почему так можно делать? Это могло бы стать занимательной задачей по теории вероятностей — показать, что, если карандаш длинны L случайным образом располагать на линейке и округлять координаты его концов до ближайших целых, то математическое ожидание разности этих округленных значений как раз и будет равно длине карандаша.
Примечания об оценке времени пути между районами.
Первая идея такой оценки состояла в усреднении времени по всем имеющимся записям поездок из одного района в другой для данного времени суток и дня недели. Однако мне показалось, что такая величина будет слегка завышена из-за всякого рода времени укладки багажа, высадки и посадки пассажиров, а так же проезду к крыльцу дома по узким улочкам, куда совершенно нет необходимости отправлять машины, реализуя просто их переброску. Поэтому я упрощенно предположил, что время заказа есть некоторая константа задержки плюс величина, пропорциональная расстоянию, указанному в заказе. Константу я отсек применив метод наименьших квадратов (смотрите в этой программе), а затем усреднил только второе слагаемое. Если доля константы во времени заказа была больше трети, я вычитал только треть.
Автор: Sergey_Kovalenko
