Вы сами уже все нашли )
Я лишь могу подтвердить, что числа на левелсах — адекватные. Понятно, у кого-то меньше будет, у кого-то больше, но в целом все так.
> примерно +250
это без хвоста
с хвостом примерно +1000
> хвост — ну он на то и хвост, что он когда-то потом будет
это верно
но те, кто пришли чуть раньше и нарастили его к 2020 году, получили при тех же условиях (17С) гораздо больше, +1500 или даже +2000 в месяц. Да, это не навсегда, а только пока вестятся акции, которые выдавали, когда курс был 30 за акцию, а сейчас стал 60. Если курс дальше не вырастет, то такого больше не будет. А если вырастет — то будет.
Безусловно.
Если вдруг по какой-то причине ее нельзя будет ввозить, вы всегда сможете вколоть ее в Белоруссии. Там уже известный центр производства и экспорта морепродуктов, теперь еще и центр медицинского туризма будет.
Ожидание: есть принципы проектирования БД, позволяющие изначально правильно выстроить ее архитектуру, чтобы и гибко было, и работало быстро, сейчас мне про них доступно и коротенечко расскажут.
Реальность: есть несколько способов размещать сущности в таблицах БД. Если вы вдруг облажались, решив, что номер паспорта это свойство, а не отдельная сущность, и через некоторое время выяснилось, что связь человек-паспорт это один-ко-многим, то вы можете переделать схему БД, чтобы стало правильно. А потом еще раз переделать, когда вскроется следующая проблема. И еще раз.
на фото Кукуц
хоть и с «розоовыми волосами», но он не опровергает, а подтверждает тезис автора о том, что надо следить за своим внешним видом, т.к. он, судя по продуманности и частоте изменений, много времени этому уделяет
Спасибо, интересный текст. Насколько я понимаю, основная проблема — это отсутствие у яндексной маршрутизации полноценной поддержки грузового графа дорог. Это известная задача, пока что начали с Москвы и ее «грузового каркаса».
Правда, некоторые моменты в вашей статье остались неясными, например, про мобильное приложение и ключ :) Это же не масштабируемо. Они что-то даже цены не пишут (или я не нашел), ради интереса запросил ключ через сайт, пока не ответили.
как это вы VRP решаете с помощью одного лишь алгоритма Дейкстры, как указано в статье
Этого не указано в статье. Если вы считаете иначе, то приведите цитату, пожалуйста.
Мы с вами как будто на разных языках разговариваем. Вы то ли троллите, то ли правда не понимаете, что там написано. Поэтому я прекращу комментировать, можете считать, что я слился.
Это все отлично и правильно, более того, логисты руками «на коленках» именно так и делают: кластеризуют точки на глазок, а потом внутри кластеров, по сути, решают TSP-задачу с окнами. Или не решают, а отдают на откуп водителю. В начале статьи есть ссылка на мою статью, там даже картинка с кластерами приведена.
Но только все эти манипуляции
1) очевидно, не оптимальны — вы теряете несколько процентов от оптимума уже в момент кластеризации
2) на практике, довольно сложны и трудоемки. Вам надо потюнить параметры кластеризации, потюнить параметры решения TSP-задач, обернуть это все в конвейер, если вы решаете задачу больше одного раза.
Гораздо лучше иметь сразу нормальный VRP-солвер, не пытаться сделать его из TSP-солвера и такой-то матери.
Как я понимаю, в вашей работе нужно примерно оценить количество машин, тогда ваш подход понятен и правилен: из имеющихся инструментов с небольшими доработками получим результат, который на 10% хуже оптимума. Нам же надо попадать в оптимум, поэтому, возвращаясь к теме статьи, нам нужна честная большая матрица расстояний, посчитанная максимально быстро.
О, это интересно!
Я вряд ли смогу повторить на своей стороне, потому что надо дорожный граф засунуть в постгрес. Можете ли сказать,
1) верно ли я понимаю, что вы сначала отдельным запросом вычисляете матрицу с помощью pgr_dijkstraCostMatrix, и дальше этот подзапрос не пересчитывается заново? Сколько времени занимает вычисление матрицы для 5к точек в постгресе?
2) что делает pgr_dijkstraSymmetrizeCostMatrix? В доке по pgRouting я такой функции не вижу
3) в pgr_TSP можно задавать processing time и еще всякие параметры отжига. Верно ли, что если давать ему работать не несколько секунд, а больше (скажем, полчаса), то общий TSP-маршрут будет сильно (на 5-10%) оптимальнее?
Ну я вам сразу написал, вы неправильно понимаете, какую задачу мы решаем. Возможно, в тексте Тихона это не совсем удачно написано, но вроде очевидно, что 5000 заказов никак одной машиной в реальной жизни нельзя развезти, то есть, это не может быть TSP-задача на 5000 точек.
Как насчет того, что ваше утверждение про разрезание TSP неверно? Пример, который я привожу выше — это простейшая VRP задача, без Time Windows.
Простите, вы что-то очень странное пишете. Кажется, вы говорите о какой-то сферической 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 точек — вполне актуальная задача.
Нет, к сожалению, все верно. Речь про веб-карты, туда выкатили сильно урезанную функциональность, поэтому сейчас оно не для всех сценариев подходит. Возможно, в будущем что-то поменяем/улучшим.
Я лишь могу подтвердить, что числа на левелсах — адекватные. Понятно, у кого-то меньше будет, у кого-то больше, но в целом все так.
Здесь, безусловно, есть вина собеседующих. Но вряд ли исключительно лишь их вина.
это без хвоста
с хвостом примерно +1000
> хвост — ну он на то и хвост, что он когда-то потом будет
это верно
но те, кто пришли чуть раньше и нарастили его к 2020 году, получили при тех же условиях (17С) гораздо больше, +1500 или даже +2000 в месяц. Да, это не навсегда, а только пока вестятся акции, которые выдавали, когда курс был 30 за акцию, а сейчас стал 60. Если курс дальше не вырастет, то такого больше не будет. А если вырастет — то будет.
74 плюса за этот комментарий, минимум 74 хабрапользователя согласны с этой точкой зрения
Уважаемые товарищи, существует ли в мире какой-либо продукт, который вы считаете «не говном»?
Если вдруг по какой-то причине ее нельзя будет ввозить, вы всегда сможете вколоть ее в Белоруссии. Там уже известный центр производства и экспорта морепродуктов, теперь еще и центр медицинского туризма будет.
Ожидание: есть принципы проектирования БД, позволяющие изначально правильно выстроить ее архитектуру, чтобы и гибко было, и работало быстро, сейчас мне про них доступно и коротенечко расскажут.
Реальность: есть несколько способов размещать сущности в таблицах БД. Если вы вдруг облажались, решив, что номер паспорта это свойство, а не отдельная сущность, и через некоторое время выяснилось, что связь человек-паспорт это один-ко-многим, то вы можете переделать схему БД, чтобы стало правильно. А потом еще раз переделать, когда вскроется следующая проблема. И еще раз.
Спасибо, кэп, но так я и сам умею.
хоть и с «розоовыми волосами», но он не опровергает, а подтверждает тезис автора о том, что надо следить за своим внешним видом, т.к. он, судя по продуманности и частоте изменений, много времени этому уделяет
Известно же, чем заканчивается: не спишь, расстраиваешься, еще и минусов в карму, небось, напихали.
Правда, некоторые моменты в вашей статье остались неясными, например, про мобильное приложение и ключ :) Это же не масштабируемо. Они что-то даже цены не пишут (или я не нашел), ради интереса запросил ключ через сайт, пока не ответили.
Этого не указано в статье. Если вы считаете иначе, то приведите цитату, пожалуйста.
Мы с вами как будто на разных языках разговариваем. Вы то ли троллите, то ли правда не понимаете, что там написано. Поэтому я прекращу комментировать, можете считать, что я слился.
Но только все эти манипуляции
1) очевидно, не оптимальны — вы теряете несколько процентов от оптимума уже в момент кластеризации
2) на практике, довольно сложны и трудоемки. Вам надо потюнить параметры кластеризации, потюнить параметры решения TSP-задач, обернуть это все в конвейер, если вы решаете задачу больше одного раза.
Гораздо лучше иметь сразу нормальный VRP-солвер, не пытаться сделать его из TSP-солвера и такой-то матери.
Как я понимаю, в вашей работе нужно примерно оценить количество машин, тогда ваш подход понятен и правилен: из имеющихся инструментов с небольшими доработками получим результат, который на 10% хуже оптимума. Нам же надо попадать в оптимум, поэтому, возвращаясь к теме статьи, нам нужна честная большая матрица расстояний, посчитанная максимально быстро.
Я вряд ли смогу повторить на своей стороне, потому что надо дорожный граф засунуть в постгрес. Можете ли сказать,
1) верно ли я понимаю, что вы сначала отдельным запросом вычисляете матрицу с помощью pgr_dijkstraCostMatrix, и дальше этот подзапрос не пересчитывается заново? Сколько времени занимает вычисление матрицы для 5к точек в постгресе?
2) что делает pgr_dijkstraSymmetrizeCostMatrix? В доке по pgRouting я такой функции не вижу
3) в pgr_TSP можно задавать processing time и еще всякие параметры отжига. Верно ли, что если давать ему работать не несколько секунд, а больше (скажем, полчаса), то общий TSP-маршрут будет сильно (на 5-10%) оптимальнее?
Как насчет того, что ваше утверждение про разрезание TSP неверно? Пример, который я привожу выше — это простейшая VRP задача, без Time Windows.
Девятнадцатая ссылка из статьи про Дейкстру в английской википедии:
Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra's Algorithm
у всех давно и прекрасно работает
Ну нет же, это выглядит очевидно неверным. Я выше привел пример.
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 уже ответил выше
Нет, к сожалению, все верно. Речь про веб-карты, туда выкатили сильно урезанную функциональность, поэтому сейчас оно не для всех сценариев подходит. Возможно, в будущем что-то поменяем/улучшим.