Разработка оптимальных маршрутов следования

Сущность и классификация маршрутов

Ключевым понятием для разработки оптимальных маршрутов является собственно маршрут.

Маршрутизация позволяет выполнить оптимизацию грузопотоков по разным критериям:

• по объему перевозок, направлениям и дальности;
• по протяженности во времени;
• по последовательности движения;
• по загруженности дорог (по категориям);
• по эффективности доставки.

Основные задачи маршрутизации:

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

Маршруты могут быть классифицированы по различным основаниям:

• по назначению и порядку использования транспорта,
• по условиям организации,
• по полигонам и условиям обращения,
• по принадлежности транспортных средств.

Задача коммивояжера

Вопросы, впоследствии изучаемые комбинаторикой, занимали еще древних (древнегреческих, древнеиндийских, древнекитайских) математиков. Активизация интереса была связана с появлением в XIX веке теории графов. Комбинаторика находит применение во многих математических направлениях:

• теория графов,
• криптография,
• программирование,
• теория вероятностей.

Задача коммивояжера является классической комбинаторной задачей. Для наглядной демонстрации ее значимости рассмотрим историю поиска ее решения:

• ирландский математик сэр Уильям Роуэн Гамильтон и британский математик Томас Пенингтон Киркмен в XIX веке изучали математические проблемы, непосредственно связанные с задачей коммивояжера. Гамильтон в 1857 году создал игру Икосиан, смысл которой состоял в том, чтобы соединить 20 точек додекаэдра так, чтобы каждая из точек была использована только один раз, а конечная точка пути совпадала с исходной. На основе этой игры было сформировано понятие гамильтонова цикла;
• с математической точки зрения задачу поиска оптимального пути впервые рассмотрел математик и экономист Карл Менджер в 1930-х;
• популяризация задачи коммивояжера была связана с предпринятыми в 1940-х попытками статистиков Мэхаланобиса, Джессена, Гоша и Маркса применить ее решение к сельскохозяйственному экономическому сектору. Благодаря этому с 1950-х предложения по решению задачи коммивояжера начали активно публиковать в научных журналах;
• в 1954 году Данцигом, Фалкерсоном и Джонсоном было издано описание метода для решения задачи коммивояжера. В качестве практической иллюстрации было приведено решение с 49 городами – таким образом, исследователи соединили города из всех американских штатов;
• в 1971 году Хельду и Карпу удалось решить задачу построения оптимального маршрута для 64 городов;
• в 1973 году Керниган и Лин предложили применение задачи коммивояжера в инженерии – для соединения точек при резке лазером;
• в 1977 году Мартином Гротчелом был построен оптимальный путь между 120 городами;
• в 1987 году Гроешел и Голланд решили задачу с 666 городами, а Ринальди и Падберг – с 2392 городами;
• в 1994 году количество соединяемых городов удалось увеличить до 7397, а в 2006 – до 85900.

Алгоритмы разработки оптимального маршрута

Все алгоритмы, используемые для решения задачи коммивояжера, делятся на две группы:

• точные алгоритмы,
• неточные алгоритмы.

Точные алгоритмы предусматривают перебор всех возможных вариантов построения маршрута. Иногда удается найти решение достаточно быстро, но в общем случае необходимо перебрать n! циклов. Неточные алгоритмы обычно используют в задачах, которые не имеют точного решения или требуют для точного решения неоправданных значительных затрат времени.

Точные алгоритмы решения задачи коммивояжера, в свою очередь, подразделяются на две группы:

• в первой группе используются методы релаксации линейного программирования. В нее входят метод Гомори, метод ветвей и границ, метод внутренней точки;
• во второй группе используются методы динамического программирования.

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

Неточные алгоритмы потенциально могут дать неоптимальное решение, однако получено оно будет быстрее, чем в точном алгоритме. Неточные алгоритмы делятся на:

• приближенные,
• эвристические.

В качестве примеров неточных алгоритмов можно назвать:

• алгоритм Кристофайдеса,
• алгоритм ближайшего соседа,
• жадный алгоритм,
• алгоритм Кернигана-Лина,
• алгоритм с запретами,
• муравьиный алгоритм,
• оценка нижней грани Хелд-Карпа.

Перспективным направлением исследования представляются генетические алгоритмы. Они относятся к классу методов оптимизации, построенных на основе природных биологических процессов. Генетические алгоритмы универсальны, поскольку от условий поставленной задачи зависят только кодирование решений и функция приспособленности. Когда алгоритм выполняется, во внимание принимают следующие общие правила:

• начальную популяцию нужно формировать случайным образом,
• количество особей в популяции не меняется,
• каждую особь кодируют с помощью строки определенной длины.

На каждом шаге алгоритма выполняют три этапа:

• отбирают особей для производства потомства в зависимости от их приспособленности,
• промежуточную популяцию разбивают на пары и скрещивают,
• полученное поколение подвергают мутации.