Задача маршрутизации - Математические модели, используемые в системе оптимизации доставки товаров автотранспортом

Задача маршрутизации реализуется набором алгоритмов, каждый из которых осуществляет решение задачи коммивояжера. Коммивояжер (распространитель товаров) должен объехать всех получателей товаров внутри одной зоны обслуживания. Он выезжает из некоторого пункта и должен вернуться в него же в конце путешествия. Предполагается, что коммивояжер никогда не бывает дважды в одном пункте. Расстояния между получателями товаров задаются с помощью квадратной матрицы расстояний С = [С(i, j)] размерности K x K, где K - количество получателей товаров, С(i, j) - расстояние от получателя i до получателя j. Отметим, что, в общем случае, матрица расстояний не является симметричной. Диагональные элементы матрицы расстояний равны нулю.

Задача коммивояжера состоит в таком объезде всех получателей, чтобы суммарное пройденное расстояние было минимальным. Следует выбрать один оптимальный маршрут из (K-1)! возможных.

Если количество получателей невелико: (K < 13), то решение может быть получено с использованием простого Метода перебора.

С ростом размерности задачи (13 ? K ? 15), целесообразно использовать Метод ветвей и границ. Другое название этого же метода - Метод поиска по дереву решений. Опишем основные шаги решения задачи коммивояжера этим методом. Вначале находится некоторое допустимое решение (допустимый маршрут). После этого на каждом шаге поиска оптимального решения множество всех оставшихся маршрутов разбивается на два подмножества. В первое подмножество включаются те маршруты, которые содержат некоторую выделенную дугу, во второе подмножество включаются те решения, которые эту выделенную дугу не содержат. Для каждого подмножества вычисляется нижняя граница стоимостей всех решений, вырастающих из этого подмножества. С помощью найденных границ проводят дальнейшее разбиение подмножеств допустимых маршрутов. Алгоритм метода возвращается всякий раз, когда стоимость текущего частичного решения равняется или превосходит стоимость лучшего решения, найденного до сих пор. В конечном итоге остается один из оптимальных маршрутов. Отметим, что в некоторых задачах при использовании метода ветвей и границ объем вычислений может оказаться близким к объему вычислений методом перебора. маршрутизация сообщение множество регион

Для задач бульшей размерности (K > 15) метод ветвей и границ становится неприемлемым. В этом случае наиболее эффективным оказывается Метод имитации отжига, основанный на аналогии с физическими эффектами, возникающими при охлаждении расплавленных металлов. При быстром охлаждении расплава последний обычно затвердевает, приобретая аморфные структуры расположения отдельных атомов. Эта неупорядоченная структура представляет собой одно из метастабильных состояний с локальным минимумом энергии. Однако перевести систему из расплава в кристаллическое состояние все же можно, если воспользоваться техникой отжига, заключающейся в очень медленном охлаждении системы с течением времени.

Алгоритм метода имитации отжига применительно к задаче коммивояжера [3] состоит в построении последовательности укорачивающихся допустимых маршрутов с использованием локализованных мутаций, затрагивающих ровно два произвольно взятых пункта объезда. Пусть - некоторый допустимый маршрут протяженности. Мутация, затрагивающая пункты и, заключается в том, что и меняются местами в последовательности объезда. Она приводит к новому маршруту протяженности. Обозначим. В соответствии с алгоритмом метода имитации отжига результат мутации безоговорочно принимается, если она привела к сокращению протяженности маршрута: . Результат мутации принимается с некоторой вероятностью, если в результате мутации протяженность маршрута не уменьшилась: . Если мутация принята, то новый маршрут используется в качестве нового допустимого маршрута. Если же мутация отвергается, то допустимый маршрут остается прежним. Построение последовательности маршрутов продолжается до тех пор, пока протяженности маршрутов уменьшаются. Имитация отжига заключается в том, что значение параметра Н, играющего роль температуры, от мутации к мутации уменьшается и стремится к нулю. Подбирая подходящую скорость уменьшения температуры, можно добиться того, что последовательность допустимых маршрутов будет стремиться к оптимальному маршруту.

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

В некоторых случаях достаточно эффективным оказывается приближенный, так называемый "хитро-жадный" метод. Этот метод является "усеченным" вариантом метода ветвей и границ. Отличие "хитро-жадного" метода от метода ветвей и границ состоит в том, что после проверок небольшого количества ветвей (жадность), содержащих наиболее короткие дуги графа (хитрость), вычисления прекращаются, и в качестве решения выбирается наилучшее решение, найденное к настоящему моменту.

В ряде случаев эффективными оказываются популярные в настоящее время адаптивно поисковые алгоритмы, основанные на эволюционных факторах получения решения, - Генетические алгоритмы [4].

Похожие статьи




Задача маршрутизации - Математические модели, используемые в системе оптимизации доставки товаров автотранспортом

Предыдущая | Следующая