API оптимизации Mapbox возвращает оптимизированный по продолжительности маршрут между входными данными coordinates, который также известен как решение так называемой "задачи коммивояжера" . Это хорошо известная проблема теории графов NP-hard , означающая, что для этой проблемы не существует общего решения за полиномиальное время.
Базовые данные, используемые для вычисления вышеупомянутой длительности оптимизированный маршрут - это функции стоимости ребер, соединяющих вход coordinates с запросом API. Вы можете получить значения затрат (включая traffi c) между набором этих координатных позиций, используя Матричный API Mapbox .
Добавление второго водителя / продавца к проблеме делает проблему экспоненциально труднее решить, как обсуждалось в ответе на этот пост переполнения стека .
Вот ссылка на научную c статью , обсуждающую возможный подход к этому проблема.
Как свидетельствует исследовательское сообщество, решение проблемы Multiple Traveling Saleser не так просто реализовать. Если вы не хотите участвовать в этой нетривиальной задаче по реализации алгоритма, который решит его за вас, вы можете реализовать функцию, которая сделает обоснованное предположение о том, как разделить пункт назначения coordinates между двумя драйверами. Это «обоснованное предположение» может основываться на значениях, полученных из Matrix API. Вы можете сделать запрос один ко многим для каждого драйвера, затем взять меньшее из двух значений длительности для каждой координаты и назначить координату соответствующему драйверу. Затем вы можете использовать API-интерфейс оптимизации Mapbox для индивидуального решения двух отдельных задач коммивояжера.
Даже если вы внедрили алгоритм, который решал бы проблему многократного коммивояжера, сложность задачи экспоненциально возрастает с увеличением количества водителей. и количество путевых точек. Следовательно, вы можете получить решение, которое работает, но не обязательно будет вычисляться в течение надежного промежутка времени. Эти ограничения производительности следует учитывать при реализации решения.