Расчёт оптимального маршрута - решение задачи коммивояжёра

Почему из большого множества алгоритмов для решения задачи коммивояжёра, был выбран именно генетический алгоритм? Какое максимальное количество точек (кроме начала и конца маршрута) может оптимизировать «Сервис доставки»? По каким критериям происходит расчёт (кратчайших путь или минимальное время)?

Спасибо, вроде понятно. Хотя ехать по кратчайшему пути не всегда оптимально. Тем более во многих цифровых картах присутствует коэффициент качества дороги (приоритетность), учитывая который можно рассчитать маршрут с наименьшим временем прохождения, исключая тропы и дворовые проезды.

А планируется ли отправка маршрута на навигатор через GPRS? Если да, на какие марки/модели?

Можете так обратить внимание на веб-сервис "Департамент логистики". Интеграция с wialon`ом уже есть. Маршрутизация производится по графу openstreetmap. При оптимизации учитываются временные окна, а так же возможны промежуточные погрузки в пути. Для всех крупных городов бывшего СССР созданы пробочные профили по районам города и времени суток (скорость движения различается в зависимости от времени выезда).

Мы не используем API openstreetmap. У нас разработан собственный роутер и геокодер на основе данных OSM. Система изначально проектировалась как "бесконечно" масштабируемая (помимо основных серверов, при необходимости автоматически запускаются инстансы на амазоне). Теоретического ограничения на количество точек в маршруте нет, но если вы собираетесь использовать более 100 точек в одном маршруте (хотя не очень понимаю где это применимо), то лучше свяжитесь с нами.

Luxena
1. Работает с Garmin точно, с другими не знаю. На сайте Garmin можно сделать выборку навигаторов, которые поддерживают FMI
2. Работает например с Galileo, Телтоника вроде еще умеет
3. Там смысл в том что с сервера отправляется одна точка, а навигатор принимает ее и строит маршрут до нее.

Вся информация чисто теориетическая, сам не пробовал. Так что поправьте меня кто знает более точно

Спрос на решение данной задачи есть. Причем очень и очень значительный

Только представьте, что в среднем транспортные расходы можно снизить на 15%, а это 7-15 тыс руб с автомобиля в месяц!

Интересуют следующие задачи:
- построение порядка внутри маршрута
- распределение точек по маршрутам
- выбор дня для обслуживания каждой из точек
- принятие решения о неэффективности поездки в ту или иную точку
- выбор собственного или наемного транспорта для исполнения маршрута

Ограничения при планировании:
- грузоподъемность и вместимость автомобилей
- предпочтительное время подъезда на конечные точки
- время доступности водителей и склада
- типы грузов (заморозка, охлажденка и пр)
- совместимость товаров
- отдыхи водителей во время движения и ограничения по длительности вождения

Также иногда важно
- прокладка маршрутов с учетом типа ТС (нагрузка на ось, габариты)
- предпочтительные водители для осблуживания отдельных клиентов
- равномерное распределение задач между водителями
- нарушение отдельных ограничений в угоду оптимальности маршрутов

Следующие алгоритмы решают задачу:
- мульти-агентный
- эвристические (целое семейство - from far например)
- полный перебор - не очень эффективно ))) на 13 точках в маршруте - уже 6 миллиардов комбинаций!!!!

Приложения для маршрутизации в различных отраслях - www.maxoptra.ru