Geum.ru
Темы диссертаций по экономике » Математические и инструментальные методы экономики

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



Автореферат



Ученая степень кандидат экономических наук
Автор Карпов, Александр Вениаминович
Место защиты Санкт-Петербург
Год 1993
Шифр ВАК РФ 08.00.13

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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

КАРПОВ АЛЕКСАНДР ВЕНИАМИНОВИЧ

ЗАДАЧИ МАРШРУТИЗАЦИИ И ИХ ПРИЛОЖЕНИЕ К СИСТЕМАМ УПРАВЛЕНИЯ ПРОМЫШЛЕННЫМ ЖЕЛЕЗНОДОРОЖНЫМ ТРАНСПОРТОМ.

08.00.13 - экономико-математические метода

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата экономических наук

На правах рукописи УДК 519.85 '

САНКТ-ПЕТЕРБУРГ 1993

Работа выпонена на кафедре прикладной математики и кибернетики Петрозаводского государственного университета.

Научные руководители : доктор технических наук, профессор Чернецкий В.И.,

кандидат экономических наук, доцент Кузнецов В.А.

Официальные оппоненты: доктор физико-математических наук, профессор Романовский И.В.,

кандидат экономических наук Трофимов A.A.

Ведущая организация : Институт технической кибернетики Академии наук Белоруссии.

Защита диссертации состоится "/f" CiiCa^P 1993 г. в / часов на заседании специализированной Совета Д.063.57.43 по защите диссертаций но соискание ученой степени доктора экономических наук при Санкт-Петербургском государственном университете по адресу : I9II94. г.Санкт-Петербург, ул. Чайковского, д.62, ауд. 301.

С диссертацией можно ознакомиться в научной библиотеке им. А.М.Горького Санкт-Петербургского государстиешюго университета.

Автореферат разослан ". "U>j>ifz-P 1993 г.

Ученый секретарь специализированного Соьета. кандидат экономических наук

A.B. Монахов

Общая характеристика работа :

Актуально.с тъ томи . .Большие простои подвижного состава (порожних и груженых вагонов) на железнодорожных станциях промышленных предтриятий и огромные штрафы выплачиваемые предприятиями приводят к необходимости создшш." автоматизированных систем оперативно-диспетчерского управлегатя (ОДУ) процессами сортировки, погрузки и выгрузки вагонов, приемом и отправкой составов, регулированием движения транспор'пшх средств (ТС) на территория железнодорожного цеха (ЖДЦ) промпредприятия.

В системах ОДУ ЖДЦ значительное место занимают задачи планирования перевозочного процесса (координации графиков работа грузовых фронтов и локомотивных бригад), тесно связанные с задачами своевременного обеспечения производства всеми видами ресурсов и сбыта готовой продукции. Несвоевременное обеспечение предприятия ресурсами и порожними вагонами под погрузку готово!! продукции шкет привести к гуцествешшм материалышм и финансовым потерял, снижению уровня производства в целом. Но менее важной является проблема снижения сверхнормативного простоя вагонов на ЖДЦ и огромные страфя выплачиваемые предприятием.

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

В рамках диссертационной работы рассматриваются задачи оптимизации маршрутов движения ТС с ограничениями на сроки и порядок выпонения рейсов, в которых учитываются особенности организации перевозочного и грузового процессов на ЖШ предприятия.

Среди огромного количества публикаций по данной теме (а доступной автору литературе) вопросам постановки зада1: маршрутизации с ограничениями накладываемыми на маршруты ТС и расписания выпонения рейсов для критерия минимизации суммарного штрафа за задержку и запаздывание рейсов уделяется незначительное место. Большинство подобных задач является крайне сложными для рез-.-нл;!.

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

