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

На правах рукописи

Казак Александр Александрович

МОДЕЛИРОВАНИЕ СЛОЖНЫХ ПРОЦЕССОВ ЖЕЛЕЗНОДОРОЖНОГО И АВТОМОБИЛЬНОГО ТРАНСПОРТА ПА ОСНОВЕ ИСПОЛЬЗОВАНИЯ ЗАДАЧИ КОММИВОЯЖЕРА

Специальность 05.13.18 — Математическое моделирование, численные

методы и комплексы программ

АВТОРЕФЕРАТ ДИССЕРТАЦИИ

НА СОИСКАНИЕ УЧЕНОЙ СТЕПЕНИ КАНДИДАТА ТЕХНИЧЕСКИХ НАУК

Ростов-на-Дону 2006

Работа выполнена на кафедре «Информатика» Государственного образовательного учреждения высшего профессионального образования «Ростовский государственный университет путей сообщения» (РГУПС)

Научный руководитель:

доктор технических наук, профессор Лябах Н.Н,

Официальные оппоненты:

доктор технических наук, профессор Ковалев С.М., кандидат технически* наук, доцеш Мермельштейн Г.Г.

Ведущая организация:

Таганрогский государствешшй радиотехнический университет.

Защита состоится « 28 » декабря 2006 г. в 12*00 часов в конференц-зале РГУПС на заседания диссертационного совета К 218.010.0t при Ростовском государственном университете путей сообщения (344038, г. Ростов-на-Дону, пл. Народного Ополчения, 2).

С диссертацией можно ознакомиться в библиотеке Ростовского государственного университета путей сообщения.

Автореферат разослан « 27 » ноября 2006 г. Отзывы на автореферат в двух экземплярах, заверенные печатью просим направлять по адресу: 344038, г. Ростов-на-Дону, пл. Народного ополчения, 2, РГУПС, диссертационный совет.

Ученый секретарь

диссертационного совета К 218.010.01 кандидат технических паук, доцент

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Астуальвостъ нсследооання. Коренные социально-экономические преобразования, осуществляемые в Российской Федерации в последние годы, отразились прежде всего на парадигме управления отраслями народного хозяйства на основе экономических критериев. Поскольку железнодорожный транспорт по-прежнему играет ключевую роль в экономике страны, приспособление его к новым методам хозяйствования в условиях рыночной системы является важной и своевременной задачей на современном этапе развития общества. В новых условиях хозяйствования значительно повышается роль иных видов транспорта, в том числе автомобильного, обеспечивающего перевозки на ограниченные расстояния и в ограниченных объемах.

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

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

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

В работе использованы труды таких авторов, разрабатывающих теорию графов и, в частности, задачу коммивояжера, как Ахо А„ Басакер Р., Белл-ман Р., Беллмор М., Белов В.В., Бсрж К., Голыптейн Е.Г., Гудман С., Евстигнеев В.А., Ерусалимский Я.М., Зыков A.A., Иванов Б.Н., КонвеЙ Р.В., Кристофи-дсс Н., Литл Дж., Майника Э., Новиков Ф.А., Ope О,, Пападмитриу X., Рейнгольд Э., Романовский И.В., Свами М, Сергиенко HB., У ял сок Р., Харари Ф.

Организация эксплуатационной работы на транспорте рассмотрена в трудах Буянова В.А., Зубкова В.Н., Кочнсва Ф.П., Мамаева ЭЛ., Мусиснко H.H., Осьшппша А.Т., Прилепина Е.В., Сапунова H.A., Сологуба Н.К., Смехова A.A., Сотникова И.Б., Сотникова Е.А., Тншкина EJVf., Угрюмова А.К., Шарова В.А., Эрлиха Н.В.

Общие вопросы теории систем, рассматриваемые в работ-е, изложены в труда Баранова Л.А., Бира Ст., Богданова A.A., Дружинина В.В., Ивннцкого

B.А., Мермельштейна Г.Г., Райбмана И.С, Растрилша Л.А., Саршшса Дж.

Вопросы управления сложными объектами на транспорте и в экономике,

поставлены и решались в трудах Иванченко В.Н., Лисеикова В.М., Лябаха H.H., Орлова А.И.

Частные вопросы, нашедшие отражение в диссертации, рассмотрены в работах Белявского Г.И., Берпгтейпа Л.С., Бутаховой М.А., Гуды А.Н., Ковалева

C.М., Улъшщцкого В.М., Шабельникова А.Н. и др.

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

- слабой адаптируемости этих подходов п методов к решению транспортных задач;

- не разработанности ряда теоретических и практических положений;

- отсутствия методик использования задачи коммивояжера на транспорте.

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

- выявление недостатков существующих методов решения задач оптимизации (в том числе маневровых передвижений на сортировочной станции и задачи развозки грузов автомобильным транспортом);

- обоснование выбора модели, формализующей задачу управления перевозками;

- разработка практических алгоритмов решения поставленных задач и программная нх реализация;

- применение предложенных моделей, разработанных алгоритмов и программного обеспечения для решения рада практических задач.

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

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

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

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

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

Чтобы обеспечить достижение поставленной цели необходимо решнгь следующие математические задачи:

- проанализировать возможности и условия применения задачи коммивояжера;

- развить задачу на случай нескольких агентов;

- разработать алгоритм решения задачи нескольких коммивояжеров;

- предложить методы решения проблемы многокритериахыюсти;

- учесть специфику железнодорожного и автомобильного транспорта;

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

- синтезировать методику использования математических формализмов и программно-математического обеспечения при решении практических задач на транспорте;

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

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

Теоретические исследования, проведенные в работе, апробировались ва имитационном эксперименте и на реальных задачах управления.

Научна» новизна состоит в следующем:

- разработана и обоснована обобщенная модель задачи коммивояжера для случая нескольких агентов и множества критериев, имеющая широкий спектр практических приложений в областях автоматизации управления технологическими процессами на транспорте;

- разработан новый метод решения предложенной задачи, основанный на идеях адаптивного случайного поиска, позволяющий получать квазиоптимальные решения за практически приемлемое время, что обеспечивает возможность его использования в системах оперативного управления;

~ с целью выявления точного минимума многоагентной задачи коммивояжера развиты метод полного перебора и метод ветвей и границ;

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

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

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

Теоретическая значимость работы состоит в развитии новых методов математического моделирования транспортных процессов, основанных на использовании современного аппарата теории графов (задача нескольких коммивояжеров).

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

Апробация работы. Основные положения диссертации и научные результаты исследования докладывались и обсуждались на заседаниях и семинарах кафедры «Информатика» Ростовского государственного университета путей сообщения (РГУПС); второй международной научно-практической конференции «Проблемы регионального управления, экономики, нрава и инновационных процессов в образовании», г. Таганрог, 2001 г.; на научно-теоретической конференции профессорско-преподавательского состава РГУПС «Транспорт-2002», г. Ростов-на-Дону, 2002 г.; научно-теоретической конференции профессорско-преподавательского состава «Транснорт-2003», г. Ростов-на-Дону, 2003 г.; всероссийской научно-практической конференции профессорско-преподавательского состава «Транспорт-2004», г. Ростов-на-Дону, 2004 г.; международной научной конференции «Актуальные проблемы развита транспорта России: стратегические, региональные, технические», посвященной 75-летию РГУПС, г. Ростов н/Д, 2004 г.; всероссийской научно-практической конференции «Транспорт-2005», г. Ростов-на-Дону, 2005 г.; всероссийской на-учно-практнческой конференции «Транспорт-2006», г. Ростов-на-Дону, 2006 г„ VII всероссийском симпозиуме по прикладной и промышленной математике, г. Москва, 2006 г.

Публикации, По результатам диссертационного исследования опубликовано 13 печатных работ общим объемом в 4,57 пл. (из них лично автору принадлежит 4,36 п л.), в том числе И без соавторов,

Внедрение результатов работы. Математическое обеспечение, предложенное в диссертации, внедрено в Ростовском филиале Российского научно-исследовательского и проектно-конструкгорского института информатизации, автоматизации н связи МПС России, в структурном подразделении администрации города Ростова-на-Дону муниципальном учреждении «Чистый город». Материалы диссертационного исследования были использованы для методических целей в учебном процессе РГУПС при проведении запятой по информаш-

ке (были написаны методические указания к практическим занятиям). Получены акты о внедрении.

Структура н объем работы. Диссертация состоит ю введения, четырех глав, содержащих 25 параграфов, заключения, библиографического списка и приложений. Основное содержание диссертации изложено на 148 страницах, содержит 60 рисунков и 4 таблицы. Библиографический список содержит 179 наименований отечественных я зарубежных источников.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе «Задача коммивояжера и ее модификации: описание, проблемы, пута решения» дана характеристика объекта исследования, перечислены задачи управления в рамках исследуемых оптимизационных задач, а также возможные мехзнизмы их решения, проведен анализ существующих подходов к решению рассматриваемых проблем.

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

Приведен авторский обзор методов решения задачи коммивояжера. Рассмотрены метод полного перебора, метод динамического программирования, представление задачи в терминах целочисленного линейного программирования, метод ветвей и границ эвристические подходы. Имеется также необходимый анализ применения методов, изложены их достоинства и недостатки.

