Простите, вы что-то очень странное пишете. Кажется, вы говорите о какой-то сферической TSP-задаче в вакууме.
1) я посмотрел доку PgRouting pgr_TSP(matrix_cell_sql,...)
...
Example:
SELECT * FROM pgr_TSP(
$$
SELECT * FROM pgr_dijkstraCostMatrix(
...
ну то есть решение TSP-задачи никоим образом не избавляет нас от необходимости иметь матрицу расстояний, что логично.
Вы пишете выше, что PgRouting за секунды решает TSP-задачу на 5000 точек — имеется в виду режим, в котором нужно сначала вычислять матрицу? Или более простая функция, pgr_eucledianTSP, которая на вход берет просто координаты и считает евклидовы расстояния? Если второе, то так может быть, ведь там можно применять А*-алгоритм. Если первое, т.е. расстояния по графу дорог — извините, не верю в несколько секунд.
2) Про разрезание TSP-маршрута тоже подозрительно. Откуда следует, что так можно делать? Его же можно многими способами разрезать, как из них выбрать оптимальный для VRP-задачи? Кажется, легко подобрать пример, когда разрезанный TSP-маршрут не будет оптимальным для VRP-задач. Рассмотрим «звезду»: нам надо объехать точки по оси Х вправо (1,0) (2,0) ... (5,0)
по оси Х влево (-1,0) (-2,0) ... (-5,0)
По оси Y вверх (0,1) .. (0, 5)
по оси Y вниз (0, -1) .. (0, -5) Стартуем в нуле.
Оптимальный TSP-объезд может выглядеть так: направо до (5,0), по диагонали налево-вверх до (0, 5), вниз до (0, -5), по диагонали до (-5, 0), обратно в начало координат. Он содержит в себе два длинных диагональных перехода между лучами. Очевидно, при разрезании его на несколько маршрутов эти переходы могут быть не нужны, т.к. дешевле отправлять машины по лучам.
Пусть одна машина вмещает 4 единицы, тогда оптимальные маршруты будут, на глаз, такие: route 1 - (2, 0) (3, 0) (4, 0) (5, 0) - именно в таком порядке, чтобы пустым ехать обратно
route 2 - (0, 2) (0, 3) (0, 4) (0, 5)
route 3 - (-2, 0) (-3, 0) (-4, 0) (-5, 0)
route 4 - (0, -2) (0, -3) (0, -4) (0, -5)
route 5 - (1, 0) (0, 1) (-1, 0) (0, -1)
Эти маршруты (в частности, route 5) не являются отрезками решения оптимального TSP-маршрута.
ну и
3) У нас VRPTW-задача. Локации имеют окна доставки, в которые нужно попадать, в этом смысл. Объезд этих локаций одним коммивояжером вообще никак не поможет.
Вы неправильно понимаете, мы решаем не TSP, а VRP на 5000 точек.
Один маршрут на 5000 точек — похоже на экзотику (непонятно, где в реальной жизни это может быть применимо), а вот VRP на 5000 точек — вполне актуальная задача.
Нет, к сожалению, все верно. Речь про веб-карты, туда выкатили сильно урезанную функциональность, поэтому сейчас оно не для всех сценариев подходит. Возможно, в будущем что-то поменяем/улучшим.
А запрос от «нефтянников» был не из Газпром-Нефти, случайно?
не могу сказать ) у нас есть несколько публично известных партнерств, но это, кажется, не из их числа
BIA-Technologies
Прикольно, если я правильно понял, вы сделали свой ati.su, теперь пилите маршрутизацию в каком-то виде.
Даже грузовой навигатор есть! А откуда карты брали, если не секрет?
триал идет в данный момент и до середины апреля, 3 месяца бесплатно новым подключившимся компаниям
не знаю, уместно ли тут оставлять ссылку, могу отправить в личку, если интересно
1) я посмотрел доку PgRouting
pgr_TSP(matrix_cell_sql,...)
...
Example:
SELECT * FROM pgr_TSP(
$$
SELECT * FROM pgr_dijkstraCostMatrix(
...
ну то есть решение TSP-задачи никоим образом не избавляет нас от необходимости иметь матрицу расстояний, что логично.
Вы пишете выше, что PgRouting за секунды решает TSP-задачу на 5000 точек — имеется в виду режим, в котором нужно сначала вычислять матрицу? Или более простая функция,
pgr_eucledianTSP, которая на вход берет просто координаты и считает евклидовы расстояния? Если второе, то так может быть, ведь там можно применять А*-алгоритм. Если первое, т.е. расстояния по графу дорог — извините, не верю в несколько секунд.2) Про разрезание TSP-маршрута тоже подозрительно. Откуда следует, что так можно делать? Его же можно многими способами разрезать, как из них выбрать оптимальный для VRP-задачи? Кажется, легко подобрать пример, когда разрезанный TSP-маршрут не будет оптимальным для VRP-задач. Рассмотрим «звезду»: нам надо объехать точки
по оси Х вправо (1,0) (2,0) ... (5,0)
Стартуем в нуле.по оси Х влево (-1,0) (-2,0) ... (-5,0)
По оси Y вверх (0,1) .. (0, 5)
по оси Y вниз (0, -1) .. (0, -5)
Оптимальный TSP-объезд может выглядеть так: направо до (5,0), по диагонали налево-вверх до (0, 5), вниз до (0, -5), по диагонали до (-5, 0), обратно в начало координат. Он содержит в себе два длинных диагональных перехода между лучами. Очевидно, при разрезании его на несколько маршрутов эти переходы могут быть не нужны, т.к. дешевле отправлять машины по лучам.
Пусть одна машина вмещает 4 единицы, тогда оптимальные маршруты будут, на глаз, такие:
route 1 - (2, 0) (3, 0) (4, 0) (5, 0) - именно в таком порядке, чтобы пустым ехать обратно
route 2 - (0, 2) (0, 3) (0, 4) (0, 5)
route 3 - (-2, 0) (-3, 0) (-4, 0) (-5, 0)
route 4 - (0, -2) (0, -3) (0, -4) (0, -5)
route 5 - (1, 0) (0, 1) (-1, 0) (0, -1)
Эти маршруты (в частности, route 5) не являются отрезками решения оптимального TSP-маршрута.
ну и
3) У нас VRPTW-задача. Локации имеют окна доставки, в которые нужно попадать, в этом смысл. Объезд этих локаций одним коммивояжером вообще никак не поможет.
Один маршрут на 5000 точек — похоже на экзотику (непонятно, где в реальной жизни это может быть применимо), а вот VRP на 5000 точек — вполне актуальная задача.
UPD: tuxxon уже ответил выше
Нет, к сожалению, все верно. Речь про веб-карты, туда выкатили сильно урезанную функциональность, поэтому сейчас оно не для всех сценариев подходит. Возможно, в будущем что-то поменяем/улучшим.
не могу сказать ) у нас есть несколько публично известных партнерств, но это, кажется, не из их числа
Прикольно, если я правильно понял, вы сделали свой ati.su, теперь пилите маршрутизацию в каком-то виде.
Даже грузовой навигатор есть! А откуда карты брали, если не секрет?
триал идет в данный момент и до середины апреля, 3 месяца бесплатно новым подключившимся компаниям
не знаю, уместно ли тут оставлять ссылку, могу отправить в личку, если интересно
вот это те, с кем мы конкурируем за контракты