Статья

Название статьи МЕТАЭВРИСТИЧЕСКИЕ АЛГОРИТМЫ В АВТОМАТИЗИРОВАННЫХ СИСТЕМАХ УПРАВЛЕНИЯ ТЕХНОЛОГИЧЕСКИМИ ПРОЦЕССАМИ НА СОРТИРОВОЧНЫХ СТАНЦИЯХ
Автор А.Н. Шабельников
Рубрика РАЗДЕЛ III. БЕЗОПАСНОСТЬ СЛОЖНЫХ СИСТЕМ
Месяц, год 08, 2016
Индекс УДК 656.212.5
DOI 10.18522/2311-3103-2016-8-102114
Аннотация Разрабатывается новый метаэвристический подход к решению оптимизационных задач, связанных с управлением технологическими процессами на железнодорожных сортировочных станциях и горках. В основу предлагаемого подхода положен модифицирован-ный метод управляемого случайного поиска с запретами, рассматриваемый на примере задачи выбора оптимальной очередности расформирования составов, где требуется многокритериальная оптимизация, которая в настоящее время производится диспетчерским персоналом. В этой связи принимаемые решения не всегда являются оптимальными. В работе показано, что задача выбора оптимальной очередности роспуска состава может быть реализована по критерию минимизация суммарного простоя вагонов на сортировочной станции. При этом стоит отметить, что задача минимизации простоя может оказаться не тривиальной, если учитывать в расчётах доставку скоропортящихся грузов, т.е. наложить некоторый штраф за простой данных вагонов с целью своевременной доставки скоропортящихся грузов. Предлагаемый алгоритм осуществляет локальный поиск в пространстве решений с использованием поочередно применяемых процедур интенсификации и диверсификации поиска, основанных на адаптивном изменении параметра рандомизации окрестности. Кодирование и модификация решений осуществляются путем задания перестановок на множестве порядковых номеров подлежащих расформированию поездов. Рассматриваются результаты компьютерных экспериментов, проведенных с целью проверки эффективности предложенного подхода. Первая часть экспериментов направлена на выявления оптимальных параметров для разработанного поискового алгоритма. Во второй части при найденных оптимальных значениях параметров алгоритма были про-ведены эксперименты с имитационными моделями техпроцесса с целью оценки эффективности предлагаемого метода. Моделирование показало, что разработанный алгоритм позволяет получить более точные решения задачи по сравнению с жадными алгоритмами, используемыми в настоящее время в автоматизированных системах. В работе отмечается, что предложенный метаэвристический подход, основанный на использовании метода управляемого случайного поиска с запретами, применим также к решению многих практических задач, связанных с управлением технологическими процессами на сортировочных станциях и горках.

Скачать в PDF

Ключевые слова Метаэвристический алгоритм; кодирование решений; локальный поиск; окрестность решения; рандомизированная окрестность; расформирование состава; простой вагонов
Библиографический список 1. Долгий И.Д., Ковалев С.М., Криволапов С.В. Оптимизация графиков движения поездов на основе методов эволюционного моделирования // Интеллектуальные модели и мягкие вычисления в искусственном интеллекте: Сборник научных трудов 7-й Международной научно-технической конференции. – Коломна, 2013. В 3-х т. Т. 1. – С. 862-868.
2. Ковалев С.М. Тарасов В.Б. Проблемы развития интеллектуальных технологий на транс-порте и производстве // Автоматизация и механизация технологических процессов на сортировочных станциях: Труды Международной научно-практической конференции.
– М., 2010. – С. 68-72.
3. Ковалев С.М. Шабельников А.Н. Теоретические проблемы интеллектуализации транс-портных процессов // Автоматизация и механизация технологических процессов на сортировочных станциях: Труды Международной научно-практической конференции. – М., 2010. – С. 15-19.
4. Гершвальд А.С. Оптимальное управление процессами работы базовой станции опорного центра // Железные дороги мира. – 2002. – № 6.
5. Papadimitriou C.H. and Steiglitz K. Combinatorial Optimization – Algorithms and Complexity. – New York: Dover Publications, 1982.
6. Lawler E., Lenstra J.K., Rinnooy Kan A.H.G., and Shmoys D.B. The Travelling Salesman Problem. – New York: John Wiley & Sons, 1985.
7. Nemhauser G.L. and Wolsey A.L. Integer and Combinatorial Optimization. – New York: John Wiley & Sons, 1988.
8. Glover F. Future paths for integer programming and links to artificial intelligence // Computers & Operations Research. – 1986. – No. 131. – P. 533-549.
9. Glover F. and Kochenberger G., eds. Handbook of Metaheuristics. – Norwell: Kluwer Aca-demic Publishers, 2002.
10. Щербина О.А. Метаэвристические алгоритмы для задач комбинаторной оптимизации // Таврический вестник информатики и математики. – 2014. – № 1 (24). – C. 23-47.
11. Glover F. and Laguna M. Tabu Search. – Norwell: Kluwer Academic Publishers, 1997.
12. Osman I.H., Laporte G. Metaheuristics: a bibliography // Ann. Oper. Res. – 1996. – Vol. 63.
– P. 513-628.
13. Vob S. Tabu Search: Applications and Prospects // Network Optimization Problems / Du D.-Z. and Pardalos P., eds. – P. 333-353. – Singapor: World Scientific Publishing Co., 1993.
14. Кононов А.В., Кочетов А.В., Плясунов А.В. Конкурентные модели размещения производства // Журнал вычислительной математики и математической физики. – 2009. – Т. 49, № 6. – C. 1037-1054.
15. Кононова П.А., Кочетов Ю.А. Локальный поиск с чередующимися окрестностями для задачи Джонсона с пассивным буфером // Дискретный анализ и исследование операций. – 2012. – Т. 19, № 5. – С. 63-82.
16. Кочетов Ю.А. Вычислительные возможности локального поиска в комбинаторной оптимизации // Журнал вычислительной математики и математической физики. – 2008.
– Т. 48, № 5. – C. 747-764.
17. Кочетов Ю.А., Плясунов А.В. Генетический локальный поиск для задачи о разбиении графа на доли ограниченной мощности // Журнал вычислительной математики и математической физики. – 2012. – Т. 52, № 1. – С. 164-176.
18. Гладков Л.А., Курейчик В.В, Курейчик В.М. и др. Биоинспирированные методы в опти-мизации: монография. – М.: Физматлит, 2009. – 384 c.
19. Руднев А.С. Вероятностный поиск с запретами для задачи упаковки кругов и прямо-угольников в полосу // Дискретный анализ и исследование операций. – 2009. – Т. 16,
№ 4. – C. 61-86.
20. Борознов В.О. Построение модели для задачи о порядке роспуска составов на сортировочной железнодорожной станции // Вестник АГТУ. – 2012. – № 6. – C. 178-182.

Comments are closed.