Делается вывод, что традиционная постановка задачи не отражает многие практические случаи, поскольку технологические процессы на транспорте сложны и многоаспектны. Постановка задач оптимального управления ими требует одновременного учета значений нескольких параметров их функционирования ^, г = . Возникают вопросы согласования и оптимизации выделенных критериев. Описываются возможные механизмы учета многих критериев в задаче коммивояжера, такие, как свертаваняе критериев с некоторыми весовыми коэффициентами, оптимизация главного критерия Рт с наложением ограничений на остальные, Метод Парето, наложение ограничений на все критерии.

Указан существующий подход к решению задачи оптимизации маневровых передвижений на сортировочной станции. Задачу оптимизации маневровых передвижений можно сформулироватъ как задачу коммивояжера: маневровому локомотиву, находящемуся в вершине 1, необходимо побывать ровно один раз

в каждой из п — 1 других вершил графа (точек сортировочной станции, требующих маневров), и вернуться в исходную точку 1. Требуется найти такой порядок обхода вершин, при котором общее расстояние, пройденное локомотивом, будет минимальным.

При этом не в полной мере учтены характерные особенности функционирования современных транспортных систем:

1. Возможность несовпадения начального и конечного пунктов движения транспортного средства. По окончании работы локомотив должен прибыть в точку, предназначенную для отстоя локомотива (путь подгорочного парка, на который не осуществляется роспуск состава). В частном случае это может быть путь, с которого тепловоз начал свое движепие ~ тогда имеем задачу коммивояжера в ее классическом виде. Если тепловоз по окончании маневров должен занимать иную позицию, то мы имеем разомкнутую задачу коммивояжера.

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

3. Задача многокритериальна, причем требует одновременного учета многих критериев.

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

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

Вторая глава «Разработка модели нескольких коммивояжеров» посвящена математическому моделированию транспортных процессов на основе использования задачи коммивояжера, а именно развитию задачи коммивояжера па случай нескольких агентов. Имеется число .г - количество агентов, п - количество городов (г может быть меньше, больше, или равно п), полный граф С(Х,и}> связывающий все города и точки местонахождения коммивояжеров. Структура матрицы весов этого графа представлена па рис. 1. Множество X содержит п+2$ вершин, из них:

1. п небазовых вершин (где требуется побывать);

2. щ, / = 1,5 — точки начального местонахождения, базовые вершины;

3. Ь1г / = 1,5 — точки конечного местонахождения, базовые вершины.

Необходимо:

1. Определить количество коммивояжеров т.

2. Выбрать т конкретных агентов из 5 имеющихся.

3. Выделить на графе непересекающиеся маршруты движения выбранных коммивояжеров, в совокупности содержащие все небазовые вершины.

4. Добиться минимума критерия У качества решения:

где ¿х — сумма длин всех маршрутов в данном решении, — длина максимального маршрута, аг и а2 — показатели важности рассматриваемых критериев. Определение показателей важности производится посредством опроса Я экспертов. Если Я, экспертов считают нужным минимизировать а Я2 экспертов — минимизировать ( Я] + Я2 = Я), в качестве показателя ах следует

взять отношение —, а в качестве а2 взять —.

Я Я

] 0 ¿(1,2) ¿(1,3) ¿аа,) ¿оа) ¿а о2) ¿(1 А)

2 ¿(2,1) 0 ¿(2,3) ¿(2,«1) ¿(2А) ¿(2,^) ¿(2А)

3 ¿(3,1) ¿(3,2) 0 ¿(3,«1) ¿(ЗА) ¿(3,а2) ¿(ЗА)

а\ ¿(а„1) ¿(а, ,2) 0 ¿(«1>о2) ¿(^А)

¿1 ¿(¿,,1) ¿ф, 2) 3) 0 ¿(6„«2) ¿АА)

<ОагХ) ¿(л2,2) ¿0*2,3) ¿0*2, «1> ¿(а2Л) 0 ¿(а2А)

Ьг ¿(М) ¿(М) ¿№*А) 0

Рис. 1. Матрица весов графа задачи нескольких коммивояжеров при и = 3, .1 = 2; диагональные элементы полагаются равными нулю, либо бесконечности

Как известно, количество Р вариантов, подлежащих перебору в задаче коммивояжера, равно п\, или (и—1)!, в случае фиксации первоначального города. Подсчитываете» количество допустимых решений в сформулированной задаче нескольких коммивояжеров. Оно будет равно

С -п^у"'

В диссертации приводятся примеры роста данной величины.

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

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

Время работы метода полного перебора

Таблица1

1 ■ 2 3 4 5 6 7 8

6 0:00 0:00 0:00 0:00 0:00 0:00 0:00 0:01

7 0:00 0:00 0:00 0:00 0:01 0:04 0:10 0:22

8 0:00 0:00 0:01 0:07 0:22 1:02 2:32 5:34

9 0:00 0:03 0:20 1:27 5:02 14:52 - -

10 0:03 0:38 4:12 20:03 — - - -

И 0:38 7:48 - - - - - -

12 7:50 - - — — - — -

1 2 3 «1 ь, «2 Ьг

1 со 40 32 3 11 48 34

2 26 00 40 29 26 47 44

3 10 40 00 2 16 21 31

34 25 32 оо 12 23 4

Ь 22 2 39 40 во 7 45

аг 19 9 5 12 29 да 31

Ьг 49 31 48 17 4 21 оо

Рис. 2. Матрица весов конкретной задачи нескольких коммивояжеров

Решая этим методом задачу нескольких коммивояжеров (у = 2, л = 3) с матрицей иа рис. 2, приходим к следующему оптимальному решению:

2)03,3,1,62; ¿2 =49, Л =100, ./хв51../-510а

Далее рассмотрен разработанный метод, использующий деревья поиска, являющийся развитием метода ветвей и границ решения задачи коммивояжера. Пусть количество агентов равно т. Укажем, какие элементы матрицы следует запретить (положить равными бесконечности) и каким образом вычислять ннжние границы критерия качества.

1) Запрещаем элемешы главной диагонали матрицы, веса всех дуг графа, входящих в а( нвыходящихиз Ь,, элементы матрицы (а^ЬЛ, (,_/==!,т.

2) При добавлении звена (л.^) образуется путь от д к р:

-если и р^Ь^ /=, то запрещаем элемент (р, д);

— если д — и р = Ь1г ¿е1,/п, количество сформированных маршрутов / увеличиваем на единицу: / = /+1;

- просматриваем каждый меньший бесконечности элемент (х,^) текущей подматрицы. Запрещаем его, если т — / =1, а присоединение (х,х) дает путь между дяр, где д = р = Ь¡¡, (61, от, или если т — /> 1, а присоединение (х,у), дает путь между д нр, где д = а^ р=Ь}, 1,]е\,т, .

3) Вычисление нижних границ целевого функционала:

J^H,

J¿ —. т

т

Порядок работы метода:

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

2. м-!.

3. *«1.

4. Генерируем к-е сочетание из 5 по т.

5. Применяем метод ветвей и границ к задаче с т коммивояжерами. Бели получили решение ЯТ задачи со значением крнгерия качества, проверяем выполнение <J. Если это неравенство выполняется, то эталоном для сравнения становится новое решение Л = ЛГ, J~ 7Г.

л1

6. £ = £+1. Если к £ С" =-:-, переход к шагу 4.

7. т = т+\. Если т <, шт(1,п), переходим к шагу 3.

8. Выводим найденное решение К и значение крнгерия качества ./. Завершаем работу алгоритма

Таблица 2

S 1 2 3 4 5 б 7 8 9 10

п 61 50 40 30 25 21 19 17 16 16

Из таблицы 2 видно, что по сравнению с перебором всех вариантов метод значительно расширяет множество разрешимых за обозримое время задач.

Недостатки метода: множество разрешимых задач все же недостаточно велико; ненадежность, трудности с прогнозированием времени работы про* граммной реалшации; все значения минимгаируемых критериев, а также показатели важности и все элементы исходной матрицы должны быть строго неотрицательными; проблемы с развитием метода на случай многих критериев наиболее общего вида, других свертывающих зависимостей, учетом возможных ограничений, которые могут быть введены tía множестве значений целевого функционала и множестве допустимых решений задачи.

Ход работы метода продемонстрирован на том же примере, который решался при рассмотрении метода полного перебора.

Описан разработанный эвристический алгоритм, представляющий собой совокупность пяти эвристик.

1. Составляем произвольное решение Д задачи нескольких коммивояжеров — начальное приближение оптимального решения.

2. Полагаем номер итерации к равным 0.

3. Начало итерационного процесса Если к < ШгНит, то к~к + \. Иначе, когда в течение Лел№»п итераций улучшепия решения не произошло, переход к шагу 11.

4. С вероятностью 1/2 формируем новое решение задачи, либо улучшаем ранее полученное. Генерируем вероятность — случайное число Р1 в интервале (0,1). Если Р] >0,5, переходим к шагу 5 (формируем новое решение), иначе к шагу 7 (улучшаем имеющееся решение).

5. Случайным образом выбираем т5тш{я,1) коммивояжеров из 5 имеющихся и количество городов для каждого маршрута; т — текущее количество коммивояжеров. Генерируем случайную последовательность городов.

