Задача маршрутизации - Математические модели, используемые в системе оптимизации доставки товаров автотранспортом
Задача маршрутизации реализуется набором алгоритмов, каждый из которых осуществляет решение задачи коммивояжера. Коммивояжер (распространитель товаров) должен объехать всех получателей товаров внутри одной зоны обслуживания. Он выезжает из некоторого пункта и должен вернуться в него же в конце путешествия. Предполагается, что коммивояжер никогда не бывает дважды в одном пункте. Расстояния между получателями товаров задаются с помощью квадратной матрицы расстояний С = [С(i, j)] размерности K x K, где K - количество получателей товаров, С(i, j) - расстояние от получателя i до получателя j. Отметим, что, в общем случае, матрица расстояний не является симметричной. Диагональные элементы матрицы расстояний равны нулю.
Задача коммивояжера состоит в таком объезде всех получателей, чтобы суммарное пройденное расстояние было минимальным. Следует выбрать один оптимальный маршрут из (K-1)! возможных.
Если количество получателей невелико: (K < 13), то решение может быть получено с использованием простого Метода перебора.
С ростом размерности задачи (13 ? K ? 15), целесообразно использовать Метод ветвей и границ. Другое название этого же метода - Метод поиска по дереву решений. Опишем основные шаги решения задачи коммивояжера этим методом. Вначале находится некоторое допустимое решение (допустимый маршрут). После этого на каждом шаге поиска оптимального решения множество всех оставшихся маршрутов разбивается на два подмножества. В первое подмножество включаются те маршруты, которые содержат некоторую выделенную дугу, во второе подмножество включаются те решения, которые эту выделенную дугу не содержат. Для каждого подмножества вычисляется нижняя граница стоимостей всех решений, вырастающих из этого подмножества. С помощью найденных границ проводят дальнейшее разбиение подмножеств допустимых маршрутов. Алгоритм метода возвращается всякий раз, когда стоимость текущего частичного решения равняется или превосходит стоимость лучшего решения, найденного до сих пор. В конечном итоге остается один из оптимальных маршрутов. Отметим, что в некоторых задачах при использовании метода ветвей и границ объем вычислений может оказаться близким к объему вычислений методом перебора. маршрутизация сообщение множество регион
Для задач бульшей размерности (K > 15) метод ветвей и границ становится неприемлемым. В этом случае наиболее эффективным оказывается Метод имитации отжига, основанный на аналогии с физическими эффектами, возникающими при охлаждении расплавленных металлов. При быстром охлаждении расплава последний обычно затвердевает, приобретая аморфные структуры расположения отдельных атомов. Эта неупорядоченная структура представляет собой одно из метастабильных состояний с локальным минимумом энергии. Однако перевести систему из расплава в кристаллическое состояние все же можно, если воспользоваться техникой отжига, заключающейся в очень медленном охлаждении системы с течением времени.
Алгоритм метода имитации отжига применительно к задаче коммивояжера [3] состоит в построении последовательности укорачивающихся допустимых маршрутов с использованием локализованных мутаций, затрагивающих ровно два произвольно взятых пункта объезда. Пусть - некоторый допустимый маршрут протяженности. Мутация, затрагивающая пункты и, заключается в том, что и меняются местами в последовательности объезда. Она приводит к новому маршруту протяженности. Обозначим. В соответствии с алгоритмом метода имитации отжига результат мутации безоговорочно принимается, если она привела к сокращению протяженности маршрута: . Результат мутации принимается с некоторой вероятностью, если в результате мутации протяженность маршрута не уменьшилась: . Если мутация принята, то новый маршрут используется в качестве нового допустимого маршрута. Если же мутация отвергается, то допустимый маршрут остается прежним. Построение последовательности маршрутов продолжается до тех пор, пока протяженности маршрутов уменьшаются. Имитация отжига заключается в том, что значение параметра Н, играющего роль температуры, от мутации к мутации уменьшается и стремится к нулю. Подбирая подходящую скорость уменьшения температуры, можно добиться того, что последовательность допустимых маршрутов будет стремиться к оптимальному маршруту.
Отметим, что метод имитации отжига позволяет найти лишь приближенное решение. Вопрос: на сколько найденное приближенное решение близко к оптимальному, остается открытым.
В некоторых случаях достаточно эффективным оказывается приближенный, так называемый "хитро-жадный" метод. Этот метод является "усеченным" вариантом метода ветвей и границ. Отличие "хитро-жадного" метода от метода ветвей и границ состоит в том, что после проверок небольшого количества ветвей (жадность), содержащих наиболее короткие дуги графа (хитрость), вычисления прекращаются, и в качестве решения выбирается наилучшее решение, найденное к настоящему моменту.
В ряде случаев эффективными оказываются популярные в настоящее время адаптивно поисковые алгоритмы, основанные на эволюционных факторах получения решения, - Генетические алгоритмы [4].
Похожие статьи
-
В работе рассматривается задача нахождения маршрутов развоза товаров на объекты заданного региона, возникающая у компаний, желающих сократить...
-
Для заданного региона обслуживания с помощью технологии ГИС предоставляется карта автомобильных дорог, на которой указаны пункты, соответствующие...
-
Система "Диспетчер" апробирована на реальных исходных данных двух регионов Нефтяной Компании "Юкос" (Липецкая и Воронежская области) и показала свою...
-
Основные результаты работы состоят в следующем: 1. Рассмотрены математические модели, лежащие в основе системы оптимизации доставки товаров...
-
Задача кластеризации реализуется набором методов (алгоритмов), каждый из которых осуществляет разбиения региона на компактные зоны обслуживания. Аппарат...
-
Подход к постановке задачи аналогичен предыдущему, но в качестве исходной модели рассматривается матрица инциденций Q = [ Q (i, j)]. Столбцам матрицы...
-
При управлении подвижными объектами (такими, например, как мобильные роботы, подводные аппараты и т. п.) часто имеет место неопределенность цели, когда...
-
Задача кластеризации может быть сведена к задаче раскраски вершин графа. Для этого строится граф несовместимости. Вершинам графа соответствуют...
-
Математическая модель задачи нелинейного программирования (ЗНП) (*) Для ЗНП в отличие от Задачи Линейного Программирования (ЗЛП) нет единого метода...
-
Важнейшие математические модели обычно обладают важным свойством Универсальности : принципиально разные реальные явления могут описываться одной и той же...
-
На основании вышеприведенных обозначений сформулируем математическую модель задачи оптимизации графиков занятости работников с многосменной организацией...
-
Для обеспечения бесперебойной и эффективной работы некоторых предприятий, работающих в условиях неравномерной нагрузки, важное значение имеет оптимальный...
-
Основные понятия теории экономико-математического моделирования Кибернетический подход к исследованию экономико-математических систем Обычно...
-
Условие задачи. Пусть имеются n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами CIj (i, j = 1,2,..., n)....
-
1. Цыпкин, Я. З. Частотные критерии робастной модальной линейных дискретных систем / Я. З. Цыпкин, Б. Т. Поляк // Автоматика.-1990. - № 5. - С.4-11. 2....
-
Геометрическая интерпретация - Математические методы и модели в экономике
Геометрическая интерпретация задачи линейного программирования является основой графического метода и применяется в основном при решении задач двумерного...
-
Модель "вход - выход" для нестационарной системы управления можно представить в следующем виде [2] . Где коэффициенты матриц возмущения и ограничены...
-
В большинстве случаев структурная неопределенность вызвана неполнотой знания аналитической структуры уравнений модели объекта управления. При не...
-
К числу приближенных методов оптимизации задач календарного планирования относятся: частичный и направленный перебор, метод Монте-Карло,...
-
Оптимальное решение модели. - Методика решения задачи целочисленного программирования
Рис. 1 Шаг 1. Исходную задачу 1 заносим в дерево задач. В качестве исходного допустимого решения берем: x1=x2=x3=0. Соответствующее значение целевой...
-
Все генетические алгоритмы участвовали в двух группах тестов. В каждой группе исследовались различные наборы значений управляющих параметров МГА:...
-
Решение транспортной задачи методом потенциалов - Математическая модель решения транспортной задачи
Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями...
-
Задачи, связанные с поиском гамильтоновых циклов - Гамильтоновы циклы
В ряде отраслей промышленности возникает следующая задача планирования. Нужно произвести n продуктов, используя единственный тип аппаратуры. Аппарат...
-
Классификация по типу задач. - Виды моделей
Описательные (дескриптивные) модели (к ним часто приводят, постановки задач типа. А) предназначены для описания изучаемого процесса, объяснения...
-
В практике управления системами различного назначения (экономическими, финансовыми, техническими и др.) неизбежно приходится сталкиваться с различными...
-
Оптимизация инвестиционного портфеля (ИП) [Дубровин и др., 2008], [Мищенко и др., 2002], [Серов, 2000] является одной из важных экономических задач,...
-
Реализуем математическую модель (2) (6) в MS Excel. Для этой цели построим таблицы исходных данных задачи по расчету оптимального графика занятости при...
-
Необходимость введения нового ограничения может возникнуть, например, когда первоначально для сокращения затрат машинного времени некоторые интуитивно...
-
Сначала обсудим один из широко применяемых методов кластер-анализа - с метода k-средних. Он предназначен для разбиения исходного множества элементов...
-
Календарный производственный программирование однооперационный Все существующие методы решения задач календарного планирования3 по степени достижения...
-
Пусть ограничения (4) не противоречивы, т. е. не пусто множество допустимых решений, а оптимальное решение достигается я в точке для каждой K -ой...
-
Теоретическое обоснование математического моделирования - Математические методы и модели в экономике
Коммерческая деятельность в том или ином виде сводится к решению таких задач: как распорядиться имеющимися ресурсами для достижения наибольшей выгоды или...
-
Решение задачи графическим методом - Математическое моделирование в менеджменте и маркетинге
Необходимо найти максимальное значение целевой функции L(x)= 2x1+2x2 > max, при системе ограничений: 6x1+8x2?48, (1) 8x1+11x2?88, (2)...
-
Модель сети с обратным распространением - Прогнозирующие системы
Способом обратного распространения (back propogation) называется способ обучения многослойных НС. В таких НС связи между собой имеют только соседние...
-
Модель Мальтуса Скорость роста пропорциональна текущему размеру популяции. Она описывается дифференциальным уравнением Где б -- некоторый параметр,...
-
В данном случае анализируемые системы характеризуются не одним набором показателей эффективности, а несколькими: (18) Где - группа показателей...
-
Наша группа работала над учебным межпредметным проектом "Математические модели в рыночной экономике". Мы покажем применение в экономике систем уравнений....
-
Постановка задачи За сельскохозяйственной артелью "Горизонт" закреплено 3 890 га сельскохозяйственных угодий, в том числе 3406 га пашни, 389 га сенокосов...
-
С целью формализации задачи введем необходимые обозначения: I - код изделия (i = 1,...,n); ХI - искомый объем выпуска годовой программы по i-му изделию;...
-
Экономико-математические методы представляют собой совокупность математических методов (математического программирования, теории вероятностей, теории...
Задача маршрутизации - Математические модели, используемые в системе оптимизации доставки товаров автотранспортом