Клуб API Карт

Клуб API Карт

Рассчет оптимально расположения филиалов доставки

Пост в архиве.

Есть такая задача:

  1. Есть определенная территория, допустим город
  2. Необходимо программно рассчитать, какое количество точек и в каких местах (зонах) их нужно расположить чтобы доехать до любой точки территории за 40 мин с учетом пробок (в часы наибольшего траффика, в часы среднего траффика)

Надеюсь понятно написал.

Получиться ли для этого использовать яндекс API, сталкивался ли кто с такиой задачей, какие есть мысли?

Заранее спасибо, надеюсь получить хоть какую нибудь информацию, чтобы понять куда дальше копать.

6 комментариев
Авторизуйтесь, чтобы оставить комментарий
Алексей Yarrr!
28 января 2016, 02:43

Триангуляция Делоне по гео. координатам филиалов?

А после по нужным точкам построение маршрутов через api и уже конечный расчет.

vadim.zhiltsov
28 января 2016, 02:43

можно по подробней, если не сложно? Или хотя бы ссылочку на решение похожей задачи. 

Решал как-то такую же задачу, но как я понимаю "варварским" методом. Брал левую нижнюю точку, от неё делал шаг N по координатам и на каждом шаге итерации расчитывал сумму дистанций от моей точки, до каждой вершины. Там где вышла минимальная сумма дистанций - считал за оптимальный центр.
Хотелось бы узнать как это делается правильно) 

Алексей Yarrr!
28 января 2016, 02:43

Ну на мой взгляд вам нужно разбить плоскость (проекцию поверхности земли) на сегменты, затем считать расстояния от пересечений или центров ребер треугольников/полигонов. Давно таким занимался.

Можете еще посмотреть на Диаграммы Воронова. Тоже по теме, по-моему.

После разбиения вам уже не нужен будет алгоритм, имхо, потому что вам нужно будет найти путь по графу дорог города (в частности, Москвы), для чего нужно иметь этот граф — нет смысла реализовывать тоже самое, когда Яндекс.АПИ уже предоставляет этот функционал.

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

Самый простой вариант, видимо, перебором ;-)

vadim.zhiltsov
28 января 2016, 02:43

Ещё, если не ошибаюсь, то можно сформировать многоугольник по области нашим точкам и найти его центр тяжести?

Алексей Yarrr!
28 января 2016, 02:43

Тогда возникает вопрос, как определять эти многоугольники (области). На глазок?

tekunova
28 января 2016, 02:43

Как же круто, что вы решили так сделать!