Диссертация (792664), страница 4
Текст из файла (страница 4)
Она используется в тренажере поездного диспетчера линии метрополитена [90] [91]; автоматизированной системе оперативного диспетчерского управлениядвижением поездов [92] [88]; автоматизированной системе энергооптимальных тяговых расчетов[93] [94] [95]; автоматизированной системе построения плановых графиков движенияпассажирских поездов [96] [97] [98] [99] [44]; автоматизированной системе оценки эффективности использованиярекуперативного торможения на электроподвижном составе метрополитена инакопителей энергии [93] [100].При построении графа, описывающего топологию линии метрополитена,используется несколько видов вершин, соответствующих следующим объектамлинии метрополитена: тупикам – смежные с одним ребром;20 краям платформы станций – смежные с двумя ребрами; изолирующим стыкам между рельсовыми цепями – смежные с двумяребрами; стрелкам – смежные с тремя ребрами.Связывающие вершины ребра объединяются в пути, описывающие путиреальнойлинииметрополитена.Построеннаяграфоваямодельлинииметрополитена позволяет моделировать движение поездов по главным истанционным путям в различных направлениях в соответствии с ПГД иликомандами поездного диспетчера.Для описания технологических процессов и алгоритмов управленияиспользуетсядискретно-событийноемоделирование.Распространеннымиспособами такого моделирования являются сети Петри и нотации бизнесмоделирования,которыевместесосхемамиалгоритмовявляютсяразновидностью графовых моделей.В ходе работ, выполненных на кафедре «УиЗИ» РУТ(МИИТ) построеныграфовые модели следующих процессов: реализуемых в тренажере поездного диспетчера линии метрополитена[90]; протекающих при управлении движением поездов в соответствии сплановым графиком движения или командами поездного диспетчера [92] [101] ; являющихся основой функционирования системы маршрутно-релейнойцентрализации линии метрополитена и систем обеспечения безопасностидвижения [92] [94] [102].Выбор той или иной формализации определяется задачами, для решениякоторых описание процесса используется.При решении задач управления графовые модели применяются дляиллюстрации работы дискретного варианта динамического программированияБеллмана, аналогичных или построенных на его основе методов решенияоптимизационныхзадач.Сихиспользованиемврамкахработпо21автоматизацииуправлениядвижениемпоездовметрополитенарешеныследующие задачи: выбора энергооптимальных режимов ведения поездов по перегонамметрополитена [93] [94]; оптимального по быстродействию восстановления движения поездовпо плановому графику после ликвидации причин возникновения больших сбоев[93] [100]; построения рационального по критерию равномерности назначенияосмотров сценария технического обслуживания электроподвижного состава[33].Входедиссертационногоисследованияразработаныследующиеграфовые модели: процессов,входящихвжизненныйциклграфикаоборотаэлектроподвижного состава и планового графика движения пассажирскихпоездов [29] [103]; автоматическогоосвобожденияопределенияуказателейночнойпоследовательностирасстановкизаполнениясоставовнаилинииметрополитена.В данной работе теория графов применена в 3 главе для решения задачиавтоматизированногоопределенияпоследовательностизаполненияиосвобождения указателей ночной расстановки составов на лини метрополитена.1.4 Опыт использования генетических алгоритмов для решения задачавтоматизации управления транспортными системамиГенетические алгоритмы (ГА) были формализованы Джоном Холландомв 1960-х годах и в дальнейшем разработаны его студентами и коллегами изМичиганского университета в 1960-х и 1970-х годах [104] [105].22При описании ГА используются определения, заимствованные изгенетики [106] [107].
В Таблице 1.2 представлены основные термины [108][109].Таблица 1.2 – Основные термины генетического алгоритмаТермин,заимствованныйиз генетикиПопуляция,поколениеОсобьХромосомаГенГенотипЛокусАллельФитнесфункцияМутацияАналогичныйОпределениетехнический терминсовокупностьособей (хромосом)конечноемножествоособей,рассматриваемоенаитерацииэволюциииндивидуум,генотип либо единичная хромосома,экземпляресли генотип состоит из однойхромосомыцепь,двоичная упорядоченные последовательностипоследовательность, геновцепочкаиликодоваяпоследовательность.Понятие«хромосомы»и«особи» совпадают,еслиособьописывается однойхромомсомой.свойство, знак или атомарный элемент генотипа, вдетекторчастности, хромосомыструктуранабор хромосом особиместоместоположение определённого генана генетической карте хромосомыодноиз форма состояния генов, занимающихальтернативныходни и те же локусы в хромосомах исостояний генаобусловливающих фенотипическиеразличия одного и того же признакацелеваяфункция мера точности решения или мерадляособей удовлетворения решению задачипопуляцииизменение генотипа стойкое (то есть такое, котороеможет быть унаследовано потомкамиданной клетки или организма)изменение генотипа, происходящееподвлияниемвнешнейиливнутренней среды.
Мутация изменяет23КроссинговерЭволюцияодно или несколько значений генов вхромосомеобмен генетическим основной генетический оператор, заматериалом между счет которого производится обменхромосомамигенетическим материалом междуособями,моделируетпроцессскрещивания особейпроцессПроцесс изменения популяция домоментавыполнениякритерияостановки алгоритмаВычислительныесистемы,основанныенатеоретическихиммунологических и генетических механизмах, в настоящее время широкоприменяются для решения разнообразных научных и технических задач [110].В частности, ГА [111] нашли широкое применения для решения задачавтоматизации управления транспортными системами, например, для: логистической организации городских пассажирских перевозок [112]; организации контейнерных перевозок [113]; управления морским транспортом [113]; решения транспортной задачи [114], [115]; решения задачи планирования проектных работ при создании средствавтоматизации [116]; решениязадачитестированияиповышенияконтролепригодностидискретных устройств [117] [118]; поиска максимума функции, оценки регрессионных и нелинейныхстатистических моделей [119]; решения задач визуализации и раскраски графов [120] [121].В данной работе генетический алгоритм применен в 4 главе для решениязадачи автоматизированного построения графика оборота электроподвижногосостава метрополитена.241.5 Постановка задачи научного исследованияСоздание систем поддержки принятия решения, к которым относятсясредства автоматизированного построения ПГД ППМ, предполагает разработкуразвитого математического обеспечения, которое определяет бизнес-логикусистемы, и соответствующего программного обеспечения.
В связи с этимактуальным является построение моделей автоматизируемых технологическихпроцессов или бизнес-процессов, которые в дальнейшем будем называть простопроцессами, в качестве основы для реализации следующих этапов разработкисредствавтоматизации.Этоявляетсяпервымнаправлениемданногодиссертационного исследования.Реализация процесса ухода составов на ночную расстановку наряду свыполнением заданной в виде функции времени парности движения в течениевсего времени движения пассажирских поездов и реализацией ГО являетсяцелью управления, на достижение которой направлено построение ПГД.Соответствующий сценарий построения ПГД должен учитывать информацию опоследовательностизаполненияиосвобожденияуказателейночнойрасстановки составов. В основу рекуррентной процедуры автоматизированногопостроения ПГД положен метод полного перебора вариантов построения ПГД.Учет всех возможных вариантов выхода из ночной расстановки в началедвижения и ухода на ночную расстановку в конце движения позволяетувеличить число рассматриваемых вариантов построения ПГД, повыситьвероятность нахождения решением поставленной задачи после рассмотренияменьшего числа вариантов, и повысить качество ПГД [96].
В связи с этимактуальнымявляетсяавтоматическоеопределениепоследовательностизаполнения и освобождения указателей ночной расстановки составов, котораяне была решена ранее. Раньше эта задача не была решена, поэтому в данномисследовании она является одним из направлений научного исследования.25Планированию технического обслуживания транспортных средств (ТС), вчастности построению ГО ЭПС метрополитена, посвящено большое числоработ.В работе [122] эта задача рассматривается как классическая задача оназначениях.Существует возможность рассматривать задача построения ГО ЭПСметрополитена как задачу о назначениях с изменяющейся во времени матрицейстоимостей [123] [124] [125].В работе [11] рассматривается задача организации эксплуатации итехнического обслуживания ЭПС железных дорог при наличии жесткихвременных ограничений в условиях открытого рынка – при наличиинескольких конкурирующих компаний, желающих участвовать в решении этойзадачи.Работы [59] [126] посвящены мониторингу технического обслуживания,ремонтаиэксплуатациивысокоскоростныхпоездов,использующемуинформацию, поступающую от RFID (Radio Frequency Identification) датчиков,и основывающемуся на обработке событий и семантики для оценкиэффективности анализируемой деятельности.В работе [53] выполнена строгая формализация задачи построенияпланирования технического обслуживания электроподвижного состава (ЭПС)метрополитена, построения графика оборота ЭПС (ГО), и приведено еёрешение с использованием методов теории графов [127] [128] и принципаоптимальности Беллмана [129].
Разработанный в статье метод решения задачидаетвозможностьполучитьвсёмножестводопустимыхназначенийобслуживаний и выбрать то, которое с одной стороны будет соответствоватьплановому графику движения поездов метрополитена (ПГД), а с другой –минимально отличаться от оптимального по выбранному критерию, что имеетбольшое практическое значение. Оценка сверху мощности множестваполученных вариантов построения ГО имеет порядок 109 [53]. Их перебортребует значительных затрат времени.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