6. Генерируем случайное число Рг в интервале (0,1). Если Р2>0,7, применяем алгоритм № 1 (развитие метода ближайшего соседа). В противном случае используем модифицированный прием метода статистических испытаний решения задачи коммивояжера - формируем новое произвольное решение НТ задачи, используя данные, полученные на шаге 5. Переход к тагу 8.

7. Генерируем вероятность Р3. Если 0<1% < 0,3, то применяем алгоритм № 2; если 0,3 < Р3 £ 0,6, применяется алгоритм № Иначе выполняется алгоритм № 4.

8. Подсчитываем длину каждого маршрута решения Лг, находим сумму длин, выделяем максимальную длину. Вычислят значение У7.

9. Сравниваемой Зт. Если 3 < О7, то к = 0, и эталоном для сравнения становится новое решение Ят: Д = Ит, J — В противном случае остается прежний эталон Я.

10. Переход к шагу 3.

11. Выводим результат — решение Я и значение критерия качества Jt заканчиваем работу алгоритма

Таблица 3

1 2 3 4 5

10 0 0 0 0 0

20 1,54 14,09 12,75 21,38 18,86

30 39.98 44,57 38,86 38,17 -

40 57,35 51,51 50.15 — —

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

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

ф*

V,-

7-1

Рис. 3. Иллюстрация работы алгоритма № 2

Рис. 4. Иллюстрация работы алгоритма № 3

«I

А^ = ,у|+1) - d{vl_l,vi) - ¿(у, ,у/+1)

Рис. 5. Иллюстрация работы алгоритма № 4

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

1. Минимизировать время проведения работ;

2. Минимизировать энергетические затраты;

3. Минимизировать общее пройденное локомотивами расстояние;

4. Минимизировать израсходованное количество горючесмазочных материалов;

5. Минимизировать стоимость проведения работ;

6. Минимизировать количество используемых маневровых локомотивов;

7. Минимизировать потери от боя вагонов и грузов;

8. Максимизировать безопасность движения;

9. Максимизировать надежность (вероятность безотказной работы).

В свете решения многокритериальной задачи нескольких коммивояжеров рассмотрены различные методы решения многокритериальных задач. Обозначим через А/множество решений задачи нескольких коммивояжеров, Ы— количество частных критериев, — к-й частный критерий (его числовое значение),

рк — показатель важности к-го критерия, Д г 0, к « I, N. Через {х^ будем обозначать матрицу весов графа, посредством суммирования определенных элементов которой производится подсчет числового значения частного критерия к = Без потери общности можно считать, что все критерии требуют минимизации.

1. Метод свертывания критериев. Обобщенная составляющая Г, подлежащая минимизации, может иметь вид:

-= шах (ДЛ).либо гаах {рР*); НЛО* *

2. Свертывание элементов матриц к = \,Ы.

N

- у» = ; *=1

= Ж^Ф- итУ9т тах{(4)А};

Г

3. Ранжирование критериев и метод уступок. Располагаем критерии в порядке убывания важности: Р2>... , Р^.

М1 = ДО е М,РХ{К) = /г,0"1), М2 = {К| Л е ММН) = Р^}, и т.д. Решение, доставляющее минимум последнему критерию Р^ па

множестве принимается за искомое.

Метод уступок:

= А/2 = {Я| Д е Л/,, Рг(К) £ +е2} и

т.д.

4. Выделение главного критерия Рт:

Минимизируется только один критерий Рт, на остальные накладываются ограничения.

5. Метод Парето. Оптимум Парето Ка характеризуется тем, что не существует решения :

Fif.Rn) ^ / = , причем Р1{КИ)<Р^КП) хотя бы для одного

6. Метод введения внешнего критерия. Накладываем ограничения на все критерии, В результате получим области £>* точек, допустимых по каждому критерию в отдельности.

* = ЛеД/ -»• О = С0к,к = ^ или = к-Т^.

Выделяем граничные точки £)д: РЦ? <.Рк{К)-&Р% и внутренние точки

Обозначим Ок — множество внутренних точек множество граничных - 0'кр, Щ и = Вк. В" - множество внутренних точек О, В*? — множество граничных точек В. Разработаны метод полного перебора и эвристический алгоритм нахождения областей £3^, Вк, В", Вф и В.

На множестве допустимых решений О вводится внешний критерий - требование максимальной надежности функционирования системы. Другими словами, в £> следует выбирать точку, удовлетворяющую заданному критерию, обеспечивающему максимальный запас работоспособности. Оптимальным будем считать решение И<явя, которое минимизирует вероятность выхода за пределы множества допустимых решений при возможных отклонениях в работе системы, то есть максимально отстоит от определяемых статистическим либо экспертным путем, и потому ненадежных, заданных с ошибками границ облаете Л Возможные виды внешнего критерия: центр области £>:

медиана области ¡У. Rg,^ =argmax

R Rip

Выбор одного из двух предложенных оптимумов осуществляется Е экспертами на основе дополнительной информации, регламентирующей требования к функционированию исследуемой системы. Если Е1 экспертов высказались в пользу поиска центра, а Е2 — за поиск медианы, берем свертку внешних

критериев с коэффициентами и Щ- соответственно.

Е Е

Медиана без выделения граничных точек:

' J

Проанализирована возможность применения каждого метода для решения обобщенной многокритериальной задачи нескольких коммивояжеров. Указаны недостатки методов. Для корректной их работы необходимо ввести метрику на множестве допустимых решений задачи нескольких коммивояжеров. С этой целью рассматриваются множества различных комбинаторных объектов, и вводится понятие расстояния на каждом ю них.

1. Множество всех перестановок п чисел Р. Метрикой на нем является величина рР(х,у), равная минимальному количеству транспозиций, переводящих одну перестановку в другую:

дК2,3,1,4),1,3,4); рР(х,у) = 1.

2. Множество С сочетаний из « по к. Если л.^еС.то

