Клуб API Карт

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

Владимир
14 февраля 2013, 12:49

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

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

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

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

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

6 комментариев
Подписаться на комментарии к посту

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

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

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

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

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

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

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

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

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

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

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

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