Учитывая набор водителей и набор потенциальных пассажиров, как мы можем эффективно направлять водителей, чтобы забрать пассажиров и высадить их в пункте назначения? Это одна из многих (часто пересекающихся) проблем, которые решили UberPOOL и Lyft Line для развития своего бизнеса, повышения эффективности и повышения устойчивости транспортных сетей.
Как мы можем разбить эту проблему на подзадачи или свести к более простой проблеме? Если мы сможем это сделать, возможно, мы сможем постепенно добавлять сложность, чтобы получить более полное решение. Даже если более простые проблемы не могут быть объединены, мы можем получить достаточно информации из их решения, чтобы создать решение исходной проблемы.
Для начала нам нужно преобразовать интуитивное описание проблемы в более формальную формулировку. Но еще до того, как мы это сделаем, мы можем начать делать некоторые упрощения.
Упрощение №1. Считайте, что местоположение каждого водителя и пассажира фиксировано.
При таком упрощении расстояния между ними будут фиксированными. Это могло бы быть приемлемым упрощением, если бы мы периодически запускали алгоритм, по сути, прокладывая маршрут с использованием снимков местоположения водителя и пассажира. В частности, мы планировали бы доступных пассажиров для доступных водителей в определенный момент времени, а затем повторили бы процесс, используя новый набор водителей и пассажиров через некоторый период времени.
Тогда возникает другой вопрос: как мы хотим измерить эффективность маршрута? Имеет значение только общее расстояние? Или нужно учитывать другие затраты?
Упрощение №2. Предположим, что стоимость поездки между двумя точками известна, фиксирована и симметрична.
В эту стоимость могут входить такие вещи, как время, расстояние, топливо и т. Д.
Используя эти два начальных упрощения, мы можем затем представить проблему в виде графа. Каждое местоположение водителя и пассажира является узлом в полном взвешенном графе, а взвешенное ребро между каждой парой узлов представляет собой стоимость путешествия между этими местоположениями. Назовем это графиком затрат.
Но это не полностью представляет проблему. А именно, у нас есть дополнительное ограничение, заключающееся в том, что место отправления каждого пассажира должно предшествовать месту назначения в маршруте. Эти ограничения также могут быть представлены в отдельном ориентированном графе, где ребро (a, b) существует в графе, если пассажир хочет уйти из пункта a до местоположения b. Назовем это графом зависимости путей.
Давайте сделаем еще одно упрощающее предположение, чтобы еще больше сократить проблему.
Упрощение №3: предположим, что драйвер один.
Теперь у нас есть следующая подзадача:
Подзадача № 1: для полного графика взвешенных затрат C, графа зависимостей пути D и исходного узла o, найти минимальный маршрут, начинающийся в o через все другие узлы в C, при соблюдении порядка расположения, закодированного в D.
В качестве примечания, путь, который проходит через все узлы графа ровно один раз, известен как гамильтонов путь.
Мы можем попытаться решить это наивно с помощью подхода грубой силы:
- Сгенерируйте все допустимые гамильтоновы пути, которые удовлетворяют зависимостям пути
- Оцените каждый путь, суммируя его веса
- Верните один из минимальных путей
Шаг (1) похож на хорошо известную проблему поиска топологической разновидности ориентированного графа с изменением, заключающимся в том, что мы хотим возвращать все такие типы узлов. Известны алгоритмы для возврата одной топологической сортировки за линейное время (т. Е. O (| V | + | E |)), где V - набор вершин, а E - набор ребер в графе зависимостей путей.
Как мы можем добиться большего?
По сути, мы дважды перебираем узлы на каждом допустимом пути, один раз на шаге (1), а затем еще раз для суммирования длин путей на шаге (2). Мы могли бы объединить эти два шага, чтобы сгенерировать допустимые пути, одновременно отслеживая их длину. Нам нужно быть осторожными, чтобы различать график зависимости пути, который определяет допустимые пути, и график затрат, который описывает стоимость путешествия между двумя местоположениями.
Но давайте сделаем шаг назад. График зависимости пути на самом деле довольно особенный. Половина узлов предназначена для пассажиров, а другая половина - для пассажиров. Кроме того, каждый исходный пункт имеет только границу с одним пунктом назначения. Итак, для трех пассажиров это будет выглядеть примерно так:
Учитывая, что мы пытаемся построить допустимые пути с самого начала, как мы можем использовать эту особую структуру зависимостей пути? Мы представляли зависимости в виде кортежей, но, может быть, они лучше подходят для какой-то другой структуры данных? Учитывая, что для каждого узла существует не более одной зависимости, мы могли бы сохранить их в словаре: D = {b: a, d : c, f: e}, где D [b] = a указывает, что b должен стоять после a в маршруте.
Используя наше новое представление и учитывая, что наш путь до сих пор действителен, как мы можем определить, сохранит ли добавление нового узла n этот путь? Мы могли бы проверить, есть ли у n зависимость, и если да, то есть ли эта зависимость в узлах, посещенных до сих пор. А именно, если D [n] существует, то он должен быть в наборе посещенных узлов.
Учитывая, что мы поддерживаем набор посещенных узлов при генерации гамильтоновых путей, это дает нам быстрый способ проверить, является ли добавление нового узла допустимым расширением пути:
Это оставляет нас с подзадачей генерации минимальных гамильтоновых путей (которые мы можем отсечь динамически, используя приведенную выше проверку). К сожалению, это NP-полная проблема, и поэтому мы не можем ожидать найти эффективные алгоритмы для ее решения в целом. Эта проблема также тесно связана с проблемой коммивояжера (TSP), с той разницей, что решение TSP - это минимальный путь, возвращающийся к своему источнику (также называемый гамильтоновым циклом).
Существует множество алгоритмов для поиска приближенных решений этого набора проблем. Один известен как алгоритм ближайшего соседа. В этом алгоритме мы создаем короткий путь, жадно выбирая узел, ближайший к текущему узлу, в качестве следующего узла на пути. Вот простая реализация этого алгоритма для этой проблемы с использованием нашей предыдущей функции, которая может удалить недопустимых ближайших соседей:
Можно было бы оценить асимптотическую сложность этого алгоритма, но на практике это, вероятно, не имеет значения. Количество пассажиров, которых заберут по маршруту, обычно невелико, поэтому асимптотическое поведение не является реалистичным. Учитывая, что количество пассажиров достаточно мало, мы могли бы даже использовать наше решение грубой силы, которое генерирует все допустимые пути, чтобы найти точный минимальный путь вместо приближения.
Обратите внимание, что это решение фактически не использует всю силу упрощения (2). А именно, он все равно предложит хорошее приближенное решение независимо от того, является ли график стоимости симметричным. На практике график затрат, вероятно, не является симметричным из-за таких вещей, как улицы с односторонним движением и разная топология дорог в каждом направлении, поэтому хорошо, что мы можем ослабить это предположение.
В заключение, этот пост рассматривает простой подход к сложной проблеме и делает ряд упрощающих предположений. В следующем посте мы увидим, сможем ли мы ослабить некоторые из этих предположений и восстановить проблему до чего-то более близкого к ее первоначальной формулировке.
Читайте вторую часть серии здесь.
