Планировщик маршрутов v2.0

Я послушал ваши отзывы и комментарии по поводу моего небольшого проекта. Реализовал некоторые из высказанных идей и, конечно, добавил к ним часть своих.

  1. Самое главное, самое сложное и самое незаметное: поменялся алгоритм поиска. Вместо точного и медленного метода ветвей и границ теперь почти точный и метаэвристичекий метод муравьиной колонии. В основе проекта лежит Travelling Salesman Problem (Задача коммивояжёра), которая является NP-полной. А это означает, что нет другого пути решения её, кроме как перебрать все варианты. Количество вариантов можно посчитать по формуле \(n! \over 2\), где \(n\) — количество промежуточных городов. Если подставить в эту формулу, например, 15 получим 653 837 184 000 вариантов, а это уже очень много. Поэтому пришлось воспользоваться приближенным алгоритмом, который работает быстро, но и решение выдаёт не всегда оптимальное. Кстати, так как внутри алгоритма задействован генератор случайных чисел, решение может меняться от запуска к запуску, достаточно нажать кнопку обновить.

  2. Я убрал из проекта AngularDart, что позволило уменьшить размер JavaScript-файла в 3 раза.

  3. Теперь можно скопировать ссылку с маршрутом и отправить кому-нибудь. Только осторожно, чем больше городов будет в маршруте, тем длиннее будет ссылка и некоторые браузеры могут не справиться с такой длиной. Вот вам, например, ссылка на маршрут по всем европейским столицам.

  4. Упростилось добавление городов в маршрут. Из вариантов объектов теперь убираются лишние, если вариант только один, то он добавляется автоматически. И самое главное: можно добавлять города, даже не прикасаясь к мышке, используя для выбора варианта клавиши «Вверх», «Вниз» и «Enter».

  5. А ещё теперь можно развернуть карту на весь экран, чтобы было удобнее её изучать.

  6. Исправлены ошибки.

Маршрут по Европе

Маршрут по Европе

Прошу любить и жаловать. Замеченные недочёты можно описывать в комментариях к этому посту, ну или присылать любым другим способом.

Планировщик маршрутов

Здравствуйте, дорогие читатели!

За окном вовсю сияет март, а мы уже начали готовиться к новому большому летнему путешествию (обязательно посмотрите предыдущее, если, конечно, ещё не видели его). К сожалению, идея проехать Соединённые Штаты поперёк накрылась медным тазом отложена до лучших времён. Но это не причина для уныния, ведь есть ещё сотни стран, требующих нашего внимания. И мы решили не заморачиваться и повторить прошлогодний опыт бэкпэкерства с InterRail, благо пол-Европы осталось неизъезженной.

Сказано — сделано. Набросали списочек городов для посещения и оказалось, что маршрут, в отличие от предыдущего года, не очевиден. В каком порядке их нужно объезжать, чтобы расстояние, преодолённое на поезде, получилось минимальным? Поиск нужных сервисов для составления маршрутов ничего не дал, а значит нужно написать свой! Что я и сделал.

Представляю вам планировщик маршрутов. Сервис довольно простой: вводишь начальный город, конечный, а также список городов посередине, — и получаешь оптимальный маршрут. Расстояния между городами считаются по прямой, поэтому результат оптимален только для самолётов. А для остального транспорта стоит учитывать, что дороги кривые и ездят по ним с разной скоростью. Но для того, чтобы прикинуть маршрут, информации достаточно. Конечно, между некоторыми пунктами дороги может вообще не существовать, но не беда: любой отрезок из пути можно исключить и система выдаст другой маршрут с учётом этого ограничения.

Проложить свой маршрут

Проложить свой маршрут

Для приготовления сервиса мне понадобились: Яндекс.Карты, AngularDart, Bootstrap. Туда пришлось добавить немного логики и свободного времени. Всё это было смешано, взболтано, вылито в высокий бокал и украшено методом ветвей и границ, прямо как учили в универе. Приятного аппетита.

Прошу опробовать и написать свои замечания и пожелания в комментариях. Исходники всего это дела можно увидеть всё там же — на GitHub.

Всегда к вашим услугам,
Редакция блога.