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

О передовом алгоритме оптимизации в подкасте Nature рассказал его автор — исследователь из Senseable City Lab при МТИ Мо Вазифех.

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

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

Вазифех говорит, что алгоритм работает в двух вариантах. Первый пригоден для службы доставки, которая распределяет все заказы на день рано утром. Оптимизация сделала ненужными около 40% автомобилей.

Затем алгоритм проверяли в режиме такси, когда заказы возникают в реальном времени. Для тестов взяли данные из Нью-Йорка за прошлый год — около 150 млн заказов. Система позволила снизить необходимое для их обслуживания число такси на 30%.

«На простом домашнем компьютере вы можете решить задачу в очень короткое время — примерно за полсекунды», — подчеркивает Вазифех.

На третьем этапе систему еще более приблизили к жизни. Исследователи учли, что заказы могут обрабатываться не одной службой такси, а несколькими. Ученый утверждает, что если они будут вести общую базу данных, эффективность распределения машин понизится лишь 6-7%. Может алгоритм справиться и с «человеческим фактором» — например, если клиент попросит водителя проехать по любимым улицам или заскочить в соседний квартал за знакомым.

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

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

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