Объем рынка транспортно-логистических услуг растет во всем мире, и в связи с этим решение различных задач маршрутизации становится все более актуальной проблемой. Основной целью в данных задачах является построение маршрутов для транспортных средств, обслуживающих определенное множество клиентов. При этом выбор неудачного маршрута влечёт за собой дополнительные издержки по транспортировке товара.
Класс задач маршрутизации в настоящее время является очень широким. Распространённым и самым ранним примером является задача коммивояжера или задача TSP (Travelling Salesman Problem). Для исследования была выбрана задача коммивояжера, зависящая от времени или задача TDTSP (Times Dependent Travelling Salesman Problem).
Алгоритмы, решающие данную задачу, разделяют на точные и эвристические. Так как задача коммивояжера принадлежит классу NP- трудных задач, очевидно, что точные алгоритмы применимы только для малоразмерных задач и не подходят для решения реальных задач. Поэтому, как правило, используют эвристические алгоритмы. Они генерируют решения, приближенные к оптимальному, но за меньшее по сравнению с точными методами время.
Особенностью многих эвристических алгоритмов является разнообразие решений, получаемых при применении алгоритма к одному и тому же примеру. Это обусловлено тем, что при построении маршрута различным вариантам продолжения маршрута соответствует вероятность их выбора, так как постоянный выбор наилучшего продолжения на каком-либо шаге алгоритма в итоге не всегда дает оптимальное решение. Ввиду больших расстояний, в рассматриваемых на практике задачах любое улучшение алгоритма позволит существенно уменьшить расхождение полученных решений с оптимальным.
В первой главе рассмотрены задачи TSP и TDTSP, представлены их математические модели. Во второй главе приведен обзор литературы по
природным алгоритмам и их сравнение. В третьей главе подробно рассмотрено применение муравьиного алгоритма (ACO) для построения решения задачи TDTSP. В четвертой дается определение динамической адаптации как критерия оценки алгоритмов и проведена оценка ACO. В пятой главе предложен метод динамической адаптации алгоритма, а так же его сравнение с ACO. В шестой главе описана проделанная работа и полученные результаты.
В работе была исследована одна из задач маршрутизации транспорта - динамическая задача коммивояжера. Были рассмотрены различные эвристические алгоритмы природного класса.
Подробно изучен, описан и реализован на языке программирования Java муравьиный алгоритм (ACO) для решения задачи TDTSP. Произведена оценка уровня динамической устойчивости решений, генерируемых данной эвристикой. Из-за того, что эвристики не обеспечивают получение оптимальных решений, но близких к ним, среднее значение этой величины для рассмотренных задач получилось равным 0,6504.
Принцип динамической адаптации показал, что любой алгоритм, который генерирует различные решения для одной и той же задачи, можно улучшить с помощью алгоритма динамической адаптации. Динамическая адаптация муравьиного алгоритма (DAACO) повысила уровень динамической устойчивости решений до 0,9608. Также среднее значение длины решений, сгенерированных алгоритмом DAACO, получилось меньше, чем классическим муравьиным алгоритмом. Средний процент улучшения решений равен 4%. Результаты экспериментов показали, что использование динамической адаптации муравьиного алгоритма будет эффективней, чем простого муравьиного алгоритма, за счет генерируемых маршрутов меньшей длины.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
