Comments 13
Почитал вашу статью, интересно, в детали пока не вдавался. В вашей терминологии получается, я сделал не только "на коленке", а еще и "одним топором, без единого гвоздя" ) Из сторонних библиотек и компонентов только гугл-карты для визуализации, и то их можно без труда заменить на альтернативы типа яндекс-карт и подобного.
Статья из разряда как нарисовать сову. Добавьте ключевые технические детали. Например, где вы взяли граф дорог и перекрестков? Неужели сами мышкой накликали для всего США?
Ну зачем для всего США, для пары регионов - Сан Франциско и Лос Анжелес. А потом сделал интерфейс чтобы менеджер сам задавал сетки для новых регионов. Не кликая мышкой, а драгая маркер по карте, но не суть. Да и вопрос в степени детальности сетки - в скриншотах статьи приведен искусственный пример (для наглядности), но реальная сетка не сказать чтобы радикально детальнее.
А как вы отслеживаете и обновляете информацию о пробках / ремонтах / проездах для грузовиков и тп?
Топология графа (перечень вершин и ребер) не меняется, но задается скорость по каждому ребру в зависимости от времени дня. Если не задана (в большинстве ребер) - то по умолчанию 60 км/ч. Даже если ничего не менять, это уже задает регулярные пробки и односторонние движения. А если менять, то можно отклоняться от обычной регулярности - ремонты и т.п. Изменения руками (через интерфейс) волевым решением юзера, который узнал о ремонте и закрытии участка трассы.
Все, теперь понял.
Просто я сталкивался с гео-задачами и в целом мне эта тема интересна. Но основная проблема в том, что, пожалуй 70-80%, работы - это обновлять граф актуальными и полными сведениями. Остальные 30-40% - это вот сделать модельку с весами и прикрутить алгоритм.
И если актуализировать граф вручную - это занимает уйму времени, а так же ухудшает качество расчетов, так как это происходит с запозданием.
Я сам их так и не решил, были идеи начиная с парсинга опен стрит мап, поиском апи, которое предоставляло бы информацию о пробках (я так же нашел те гугло-сервисы, которые могли бы помочь за мзду), и вплоть до сбора данных самому (на основе данных своих же пользователей).
А выходит вы их тоже не решили / не решали.
Я бы рекомендовал использовать муравьиный алгоритм.
Из статьи не сразу очевидно почему брутфорс не подходит. Обычно до 20 точек легко. А с учётом множества ограничений, пространство поиска сильно суживается, может и намного больше точек. В примере всего лишь 12 точек.
Непонятно чем вам не понравился быстрый и надежный 2-opt. Тем более, что основная мысль статьи в том, что не так важен сам алгоритм, как приближенные к реальности ограничения и весовая функция.
я бы хотел вернуться к основной теме этой статьи и рассказать об алгоритме составления оптимального маршрута.
Так алгоритм не важен или это всё-таки основная тема статьи? Имеет смысл убрать тег "алгоритмы", если не важно.
Для 12 точек полный перебор практически мгновенно решает задачу, находя глобальный оптимум гарантировано.
2-опт - это тот случай, когда "быстрый и надёжный" синоним "примитивный". Эта просто жадная стратегия. Никто его не использует.
По поводу реальных ограничений удивлен, что не использовали OSM. Лет 15 назад будучи студентом ещё, использовал это бесплатное решение, когда надоело вручную векторизовывать карту.
лет 25 назад решал подобную задачу. Развозка заказов по аптекам для Питера. город был разбит на сектора и участки. их было штук 20-30. Заказы группировались по ним. Заказы естественно случайные. Машина посещала 1 или 2 участка. Задача была чтобы заказов было 6-7 на машину, больше за день не успеть. Ручной регулировки практически не было.
Сферический коммивояжёр в вакууме и в реальной жизни