Pc (*. ¿О =

3. Множество F размещений из п по к. Расстояние между элементами * ну, где x = {xl,x2,...,xli)çv, У = (У1,У2>—>Ую)£У вычисляется следующим образом:

4. Множество W разбиений множества чисел патуралыгого ряда от 1 до п. При x,yeW имеем:

Î6I IНУ Î«

5. Множество M решений задачи нескольких коммивояжеров. Доказывается, что для элементов х, у е M расстояние между ними может быть найдено по формуле:

Рм (*> У) = >?ах min ру (£,/?) + шах min ру (g, ij).

fe* П€у ijey iei

Глава четыре «Использование разработанных методов при моделировании специфических транспортных процессов» посвящена применению разработанных методов и подходов для решения различных прикладных вопросов. Рассматривается пример использования задачи нескольких коммивояжеров при нормализации результатов роспуска составов на сортировочной горке. На рисунках 6, 7, S и 9 схематично изображен пример ситуации, которая могла бы возникнуть в подгорочном парке. Здесь удобно воспользоваться следующей

терминологией. Прописной буквой «П» с номером обозначены подгорочные пути. Точки, требующие маневра, обозначены буквой «М» с указанием имени пути, на котором должен находиться данный вагон (на рисунках б, 7, S и 9 эти вагоны заштрихованы). Точки расположения маневровых локомотивов обозначаются буквой «Л» плюс имя того пути, где должен находиться данный локомотив по окончании работы. Условно делим все участки станции, которые нужно посетить для выполнения маневров, на два типа Назовем участок х точкой 1-го типа, если локомотив, после прибытия туда и выполнения маневра, находится приблизительно в той же точке х. К таким точкам относятся в основном «окна». Будем называть участок х точкой 2-го тина, когда после прибытия в х, локомотив вынужден проехать некоторый отрезок пути, и выехать из другой точки у. Такая необходимость возникает благодаря «чужакам» и ситуациям «нет прохода». В нашем примере точки, требующие обслуживания, на путях ГО и П5 отнесем к точкам 1-го типа, остальные — к точкам второго типа.

Используя предложенные схемы, формируем исходный граф задачи нескольких коммивояжеров.

Рис. 7. «Чужаки» на пути П6; «окно» па пути П5

гГК

Рис. 8. Маневровый локомотив на пути П4; «окна» на пути ПЗ

Приводимая ранее постановка задачи нескольких коммивояжеров предполагает полноту исходного графа, а сформированный нами граф полным, вообще говоря, не является. Данное обстоятельство приводит к необходимости преобразования исходного графа задачи к полному графу. Показано, каким образом следует производить данное преобразование, используя алгоритм Флой-да

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

где И? - вычисляемая длина пути от точки х до точки у;

Ц^ — кратчайшее расстояние от х до г;

— кратчайшее расстояние от г до у,

К(г, у) - коэффициент загруженности на участке пути от г до у.

Так как локомотивы, вообще говоря, начинают работу не одновременно, нами задается время старта каждого локомотива и модифи-

цируется формула вычисления длины /-го маршрута для каждого (':

г' Г^ I р

¿'новое 4 ^евщюе •

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

Вычислим время прибытия в каждую точку маршрутов по формуле:

Особое значение имеют величины Ти - так обозначается момеш посещения одним из локомотивов участка станции и, где нужно побывать для выполнения маневра. Все числа Тя находятся среди чисел Т^ ^. Если и и V—две вершины из графа приоритетов в обслуживании, и в точке и необходимо побывать раньше, чем в точке V, требуем выполнения Ти<Т„, или хотя бы

Введены дополнительные критерии качества решения задачи нескольких коммивояжеров, обеспечивающие максимум надежности и безопасности маневровых работ на станции. Это критерий ,)3, минимизирующий общее количество пересечений маршрутов локомотивов, и критерий 3А, не дающий локомотивам одновременно находиться в одной точке, что препятствует возникновению {(пробок» и крушений. Показано, как подсчитывать значепия этих новых критериев, а также результирующего критерия. Критерий -/3 включается в свертку с показателем важности аъ; требуем, чтобы значение «/4 было не менее некоторой, наперед заданной пороговой величины Делается вывод: метод, использующий деревья поиска и комбинированный алгоритм, не могут быть развиты на случай указанной модификации модели нескольких коммивояжеров. В диссертации приводится иллюстративный материал.

Рассмотрена задача оптимального упорядочения обхода ребер ориентированного, неориентированного либо смешанного исходного графа. Ее решение указывает маршруты передвижения ремонтным бригадам, в том случае, когда им требуется осмотреть все участки пути на предмет неисправности, либо маршруты мусоровозов, в случае, когда мусор сосредоточен не в вершинах, а на ребрах графа Показано, каким образом при поиске минимума задачи оптимального упорядочения обхода ребер может быть использована предложенная задача нескольких коммивояжеров.

Проведены разработка и внедрение программно-математического обеспечения логистической системы «Чистый город». Муниципальное учреждение «Чистый город» — это структурное подразделение администрации города Ростова-на-Дону, на которое возложена функция обеспечения сбора, вывоза и ути-

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

Критерии эффективности функционирования логистической системы «Чистый города:

1. — время реализации функции по сбору мусора;

2. ~ стоимость процедуры.

Предлагается выделить зоны значений критериев (рис. 11).

Рис, П. Структура критериев: Н - норма, не требующая корректировки; П - предаварийная ситуация, требует мер по вхождению в область Н; Л - аварийный режим

ЦПР — центр принятия решений, ГИБДД — городская инспекция безопасности дорожного движения, ЖКХ - жилищно-коммунальное хозяйство. Объекты исследования: О—точки сбора мусора; X—точки накопления; О — точки старта и финиша транспорта перевозки

Система учитывает:

— вероятностные законы распределения накопления отходов в точках сбора;

-объемы контейнеров в точках сбора;

— режим вывоза (например, по санитарным нормам);

— количество и грузоподъемность (объемы) транспортных средств;

— маршруты и их загрузка в течение дня;

— экономические показатели: стоимость эксплуатации технических средств, затрат на сопровождение системы и пр.

Математический аппарат предусматривает возможность изменения:

—топологии расположения точек системы;

— структуры разрешенных маршрутов;

— количества и грузоподъемности транспортных средств;

— некоторых других параметров процесса: условия вывоза (санитарные) и прочие.

Схема фушсционироваты:

— операторы, вывозящие мусор, обеспеченные средствами мобильной связи, получают в начале смены своей работы маршрутные листы;

— исполняя заложен! пай в маршрутных листах план, они сообщают диспетчеру об изменениях в системе (ноломка средств, закрытие маршрутов, изменения в точках сбора и сдачи мусора и т.д.);

— диспетчер, связываясь с муниципальными органами, ГИБДД вводит дополнительные ограничения;

— в начале смены выше указанные условия вводятся в программу «Рзечет оптимальной схемы развоза груза»;

— расчетная система выдает вариант оптимального решения;

— полученное решение выдается следующей смене операторов (см. первый пункт алгоритма).

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

1. С целью построения адекватных математических моделей возникающих практических задач произведена разработка задачи коммивояжера на случай нескольких агентов с использованием теории графов; доказана возможность и необходимость моделирования сложных транспортных процессов с по* мощью задачи нескольких коммивояжеров.

2. Известные точные и приближенные методы поиска оптимума задачи коммивояжера (метод полного перебора, ветвей н границ, эвристические подхода) развиты для нахождения оптимального плана предложенной задачи нескольких коммивояжеров. Разработан специальный метод ее решения, основанный на идеях адаптивного случайного поиска. Указана область применения, изложены достоинства и недостатки полученных алгоритмов. Приведены конкретные численные примеры работы алгоритмов.

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

пертных оценок. Определена формула вычисления расстояния на множестве всех допустимых решений задачи.

4. Предложено формализованное представление задачи нормализации результатов роспуска на сортировочной станции и процедуры вывоза твердых отходов, осуществляемой МУ «Чистый город», на основе разработанной теоретико-графовой модели. Задача нескольких коммивояжеров развита на случай, когда каждое транспортное средство имеет определенную грузоподъемность, а для каждого участка сети (вершины или ребра смешанного графа) известно, сколько единиц подлежащего перевозке груза там находится. При таком рассмотрении не все решения многоэтапной задачи будут допустимыми в смысле новой ее постановки. Показано, каким образом в процессе работы модифицированных методов ее решения следует отбрасывать недопустимые наборы маршрутов.

5. Разработан комплекс программ на ЭВМ, реализующих предложенные методы и подходы, а в частности редактор графов, облегчающий создание и редактирование исходных данных оптимизационных задач на графах.

Результаты диссертационного исследования опубликованы в следующих работах:

1. Казак A.A. Применение усовершенствованной задачи коммивояжера для решения экономических задач // П Международная научно-практическая конференция «Проблемы регионального управления, экономики, права в инновационных процессов в образовании». — Таганрог: Изд-во ТИУиЭ, 2001. — С. 56-57.

2. Лябах RH., Казак А^А. Применение и развитие задачи коммивояжера для решения технологических задач на железнодорожном транспорте // Вестник РГУПС №1. -Ростов н/Д: Изд-во РГУПС, 2002. - С. 141-143.

3. Казак A.A. Разработка алгоритмов для задач типа коммивояжера, учитывающих особенности применения на железных дорогах П Труды научно-теоретической конференции профессорско-преподавательского состава «Транспорт-2002», часть 1. - Ростов и/Д: Изд-во РГУПС, 2002. -С. 51-52.

4. Казак A.A. Анализ подходов к решению задачи нескольких коммивояжеров Н Научная мысль Кавказа № 3. - Ростов н/Д : Изд-во СКНЦ, 2002. - С. 91-94.

5. Казак A.A. Примеры задач железнодорожного транспорта, приводящих к нахождению центров и медиан в графах // Труды научно-теоретической конференции профессорско-преподавательского состава «Транспорт-2003», часть I. -Ростов и/Д: Изд-во РГУПС, 2003. - С. 38-39.

6. Казак A.A. Организация маневровой работы на сортировочной станции // Труды всероссийской научно-практической конференции профессорско-преподавательского состава «Транспорт-2004», часть 1. — Ростов н/Д : Изд-во РГУПС, 2004. -С. 42-43.

7. Лябах Н.Н, Казак A.A. Пути решения задачи коммивояжера в много* критериальной постановке // Труда международной научной конференции

«Актуальные проблемы развития транспорта России: стратегические, региональные, технические», посвященной 75-летию РГУПС. - Ростов н/Д : Изд-во РГУПС, 2004,-С. 81.

8. Казак A.A. Метод полного перебора для решения задачи нескольких коммивояжеров // Изв. вузов. Северо-Кавказский регион. Технические науки. Приложение №1. - Новочеркасск: Изд-во ЮРГТУ (ИЛИ), 2005. - С. 56-61.

9. Казак A.A. Разработка метода решения одной задачи маршрутизации на транспортной сети // Труды Всероссийской научно-практической конференции «Транспорт-2005», часть 1. -Ростов н/Д: Изд-во РГУПС, 2005. -С, 98-100.

10. Казак АЛ. Эвристический алгоритм решения задачи нахождения оптимальных маршрутов нескольким транспортным средствам / Актуальные проблемы развития железнодорожного транспорта: сб. научн. тр. молодых ученых, аспирантов и докторантов под ред. д-ра техн. наук, проф. А.Н. Гуды. - Ростов н/Д: Изд-во РГУПС, 2005. - С. 54-59.

11. Казак A.A. Формирование исходных данных оптимизационных задач на графах // Труда Всероссийской научно-практической конференции «Транс-патгг-2006», часть 3. - Ростов н/Д: Изд-во РГУПС, 2006. - С. 256-257.

12. Казак A.A. Задачи поиска кратчайших транспортных маршрутов и методы их решения : методические указания к практическим занятиям. - Ростов н/Д: Изд-во РГУПС, 2006. - 36 с.

13. Казак A.A. Разработка н внедрение логистической системы «Чистый город» / Обозрение прикладной и промышленной математики. Т. 13, вып. 2. -М., 2006. — С. 101-102.

Казак Александр Александрович

МОДЕЛИРОВАНИЕ СЛОЖНЫХ ПРОЦЕССОВ ЖЕЛЕЗНОДОРОЖНОГО И АВТОМОБИЛЬНОГО ТРАНСПОРТА НА ОСНОВЕ ИСПОЛЬЗОВАНИЯ ЗАДАЧИ КОММИВОЯЖЕРА

Автореферат диссертации на соискание ученой степени кандидата технических наук

Подписано в печать 24.11.06. Формат 60x84/16. Бумага офсетная. Печать офсстпая. Усл. печ. л.1,0. Тираж 100 экз. Заказ №5055.

Ростовский государственный университет путей сообщения. Ризография РГУПС.

Адрес университета: 344038, г. Ростов-на-Дону,

пл. им. Ростовского Стрелкового Полка Народного Ополчения, 2.

СОДЕРЖАНИЕ.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.

1 ЗАДАЧА КОММИВОЯЖЕРА И ЕЕ МОДИФИКАЦИИ: ОПИСАНИЕ, ПРОБЛЕМЫ, ПУТИ РЕШЕНИЯ.

1.1 Характеристика объекта исследования.

1.1.1 Роль и место задачи коммивояжера в совершенствовании транспортных процессов.

1.1.2 Постановка задач управления в рамках исследуемых оптимизационных задач.

1.2 Обзор методов решения задачи коммивояжёра.

1.3 Возможные механизмы учета многих критериев в задаче коммивояжера.

1.4 Существующий подход к решению задачи оптимизации маневровых передвижений на сортировочной станции.

1.5 Постановка задач диссертационной работы.

1.6 Выводы.

2 РАЗРАБОТКА МОДЕЛИ НЕСКОЛЬКИХ КОММИВОЯЖЕРОВ.

2.1 Определение модели нескольких коммивояжеров с использованием теории графов.

2.2 Метод полного перебора.

2.3 Метод решения, использующий деревья поиска.

2.4 Эвристический алгоритм.

2.5 Комбинированный алгоритм.

2.6 Выводы.

3 ПУТИ РЕШЕНИЯ ЗАДАЧИ НЕСКОЛЬКИХ КОММИВОЯЖЕРОВ В МНОГОКРИТЕРИАЛЬНОЙ ПОСТАНОВКЕ.

3.1 Постановка вопроса.

3.2 Сведение многокритериальной задачи к однокритериальной.

3.3 Многокритериальный подход решения задачи нескольких коммивояжеров.

3.4 Мера близости комбинаторных объектов.

3.5 Выводы.

4 ИСПОЛЬЗОВАНИЕ РАЗРАБОТАННЫХ МЕТОДОВ ПРИ МОДЕЛИРОВАНИИ СПЕЦИФИЧЕСКИХ ТРАНСПОРТНЫХ ПРОЦЕССОВ.

4.1 Предварительное преобразование исходного графа.

4.2 Разработка редактора графов.

4.3 Учет специфики железнодорожного транспорта.

4.4 Задачи автомобильного транспорта.

4.4.1 Перевозка заданного количества груза.

4.4.2 Разработка и внедрение логистической системы «Чистый город»

4.5 Оптимальное упорядочение ребер графа.

4.6 Выводы.

Актуальность исследования. Коренные социально-экономические преобразования, осуществляемые в Российской Федерации в последние годы, отразились прежде всего на парадигме управления отраслями народного хозяйства на основе экономических критериев. Поскольку железнодорожный транспорт по-прежнему играет ключевую роль в экономике страны, приспособление его к новым методам хозяйствования в условиях рыночной системы является важной и своевременной задачей на современном этапе развития общества. В новых условиях хозяйствования значительно повышается роль иных видов транспорта, в том числе автомобильного, обеспечивающего перевозки на ограниченные расстояния и в ограниченных объемах.

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

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

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

В работе использованы труды таких авторов, разрабатывающих теорию графов и, в частности, задачу коммивояжера, как Ахо А., Басакер Р., Белл-ман Р., Беллмор М., Белов В.В., Берж К., Голынтейн Е.Г., Гудман С., Евстигнеев В.А., Ерусалимский Я.М., Зыков А.А., Иванов Б.Н., Конвей Р.В., Кристофи-дес Н., Литл Дж., Майника Э., Новиков Ф.А., Оре О., Пападимитриу X., Рейнгольд Э., Романовский И.В., Свами М., Сергиенко И.В., Уилсон Р., Харари Ф.

Организация эксплуатационной работы на транспорте рассмотрена в трудах Буянова В.А., Зубкова В.Н., Кочнева Ф.П., Мамаева Э.А., Мусиенко Н.Н., Осьминина А.Т., Прилепина Е.В., Сапунова Н.А., Сологуба Н.К., Смехова А.А., Сотникова И.Б., Сотникова Е.А., Тишкина Е.М., Угрюмова А.К., Шарова В.А., Эрлиха Н.В.

Общие вопросы теории систем, рассматриваемые в работе, изложены в трудах Баранова JI.A., Бира Ст., Богданова А.А., Дружинина В.В., Ивницкого

B.А., Мермельштейна Г.Г., Райбмана И.С., Растригина JI.A., Саридиса Дж. Вопросы управления сложными объектами на транспорте и в экономике, поставлены и решались в трудах Иванченко В.Н., Лисенкова В.М., Лябаха Н.Н., Орлова А.И.

Частные вопросы, нашедшие отражение в диссертации, рассмотрены в работах Белявского Г.И., Берштейна Л.С., Бутаковой М.А., Гуды А.Н., Ковалева

C.М., Ульяницкого Е.М., Шабельникова А.Н. и др.

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

- слабой адаптируемости этих подходов и методов к решению транспортных задач;

- не разработанности ряда теоретических и практических положений;

- отсутствия методик использования задачи коммивояжера на транспорте.

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

- выявление недостатков существующих методов решения задач оптимизации (в том числе маневровых передвижений на сортировочной станции и задачи развозки грузов автомобильным транспортом);

- обоснование выбора модели, формализующей задачу управления перевозками;

- разработка практических алгоритмов решения поставленных задач и программная их реализация;

- применение предложенных моделей, разработанных алгоритмов и программного обеспечения для решения ряда практических задач.

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

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

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

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

Чтобы обеспечить достижение поставленной цели необходимо решить следующие математические задачи:

- проанализировать возможности и условия применения задачи коммивояжера;

- развить задачу на случай нескольких агентов;

- разработать алгоритм решения задачи нескольких коммивояжеров;

- предложить методы решения проблемы многокритериалыюсти;

- учесть специфику железнодорожного и автомобильного транспорта;

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

- синтезировать методику использования математических формализмов и программно-математического обеспечения при решении практических задач на транспорте;

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

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

Теоретические исследования, проведенные в работе, апробировались на имитационном эксперименте и на реальных задачах управления.

Научная новизна состоит в следующем:

- разработана и обоснована обобщенная модель задачи коммивояжера для случая нескольких агентов и множества критериев, имеющая широкий спектр практических приложений в областях автоматизации управления технологическими процессами на транспорте;

- разработан новый метод решения предложенной задачи, основанный на идеях адаптивного случайного поиска, позволяющий получать квазиоптимальные решения за практически приемлемое время, что обеспечивает возможность его использования в системах оперативного управления;

- с целью выявления точного минимума многоагентной задачи коммивояжера развиты метод полного перебора и метод ветвей и границ;

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

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

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

Теоретическая значимость работы состоит в развитии новых методов математического моделирования транспортных процессов, основанных на использовании современного аппарата теории графов (задача нескольких коммивояжеров).

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

Апробация работы. Основные положения диссертации и научные результаты исследования докладывались и обсуждались на заседаниях и семинарах кафедры «Информатика» Ростовского государственного университета путей сообщения (РГУПС); второй международной научно-практической конференции «Проблемы регионального управления, экономики, права и инновационных процессов в образовании», г. Таганрог, 2001 г.; на научно-теоретической конференции профессорско-преподавательского состава РГУПС «Транспорт-2002», г. Ростов-на-Дону, 2002 г.; научно-теоретической конференции профессорско-преподавательского состава «Транспорт-2003», г. Ростов-на-Дону, 2003 г.; всероссийской научно-практической конференции профессорско-преподавательского состава «Транспорт-2004», г. Ростов-на-Дону, 2004 г.; международной научной конференции «Актуальные проблемы развития транспорта России: стратегические, региональные, технические», посвященной 75-летию РГУПС, г. Ростов н/Д, 2004 г.; всероссийской научно-практической конференции «Транспорт-2005», г. Ростов-на-Дону, 2005 г.; всероссийской научно-практической конференции «Транспорт-2006», г. Ростов-на-Дону, 2006 г., VII всероссийском симпозиуме по прикладной и промышленной математике, г. Москва, 2006 г.

Публикации. По результатам диссертационного исследования опубликовано 13 печатных работ общим объемом в 4,57 п.л. (из них лично автору принадлежит 4,36 п.л.), в том числе 11 без соавторов.

Внедрение результатов работы. Математическое обеспечение, предложенное в диссертации, внедрено в Ростовском филиале Российского научно-исследовательского и проектно-конструкторского института информатизации, автоматизации и связи МПС России, в структурном подразделении администрации города Ростова-на-Дону муниципальном учреждении «Чистый город». Материалы диссертационного исследования были использованы для методических целей в учебном процессе РГУПС при проведении занятий по информатике (были написаны методические указания к практическим занятиям). Получены акты о внедрении.

Структура и объем работы. Диссертация состоит из введения, четырех глав, содержащих 25 параграфов, заключения, библиографического списка и приложений. Основное содержание диссертации изложено на 148 страницах, содержит 60 рисунков и 4 таблицы. Библиографический список содержит 179 наименований отечественных и зарубежных источников.

4.6 Выводы

1. Обоснована необходимость предварительного преобразования графа задачи к полному графу. Показано каким образом производить данное преобразование используя алгоритм Флойда. Введена классификация точек, требующих обслуживания, при решении задач железнодорожного транспорта. Приведен необходимый порядок нумерации всех точек сети. Указана формула вычисления длины пути между двумя точками с учетом коэффициентов загрузки. Рассмотрен конкретный пример ситуации на железнодорожном транспорте.

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

3. Рассмотрена специфика железнодорожного транспорта, заключающаяся в том, что точки для посещения имеют разный приоритет. Введены дополнительные критерии качества решения задачи нескольких коммивояжеров, не дающие локомотивам одновременно находиться в одной точке, тем самым препятствуя возникновению "пробок" и крушений. Показано как подсчитывать значения этих новых критериев, а также результирующего критерия. Изменена формула вычисления длины маршрута каждого локомотива, в связи с тем, что локомотивы начинают работу не одновременно. Делается вывод: метод, использующий деревья поиска и комбинированный алгоритм не могут быть развиты на случай указанной модификации модели нескольких коммивояжеров. Приводится иллюстративный материал.

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

Моделируется процедура вывоза твердых отходов, осуществляемая МУ «Чистый город» г. Ростова-на-Дону.

5. Рассмотрена задача посещения ребер графа, решение которой указывает маршруты передвижения ремонтным бригадам, в том случае, когда им требуется осмотреть все участки пути на предмет неисправности, либо маршруты мусоровозов. Рассмотрены случаи ориентированного, неориентированного, а также смешанного исходных графов. Показано как задача нескольких коммивояжеров может быть использована и для решения данной задачи.

131

ЗАКЛЮЧЕНИЕ

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

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

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

Вопросы, нашедшие свое отражение в диссертации:

1. Задача коммивояжера, анализ и сравнение наиболее распространенных алгоритмов решения задачи.

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

3. Задача нескольких коммивояжеров, методы поиска ее минимума.

4. Виды критериев эффективности функционирования транспортных систем, вопросы согласования и оптимизации многих критериев.

5. Метрические пространства, способы метризуемости различных множеств.

6. Формализация и решение ряда прикладных задач методами теории графов и задачи нескольких коммивояжеров.

Основные научные результаты исследований состоят в следующем:

1. Предложена и обоснована модель нескольких коммивояжеров.

2. Известные точные и приближенные методы поиска оптимума задачи коммивояжера (метод полного перебора, ветвей и границ, эвристические подходы) развиты для нахождения оптимального плана разрабатываемой задачи нескольких коммивояжеров. Указана область применения полученных алгоритмов. Приведены конкретные численные примеры работы алгоритмов.

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

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

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

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

7. Изложены алгоритмы подсчета двух дополнительных критериев качества решений задачи нескольких коммивояжеров. Эти критерии обеспечивают максимум надежности и безопасности маневровых работ.

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

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

10. Разработан комплекс программ на ЭВМ, реализующих предложенные методы и подходы, а в частности редактор графов, облегчающий создание и редактирование исходных данных оптимизационных задач на графах.

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

1. Совершенствование разработанного метода, использующего деревья поиска.

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

- Изменить политику ветвления: вместо производимого методом ветвления в глубину реализовать ветвление побегами, в ширину, или указать какое-либо другое, лучшее правило ветвления, позволяющее сократить размеры деревьев.

2. Совершенствование эвристического алгоритма.

- Помимо методов Монте-Карло, Лина-Кернигана и ближайшего непосе-щенного города, составляющих предлагаемый в данной работе эвристический алгоритм, развить на случай задачи с несколькими коммивояжерами прочие известные методы решения задачи с одним коммивояжером, а в частности, рассмотренные в первой главе. Дополнить ими разработанный эвристический алгоритм.

- Указать наилучший выбор вероятностей работы алгоритмов, входящих в общий эвристический алгоритм.

3. Разработать генетический алгоритм решения задачи нескольких коммивояжеров и сравнить его с предложенным эвристическим методом.

4. Разработать процедуру формирования экспертных комиссий с учетом степени компетентности каждого из претендентов в комиссию, а также методы опроса экспертов, позволяющие в результате определить численное выражение показателей @к важности критериев, элементов весовых матриц {x-j , уступок sk, пороговых величин Fk и Fkp, введенных в третьей главе.

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

1. Айзинбуд С.Я., Козубенко В.Г., Курков В.Н. Машинист и безопасность. М.: Транспорт, 1992. - 48 с.

2. Акоф Р., Сасиени М. Основы исследования операций. М.: Мир, 1971. -536 с.

3. Акулиничев В.М., Правдин Н.В., Болотный В .Я., Савченко И.Е. Железнодорожные станции и узлы. М.: Транспорт, 1992. - 480 с.

4. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001.-288 с.

5. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 536 с.

6. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука. Гл. ред. физ.-мат. лит., 1974.-368 е.: ил.

7. Батищев Д.И., Шапошников Д.Е. Многокритериальный выбор с учетом индивидуальных предпочтений. Нижний Новгород: ИПФ РАН, 1994. - 92 с.

8. Беллман Р. Динамическое программирование. М.: Изд-во иностр. лит., 1960.-400 с.

9. Белов В.В., Воробьёв Е.М., Шаталов В.Е. Теория графов. М.: Высш. школа, 1976.-392 с.

10. Белоконь М.А. Разработка оптимальных алгоритмов функционирования технологических объектов, представляемых открытыми системами // Диссертация на соискание учёной степени кандидата технических наук. Ростов н/Д, 1996.

11. Белоусов А.И., Ткачев С.Б. Дискретная математика. М.: Изд-во МГТУ им. Н.Э. Баумана, 2002. - 744 с.

12. Белявский Г.И., Корабельииков Г.Я., Логвинов Ю.Н., Фалькович М.А. Распознавание образов. Теория и приложения. Ростов н/Д: Изд-во РГУ, 1993. -123 с.

13. Березина Л.Ю. Графы и их применение / Пособие для учителей. М.: Просвещение, 1979. -143 е.: ил.

14. Березовский Б.А., Барышников Ю.М., Борзенко В.И., Кемпнер Л.М. Многокритериальная оптимизация: Математические аспекты. М.: Наука, 1989.- 128 с.

15. Берж К. Теория графов и её применения. М.: Изд-во иностр. лит., 1962.-319 с.

16. Берштейн Л.С. Пособие к практическим занятиям по курсу «Математические основы кибернетики». Таганрог: ТРТИ, 1976. - 70 с.

17. Вагнер Г. Основы исследования операций. М.: Мир, 1973. - Том 2. -488 с.

18. Варфоломеев В.В., Колодий Л.П. Устройство пути и станций/ Учебник для техникумов железнодорожного транспорта. М.: Транспорт, 1992. - 303 с.

19. Васильев В.В., Ралдугин Е.А. Электронные модели задач на графах. -Киев: Наукова думка, 1987. -152 с.

20. Васильев Ф.П., Иваницкий A.IO. Линейное программирование. М.: Изд-во «Факториал», 1998. -176 с.

21. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. М.: Наука, 1988. - 208 с.

22. Волков И.К., Загоруйко Е.А. Исследование операций. М.: МГТУ им. Н.Э. Баумана, 2000.-436 с.

23. Волкович В.Л. Многокритериальные задачи и методы их решения. -М.: Кибернетика и вычислительная техника, 1969.

24. Вороновский Г.К. и др. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. Харьков: Основа, 1997. -112 с.

25. Вощинин А.П., Сотиров Г.Р. Оптимизация в условиях неопределенности. М.: МЭИ, София: Техника, 1989. - 224 с.

26. Гаджинский A.M. Логистика. М.: Издательско-торговая корпорация «Дашков и К0», 2003. - 408 с.

27. Галкина В.А. Дискретная математика: комбинаторная оптимизация на графах. М.: Гелиос АРВ, 2003. - 232 с.

28. Голынтейн Е.Г., Юдин Д.Б. Новые направления в линейном программировании. М.: Сов. радио, 1966. - 524 с.

29. Гоманков Ф.С. Технология и организация перевозок на железнодорожном транспорте: учебник для вузов. М.: Транспорт, 1994. - 208 с.

30. Горбатов В.А., Горбатов А.В., Горбатова М.В. Дискретная математика. М. ООО «Изд-во ACT»: ООО «Изд-во Астрель», 2003. - 447 с.

31. Гроппен В.О. Модели и алгоритмы комбинаторного программирования. Ростов н/Д: Изд-во РГУ, 1983.- 148 с.

32. Грунтов П.С., Бабченко С.А., Кузнецов В.Г. Автоматизированные диспетчерские центры управления эксплуатационной работой железных дорог. -М.: Транспорт, 1990. 228 с.

33. Гуда А.Н. Математическое моделирование сложных технологических процессов железнодорожного транспорта. Ростов н/Д: Изд-во РГУ, 1995. -155 с.

34. Гуда А.Н. Методы анализа данных и принятия решений в затруднённых условиях. Ростов н/Д: Изд-во Северо-Кавказского научного центра высшей школы, 1997. -139 с.

35. Гудман С., Хидитниеми С. Введение в разработку и анализ алгоритмов. -М.: Мир, 1981.-368 е.: ил.

36. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. - 416 с.

37. Евстигнеев В.А. Применение теории графов в программировании. М.: Наука, 1985.-352 с.

38. Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. Новосибирск: ВО «Наука», 1994. - 360 с.

39. Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. Новосибирск: Наука, Сиб. предприятие РАН, 1998. -385 с.

40. Емеличев В.А., Ковалёв М.М., Кравцов М.К. Многогранники, графы, оптимизация. -М.: Наука. Гл. ред. физ.-мат. лит., 1981.-344 с.

41. Емельянов С.В., Ларичев О.И. Многокритериальные методы принятия решений. -М.: Знание. 1985.-32 с.

42. Ермольев Ю.М., Мельник И.М. Экстремальные задачи на графах. Киев: Наукова думка, 1968. -178 с.

43. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. М.: Вузовская книга, 1999. - 280 с.

44. Жарков Ю.И. Микропроцессорные информационно-управляющие системы в устройствах электроснабжения. Учебное пособие. Ростов н/Д: РИ-ИЖТ, 1990.-60 с.

45. Железнодорожные станции и узлы промышленного транспорта: учебник для вузов. М.: Транспорт, 1986. - 352 с.

46. Железнодорожные станции и узлы промышленных районов: учебник для вузов. Ростов н/Д: Изд. РГУПС, 1996. - 488 с.

47. Железные дороги. Общий курс: учебник для вузов / 4-е изд. М.: Транспорт, 1991.-295 с.

48. Зыков А.А. Основы теории графов. -М.: Наука. Гл. ред. физ.-мат. лит., 1987.-384 с.

49. Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учеб. пособие. -М.: Лаборатория Базовых Знаний, 2002.-288 е.: ил.

50. Иванченко В.Н. Теория построения и реализация информационно-управляющих микропроцессорных систем на сортировочных станциях // Диссертация на соискание учёной степени доктора технических наук. Ростов н/Д, 1988.-С. 233.

51. Иванченко В.Н., Ковалев С.М., Шабельников А.Н. Микропроцессорные технические средства автоматизации и информатизации технологических процессов на железнодорожном транспорте: учеб. пособие. Ростов н/Д: РГУПС, 2005.-76 с.

52. Ивахненко А.Г. Моделирование сложных систем по экспериментальным данным. -М. Радио и Связь, 1986. 119 с.

53. Ивахненко А.Г. Помехоустойчивость моделирования. Киев: Наукова думка, 1985.-214 с.

54. Информатика: Учеб. пособие для пед. спец. высш. учеб. заведений / Есаян А.Р., Ефимов В.И., Лапицкая Л.П. и др. М.: Просвещение, 1991. - 288 е.: ил.

55. Иозайтис B.C., Львов Ю.А. Экономико-математическое моделирование производственных систем. М.: Высш. шк., 1991. - 192 с.

56. Казак А.А. Анализ подходов к решению задачи нескольких коммивояжёров // Научная мысль Кавказа № 3. Ростов н/Д : Изд-во СКНЦ, 2002. - С. 91-94.

57. Казак А.А. Задачи поиска кратчайших транспортных маршрутов и методы их решения : методические указания к практическим занятиям. Ростов н/Д : Изд-во РГУПС, 2006. - 36 с.

58. Казак А.А. Метод полного перебора для решения задачи нескольких коммивояжеров // Изв. вузов. Северо-Кавказский регион. Технические науки. Приложение №1. Новочеркасск: Изд-во ЮРГТУ (НПИ), 2005. - С. 56-61.

59. Казак А.А. Организация маневровой работы на сортировочной станции // Труды всероссийской научно-практической конференции профессорскопреподавательского состава «Транспорт-2004», часть 1. Ростов н/Д : Изд-во РГУПС, 2004.-С. 42-43.

60. Казак А.А. Разработка и внедрение логистической системы «Чистый город» / Обозрение прикладной и промышленной математики. Т. 13, вып. 2. -М., 2006.-С. 101-102.

61. Казак А.А. Разработка метода решения одной задачи маршрутизации на транспортной сети // Труды Всероссийской научно-практической конференции «Транспорт-2005», часть 1. Ростов н/Д : Изд-во РГУПС, 2005. - С. 98-100.

62. Казак А.А. Формирование исходных данных оптимизационных задач на графах // Труды Всероссийской научно-практической конференции «Транс-порт-2006», часть 3. Ростов н/Д : Изд-во РГУПС, 2006. - С. 256-257.

63. Камерон П., Ван Линт Дж. Теория графов, теория кодирования и блок-схемы. -М.: Наука, 1980. -140 с.

64. Катулев А.Н., Северцев Н.А. Исследование операций: принципы принятия решений и обеспечение безопасности. М.: Физ.-мат.лит., 2000. - 320 с.

65. Кини P.JI., Райфа X. Принятие решений при многих критериях: предпочтения и замещения. М.: Радио и связь, 1981. - 560 с.

66. Клемент Р. Генетические алгоритмы: почему они работают? когда их применять? // Компьютерра. №11 289. «Искусственная жизнь». М.: Издательский дом «Компьютерра», 1999. - С. 20-23.

67. Климова JI.M. PASCAL 7.0. Практическое программирование. Решение типовых задач. М.: КУДИЦ-ОБРАЗ, 2000. - 496 с.

68. Кнут Д. Искусство программирования для ЭВМ: Основные алгоритмы. -М.: Мир, 1976.-736 с.

69. Кнут Д. Искусство программирования для ЭВМ: Получисленные алгоритмы. М.: Мир, 1977. - 724 с.

70. Кнут Д. Искусство программирования для ЭВМ: Сортировка и поиск. -М.: Мир, 1978.-844 с.

71. Ковалёв М.М. Дискретная оптимизация. Минск: Изд-во БГУ, 1977. -191с.

72. Ковалев С.М., Каймаков К.Г. Проектирование автоматизированных рабочих мест оперативно-диспетчерского персонала в микропроцессорных системах на железнодорожном транспорте. Учебное пособие. Ростов н/Д: РИ-ИЖТ, 1986.-65 с.

73. Кодачигов В.И. Системы искусственного интеллекта. Методы решения задач. Таганрог: ТРТУ, 1996. - 89 с.

74. Козлов П.А. Информационные технологии для новой эксплуатационной модели управления перевозками // Автоматика, связь, информатика. 2001, №4.

75. Козлов П.А. От информационных систем к управляющим // Железнодорожный транспорт. -1999, №9.

76. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. М.: Наука, 1972. - 496 с.

77. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. М.: Наука, 1975.-360 с.

78. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. -М.: Наука, 1969.-368 с.

79. Коршунов Ю.М. Математические основы кибернетики. М.: Энергия, 1980.-424 с.

80. Костенко Л.И., Тимошенко А.Г., Трайнин Э.З. Электронное моделирование задач исследования операций. Киев: Наукова думка, 1973. - 164 с.

81. Кофман А., Анри-Лабордер А. Методы и модели исследования операций.-М.: Мир, 1977.-369 с.

82. Краснощекое П.С., Петров А.А. Принципы построения моделей. М.: ФАЗИС: ВЦ РАН, 2000. - 412 с.

83. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.-432 с.

84. Кузин Л.Т. Основы кибернетики: Основы кибернетических моделей. Т.2. М.: Энергия, 1979. - 584 с.

85. Кузнецов А.В., Холод Н.И. Математическое программирование / Учеб. пособие для эконом, спец. вузов. Минск: Вышэйшая школа, 1984. - 221 с.

86. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергоатомиздат, 1988. - 480 е.: ил.

87. Кук Д., Бейз Г. Компьютерная математика. М.: Наука, 1990. - 384 с.

88. Курганов В.М. Логистические транспортные потоки. М.: Издатель-ско-торговая корпорация «Дашков и К0», 2003. - 252 с.

89. Курейчик В.В. Эволюционные методы решения оптимизационных задач. Таганрог: Изд-во ТРТУ, 1999. - 95 с.

90. Курейчик В.В. Эволюционные, синергетические и гомеостатические методы принятия решений. Таганрог: Изд-во ТРТУ, 2001. - 221 с.

91. Курейчик В.М. Генетические алгоритмы. Монография. Таганрог: Изд-во ТРТУ, 1998.-242 с.

92. Ларичев О.И. Теория и методы принятия решений, а также Хроника событий в Волшебных странах. -М.: Логос, 2002. 392 с.

93. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. М.: Наука. Гл. ред. физ.-мат. лит., 1990. - 384 с.

94. Липский В. Комбинаторика для программистов. М.: Мир, 1988. -213 с.

95. Ловас Л., Пламмер М. Прикладные задачи теории графов. Теория па-росочетаний в математике, физике, химии. М.: Мир, 1998. - 653 с.

96. Логистические транспортно-грузовые системы. М.: Издательский центр «Академия», 2003. - 304 с.

97. Лукинский B.C. Логистика автомобильного транспорта: концепция, методы, модели. -М.: Финансы и статистика, 2002. 280 с.

98. Лябах Н.Н. Математические основы разработки и использования машинного интеллекта. Ростов н/Д: Изд-во РГУ, 1989. - 112 с.

99. Лябах Н.Н., Казак А.А. Применение и развитие задачи коммивояжёра для решения технологических задач на железнодорожном транспорте // Вестник РГУПС №1. Ростов н/Д: Изд-во РГУПС, 2002. - С. 141-143.

100. Лябах Н.Н., Шабельников А.Н. Техническая кибернетика на железнодорожном транспорте. Ростов н/Д: СКНЦ ВШ, 2002. - 283 с.

101. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981.-324 с.

102. Маргупов Т.М. Графы, сети, алгоритмы и их приложения. Ташкент: Фан, 1990. -120 с.

103. Матряшин Н.П., Макеева В.К. Математическое программирование / 2-е изд. Харьков: Вища школа, 1978. - 160 с.

104. Мелихов А.Н., Берштейн JI.C., Курейчик В.М. Применение теории графов для проектирования дискретных устройств. М.: Наука, 1974. - 304 с.

105. Микони С.В. Элементы дискретной математики. СПб.: ПГУПС, 1999.- 125 с.

106. Мину М. Математическое программирование. Теория и алгоритмы. -М.: Наука. Гл. ред. физ.-мат. лит., 1990.-488 с.

107. Мишарин А.С. Развитие информатизации на Российских железных дорогах // Автоматика, связь, информатика. 2000, №11.

108. Мишарин А.С. Развитие информационных и телекоммуникационных систем железнодорожного транспорта // Автоматика, связь, информатика. -2001, №7.

109. Могилёв А.В., Пак Н.И., Хеннер Е.К. Информатика. М.: Изд. центр «Академия», 2000. - 816 с.

110. Модели и методы теории логистики. СПб.: Питер, 2003. - 176 с.

111. Моделирование задач исследования операций. М.: Энергия, 1978. -216 е.: ил.

112. Моргунов И.Б. Основы дискретной оптимизации некоторых задач упорядочения. М.: Исследовательский центр проблем качества подготовки специалистов, 1994.-215 с.

113. Москинова Г.И. Дискретная математика. М.: Логос, 2000. - 240 с.

114. Мушик Э., Мюллер П. Методы принятия технических решений. -М.: Мир, 1990.-208 с.

115. Мышкис А.Д. Элементы теории математических моделей. М.: Физматлит, 1994. - 192 с.

116. Немнюгин СЛ. Turbo Pascal: практикум. СПб: Питер, 2000. - 256 с.

117. Нефедов В.Н., Осипова В.А. Курс дискретной математики / учебное пособие. -М.: Изд-во МАИ, 1992. 264 е.: ил.

118. Никитин В.Д., Савченко И.Е., Ветухов Е.А., Ивашкевич В.К. Железнодорожные станции и узлы: расчёты и проектирование сортировочных горок. -М.: ВЗИИТ, 1970.-80 с.

119. Нильсон Н. Искусственный интеллект: Методы поиска решений. -М.: Мир, 1973.-270 с.

120. Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2001.-304 е.: ил.

121. Оре О. Графы и их применение. Новокузнецк: ИО НФМИ, 2000. -168 с.

122. Оре О. Теория графов. М.: Наука, 1980. - 336 с.

123. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985. - 510 с.

124. Плесневич Г.С., Сатаров Н.С. Алгоритмы в теории графов. Ашхабад: Ылым, 1981.-312 с.

125. Плоткин Б.К. Экономико-математические методы и модели в управлении материальными ресурсами. СПб.: Изд-во СПбУЭФ, 1992. - 64 с.

126. Повороженко В.В., Резер С.М. Взаимодействие железнодорожного и автомобильного транспорта. М.: Знание, 1974. - 48 с.

127. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982. - 256 с.

128. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. -М.: Мир, 1989.-478 с.

129. Прикладные нечёткие системы. М.: Мир, 1993. - 368 с.

130. Растригин JI.A. Случайный поиск. М.: Знание, 1979. - 64 с.

131. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. - 480 с.

132. Роберте Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука. Гл. ред. физ.-мат. лит., 1986.-496 с.

133. Романовский И.В. Алгоритмы решения экстремальных задач. М.: Наука, 1977.-352 с.

134. Романовский И.В. Дискретный анализ. СПб.: Невский диалект, 2000.-240 с.

135. Рубинштейн Г.Ш. Конечномерные модели оптимизации / Курс лекций. Новосибирск: Изд-во НГУ, 1970. - 228 с.

136. Рыбников К.А. Введение в комбинаторный анализ / 2-е изд. М.: Изд-во Моск. ун-та, 1985. - 308 с.

137. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984.-454 с.

138. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. Киев: Наукова думка, 1988. - 472 с.

139. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации. Киев: Наук, думка, 1981. - 288 с.

140. Сергиенко И.В., Лебедева Т.Т., Рощин В.А. Приближенные методы решения дискретных задач оптимизации. Киев: Наук, думка, 1980. - 276 с.

141. Сивохина Н.П., Родионов В.Б., Горбунов Н.М. Логистика: учеб. пособие. М.: ООО «Издательство ACT», ЗАО «РИК Русанова», 2000. - 224 с.

142. Соболь И.М. Метод Монте-Карло. М.: Наука, Гл. ред. физ.-мат. лит., 1985.-80 с.

143. Соболь И.М. Точки, равномерно заполняющие многомерный куб. -М.: Знание, 1985.-32 с.

144. Совершенствование управляющей деятельности машиниста локомотива: учебное пособие / Козубенко В.Г., Голов Ю.В., Уразгильдеев Р.Х., Фельдман В.М. Ростов н/Д: РИИЖТ, 1991. - 40 с.

145. Статистические методы для ЭВМ. М.: Наука, 1986. - 464 с.

146. Татт У. Теория графов. М.: Мир, 1988. - 424 е.: ил.

147. Таха X. Введение в исследование операций. М.: Мир, 1985. - Кн. 1. -479 с. Кн. 2.-496 с.

148. Теория расписаний и вычислительные машины. М.: Наука, 1984. -334 с.

149. Тимковский В.Г. Дискретная математика в мире станков и деталей. Введение в математическое моделирование задач дискретного производства. -М.: Наука, 1992. -144 с.

150. Типовой технологический процесс организации централизованного вывоза (завоза) грузов автомобильным транспортом общего пользования со станций железных дорог, морских (речных) портов и пристаней. М: Транспорт, 1974.-132 с.

151. Типовой технологический процесс работы сортировочной станции. -М.: Транспорт, 1976. 104 с.

152. Топп У., Форд У. Структуры данных в С++. М.: ЗАО «Издательство БИНОМ», 2000. - 816 е.: ил.

153. Транспортная логистика: учебник для транспортных вузов. / Под общей редакцией Л.Б. Миротина. М.: Изд-во «Экзамен», 2003. - 512 с.

154. Уилсон Р. Введение в теорию графов. М.: Мир, 1977. - 208 с.

155. Ульяницкий Е.М. Микропроцессорная система релейной защиты энергоблоков. Ростов н/Д: Изд-во РГУ, 1990. - 156 с.

156. Фаронов В.В. Delphi 4. Учебный курс. М.: «Нолидж», 1999. - 464 е., ил.

157. Федоров И.П. Автоматизация извлечения знаний при построении экспертных систем// Методы и системы принятия решений. Системы, основанные на знаниях. Рига: РПИ, 1989. - С. 48-54.

158. Филоненков А.И. Математические модели в расчетах на ЭВМ: Уч. пособие. Ч. 2. Ростов-н/Д: РГУПС, 1994. - 82 с.

159. Финкельштейн Ю.Ю. Приближённые методы и прикладные задачи дискретного программирования. М.: Наука, 1976. - 264 с.

160. Фонарёв Н.М. Автоматизация процесса расформирования составов на сортировочных горках. -М.: Транспорт, 1971. 272 с.

161. Харари Ф. Теория графов. М.: УРСС, 2003. - 300 с.

162. Хейес-Рот Ф., Уотермен Д., Ленат Д. Построение экспертных систем. -М.: Мир, 1987.-441 с.

163. Холл М. Комбинаторика. М.: Мир, 1970. - 424 с.

164. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974.-520 с.

165. Чернухин Ю.В. Искусственный интеллект и нейрокомпьютеры. Таганрог: ТРТУ, 1997.-273 с.

166. Шабельников А.Н. Разработка методов автоматизации управления динамическими процессами на основе нечеткой информации // Диссертация на соискание учёной степени кандидата технических наук. Ростов н/Д, 2000.

167. Штойер Р. Многокритериальная оптимизация. Теория, вычисления и приложения. М.: Радио и связь, 1992. - 504 с.

168. Энциклопедия кибернетики. В 2-х томах. Киев, 1975. - Т. 1. - 608 е.; Т. 2.-624 с.

169. Юдин Д.Б., Горяшко А.П., Немировский А.С. Математические методы оптимизации устройств и алгоритмов АСУ. М.: Радио и связь, 1982. - 288 с.

170. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.-384 с.179. http://www.rostov-gorod.ru/index.php?id=1814