Справочник от Автор24
Найди эксперта для помощи в учебе
Найти эксперта
+2

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

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

Определение 1

Разработка оптимальных маршрутов следования – это деятельность, позволяющая выбрать из всех доступных маршрутов маршруты, обладающие наилучшими характеристиками по выбранным критериям (например, расстояние, стоимость перевозки и т. д.).

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

Определение 2

Маршрутом называют намеченный (установленный), а при необходимости – оборудованный путь следования транспорта из начального пункта в конечный.

Определение 3

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

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

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

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

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

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

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

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

Определение 4

Комбинаторика – раздел математики, предметом исследования которого являются комбинации, составленные из заданных объектов по определенным условиям, и их количество.

«Разработка оптимальных маршрутов следования» 👇
Помощь эксперта по теме работы
Найти эксперта
Решение задач от ИИ за 2 минуты
Решить задачу
Найди решение своей задачи среди 1 000 000 ответов
Найти

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • отбирают особей для производства потомства в зависимости от их приспособленности,
  • промежуточную популяцию разбивают на пары и скрещивают,
  • полученное поколение подвергают мутации.
Дата последнего обновления статьи: 07.02.2024
Найди решение своей задачи среди 1 000 000 ответов
Крупнейшая русскоязычная библиотека студенческих решенных задач
Все самое важное и интересное в Telegram

Все сервисы Справочника в твоем телефоне! Просто напиши Боту, что ты ищешь и он быстро найдет нужную статью, лекцию или пособие для тебя!

Перейти в Telegram Bot