В диссертации предложены формулировки задач маршрутизации ТС п форме задач комбинаторной оптимизации и целочисленного линейного программирования, в которой аф(октивно учтены ограничения накладываемые на порядок и сроки выпонения рейсов заданным парком ТС. Формулируются экономически обоснованные критерии оптимизации расписаний расписаний выпонения рейсов.

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

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

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

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

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

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

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

Практическая ценность .Прсдложзшше модели задач маршрутизации ТС и расписания выпонения рейсов и методы их решения могут быть Использованы при разработке программного обеспечешш систем оперативно-диспетчерского управления транспортом, что позволит более эффективно использовать ЭВМ при планировании грузовой и коммерчерской работы транспортной службы промышленного предприятия.

Практическая реализация . Внедрение результатов диссертационной работы (из-за многоплановости и сложности информационного и технического обеспечения) осуществлялось автором совместно с колективом кафедры прикладной математики и кибернетики Петрозаводского государственного университета и сотрудников отдела АСУ Архангельского ЦБК. Результаты работы нашли отражешге а отчетах кафедры по НИР.

Апробация работы . Основные результаты диссертационной работы обсуждались на сем:шарах кафедры прикладной математики и кибернетики Петрозаводского государственного университета (1989-1993 г.), научном семинаре кафедры экономической кибернетики экономического факультета Санкт-Петербургского государственного университета (1992-1993 г.), научном семинаре Института технической кибернетики АН Белоруссии (Минск, 1993 г.). IX-й Белорусской школе-семинаре "Математические методы исследования систем и сетей массового обслуживания" (Минск, 1993 г.) и международной конференции "Новые информационные технологии в образовании и управлении" (Петрозаводск, 1993 г.).

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

Структура и о о т. ом работы. Работа состоит из введения, 3 глав, общего заключения, списка литературы, включающего 65 наименований, и приложения. Объем диссертации соста-ьил 133 страницы машинописного текста, включая приложение.

Содержание работы :

Во введении обосновывается актуальность темы диссертационной работы и ее практическая значимость для решении задач оперативно-диспетчерского управления на промышленном железнодорожном транспорте (ОДУ ВДГ). Определяются цели и ограничения, учитываемые в постановке задач маршрутизации ТС и расписания выпонения рейсов.

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

Приводятся краткая характеристика и основные результаты каждой главы диссертации и результаты выносимые на защиту.

В первой главо вводится необходимый математический аппарат для описания процессов ОДУ ВДГ : планирования и управления поро-возками, обработки вагонов, грузовой и транспортной работ железнодорожной станции промпредприятия. Анализируются факторы, влия-щие на общее время оборота вагонов, вынужденные простои, потери (материальные и Финансовые) из-за простоя вагонов, снижение объемов производства (отгрузки) продукции в результате несвоевреме-ной организации подачи вагонов под погрузку и выгрузку.

Сформулирована задача оптимизации маршрутов движения тепловозов (ТС) выпоняющих Фиксированное количество взаимосвязанных рейсов подачи и уборки вагонов к грузовым фронтам с ограничениями на сроки испонения рейсов. И задаче требуется отыскать оптимальный способ назначения ТС на рейсы, последовательность и Фактические моменты Времени ВЫНОНеНИЯ ВСе.Х рейсов СООТВеТСТВушЩШИ ТС, при котором достигается минимум суммарной величины штрафа за задержу и запаздывание рейсов относительно сроков испонения.

И постановке задачи предполагается известным множество номо-[<он рейал> W ( ( 1 ,;',.. .п.п< 1 ,.. ,гнт) И ТС М (1,;\..,т), где ПЧ' р-.йс . связанный с пш.о.'ми ТС с номером ptM на маршрут. Задано

множество A=f(i,j)| i=j }, на kotojwm введено'отношение строгого

предшествования мижду рейсами, и граф редукции отношений предшествования G(N.Л). Параметрами задачи являются :

tjj - время выпонения рейса j<H ТС с номером рсЫ (время на переход ТС между пунктами начала к окончания этого рейса).

- время перехода ТС с номером piM с ройса цно па рейс jtN0 (между пунктами окончания рейса i и начала ройса j).

[a^.b^I - интервал времени выпонения ройса ji!J.

dtJ - мекрейсовий интервал (время, которое дожно пройти с момента начала рейса J до момента начала ройса j, V(i,j)cA ).

Fj(t)- штраф (потери) за задержку рейса Jdl на время t>o.

Hj(t)- штраф (потерн) за запаздшшшо ройса Jt.II на время tx>.

1, если ТС с номером р<Ц переходит с рейса i на рейс J

в противном случае

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

Oj - фактический момент начала рейса с номером J<M.

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

I (wv + W) Ч* mln <1Л9)

при ограничениях :

l I x?. = 1. Vi(NД

ptU jcN0\li>

p(U itN0\{,1)

V i H,

i.H0\(k)

JN0\(k>

кр = k j

O. VlnN. VpU

BJ - [5i

Dj + 1 5!ti'j(ti',lil'T) * T< VI",cH (liJ)" 1-tM

га,,, vd.jja .

л Ц y|

*J % "J % uj ' *J

X'({0,1}, y, i O, Vi,JiHn (l/j), VptM .

В данной задаче ограничения (Г.20)-(I.21) требуют выпонения каждого рейса только один раз и одним ТС , (1.22)-(1.23) задают условия связности маршрутов движения ТС , (1.24)-(1.25) требуют выпонения рейсов в заданном порядке и в заданные сроки.

В задаче (I Л9)-(1.26) используется m(mtn)2 булевских и 2п нипреривных поремонных, при общем количестве ограничений порядка п2+1 А| ( (гит)(т+2 ). С шел и назначение ограничений (1.23) обосновываются в доказанных Теореиах 1.1 и 1.2, в которых устанавливается невозможность образования недопустимых маршрутов ТС. Задача маршрутизации ТС в форме (1.1Э)-(1.26) относится к NP-трудным. В реальных нроизводствешшх условиях приходится решать задачи с числом ТС от 5 до 10 и числом рейсов до

Существование решения задачи (I.19)-(1.26) устанавливается в Теореме 1.3 в предположении босконтурности орграфа G(N,A), задающего частичный порядок выпонения рейсов, и свойств неубывания функций штрафа за задержу и запаздывание рейсов.

Значения перемешшх xVj , удовлетворяющих системе ограничений (I.20)-{I.23) и (1.26) , задают множество всех маршрутов ТС И1'=(р[1 ].р[2], ..,р[п1>]) в соответствии с формулами :

р(1]--п+р, р[И1]= I j'Xpii] j Х i=,nnP . 'Р--" Х (I-I3)

где pli) - номер рейса, выпоняемого i-м по порядку ТС с номером Р'.М, а ар - общее число рейсов выпоняемых этим ТС.

Пусть R-(R1 ,R?,.. ,Rm) - совокупность маршрутов движения ТС.

Для последующего анализа задачи (I.I9)-(I.2G) в з 1.2 при -водятся несколько экономически обоснованных критериев оитимиза Х ции маршрутов движения ТС и расписания выпонения рейсов.

Обозначим через Пд - множество маршрутов, допустимых относительно заданного градом G(H,A) порядка вшгронения рейсов.

Пусть S{S1 ,SR,. ,Srn) - совокупность расписаний (моментов начала) выпонения рейсов определенных маршрутами движения ТС, гдо SP-{!V(1 ]",в1.[пр]) и ap[il ~ i,!lKTl,'K;CKl,n момент начала i-ro по порядку рейса в маршруте ТС с номером чН. Оптимальность расписаний выпонения рейсов оценивается ригулярными функционалами : п

I HnHVU 11 mait4[iJ(25pUI)b

in.Mi ; 1 Mi ,rj

В качестве функций fjij) берутся Функции штрафа (потерь) за задержу или запаздывание рейсов, т.о.

Vj(sj) = Pj(Sj-aj) ИЛИ <Pj(Sj) = Hj(maxie .-b }).

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

Р1 = min { F2(S)iHj,(S) ) - минимум суммарнпых потерь от задержки и запаздывания всох рейсов для расписания S;

Р2 = min { P^iS) } - минимум потерь от задержки рейсов ;

F-j = min { Hv.(S) } - минимум потерь от запаздывания рейсов ;

F4 = min { Fmax(S) } - минимум наибольших потерь от задержки рейсов ;

F^ = min С H,n4X(S) ) - минимум наибольших потерь от запаздывания рейсов ;

F6_g - критерии, в которых учитываются время, затрачиваемое ТС на холостые рейсы; г-.ремя окончания работы последнего ТС и т.д.

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

В последующих разделах главы рассматриваются вопросы понижения размерности задачи (1.19)-(1.26), в нроднолоиошш идентичности всех ТС, и практического использования критериев оптимизации.

Во второй главе анализируются основные частныо постановки задач маршрутизации движения ТС и расписания выпонения рейсов для которых известны полиномиальные агоритмы построения оптимальных расписаний и имеющие приложение к задачам ОДУ ХДТ.

В з 2.1 предлагается удобная система обозначений для частных задач маршрутизации вида : li/A/a/b/d/F , где М - число и тип ТС, А - отношения предшествования , (а,Ь] - сроки выпонения рейсов, d - межрейсовые интервалы, р - критерий оптимальности (п^ТТэ). Анализируется связь изучаемых задач с задачами теории расписаний.

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

Г! 5 2.3 изучаются задачи развозки с ограничениями на порядок выпонения рейсов (расписание подачи и уборки вагонов к грузовым Фронтам предприятия) линейными функциями штрафа и критерия минимизации времени уборки самой последней грутш вагонов.

Каждая группа вагонов определяет два взаимосвязанных рейса ictf0 - рейс подичи вагонов к грузовому фронту, iHj - рейс уборки после выпонения грузовой операции (с тем же номером). Тогда множество всех рейсов связанных с обслуживанием грузовых фронтов составляет N = Nu U N,. Будем считать известным : - время ви-понения рейса подачи и уборки и dj - время выпонения грузовой операции для 1-й группы вагонов, =1,п . Рассмотрим процосс подачи и уоркц вагонов на подъездные пути грузовых фронтов, осуществляемый одним ТС по критерию минимума времени окончания уборки самой последний группы вагонов, задачу типа 1/С/о/ш/о/Р^ .

Обозначим через it=(ic[i I ,и[2 J,.. ,u[ii]) - порядок выпонения рейсов подичи вагонов к грузовым фронтам, о=(о[1],о(г],.,о[п]) -порядок выпонения рейсов уборки вагонов. Расписание обслуживания грузовых фронтов будем обозначать через R-(n,o). Будем считать, что все рейсы подачи вагонов предшествуют рейсам уборки.

В Утвердденим 2.5 устанавливается, что расписание R--(i.o) оптимально для рассматриваемой задачи, если выпоняются условия:

1 [о[к) ] яГ1 olkfl ] ]

I Чш + do[k] л 2 4uil4Wi] (2-30) 1=1 1=1 п п

I *о[1| - <Ч[к] > 1 l0[i] - лWn ] (2-ЗГ)

i=0~'[U(k]] i-О 1(H[к 11 ) ]

где iT1(i]=(o~1(11)'k означает, что группа вагонов i подается (убирается) к-й по порядку в последовательности тс(о). Vk-i^rvT.

Для отыскания оптимального расписания подачи/уборки вагонов, удовлитворящего условиям (2.30)-(.31), предлагается коночноша-гоьый агоритм, в котором начиная с произвольного расписания подачи % отыскивается, согласно условия (2.30), расписание уборки o(it), затом для найденного расписании о=о(и) отыскивается, согласно условия (2.31), расписание подачи и(о). Повторений действий производится До тех пор, пока расписании f-(t.a) изменяется.

И 0 2.4 изучаются задачи маршрутизации ТС с ограничениями на срони выпонения рейсов тина M'^J/a/b/O/P, _г . Для частных слу чаев утих задач приводятся известные из теории расписаний свойства ошималышх расписаний или устанавливается их КГ-трудноеть.

Tf"'iDi глава inici.niU'Mia вопросам разработки численных методов fx-aviiiW задач маршрутизации ТС и расписания ьыпчднишш рейсов. В

осново предлагаемых приближенных методов решыАш рассматриваемых задач (типа М/А/а/Ь/с1/Р1) лежит принцип ветвей и границ, включающий схему декомпозиции по ограниченном (лагранжевой релаксации) и субградионтной оптимизации для получения более точных оценок снизу оптимума целевого функционала. Предлагаются и Осуждаются различные схемы декомпозиции 1ю 01'раничениям, основанные на ви-доло1ШИ в структуре ограничений рассматриваемых задач сетевых подструктур. Достаточно много внимания уделяется изучению задачи минимизации суммарной взвешенной задержки рейсов выпоняемых однотипными или одним ТС. Предполагая линейность соответствующих функций штрафа за задержку рейсов, приходам к задаче :

л("^-а^ - гп1п (3.3)

с ограничениями :

1 (3.4) }

2 хи =Х <3-ь> 1сЫ0\{Л)

вА - в^ + (11П1/Т)х,1, л Т, VI,сМ, Ш . (3.6)

в., - в1 > , У(и)(А . (3.7)

с^ > aj , VсЫ . (3.8)

х^ао.П. . (3.9)

Порядок выпонения рейсов определяется переменными :

1 , осли рейс ,1сЫ0 выпоняется непосредственно после

рейса (безразлично каким именно ТС). О , в противном случае .

В 5 3.2 рассматриваются и сопоставляются несколько различных способов ослабления условий (снятием ряда ограничений) в задаче (З.З)-(З.Э), достоинства в сравнении с ослаблением условий цело-числинности переменных (линейной релаксации).

В основе предлагаемого способа декомпозиции рассматривается лаграяжеьа релаксация ограничений (3.4) и решение двойственной задачи (п качестве оценочной подзадачи) с использованием субгра-диентпых методов для оценки снизу оптимума задачи (3.3)-(3.9).

Поставив в соответствие ограничениям (3.4) вектор двойственных переменных 1кг"1'п, запишем двойственную функцию Щи), значе-

нии шжгой определяется решением оценочно!! задачи :

Ми) = 2 WjBj 1 "ixi;J - min (3.15)

jt'n icN0jлN0\{j)

рнничтшями (3.5) - (3.0).

Точное решение задачи (ЗЛ5) при любом фиксированном векторе двойственных переменных u(F)n,m определяет опенку снизу оптимума исходной задачи (3.3)-(3.9). Для уточнения оценки снизу используется копечношаговый итерационный процесс отыскания приближенного вектора двойственных переменных :

к1 к к к uKt1 = u + hK.fi, (u )--сЧ:k-0,1,2,... (3.22)

Ieb(u I

где еь(к) - субгродионт функции (L (и) в точке ukili, (L - оценка сверху для оптимума (3.3), )Л>о - шаг перемещения.

Выбор субградиептных методов (3.22) обоснован показан.ими в Теорема* 3.1 и 3.2 свойствами кусочной линейности, вогнутости и недифференцируемости двойственной функции 0_(и).

Компоненты субградионта е^ир определяются невязками ограничений .(3.4). Установление предельного числа шагов в (3.22) объясняется линейной скоростью сходимости (при соблюдении определенных свойств последовательности А.к) итерационного процесса.

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

Пусть ориентированный граф G(Nq1B) описывает структуру допустимого решения задачи (3.15), множество дуг которого определяется следующим образом В = {(i, j) . Vi,jtN0).

В доказанной Теореме 3.4 устанавливается, что каждая компонента связности орграфа G(No,B) является выходящим (растущим) 1-деревом. Тогда оценочной задаче (3.15) соответствует задача построения выходящего 1-дерево такого, что взвешенная сумма расстояний от корневых зершин дерева до всох остальных вершин была наименьшей. Для задачи построения 1-дорева с заданной структурой используется модификация известного агоритма Эдмовдса - Кг-ч-ч с полиномиальными оценкаЩ сложности.

Для задачи минимизации взвешенной задержки рейсов без ограничений на сроки и порядок выпонения (типа 1/{0}/о/л>/Ч/Р2) вместо точного решения оценочной задачи (3.15) предлагается приближенный метод на основа решения двойственной к ней задачи.

Предварительный анализ структуры орграфа С^.В*), отвечающего оптимальному решению вспомогательной задачи (3.15), позволяет установить необходимые свойства этого орграфа, а имешго :

и^, УЦ.ЗКВ*. (3.39)

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

Вычислительный эксперимент с использованием схемы декомпозиции по ограничениям (3.4) для задачи (З.З)-(З.Э) показал, что оценки снизу для оптимума целевой функции (3.3) оказываются болев точными (порядка 56% от оптимума) в сравнении с аналогичными оценками, полученными снятием целочисленности переменных (порядка 35%) и приводят к необходимости исследования значительно меньшого числа вершин дерева ветвления в методе ветвей и границ. Иные способы ослабления ограничений, например, ослабление условий связности (3.6), оказываются менее эффективными.

При проведетга эксперимента использовались результаты моделирования входного потока составов и распределения вагонов на основе статистических данных о работе железнодорожного цеха Архангельского целюлозно-бумажного комбината за 1991 год. В соответствующих постановках задач маршрутизации учитывалась структура ЩЩ, технология обработки вагонов и состав парка ТС. Соот-воствующие данные приведены в приложении к диссертации. При планировании работ ЩЩ Архангельского ЦБК на одну смену (8 часов) максимальное число рейсов не превосходит 100, а число локомотивов от 5 (летний период) до 10 (зимний).

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

В 5 3.3 предлагаются несколько эвристических агоритмов рсЧ

шония исходной задачи (3.3)-(3.9). Описываются схемы назначония ТС па рейсы в порядка их освобождения , основанные на специальных правилах назначения приоритетов рейсам (статических и динамических) с учЗтом сроков и порядка их выпонения. Для задач ма~ р1; 'утизации ТС общего вида, в которых учитываются многие ограничения, агоритмы эвристического типа дают достаточно хорошие решения. Сравнительный анализ различных методов решения задач маршрутизации ТС позволяет надеяться на существенное (порядка 10) сокращение вынужденных простоев вагонов и уменьшение штрафов, выплачиваемых предприятием, хотя и не гаратируот выпонимости в заданные сроки всех рейсов. Результаты экспериментов показывают, что большинство эвристических агоритмов не гарантируют сокращения времени о'борота вагонов на ЖДЦ АЦЕК до нормативного, но приводят к уменьшению вынужденных простоев вагонов в ожидании пода-I! уборки к грузовым фронтам.

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

В приложетш представлены листинги irpoграмм, реализующих предложенные агоритмы, описание ЖДЦ Архангельского ЦБК как объекта управления, приведены татистические данные о его работе за 1991 год, общая схема моделирования процесса поступления составов и распределения вагонов, результаты вычислительного эксперимента, акт о внедрении результатов диссертационной работы в промышленную эксплуатацию на Архангельском ЦБК.

Основные результаты диссертации отражены в работах :

1. Карпов A.B. Математические модели оптимизации плашгрования и управления колознодороззшм цехом ЦБК // Научно-технический прогресс и развитие науки / Тезисы докладов республиканской научно-практической конференции. Петрозаводск.-1987.-С 57.

2. Карпов A.B. Математическая модель задачи маршрутизации и расписания движения транспортных средств с допонительными ограничениями // Математическое моделирование народохозяйственных процессов. Петрозаводск / Петрозаводский гос. ун-т.-1990.-С.21-27.

3. Карпов A.B. Минимизация общего времени задержки при обслуживании одним прибором неодновременно поступающих требований без прорывания // Оптимизационные задачи и модели прикладной математики. Петрозаводск / Петрозаводский гос. ун-т.-1989.-С.16-20.

4. Кузнецов В.А., Карпов A.B. Математическая модель и метод решения задачи составления оптимального графика движения поездов с фиксировашшми маршрутами но пересекающимися во вромени // Оптимизационные задачи и модели прикладной математик.!. Петрозаводск. / Петрозаводский гос. ун-т.-1989.-С.21-25.

5. Карпов A.B. Оптимизация маршрутов движения транспортных средств с ограничениями на порядок и сроки выпонения рейсов//Труды Петрозаводского университета.Серия : прикладная математика и информатика. Выпуск I / Петрозаводский гос. ун-т.-1992.-С.82-90.

6. Кузнецов В.А., Воронин A.B., Карпов А.В, Поляков В.В. Задачи оптимизации в АСУ ремонтным производством // Новые информационные технологии в образовашш и управлении / Тезисы докладов международной конференции. Петрозаводск. -1993.-С. II2-II4.

Похожие диссертации