Содержание к диссертации
Введение
1 Задача коммивояжера и ее модификации: описание, проблемы, пути решения 12
1.1 Характеристика объекта исследования 12
1.1.1 Роль и место задачи коммивояжера в совершенствовании транспортных процессов 12
1.1.2 Постановка задач управления в рамках исследуемых оптимизационных задач 14
1.2 Обзор методов решения задачи коммивояжёра 20
1.3 Возможные механизмы учета многих критериев в задаче коммивояжера 33
1.4 Существующий подход к решению задачи оптимизации маневровых передвижений на сортировочной станции 36
1.5 Постановка задач диссертационной работы 37
1.6 Выводы 41
2 Разработка модели нескольких коммивояжеров 43
2.1 Определение модели нескольких коммивояжеров с использованием теории графов 43
2.2 Метод полного перебора 47
2.3 Метод решения, использующий деревья поиска 51
2.4 Эвристический алгоритм 63
2.5 Комбинированный алгоритм 72
2.6 Выводы 73
3 Пути решения задачи нескольких коммивояжеров в многокритериальной постановке 74
3.1 Постановка вопроса 74
3.2 Сведение многокритериальной задачи к однокритериальной 76
3.3 Многокритериальный подход решения задачи нескольких коммивояжеров 78
3.4 Мера близости комбинаторных объектов 86
3.5 Выводы 91
4 Использование разработанных методов при модели ровании специфических транспортных процессов 92
4.1 Предварительное преобразование исходного графа 92
4.2 Разработка редактора графов 104
4.3 Учет специфики железнодорожного транспорта 108
4.4 Задачи автомобильного транспорта 117
4.4.1 Перевозка заданного количества груза 117
4.4.2 Разработка и внедрение логистической системы «Чистый город» 120
4.5 Оптимальное упорядочение ребер графа 123
4.6 Выводы 129
Заключение 131
Библиографический список
- Постановка задач управления в рамках исследуемых оптимизационных задач
- Метод решения, использующий деревья поиска
- Сведение многокритериальной задачи к однокритериальной
- Учет специфики железнодорожного транспорта
Введение к работе
Актуальность исследования. Коренные социально-экономические преобразования, осуществляемые в Российской Федерации в последние годы, отразились прежде всего на парадигме управления отраслями народного хозяйства на основе экономических критериев. Поскольку железнодорожный транспорт по-прежнему играет ключевую роль в экономике страны, приспособление его к новым методам хозяйствования в условиях рыночной системы является важной и своевременной задачей на современном этапе развития общества. В новых условиях хозяйствования значительно повышается роль иных видов транспорта, в том числе автомобильного, обеспечивающего перевозки на ограниченные расстояния и в ограниченных объемах.
Один из основных путей повышения эффективности работы транспорта -это модернизация системы управления и организации его работы. В последнее время все более интенсивно в процессы мониторинга, моделирования сложных транспортных объектов, принятия решений и контроля их исполнения, составляющих суть управления на транспорте, внедряются методы математического моделирования, а также обеспечивающие их передовые информационные технологии.
В силу специфики основных технологических процессов на транспорте, представляется перспективным использование математического аппарата теории графов. Характерными примерами может служить управление маневровой работой на сортировочных станциях, развозом грузов по сети магазинов города. Вместе с тем, многокритериальность указанных задач управления, а также их программно-математическое обеспечение, не в полной мере учитывающее специфику некоторых задач, повышают вероятность ошибочных действий со стороны человека-оператора, и, как следствие, вероятность сбоев в работе сортировочных станций, автотранспортных предприятий, срывов графиков движения поездов и автомашин. В связи с этим формализация (математическое описание) задач управления транспортными системами на основе использования задачи
5 коммивояжера актуальна, так как позволяет использовать разработанные машинные методы принятия обоснованных решений.
Задачи управления транспортными потоками являются многокритериальными и плохо формализуются вследствие нестационарности и зашумленности исходной информации, противоречивым экономическим, технологическим, экологическим и другим требованиям. Важнейшими проблемами совершенствования систем автоматического управления является повышение надежности и точности их функционирования, безопасности и быстродействия. Решение этих задач позволит снять ряд технологических и организационно-экономических проблем.
В работе использованы труды таких авторов, разрабатывающих теорию графов и, в частности, задачу коммивояжера, как Ахо А., Басакер Р., Белл-манР., Беллмор М., Белов В.В., Берж К., Гольштейн Е.Г., Гудман С, Евстигнеев В.А., Ерусалимский Я.М., Зыков А.А., Иванов Б.Н., Копией Р.В., Кристофи-дес Н., Литл Дж., Майника Э., Новиков Ф.А., Оре О., Пападимитриу X., Рейнгольд Э., Романовский И.В., Свами М., Сергиенко И.В., Уилсон Р., Харари Ф.
Организация эксплуатационной работы на транспорте рассмотрена в трудах Буянова В.А., Зубкова В.Н., Кочнева Ф.П., Мамаева Э.А., Мусиенко Н.Н., Осьминина А.Т., Прилепина Е.В., Сапунова Н.А., Сологуба Н.К., Смехова А.А., Сотникова И.Б., Сотникова Е.А., Тишкина Е.М., Угрюмова А.К., Шарова В.А., Эрлиха Н.В.
Общие вопросы теории систем, рассматриваемые в работе, изложены в трудах Баранова Л.А., Вира Ст., Богданова А.А., Дружинина В.В., Ивницкого В.А., Мермельштейна Г.Г., Райбмана И.С., Растригина Л. А., Саридиса Дж.
Вопросы управления сложными объектами на транспорте и в экономике, поставлены и решались в трудах Иванченко В.Н., Лисенкова В.М., Лябаха Н.Н., Орлова А.И.
Частные вопросы, нашедшие отражение в диссертации, рассмотрены в работах Белявского Г.И., Берштейна Л.С., Бутаковой М.А., Гуды А.Н., Ковалева СМ., Ульяницкого Е.М., Шабельникова А.Н. и др.
Вместе с тем, практическое применение разработанных подходов к управлению, методов математического моделирования транспортных процессов затруднено в настоящее время вследствие:
слабой адаптируемости этих подходов и методов к решению транспортных задач;
не разработанности ряда теоретических и практических положений;
отсутствия методик использования задачи коммивояжера на транспорте.
Таким образом, в рамках данной темы нерешенными являются следующие общесистемные, технологические, математические, программные и внедренческие проблемы:
выявление недостатков существующих методов решения задач оптимизации (в том числе маневровых передвижений на сортировочной станции и задачи развозки грузов автомобильным транспортом);
обоснование выбора модели, формализующей задачу управления перевозками;
разработка практических алгоритмов решения поставленных задач и программная их реализация;
применение предложенных моделей, разработанных алгоритмов и программного обеспечения для решения ряда практических задач.
В указанных проблемах присутствует важная особенность данного исследования: коммивояжеров, реализующих технологическую задачу, несколько.
Вышесказанное определяет цель диссертационного исследования: развитие модели коммивояжера для решения практических транспортных задач с учетом наличия нескольких коммивояжеров, многокритериальности, повышения интенсивности, надежности и безопасности транспортных процессов.
В качестве объекта исследования в работе рассматриваются системы железнодорожного и автомобильного транспорта, допускающие моделирование с помощью задачи коммивояжера и отличающиеся дефицитом времени для принятия и исполнения решений, неопределенностью и несогласованностью
7 исходной информации. В частности, процесс нормализации результатов роспуска составов маневровыми локомотивами, система управления работой нескольких автомобилей, выполняющих развоз однородного груза по сети пунктов-потребителей, и др.
Предметом исследования являются методы формализованного представления транспортных процессов и систем на основе теоретико-графовых моделей, а также алгоритмы решения обобщенной многокритериальной и мно-гоагентной задачи коммивояжера.
Чтобы обеспечить достижение поставленной цели необходимо решить следующие математические задачи:
проанализировать возможности и условия применения задачи коммивояжера;
развить задачу на случай нескольких агентов;
разработать алгоритм решения задачи нескольких коммивояжеров;
предложить методы решения проблемы многокритериалыюсти;
учесть специфику железнодорожного и автомобильного транспорта;
разработать программное обеспечение, реализующее полученный алгоритм нахождения оптимального плана задачи нескольких коммивояжеров;
синтезировать методику использования математических формализмов и программно-математического обеспечения при решении практических задач на транспорте;
применить разработанные методы и подходы для решения задач нормализации процесса роспуска и доставки грузов несколькими автомобилями.
Методика исследования. Решение поставленных задач осуществлялось с использованием разнообразных подходов и методов дискретной математики, теории графов, теории вероятностей, исследования операций, многокритериальной оптимизации.
Теоретические исследования, проведенные в работе, апробировались на имитационном эксперименте и на реальных задачах управления.
Научная новизна состоит в следующем:
разработана и обоснована обобщенная модель задачи коммивояжера для случая нескольких агентов и множества критериев, имеющая широкий спектр практических приложений в областях автоматизации управления технологическими процессами на транспорте;
разработан новый метод решения предложенной задачи, основанный на идеях адаптивного случайного поиска, позволяющий получать квазиоптимальные решения за практически приемлемое время, что обеспечивает возможность его использования в системах оперативного управления;
с целью выявления точного минимума многоагентной задачи коммивояжера развиты метод полного перебора и метод ветвей и границ;
предложен общий подход к решению многокритериальной задачи нескольких коммивояжеров при конфликтном взаимодействии агентов и наличии приоритетов в обслуживании, основанный на свертке частных критериев с привлечением экспертных оценок, что позволяет при поиске решений учитывать мнения специалистов-экспертов и получать в конечном итоге более эффективные решения;
проведен вычислительный эксперимент, обеспечивающий комплексное исследование задачи нескольких коммивояжеров на основе авторских проблемно-ориентированных программ.
Достоверность и обоснованность полученных результатов исследования подтверждается рядом публикаций, апробацией на научных семинарах и конференциях, результатами вычислительных экспериментов на имитационных задачах, результатами практического использования предложенных в диссертации моделей и алгоритмов, что подтверждено соответствующими актами.
Теоретическая значимость работы состоит в развитии новых методов математического моделирования транспортных процессов, основанных на использовании современного аппарата теории графов (задача нескольких коммивояжеров).
Практическая ценность диссертации обусловлена возможностью ее использования в задачах управления сложными технологическими процессами
9 на транспорте, связанными с оптимизацией перемещений подвижных единиц, что приводит к интенсификации работ и оптимизации экономических и производственных критериев.
Апробация работы. Основные положения диссертации и научные результаты исследования докладывались и обсуждались на заседаниях и семинарах кафедры «Информатика» Ростовского государственного университета путей сообщения (РГУПС); второй международной научно-практической конференции «Проблемы регионального управления, экономики, права и инновационных процессов в образовании», г. Таганрог, 2001 г.; на научно-теоретической конференции профессорско-преподавательского состава РГУПС «Транспорт-2002», г. Ростов-на-Дону, 2002 г.; научно-теоретической конференции профессорско-преподавательского состава «Транспорт-2003», г. Ростов-на-Дону, 2003 г.; всероссийской научно-практической конференции профессорско-преподавательского состава «Транспорт-2004», г. Ростов-на-Дону, 2004 г.; международной научной конференции «Актуальные проблемы развития транспорта России: стратегические, региональные, технические», посвященной 75-летию РГУПС, г. Ростов н/Д, 2004 г.; всероссийской научно-практической конференции «Транспорт-2005», г. Ростов-на-Дону, 2005 г.; всероссийской научно-практической конференции «Транспорт-2006», г. Ростов-на-Дону, 2006 г., VII всероссийском симпозиуме по прикладной и промышленной математике, г. Москва, 2006 г.
Публикации. По результатам диссертационного исследования опубликовано 13 печатных работ общим объемом в 4,57 п.л. (из них лично автору принадлежит 4,36 п.л.), в том числе 11 без соавторов.
Внедрение результатов работы. Математическое обеспечение, предложенное в диссертации, внедрено в Ростовском филиале Российского научно-исследовательского и проектно-конструкторского института информатизации, автоматизации и связи МПС России, в структурном подразделении администрации города Ростова-на-Дону муниципальном учреждении «Чистый город». Материалы диссертационного исследования были использованы для методиче-
10 ских целей в учебном процессе РГУПС при проведении занятий по информатике (были написаны методические указания к практическим занятиям). Получены акты о внедрении.
Структура и объем работы. Диссертация состоит из введения, четырех глав, содержащих 25 параграфов, заключения, библиографического списка и приложений. Основное содержание диссертации изложено на 148 страницах, содержит 60 рисунков и 4 таблицы. Библиографический список содержит 179 наименований отечественных и зарубежных источников.
Во введении дана общая характеристика работы, обоснована актуальность темы исследования, сформулирована его цель и задачи, указаны элементы научной новизны работы и практическая ценность полученных научных результатов, описаны результаты апробаций и публикаций.
В первой главе дана характеристика объекта исследования, перечислены задачи управления в рамках исследуемых оптимизационных задач, а также возможные механизмы их решения, проведен анализ существующих подходов к решению рассматриваемых проблем, ставятся задачи диссертационной работы.
Вторая глава посвящена математическому моделированию транспортных процессов на основе использования задачи коммивояжера, а именно развитию задачи коммивояжера на случай нескольких коммивояжеров. Приводится постановка задачи нескольких коммивояжеров, подсчитывается количество вариантов решений задачи, описываются разработанные метод полного перебора, метод, использующий деревья поиска, эвристический алгоритм и комбинированный алгоритм. Анализируются сильные и слабые стороны алгоритмов, решаются конкретные численные примеры.
Третья глава указывает возможные методы решения многокритериальной задачи нескольких коммивояжеров. Перечисляются экономические критерии эффективности маневровой работы на станции. В свете решения разрабатываемой задачи рассмотрены два принципиально различных подхода к решению
многокритериальных задач. Вводится понятие расстояния между множествами допустимых маршрутов, требуемое одним из методов.
Постановка задач управления в рамках исследуемых оптимизационных задач
Оперативно-диспетчерский персонал железнодорожной станции функционирует в условиях большой размерности задач контроля и управления, дефицита времени на принятие решений, наличия ошибок в данных, миогокрите-риальности задачи управления, открытости объекта и системы управления. В связи с этим формализация (математическое описание) задачи управления актуальна, так как позволяет использовать хорошо разработанные машинные методы идентификации объекта (состояния) и принятия обоснованных решений [105]. Одним из подходов к моделированию сложных транспортных процессов, недостаточно разработанных теоретически и ещё не имеющих практической ценности, является использование постановок проблем в смысле задачи коммивояжёра. Как было сказано в п. 1.1.1, характерными технологическими задачами, решаемыми с помощью задачи коммивояжера, являются оптимизация маневровых передвижений на сортировочной станции, оптимизация развозки грузов автомобильным транспортом по торговым точкам города Рассмотрим эти и другие примеры более подробно.
Пример 1. Важнейшим звеном процесса расформирования составов на сортировочных станциях являются сортировочные горки (СГ)- На рис. 1.1 схематично представлены план а) и профиль б) СГ с указанием технологических операций, выполняемых последовательно различными подсистемами, которые в комплексе автоматизируют сортировочный процесс [174]. Это: телеуправление горочным локомотивом (ТГЛ), который обозначен номером 1 на рис. 1.1, автоматическое задание скорости роспуска состава (АЗСР), горочная автомати ческая централизация (ГАЦ), автоматическое регулирование скорости скатывания отцепов на спускной части горки (АРС - ЦНИИ, АРС - ГТСС). Кроме того, на рисунке обозначены: 2 - тормозные позиции, 3 - стрелки, 4 - указатель скорости надвига отцепа, 5 - горочный светофор, который через комбинацию цветов может выполнять функции 4,6 - измерительный участок, 7 - радиолокационный скоростемер, 8 - устройства заполнения путей.
В дальнейшем нас будет интересовать спускная часть сортировочной гор ки и подгорочный парк, где зачастую приходится, например, переставлять не
которые отцепы на другие участки пути, т.е. проводить маневровые работы. Планирование и оптимизация маневровых работ являются одним из резервов повышения перерабатывающей способности автоматизированных сортировочных горок. Необходимость в осаживании и перестановках отцепов возникает:
1. Из-за сбоев в процессе роспуска: некоторые вагоны попадают не на свой путь - ситуация «чужак»; другие не докатываются до путей подгорочного парка - ситуация «нет прохода»; если между вагонами уже сформированного состава имеются промежутки - ситуация «окно».
2. Нельзя производить роспуск с горки. Такая ситуация возникает:
- если в перевозочных документах на вагоны имеется штемпель «Не спускать с горки» или на вагонах и специальном подвижном составе имеется трафарет «С горки не спускать», благодаря вагонам с нарушенной документацией, которые необходимо отогнать на специально отведенные пути до привода в порядок докумеїггов и выяснения направления их следования;
- не подаются на горку вагоны с грузами отдельных категорий, к примеру, с живностью, взрывоопасными веществами, хрупким грузом - шифером или стеклом. Маневры с ними должны производиться осаживанием или «съемом» локомотивом со стороны подгорочного парка, осторожно, без толчков и резких остановок.
- сортировке подлежат платформы и полувагоны, загруженные грузами боковой и нижней негабаритности 4-й, 5-й, 6-й степеней и грузами с верхней негабаритностыо 3-й степени, груженые транспортеры, локомотивы в недействующем состоянии, моторвагонный подвижной состав, составы рефрижераторных поездов, пассажирские вагоны, краны на железнодорожном ходу и т.д.
В перерывах между роспусками маневровые локомотивы выполняют необходимые маневровые операции - сдвигают «окна», устраняют ситуации «нет прохода», переставляют на другие пути «чужаков» и т.п. Объективным требованием является определение таких маршрутов движения, которые позволяют локомотивам покрыть наименьшее расстояние (затратить минимальное время или энергию на работу).
Метод решения, использующий деревья поиска
Из существующих методов решения классической задачи коммивояжера одним из наиболее эффективных является метод ветвей и границ. При разработке метода ветвей и границ для решения задачи нескольких коммивояжеров в приведенной выше формулировке возникают трудности с определением нижних границ целевого функционала задачи. Количество коммивояжеров непостоянно. Сколько маршрутов будет содержать оптимальное решение заранее неизвестно. Нижние границы функционала задачи с s коммивояжерами вообще говоря не ограничивают функционал задачи с меньшим количеством агентов. Границы в задаче одного коммивояжера отличны от границ в задаче другого. Следовательно, метод ветвей и границ возможно применять лишь для тех задач, где количество и состав коммивояжеров фиксированы. Идея разработанного метода, использующего деревья поиска, состоит в последовательной генерации каждой допустимой выборки т коммивояжеров из s имеющихся, формировании задачи конкретных т коммивояжеров, и ее решении методом ветвей и границ.
Первым делом рассмотрим алгоритм решения задачи с фиксированным количеством агентов, равным т. Поскольку метод ветвей и границ для задачи коммивояжера достаточно подробно изложен в главе 1, остановимся только на изменениях, вносимых в метод в связи с рассматриваемой постановкой.
1) Сначала необходимо подготовить матрицу задачи (матрицу весов ис ходного графа) для работы алгоритма, запретив те ее элементы, которые заве домо не входят в допустимые решения. Положим равными бесконечности (большому числу): - элементы главной диагонали матрицы; - веса всех дуг графа, входящих в at и выходящих из bt, i=\,m, т.е. все элементы столбцов а,- и строк bit i-\m становятся равными бесконечности (эти строки и столбцы можно вычеркнуть); - элементы матрицы, соответствующие дугам вида (aifbj), i,j = \,m, что бы непосредственной связи между концевыми точками маршрутов не было.
2) В процессе работы алгоритма включение очередного звена (х,у) мар шрута в частичное решение приводит к образованию некоторого пути от пунк та q к пункту р (в простейшем случае q = x и р=у). При этом следует рас сматривать возможности наложения запретов на элементы матрицы в следую щем порядке. - если дфц и р Ф fy, і = 1, т, то следует положить элемент (р, q) равным бесконечности для предотвращения образования контура, не содержащего никакие из щ и , / — 1»/п; - равенства q- а,- и p=bh /І,т означают, что получен один из маршрутов искомого допустимого решения. Количество сформированных маршрутов/увеличиваем на единицу: / := / +1 (в начале работы / = 0). - теперь следует просмотреть каждый меньший бесконечности элемент (х,у) текущей подматрицы: нужно ли его запретить? Чтобы ответить на этот вопрос, необходимо знать к чему привело бы последующее присоединение данного звена к частичному решению. Звено запрещается в двух случаях.
1. В случае, когда в данный момент m-f=\, а присоединение дуги (х,у) дает путь между пунктами q и р, где q=ah p=bn /є1,/и. Равенство m f=\ означает, что неопределенным остался единственный маршрут. Чтобы предотвратить его преждевременное образование, сформировав таким образом т маршрутов, охватывающих менее п городов, полагаем вес (х,у) равным бесконечности.
2. Если в настоящее время выполнено неравенство m-f \, а включе ние в частичное решение звена (х,у) приводит к образованию пути между пунктами q ир, причем q=ah p = bj, i,je\,m, іФ j. Так как подобные мар шруты не являются допустимыми по условию задачи, запрещаем включение звена (х,у).
3) Опишем теперь способ вычисления нижних границ целевого функционала. Возьмем произвольное допустимое решение рассматриваемой задачи с фиксированными т коммивояжерами. Как и в классической задаче коммивояжера, каждая строка и столбец преобразованной на первом этапе матрицы весов задачи т коммивояжеров содержат единственное звено, входящее в это допустимое решение. Следовательно, при вычитании из какой-либо строки или столбца преобразованной матрицы весов некоторого положительного числа, величина Jx, очевидно, изменится на то же самое число.
Сведение многокритериальной задачи к однокритериальной
Данный подход получил название «свертывание критериев». Заключается он в том, что по исходным критериям Fk и показателям их важности рк, k = \,N производится построение одного синтезирующего критерия F, называемого сверткой критериев/ . Будем предполагать, что все критерии требуют минимизации. Это достигается преобразованием рк: A = рк , если Fk требует минимизации, -рк, если Fk требует максимизации. Обобщенная составляющая F, подлежащая минимизации, может быть: - аддитивным функционалом, т.е. «взвешенной суммой» отдельных со ставляющих: F = YpkFk, k = lN; - мультипликативным функционалом, т.е. «взвешенным произведением» отдельных составляющих: -обобщенным логическим критерием оптимальности: F = max {6kFk}, либо F = max {Ffk}; - среднестепенным обобщенным критерием оптимальности: - какой-либо другой формой свертки критериев.
Данный подход приводит к частным задачам: выбору вида свертывающей зависимости и расчету коэффициентов (показателей) рк. Это требует дополнительного исследования и не относится к кругу вопросов, рассматриваемых в настоящей работе.
Процедура свертывания обладает тем недостатком, что малоэффективное значение одного критерия может быть скомпенсировано хорошим значением другого. Возникает также проблема объективности: адекватный выбор коэффициентов рк невозможно осуществить посредством какой-либо математической процедуры, и потому приходится обращаться к субъективным мнениям специалистов (экспертов).
Метод полного перебора и эвристический алгоритм легко развиваются на случай решения многокритериальной задачи минимизацией одного синтезирующего критерия, каким бы он ни был. Порядок работы методов останется прежним, изменится лишь формула вычисления значения критерия качества допустимых решений, генерируемых по мере работы. Что касается метода, использующего деревья поиска, его нужным образом модифицировать не удается.
Предположим, что мы выполнили приведение всех матриц { , }" ={ и зафиксировали в одной из них самый тяжелый нуль. Тот же элемент другой матрицы может быть не самым тяжелым нулем в ней, а то и вовсе ненулевым элементом. Если существуют частные критерии Fk, требующие максимизации, а не минимизации, ігужно вычислять не нижние, а верхние их границы. Таким образом, не ясно, по каким элементам производить ветвление и как вычислять нижние (или верхние?) границы свертки при наличии нескольких весовых матриц.
Второй способ перехода от многокритериальной задачи к однокритери альиой производит свертывание не критериев Fk, а элементов матриц {JK»}JJJ, к = 1, N. Из имеющихся N матриц образуем одну новую матрицу, используя одну из вышеперечисленных форм свертывающих зависимостей. Элементы уу обобщенной матрицы весов 0} при каждой фиксированной паре / uj мо гут иметь вид: N к. -л,=П(4 А; Р,Р 0; y0 = і ум к=1 - другой формы свертки.
После чего решаем обычную, сформулированную во второй главе задачу нескольких коммивояжеров на полученной матрице, применяя разработанные во второй же главе алгоритмы. Преимущество данного способа: нет проблем с развитием метода, использующего деревья поиска и комбинированного алгоритма для решения многокритериальной задачи в случае, когда все элементы матрицы весов 0} неотрицательны. Если же имеются отрицательные веса, метод, использующий деревья поиска, равно как и комбинированный алгоритм применять нельзя.
Учет специфики железнодорожного транспорта
Ранее предполагалось, что каждый локомотив в любое время может доехать до любой, требующей обслуживания, точки чтобы выполнить необходимые маневровые операции. Нужно было указать локомотивам наилучшие в некотором смысле маршруты движения, проходящие через все выделенные участки станции. Никаких дополнительных ограничений на структуру искомых маршрутов не накладывалось. На рисунках 4.5-4.9 рассматривалась ситуация «нет прохода» на пути Ш и П2, хотя точек для выполнения маневров П1 и П2 не содержали. Предположим, что Ш и П2 содержат такие точки. Тогда локомотив не сможет в них побывать, не устранив предварительно имеющуюся ситуацию «нет прохода» (см., например, рис. 4.18). Таким образом, одни обслуживания иногда должны быть выполнены строго раньше, чем некоторые другие. Благодаря данному обстоятельству появляется необходимость частичного упорядочения всех маневровых операций. Вводятся условия предшествования, вытекающие из технологии нормализации процесса роспуска, т.е. условия вида «работа х должна быть сделана прежде, чем начнется работа у». При этом будем говорить, что операция предшествует операции у, либо что у следует за , и коротко записывать х у. Заметим, что отношение порядка -с транзитивно: при х .у и y z выполнено также x z. Будем говорить, что операция непосредственно предшествует операции у (или у непосредственно следует за ), если х у и не существует такой работы z, что z у. Обозначение х«у. Всю совокупность условий предшествования удобно изобразить в виде бескон 109 турного графа типа того, что представлен на рис. 4.15. Каждому отношению х-«у соответствует дуга, идущая от вершины х к вершине у. Граф может иметь несколько компонент связности. На рисунке две компоненты связности. Граф приоритетов в обслуживании
Требуется найти такое решение задачи нескольких коммивояжеров, чтобы в первую очередь удовлетворялись условия предшествования, а уже во-вторых значение критерия качества было бы минимально возможным. Наличие условий предшествования приводит к необходимости рассмотрения среднего времени движения локомотива между точками путевого развития станции в качестве весов ребер графа исходной задачи.
Помимо условий предшествования вводятся дополнительные критерии эффективности решения рассматриваемой задачи. Дело в том, что маршруты, составляющие решение, могут иметь общие части. Поскольку тепловозы не могут одновременно находиться в одной точке, объективным условием является прохождение общих отрезков пути в различное время. В случае, когда, согласно полученному решению, общий отрезок проходится приблизительно в один и тот же момент времени, некоторые локомотивы будут вынуждены делать остановки, пропуская другие, что нежелательно. Снизится ожидаемый эффект от привлечения к работе нескольких локомотивов вместо одного. Возможно возникновение «пробок», недопустимое увеличение времени выполнения маневров. Работы станут менее безопасными, повысится вероятность ошибочных действий и сбоя. Новый критерий Jy минимизирует общее количество пересечений маршрутов независимо от времени, а критерий J4 не позволяет локомотивам одновременно находиться в одном и том же месте.
Чтобы подсчитать значения критериев J$ и J4 полученного на некотором шаге множества маршрутов, а также обеспечить выполнение условий предшествования, нам понадобятся множества чисел vn(i, х) и Т х, i=\,m, х = l,size. Здесь / представляет номер маршрута, m - текущее количество маршрутов, через х мы обозначили вершину начального графа G0, size - количество всех вершин Go (базовых, иебазовых и остальных). Будем также пользоваться обозначением x(i,j): вершина х, находящаяся в маршруте / по порядковому номеру у. x(i,0) = aj. Каждая вершинах встречается в маршруте / 0, 1 или несколько раз. Найдем число попаданий х в /. Результаты запишем в виде матрицы vn. Элементы vn(i, х) равны количеству вхождений вершины х в маршрут / .
Величины Т х представляют время прибытия /-го локомотива в вершину х. Начальные значения Тгх(іщ являются исходными данными, и должны быть заданы до начала работы алгоритма. Начальные величины Т щ интерпретируются как время старта локомотивов, стартующих, вообще говоря, не одновременно. В связи с этим формула вычисления длины L маршрута / изменится, и примет вид Цювое = x(i,Q) + старое \ -Ч Каждое значение T j) вычисляется через предыдущее {ij-i) п0 ФР" муле ?ки) = тки-\)+Ф(и-ЪЛШ (4.3)
Особое значение имеют величины Ти - так обозначается момент посещения одним из локомотивов участка станции и, где нужно побывать для выполнения маневра. Все числа Ти находятся среди чисел Т х . Отдельно выпишем Тц для каждой точки и, требующей маневра.
