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

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

Борознов Владимир Олегович

00348ЭБ

Управление процессом расформирования железнодорожных составов на основе эвристических методов

05.13.06 «Автоматизация и управление технологическими процессами

и производствами» 05.13.01 «Системный анализ, управление и обработка информации».

Автореферат

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

о 4 ДЕК 2009

Астрахань - 2009

003489614

Работа выполнена на кафедре «Информационная безопасность» в государственном образовательном учреждении высшего профессионального образования «Астраханский государственный технический университет»

Научный руководитель: доктор технических наук, профессор

Попов Георгий Александрович

Официальные оппоненты: доктор технических наук, профессор

Лукьянов Виктор Сергеевич

кандидат технических наук, Алексеев Александр Викторович

Ведущая организация: Волгоградский государственный университет

Защита состоится "_25_" декабря 2009 г., в _12-00_ часов на заседании диссертационного совета Д.307.001.01 в Астраханском государственном техническом университете по адресу: г. Астрахань, ул. Татищева, 16, главный корпус, ауд. 305

С диссертацией можно бзнакомиться в библиотеке АГТУ по адресу: г. Астрахань, ул. Татищева, 16, главный корпус

Автореферат разослан £с0а?5~2009 г.

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

диссертационного совета Д.307.001.01 доктор технических наук, профессор

Попов Г.А.

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

Актуальность темы

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

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

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

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

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

Объект исследования — сортировочная железнодорожная станция.

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

Цель и задачи исследования. Целью исследований является повышение эффективности управления процессом

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

1. Проведен системный анализ технологического процесса работы сортировочной станции.

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

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

4. Проведено экспериментальное сравнение методов и алгоритмов с целью выявления наиболее эффективных по выбранному автором критерию.

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

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

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

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

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

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

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

5. Проведен сравнительный анализ эффективности различных "эвристических методов и алгоритмов поиска решения рассматриваемой задачи.

На защиту выносятся

1. Математическая модель технологического процесса работы

сортировочной станции по роспуску составов.

2. Процедура формирования множества задач в процессе

функционирования железнодорожной сортировочной станции.

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

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

Практическую ценность имеют:

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

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

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

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

5. Предложенный метод поиска оптимальных решений для комбинаторных задач, а также метод адаптации алгоритмов, которые используются в учебном процессе в Астраханском государственном техническом университете (АГТУ) при преподавании дисциплины «Алгоритмы направленного перебора».

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

Публикации. Основные результаты работы опубликованы в 9 статьях, в том числе в 3 - в изданиях по перечню ВАК, и материалах 5 конференций.

Структура и объем работы. Диссертация состоит из введения, четырёх глав основного текста, списка литературы из 102 наименований, заключения и 4 приложений, общим объемом 130 страниц. В работе содержится 21 рисунков и 17 таблиц.

Основное содержание работы

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

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

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

Решение данной оптимизационной задачи является резервом повышения эффективности работы сортировочной станции, резервом повышения её

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

При решении задачи о порядке роспуска поездов на сортировочной станции потребуется производить расчёт за время меньшее, чем технологическое время формирования/расформирования состава, или доверительный интервал автоматизированной системы оперативного управления перевозками, равный 15 минутам. Это связано с изменением ситуации на полигоне, а также с грузовой работой станции.

Приведен обзор наиболее перспективных методов решения рассматриваемой ЫР- задачи: точных, эвристических, а также методов, основанных на алгоритмах поиска: генетическом и муравьином. Л'Р-полнота подразумевает, что поиск ведется в пространстве, растущем от N неполиномиально, и, соответственно, вычислительная сложность алгоритмов, основанных на полном переборе или на построении дерева решений, растет экспоненциально от N. Эти алгоритмы способны решать задачу лишь для малого N (ТУ » 20) за время вычислений, лежащее в разумных пределах. Именно поэтому для решения сложных задач используются различные эвристики.

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

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

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

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

f(x) —> min,

леМВП

где МВП - множество вариантов порядка формирования/расформирования составов;

/(х) - функция простоя вагонов на сортировочной станции за план х;

х - план порядка формирования/расформирования составов на сортировочной станции.

В данной функции присутствуют 3 основные составляющие: поезда, идущие в расформирование; поезда, находящиеся под накоплением и сформированные поезда.

Поезда, идущие в расформирование, обозначим как noe3d[x[f]f - количество вагонов в x\j] поезде в направление Z, где Z = 1, Н. Тогда последовательность

N Н

роспуска поездов будет иметь вид ^]ГЯоезф.-[/]]-' . Вагоны, находящиеся под

J-1 т-1

накоплением, обозначим как Накопление-- количество вагонов под накоплением в направление Z, где Z= 1, Н. Следует отметить, что после роспуска очередного, у-го состава количество вагонов, находящихся под накоплением, изменяется:

И

1?=1(Накоплениег ) + У) Новзд[ 4J]]' .

1-1

После накопления группы вагонов согласно плану формирования осуществляется формирование поезда. Введем вспомогательную переменную ^, которая показывает, имеется ли достаточное количество вагонов для формирования поезда в направление 7..

и

1,при у Накопление* > Мин.усл.дл.

¡гааче, 0

Введем дополнительную переменную хпр1,6, которая показывает, стоит поезд в ожидании расформирования на станции: хприб = 1 или нет: *„р„а=0. Для начисления простоя по данным вагонам сделаем привязку ко времени. Примем: ¿0-начальное время простоя; /™'и- время прибытия поездов на станцию, где j

= I, И; - технологическое время формирования поезда;

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

я н

/С*) = 2Д»жМ ^(Накопление* +

1-1 ж=1

1-1

Л

(тфибпхзд тфл£пое\ \ 1

'»О! ~ е*£/-1Л

¿=1

Существуют два способа отправления поезда: по жесткой нитке графика либо по диспетчерской. Жесткие нитки графика составляются службой перевозок и могут изменяться в случае изменения грузопотоков. Если поезд готов к отправлению, а ближайшая нитка графика значительно удалена по времени, поезд может быть отправлен по диспетчерской нитке.

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

начисления простоя для сформированного поезда, а именно:

т^ ~ /- - Тфьбпоеад А-оы

Временной интервал будет увеличен до — + +

следующей нитки в направление 2.

Если время до следующей нитки графика велико, диспетчер может проложить свою нитку графика, поэтому данное ограничение примет вид

(».- = ( «■"-> махс.врсмяожаднш. то ^ = время до свободной нитки;

( иначе, нормативное вреднасоставление нитки.

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

№ = - да^)^!^! ^»(Накопление?) +

н м

3=1 «=1

Н И

^"Хь'{накоп-тен,,е')(^6п"гл - +»¿г->+

а=1 #=1

1 И 24

г=1 «=1

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

на сортировочной станции, введением коэффициентов при расчёте значения целевой функции.

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

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

ВУ-метод основан на анализе имеющегося эталонного маршрута и его оптимизации. Решение условно состоит из двух этапов: 1) получение начального решения; 2) оптимизация начального решения.

Начальное решение представляет собой лучшее решение из всех решений, полученных на основе «жадного» метода.

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

Перед применением ВУ-модификаторов необходимо построить матрицу А оценок. На основании матрицы А выявляются неоптимальные участки в эталонном маршруте. Процесс построения ВУ-матрицы:

- строится матрица А размерами N х IV, первоначально заполненная нулями;

- затем, путём просматривания N построенных «жадных» маршрутов, последовательно формируется А [р,

- для каждой пары соседних вершин р и д соответствующий элемент матрицы оценок А [р, д/ увеличивается на единицу.

Дальнейшее преобразование эталонного маршрута заключается в последовательном применении ВУ-модификаторов к каждой паре вершин,

которым соответствует ненулевой элемент матрицы оценок. Каждый ВУ-модификатор в качестве параметра вызова получает р \\ ц (позиции) двух вершин, которым в ВУ- матрице сопоставлено любое ненулевое число. При каждом вызове каждый ВУ- модификатор хранит в себе наилучшее значение модифицированной целевой функции и пары вершин. После прохода по всей ВУ-матрице из всех ВУ-модификаторов выбирается наилучшее значение модифицированной целевой функции и сравнивается с эталоном. Если модифицированный маршрут имеет превосходство, то он становится эталоном, а в матрице оценок для данной пары вершин р ид присваивается значение - 0. Проход по матрице оценок повторяется до тех пор, пока модифицированные маршруты имеют превосходство над эталоном. Превосходство или равенство эталона над модифицированным маршрутом говорит о том, что полученное решение является конечным для данного метода решения.

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

| Начало )

_1_

Получение опорного решения I

I

_I _

Эталонное решение = опорному решению

Вызов Ьу - модификаторов |

Выбор лучш ей модификации I

j Решение улучшилось? {___..__

Конец |

Рис. 1. Упрощенная блок схема ВУ-метода

Эталонное решение лучшей модификации

Отличительные особенности ВV-метода:

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

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

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

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

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

В этой же главе представлены результаты сравнения рассматриваемых в работе методов и ВУ-метода на основе задачи коммивояжера как частного случая квадратичной задачи о назначениях, дана их практическая временная сложность и эффективность. Так, приведена апробация методов на задачах ЕНоп'в 50, ЕНоп'б 75.

Для каждой задачи размерности N проводилось по 33 испытания, что соответствует доверительной вероятности 0,75 и ошибке 0,1. Случайным образом строилась матрица расстояния заданной размерности N, после чего задача решалась четырьмя методами. Генетический алгоритм был взят со следующими параметрами: вероятность кроссинговера - 0,85; вероятность мутации - 0,1; критерий окончания эволюции следующий: за последние 20 поколений целевая функция не улучшилась. Параметры муравьиного алгоритма: глобальное испарение СЕ = 0,5; локальное испарение ЬЕ — 1; параметр баланса между использованием накопленных знаний и исследованием новых решений д0 = 0,3; начальное значение феромона -0,0001; Муравьёв = N. Среднее отклонение считалось относительно ВУ-метода. Результаты моделирования представлены в таблице.

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

Таблица. Относительная ошибка методов

N _ Рцсл исюю ^В *.ппо/ Лис. метода с ШЧ/о

Эвристические методы Алгоритмы поиска

Метод включения дальнего, % ВУ-метод, % Генетический, % Муравьиный, %

20 7,99 0,00 2,85 0,78

40 11,56 0,00 3,81 2,04

60 13,18 0,00 3,54 1,89

80 13,89 0,00 5,27 1,81

100 14,04 0,00 5,05 2,03

Согласно результатам исследования, ВУ-метод превзошел все рассматриваемые алгоритмы, уступив лишь методу включения дальнего в «быстродействии» (рис. 2).

16

14

Л и

о

X

3 <и а.

с. О С

12

10

20 40 СО 80 100

N, размерность задачи

-мвд.%

ГА,% • АС5-а %

Рис. 2. Относительная погрешность методов Эвристические алгоритмы - бесспорные лидеры по быстродействию, кроме того они показывают хорошее соотношение качество/время. Точные

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

На основе пакета ЭБРБ для рассматриваемых алгоритмов была произведена оценка временной сложности. Экспериментально сложность алгоритма полного перебора была оценена как I = 0,0056 • е<и788Л,); метода ветвей и границ / = 0,0745 метода ветвей и границ с пользованием эвристики

для получения стартового начального решения «жадным» методом / = 0,3164 • с'0-74® '". Метод включения дальнего (= 28,06 -1,6069 • N + 0,0227 ВV-метод оценен как * = -169,4 +15,5786-ЛГ-0,4Ю4-//2 + 0,004-лг3; генетический алгоритм г = 683 - 42,467 • N +1,0696- Л?2; муравьиный алгоритм

( = 4437,6 - 293- N + 4,6779- Ы2.

На основе полученных зависимостей построим оценочные кривые (рис. 3).

10000000 1000000

О 20 40 60 80 100 N

Рис. 3. Оценочные кривые временной сложности методов

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

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

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

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

Из плана автоматически будем исключать поезда, не подлежащие расформированию на сортировочной станции:

- с номером, начинающимся на 5ххх, и количеством вагонов меньшим 20 (рабочие поезда);

- поезда со станции формирования в индексе меньшем 0099 (пассажирские поезда и одиночные локомотивы);

- поезда со станцией назначения в индексе меньшем 0020 (поезда, идущие в регулировку).

В случае использования АСОУП-2 можно отказаться от использования запросной системы и перейти на 8(ЗЬ-запросы, при этом общая схема решения задачи не изменится (рис. 4). Наиболее целесообразно использовать также собственную базу данных для хранения информации о вагонах, находящихся под накоплением. Это позволит уменьшить число запросов к АСОУП и хранить дополнительные сведения, в частности сведения о физическом местоположении вагонов после расформирования.

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

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

Рис. 4. Общая схема решения задачи Для алгоритмов, использующих поэтапное построение решения, адаптация не понадобится. Использование эвристических алгоритмов, таких как «венгерский» и метод включения дальнего невозможно. Это связано с тем, что данные алгоритмы используют в своей работе параметры, которых нет в условиях задачи. В частности, матрица стоимости пересчитывается на каждом этапе (после расформирования поезда), т. к. её значение изменяется вследствие изменения количества вагонов, находящихся под накоплением, на

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

В качестве объекта внедрения результатов исследования целесообразно выбрать крупную железнодорожную сортировочную станцию, т. к. сложность решения задачи по определению порядка формирования/расформирования железнодорожных составов растёт экспоненциально, по мере увеличения количества поездов. Отметим, что чем больше нагрузка на сортировочной станции, тем больший эффект будет получен в результате автоматизации процесса определения очередности роспуска составов. В связи с этим наиболее целесообразно рассмотреть крупные сортировочные станции России, такие как Алтайская, им. Максима Горького и Инская (показатель роспуска - 120-130 поездов в сутки).

В решение задачи будем включать не все поезда, а только попадающие в интервал планирования — 12 часов. Условно примем, что количество поездов в двух сменах равное. Это позволяет нам примерно оценить размерность решаемой задачи, для того чтобы определиться, каким из методов её целесообразно решать. Для станций Инская, Алтайская, им. Максима Горького возможно применение только эвристических алгоритмов. Посмотрим, как изменяется эффективность предложенного метода в зависимости от количества поездов в планируемом интервале, при условии, что маневровый диспетчер действует по принципу «жадного» алгоритма.

Для выбора метода решения было проведено компьютерное моделирование. Для каждой задачи размерности N проводилось по 33 испытания, что соответствует доверительной вероятности 0,75 и ошибке 0,1. Случайным образом генерировались N поездов длиной 65-85 вагонов, а также вагоны, находящиеся под накопление, согласно плану формирования, - 0-65. Затем задача решалась четырьмя методами. Минимальная длина поезда для всех направлений - 80 вагонов, количество групп под накоплением - 20. Время расформирования поезда 720 мин/(ЛГ + 2), поезда прибывают последовательно, через случайный интервал 1 мин - (720 мин/(Л<' + 2)) 2. Генетический алгоритм был взят со следующими параметрами: вероятность

кроссинговера — 0,85; вероятность мутации - 0,1; критерий окончания эволюции следующий: за последние 20 поколений целевая функция не улучшилась, размер популяции = N. Параметры муравьиного алгоритма: глобальное испарение СЕ ~ 0,5; локальное испарение ЬЕ ~ параметр баланса между использованием накопленных знаний и исследованием новых решений <7о = 0,3; начальное значение феромона - 0,0001; муравьев = N. Для выбора метода решения задачи о порядке роспуска составов на сортировочной станции проведем испытания, используя интересующие нас размерности задачи - 2080. Относительная эффективность рассчитывалась относительно «жадного» метода (чтобы наглядно показать в процентах эффективность использования того или иного метода) по следующей формуле:

. _ Решттс получешюе_"жадньи1'_алгор11тмол^Рештае_тлучеиное_рассматришшьш_ттодам ^ | «^у "ч* ~ Решение_полуиенное^_рассматришсмым_л1етодол1 0

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

4.6

ВУ-метод

Генетический алгоритм

Муравьиный алгоритм

40 60

Размерность задачи

Рис. 5. Эффективность рассматриваемых методов

Простой вагона под накоплением - величина непредсказуемая и для каждой станции является индивидуальной. Примем в качестве метода решения задачи ВУ-метод, а его эффективность - равной 3,762 % (как худшую на интервале 20-80).

Общий приблизительный эффект по сокращению простоя вагона под накоплением по всей России за одни сутки составит: 57*5.5*4800= 56,6 тыс.ваг ч.

Это оценка является крайне приближенной, т. к. каждая сортировочная станция индивидуальна и имеет свои нормы простоев и количества вагонов, перерабатываемых в сутки. Следует учесть также допущение, что в расчёт приняты лишь крупные сортировочные станции. Можно дать оценку эффективности в денежном эквиваленте на основе тарифного руководства. Примем среднюю плату за пользование как среднеарифметическое по родам подвижного состава за простой в час. Один час простоя = 24 руб., тогда общая экономия в сутки составит 56,6 тыс. ваг ч 24 руб./ч = 1,358 млн. руб.

Можно дать примерную оценку влияния сокращения времени простоя вагона под накоплением на весь перевозочный процесс. Если принять, что в среднем вагон от пункта отправки до пункта назначения проходит четыре сортировочные станции и среднее время простоя на сортировочной станции равное 5,5 ч, то получим: 4*5.5 * 0.03762 = 50 мин.

Основные результаты и выводы

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

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

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

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

5. .Получена оценка эффективности, сокращения времени простоя вагонов, находящихся под накоплением, от использования автоматизации решения задачи о порядке роспуска поездов на сортировочной станции, которая оказалось равной 3,76%.

6. Дана оценка воздействия сокращения времени простоя вагонов под накоплением на весь перевозочный процесс. На основе полученной оценки найдено значение сокращения времени доставки груза, которое оказалось равным 50 минутам.

7. Автоматизация процесса определения порядка роспуска составов позволяет более грамотно использовать нитки графика грузового движения поездов и планировать поездную работу на более длительный период.

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

Статьи в журналах, рекомендованных для защиты кандидатских

диссертаций

1. Борознов В. О., Ведерникова О. Г. Исследования генетических методов решения задачи коммивояжера // Вестник Ростовского государственного университета путей сообщения. - 2004. - № 1. - С. 42-45.

2. Борознов В. О. Адаптация генетических алгоритмов для решения транспортной задачи // Вестник Астраханского государственного технического университета. - 2006. - № 1. - С. 81-88.

3. Борознов В. О. Дополнение метода ветвей и границ для решения задачи коммивояжера на плоскости // Вестник Астраханского государственного технического университета.-2007,-№ 1.-С. 160-163.

Статьи в российских журналах

4. Борознов В. О. Исследование эвристического метода решения задачи коммивояжера // Электронный журнал «Исследовано в России». - 2008. -С. 322-328 /http://zhumal.ape.relam.ru/articIes/2008/028.pdf.

5. Борознов В. О. Построение модели для задачи о порядке роспуска составов на сортировочной железнодорожной станции // Вестник Астраханского государственного технического университета. -2007. - № 6.-С. 178-182.

6. Борознов В. О. Некоторые аспекты формирования поездов при решении задачи по определению порядка роспуска составов на сортировочной железнодорожной станции // Журнал научных публикаций аспирантов и докторантов. - 2008. - № 4. - С. 194-196.

7. Борознов В. О. Оценка эффективности метода решения задачи «Определение порядка роспуска составов на сортировочной железнодорожной станции» // Вестник Астраханского государственного технического университета. Серия: управление, вычислительная техника и информатика. - 2009. - № 1. - С. 82-87.

8. Борознов В. О., Попов Г.А. Некоторые аспекты формирования поездов при решении задачи по определению порядка роспуска составов на сортировочной железнодорожной станции // // Вестник Астраханского государственного технического университета. Серия: управление, вычислительная техника и информатика. - 2009. - № 2. - С. 13-21.

9. Борознов В. О. Оценка эффективности метода решения задачи «Определение порядка роспуска составов на сортировочной железнодорожной станции» // // Вестник Астраханского государственного технического университета. Серия: управление, вычислительная техника и информатика. - 2009. - № 2. - С. 147-151.

Печать: Астраханская цифровая типография, г. Астрахань, пл. К. Маркса, 33. Формат 60x84 1/16. Усл.печ. л. 1,38. Тираж 100 экз. Заказ № 13293 Подписано в печать 24.11.2009.

ВВЕДЕНИЕ.

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

1.1. Постановка задачи.

1.2. Аналитический обзор разработок, связанных с поставленной задачей.

1.3. Анализ возможных методов решения задачи.

1.4. Точные, эвристические и поисковые методы решения задачи.

1.4.1. Точные методы решения.

1.4.1.1. Алгоритм полного перебора.

1.4.1.2. Метод ветвей и границ.

1.4.2. Эвристические алгоритмы.

1.4.2.1. Метод включения дальнего.

1.4.3. Генетические алгоритмы и алгоритмы поиска.

1.4.3.1. Генетический алгоритм.

1.4.3.2. Муравьиные алгоритмы.

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

Актуальность темы

Железнодорожный транспорт имеет важное стратегическое значение для России, являясь одной из основ транспортной инфраструктуры страны. От общего объёма перевезённых грузов по всей России на долю железных дорог приходится 38 % [1].

В последнее время, в связи с ежегодным увеличением объёмов железнодорожных перевозок, особенно остро встает вопрос о повышении эффективности функционирования железнодорожного транспорта (рис. 1). В 2003-2007 гг. темпы прироста объемов железнодорожных перевозок крупнотоннажных контейнеров составили в среднем 11 % в год [2]. Прогнозируемые темпы роста железнодорожных перевозок - увеличение объема в 2 раза за предстоящие 10 лет. Следует отметить возросшее количество транзитного груза, идущего по территории России. В среднем его увеличение составляет 12 % в год [3]. Именно поэтому развитию железнодорожного транспорта в настоящее время уделяется особое внимание.

18000000 16000000 14000000 г 12000000 g 10000000 8000000 6000000 4000000 2000000 0

2005 2006 2007 2008 Г°Д Погружено вагонов Рис. 1. Динамика увеличения погрузки по России

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

Процесс внедрения информационных технологий на железнодорожном транспорте был начат в середине 80-х гг. XX в. Именно в эти годы была внедрена автоматизированная система оперативного управления перевозками (АСОУП), которая в настоящее время является центральным звеном всех АСУ железнодорожного транспорта РФ [4].

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

С целью анализа эффективности процесса перевозок при проведении диссертационного исследования были рассмотрены основные этапы перевозочного процесса с момента погрузки до прибытия груза на станцию назначения (рис. 2). к

0? I

X о э с;

X аа

CS се f- Q. и с

S- о

Сортировочная станция (расформирование, накопление, формирование)

Сортировочная станция (расформирование, накопление, формирование)

Сортировочная станция (расформирование, накопление, формирование)

05 к S

S X

X г>

X ЯЗ н У СЗ X и й X

Рис. 2. Схема процесса следования вагона от станции отправления до станции назначения

Из рис. 2 видно, что в перевозочном процессе присутствуют повторяющиеся звенья - сортировочные станции. Их место в перевозочном процессе двойственно. С одной стороны, они являются центрами формирования грузовых потоков, с другой - механизмом управления потоком и его распределения на основе плана формирования [5].

Исключением являются маршрутные поезда, которые следуют из пункта отправления в пункт назначения без переработки на сортировочных станциях. Это позволяет им увеличивать скорость до 550 км/сут и сокращать время доставки грузов. Использование маршрутов позволяет снизить эксплуатационные расходы (сортировочная станция не участвует в перевозочном процессе), а также увеличить пропускную способность за счёт увеличения средней скорости поезда. Но доля маршрутных поездов мала - 5 % [6].

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

За время движения от пункта отправления до пункта назначения вагон проходит сортировочный процесс на нескольких сортировочных станциях, что значительно увеличивает время доставки и уменьшает скорость поездов до 350 км/сут [7]. Это связано с временными затратами на переработку составов: их сортировку, накопление и формирование. Наиболее значимым является время ожидания вагона под накоплением, т. к. оно превосходит на порядок остальные показатели.

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

I ACTpjxJHb-2 I А*слрлй{кля-2 > им M Горького

200S 2006 2007

ГОД

2003

Рис. 3. Время накопления состава на различных сортировочных станциях

В среднем на крупных сортировочных станциях России простой одного вагона в ожидании накопления составляет около 5,5 часов (рис. 4) [8].

4SOO ----- -------- ---------------------------------го 2500 I I 1 I ■ Амарайск.зя-2 1500 +— Я— "Я В -------------8 ■ Им.М.Горького

2005 2006 2007 2008

ГОД

Рис. 4. Среднесуточный простой вагонов на сортировочных станциях

Среднее время нахождения вагона под накоплением зависит от количества вагонов, находящихся под накоплением на сортировочной станции. Простой вагонов в сутки, выраженный в абсолютных единицах (ваг*ч), по станции Астрахань-2 в несколько раз меньше простоя по станции им. Максима Горького, несмотря на то, что среднее время простоя вагонов по станции Астрахань-2 больше. В настоящее время средний суточный простой крупной сортировочной станции составляет порядка 20-35 тыс. ваг*ч [4]. Сокращение времени простоя вагонов на сортировочной станции позволяет существенно снизить эксплуатационные затраты. В целом по России за одни сутки убытки от простоя вагонов на крупных сортировочных станциях составляют примерно 33,4 млн руб. Сокращение времени нахождения вагонов на сортировочной станции всего лишь на 1 % позволит увеличить рентабельность отрасли на 121 млн руб. в год (глава 4).

Мероприятия по сокращению времени простоя вагона на сортировочных станциях проводились неоднократно. Так, например, для повышения эффективности эксплуатационной работы сортировочных станций в 90-е гг. по сети дорог было проведено внедрение комплекса систем автоматизированного управления сортировочной станцией (КСАУ СС), включающего в себя:

- расширение зоны автоматизации до размеров всей станции;

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

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

В системе КСАУ СС реализована интеграция двух систем:

- комплексной системы автоматизированного управления сортировочным процессом (КСАУ СП), реализующей автоматизированное управление горочными стрелками, сигналами, замедлителями, маневровыми локомотивами и т. д.;

- автоматизированной системы управления сортировочной станцией (АСУ СС), обеспечивающей реализацию информационно-управляющих задач и функций планирования работы станции.

В рамках КСАУ СС, помимо традиционного набора автоматизированных рабочих мест работников станционного технологического центра, реализованы автоматизированные рабочие места станционного и маневрового диспетчеров, машиниста компрессорной установки, машиниста маневрового локомотива и т. д.

Важнейшей частью системы являются средства взаимодействия информационно-планирующего уровня АСУ СС с техническими средствами КСАУ СП. Для АСУ СС автоматически готовится информация о прибытии поезда, отцепке и уходе поездного локомотива, установке и снятии ограждения состава, расформировании состава. Это позволило значительно повысить объективность и своевременность данных об этих операциях. Внедрение КСАУ СС позволило сократить простои вагонов на 20-30 %, сократить эксплуатационные затраты, в том числе за счёт создания малолюдных технологий; повысить безопасность станционных технологий [9]. Тем не менее КСАУ СС имеет существенный недостаток - принятие решений о порядке роспуска составов возложено на маневрового диспетчера, хотя все исходные данные для автоматизированного решения задачи по определению порядка роспуска железнодорожных составов на сортировочной станции имеются.

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

Ю].

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

На основе решенных задач целесообразно разработать автоматизированную систему поддержки принятия решений (СППР), которая может быть применена для решения задач, возникающих в процессе расформирования и формирования поездов [101]. Для внедрения СППР может быть выбрана любая крупная сортировочная станция, такая, например, как станция им. Максима Горького, Инская, Алтайская (с количеством поездов в расформировании не менее 25 поездов за смену). Таким образом, поставленная задача является актуальной.

Объект исследования - сортировочная железнодорожная станция.

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

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

1. Проведен системный анализ технологического процесса работы сортировочной станции.

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

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

4. Проведено экспериментальное сравнение методов и алгоритмов с целью выявления наиболее эффективных по выбранному диссертантом критерию.

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

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

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

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

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

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

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

5. Проведен сравнительный анализ эффективности различных эвристических методов и алгоритмов поиска решения рассматриваемой задачи.

На защиту выносятся:

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

2. Процедура формирования множества задач в процессе функционирования железнодорожной сортировочной станции.

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

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

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

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

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

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

5. Предложенный метод поиска оптимальных решений для комбинаторных задач, а также метод адаптации алгоритмов, которые используются в учебном процессе в Астраханском государственном техническом университете (АГТУ) при преподавании дисциплины «Алгоритмы направленного перебора».

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

Публикации. Основные результаты работы опубликованы в 9 статьях, 3 из них - в изданиях по перечню ВАК, и материалах 5 конференций.

Структура и объем работы. Диссертация состоит из введения, четырёх глав основного текста, списка литературы из 102 наименований, заключения и 4 приложений, общим объемом 130 страниц. В работе содержится 21 рисунок и 17 таблиц.

ЗАКЛЮЧЕНИЕ

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

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

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

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

5. Проведено компьютерное моделирование с целью определить наиболее приемлемый метод решения данной задачи, выбран оптимальный метод решения.

6. Получена оценка эффективности сокращения времени простоя вагонов, находящихся под накоплением, от использования автоматизации решения задачи о порядке роспуска поездов на сортировочной станции, которая оказалась равной 3,76 %.

7. Дана оценка воздействия сокращения времени простоя вагонов, находящихся под накоплением, на весь перевозочный процесс. На основе полученной оценки найдено значение сокращения времени доставки груза, которое оказалось равным 50 минутам.

8. Автоматизация процесса определения порядка роспуска составов позволяет более грамотно использовать нитки графика грузового движения поездов и планировать поездную работу на более длительный период.

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

1. Юсупов В. А. На основе логистических технологий //Л Железнодорожный транспорт. 2008. - № 8. - С. 18-23.

2. Пресс-Центр. 22.04.2008 «ТрансРоссия-2008» / http://gzd.web.rzd/wps/portal/gzd?STRUCTUREID=4254&layerid=3854&id=104 561.

3. Доклад Министра транспорта Российской Федерации И. Е. Левитина на совместном заседании коллегии Министерства транспорта РФ, Правительства Москвы и Правительства Московской области 30 сентября 2008 год / http://www.mintrans.ru/pressa/Levitin300909.htm.

4. Тулупов Л. П., Жуковский Е. М., Гусятинер А. М. Автоматизированные системы управления перевозочными процессами на железных дорогах. М.: Транспорт, 1991. - 208 с.

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

6. Кудрявцев В. А. Управление движением на железнодорожном транспорте. М.: Маршрут, 2003. - 200 с.

7. Перепон В. П. Организация перевозок грузов: учеб. для студ. техникумов и колледжей. М.: Маршрут, 2003. - 614 с.

8. Управление эксплуатационной работой и качеством перевозок на железнодорожном транспорте / под ред. П. С. Грунтова. М.: Транспорт, 1994.- 543 с.

9. Сотников Е. А., Левин Д. Ю., Алексеев Г. А. История развития системы управления перевозочным процессом на железнодорожном транспорте. М.: Техинформ, 2007. - 237 с.

10. Савин В. И. Перевозки грузов железнодорожным транспортом: справ, пособие. М.: Дело и сервис, 2007. - 760 с.

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

12. Бородин А. Ф., Биленко Г. М., Олейник О. А., Бородина Е. В. Технология работы сортировочных станций // учеб. пособие. М.: РГОТУПС, 2001.-192 с.

13. Первозванский А. А. Математические модели в управлении производством. -М.: Наука, 1973. 615 с.

14. Буянов В. А., Ратин Г. С. Автоматизированные информационные системы на железнодорожном транспорте. М.: Транспорт, 1984. - 239 с.

15. Гершвальд А. С. Оптимальное управление процессами работы базовой станции опорного центра // Железные дороги мира. 2002. - № 6 / http://www.css-rzd.ru/ZDM/06-2002/02125-1 .htm.

16. Шапкин И. Н. Информационные технологии в организации перевозок // Железные дороги мира. 2003. - № 4 / http://www.css-rzd.ru/ZDM/04-2003/03035.htm.

17. Липатов Е. В. Теория графов и её применение. М.: Знание, 1986.32 с.

18. Булгаков И. В., Неймарк Б. А. Решение задачи коммивояжера с помощью генетических алгоритмов // Вестн. Нижегород. ун-та им. Н. И. Лобачевского. Сер.: Математическое моделирование и оптимальное управление. 1998. - № 2. - С. 186-192.

19. Просветов Г. И. Методы оптимизации. М.: Альфа-Пресс, 2009.168 с.

20. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: Вильяме, 2006. - 1296 с.

21. Овчинников В. А. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем: учеб. для вузов. -М.: Изд-во МГТУ им. Н. Э. Баумана, 2001. 288 с.

22. Просветов Г. И. Математические методы и модели в экономике. Задачи и решения. М.: Альфа-пресс, 2008. - 344 с.

23. Курейчик В. М. Генетические алгоритмы. Обзор и состояние // Новости искусственного интеллекта. 1998. - № 3. - С. 14-63.

24. Рутковская Д., Пилиньский М., Рутковский JI. Нейронные сети, генетические алгоритмы и нечеткие системы. М.: Горячая Линия — Телеком, 2006. - 452 с.

25. Приходченко Н. Н., Шкурат Т. П. Основы генетики человека. -Ростов н/Д: Феникс, 1997. 360 с.

26. Букатова И. Л. Эволюционное моделирование и его приложения. -М.: Наука, 1979. 232 с.

27. Букатова И. Л., Михасев Ю. И., Шаров А. М. Эвоинформатика. Теория и практика эволюционного моделирования. М.: Наука, 1991. - 206 с.

28. Айала Ф. Введение в популяционную и эволюционную генетику. -М.: Мир, 1984.-230 с.

29. Чернышев Ю. О., Буракова А. В. Исследование генетических методов решения задачи коммивояжера // Интеллектуальные САПР: междувед. темат. науч. сб. Таганрог, 1995. - Вып. 5. - С. 33-36.

30. Курейчик В. М. Применение генетических алгоритмов для решения комбинаторно-логических задач оптимизации // Интеллектуальные САПР: междувед. темат. науч. сб. Таганрог, 1995. - Вып. 5. - С. 242.

31. Батищев Д. И., Скидкина Л. Н., Трапезникова Н. В. Глобальная оптимизация с помощью эволюционно-генетических алгоритмов // Оптимизация и моделирование в автоматизированных системах: сб. науч. тр. -Воронеж: Воронеж, техн. ун-т, 1994.

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

33. Kling R. М., Banerjee P. Empirical and Theoretical Studies of the Simulated Evolution Method applied to standart Cell Placement // IEEE Trans, on CAD. 1991, October. - Vol. 10, N 10.

34. Курейчик В. В. Бионические методы решения задачи коммивояжера // Вестн. Южного науч. центра РАН. 2005. - Т. 1, № 4. - С. 87-92.

35. Grefenstette J., Gopal G., Rosmaita В., D. van Gucht. Genetic algorithms for the traveling salesman problem // Artificial Intelligence Review. -Springer Netherlands. P. 129-170.

36. Shahookar K., Mazumder P. A genetic approach to standard cell placement using metagenetic parameter optimization // IEEE Transactions on Computer-Aided Design. 1990, May. - 9 (5). - P. 500-511.

37. Гладков JI. А., Курейчик В. M., Курейчик В. В. Генетические алгоритмы. Ростов н/Д: ООО «Ростиздат», 2004. - 400 с.

38. Dorigo М., Maniezzo V., Colorni A. Ant system: optimization by a colony of cooperating agents // Systems. 1996. - Vol. 26, N 1. - P. 29-A\.

39. Gambardella L. M., Taillard E. D., Dorigo M. Ant Colonies for the Quadratic Assignment Problem // The Journal of the OperationalResearch Society. -1999. Vol. 50, N 2. - P. 167-176.

40. Dorigo M., Gambardella L. M. Ant colonies for the travelling salesman problem / // BioSystems. 1997. - Vol. 43, N 2. - P. 73-81.

41. Курейчик В. M., Кажаков А. А. О некоторых модификациях муравьиного алгоритма // Изв. Южного федер. ун-та. Техн. науки. Таганрог, 2008.-№4.-С. 7-12.

42. Dorigo М., Gambardella L. М. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem // IEEE Trans, on Evolutionary Computation. 1997. - № 1 (1). - P. 53-66.

43. Dorigo M., Stiitzle Т. Ant Colony Optimization. Cambridge: MIT Press, 2004. - 305 p.

44. Сагатовский В. H. Основы систематизации всеобщих категорий. -Томск: ТГУ, 1973.-432 с.

45. Дьяков Ю. В., Расулов М. JI. Технология перевозок и график движения // Железнодорожный транспорт. 1991. - № 4. - С. 7-12.

46. Левин Д. Ю. Как повысить эффективность работы дорожных диспетчеров // Железнодорожный транспорт. 2006. - № 10. - С. 12-16.

47. Шапкин И. Н. Информационные технологии в организации перевозок // Железные дороги мира. 2003. - № 4 // http://www.css-rzd.ru/ZDM/04-2003/03035.htm.

48. Буянов В. А., Кондрахина Н. В. Жесткий график движения поездов в среде информационных технологий организации перевозок // Вестн. Всерос. науч.-исслед. ин-та железнодор. транспорта. 2001. - № 4. - С. 3-7.

49. Тертеров М. Н. Доставка скоропортящихся грузов. М.: Транспорт, 1992. - 168 с.

50. Ковалев В. И. Организация вагонопотоков на сети железных дорог России в условиях реформирования отрасли. СПб.: ИЦ «Выбор», 2002. -144 с.

51. Хушит Л. И. Общий курс железных дорог. М.: Маршрут, 2005.256 с.

52. Аль-Шумари А. С., Бадах В. И., Мокейчева И. А., Стрелков М. В. Технология переработки вагонопотоков на сортировочной станции: учеб. пособие. СПб.: ПГУПС, 2003. - 68 с.

53. Шелухин В. И. Автоматизация и механизация сортировочных горок. М.: Маршрут, 2005. - 240 с.

54. Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989. - 360 с.

55. Гордеев А. В., Никитин А. В., Фильчаков В. В. Организация пакетов прикладных программ: учеб. пособие. Л.: ЛИАП, 1988. - 78 с.

56. Ван Тассел Д. Стиль, разработка, эффективность, отладка и испытание программ. М.: Мир, 1985. - 332 с.

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

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

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

60. Кэнту М. Delphi 5 для профессионалов. СПб.: Питер, 2001.944 с.

61. Бентли Д. Жемчужины творчества программистов. М.: Радио и связь, 1990. - 244 с.

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

63. Введение в математическое моделирование / под ред. П. В. Трусова. М.: Логос, 2004. - 440 с.

64. Самарский А. А., Михайлов А. П. Математическое моделирование: Идеи. Методы. Примеры. М.: Физматлит, 2001. - 320 с.

65. Инженерные расчеты на ЭВМ: справ, пособие / под ред. В. А. Троицкого. Л.: Машиностроение, 1979. - 288 с.

66. Адлер Ю. П. Введение в планирование эксперимента. М.: Металлургия, 1969. - 157 с.

67. Cohoon J. P., Paris W. D. Genetic Placement // IEEE Trans, on CAD. -1987, November. Vol. 6, N 6. - P. 956-964.

68. Kling R. Placement by Simulated Evolution. Master of science thesis. -Urbana, Illinois, USA, 1986.

69. Shahookar R., Mazumder P. Genetic Approoch to Standart Cell Placement Using Meta-Genetic Parameter Optimization // IEEE Trans, on CAD. -1990. Vol. 9.-P. 500-511.

70. Львовский Е. Н. Статистические методы построения эмпирических формул: учеб. пособие для втузов. М.: Высш. шк., 1988. - 239 с.

71. Митропольский А. К. Техника статистических вычислений. М.: Наука, 1971.-576 с.

72. Бююль А., Цефель П. SPSS: искусство обработки информации. -М.: ДиаСофт, 2005. 608 с.

73. Корнеев В. В. Параллельные вычислительные системы. М.: Нолидж, 1999. - 320 с.

74. Дикий А. А., Леонов А. А., Аршавский М. И. Параллельные вычисления при реализации метода ветвей и границ // Научная сессия МИФИ-2003: сб. науч. тр.: в 14 т. Т. 6. М.: МИФИ, 2003. -С. 268-269.

75. Арк М. А., Штуца И. М. Исследование вычислительной (временной) сложности генетического алгоритма на примере решения задачи коммивояжера // Вестн. Ижевского гос. техн. ун-та. 2008. - № 4. - С. 144-146.

76. Данилова Е. Ю., Городилов А. Ю. Сравнение генетических алгоритмов на примере задачи коммивояжера // Вестн. Перм. ун-та. Сер.: Математика. Механика. Информатика. 2009. - № 3. - С. 49-53.

77. Штовба С. Д., Рудый О. М. Муравьиные алгоритмы оптимизации // Вестн. Винницкого политехи, ин-та). 2004. - № 4. - С. 62-69.

78. Bullnheimer В., Hartl R. F., Strauss С. A New Rank-Based Version of the Ant System: A Computational Study // Central European Journal for Operations Research and Economics. 1999. - 1 (7). - P. 25-38.

79. Штовба С. Д. Муравьиные алгоритмы // Exponenta Pro: Математика в приложениях. 2003. - № 4. - С. 15.

80. Stutzle L., Hoos Н. Н. MAX-MIN Ant System // Future Generation Computer Systems. 2000. - N 8 (16). - P. 889-914.

81. Aarts E. H. L., Korst J. H. M„ Laarhoven van P. J. M. Simulated annealing // in Aarts E. Lenstra J. K. (Eds). Local search in combinatorial optimization. Chichester: Wiley, 1997. - P. 91-120.

82. Ковалев В. И. Управление парками вагонов стран СНГ и Балтии на железных дорогах России. М.: Маршрут, 2006. - 245 с.

83. Автоматизация технологических процессов в системе оперативного управления сортировочной станцией / Л. П. Кузнецов и др. Ростов н/Д: РИИЖТ, 1984.-78 с.

84. Сидорова Е. Н. Автоматизированные системы управления в эксплуатационной работе. М.: Маршрут, 2005. - 560 с.

85. План формирования грузовых поездов Приволжской железной дороги на 2007/2008 г. Саратов, 2007.

86. Расписание движения грузовых поездов по Астраханскому отделению. М., 2007.

87. Зорин 3. И. Развитие средств железнодорожной автоматики во взаимодействии с информационными системами // Автоматика, связь, информатика. 2002. - № 3. - С. 10-12 .

88. Тишкин Е. М. Автоматизация управления вагонным парком. М.: Интекст, 2000. - 224 с.

89. Левин Д. Ю. Диспетчерские центры и технология управления перевозочным процессом. М.: Маршрут, 2005. - 760 с.

90. Туманов В. Е., Гайфуллин Б. Н., Сгибнев В. Я. Введение в SQL для баз данных в архитектуре клиент/сервер. СПб.: BHV-Петербург, 2000. -188 с.

91. Смирнов С. Н. Работаем с IBM DB2. М.: Гелиос, 2001. - 304 с.

92. Баин А. М. Современные информационные технологии систем поддержки принятия решений. М.: Форум, 2009. - 240 с.

93. Трахтенгерц Э. А. Компьютерная поддержка принятия решений. -М.: Синтег, 1998. 376 с.

94. Бородин А. Ф., Биленко Г. М., Олейник О. А., Бородина Е. В. Технология работы сортировочных станций. М.: РГОТУПС, 2001. -192 с.

95. Евдокимов А. В. Моделирование объектов железнодорожного транспорта на основе использования теории массового обслуживания // Тр. Всерос. науч.-практ. конф. «Транспорт-2005». Ч. 1. Ростов н/Д: РГУПС, 2005. - С. 96-97.

96. Гладков JI. А. Решение задач и оптимизации решений на основе нечетких генетических алгоритмов и многоагентных подходов // Изв. Таганрог, гос радиотехн. ун-та. Интеллектуальные САПР. 2006. - № 8 (63). - С. 83-88.

97. Список железнодорожных станций, производящих грузовые операции, государств-участников Содружества, Латвийской Республики, Литовской Республики и Эстонской Республики (с указанием кода единой сетевой разметки ЕСР по районам сети). - М., 2003.

98. Сборник правил перевозок и тарифов железнодорожного транспорта. М., 2007.

99. Калачанов В. Д., Кобко Л. И. Экономическая эффективность внедрения информационных технологий: учеб. пособие. М.: МАИ, 2006. -180 с.

100. Схема алгоритма рекурсивного построения дерева полного перебора1. Пирамида Сагатовского1. Блок-схема BV-метода

101. Блок схема процедуры расчета простоя вагонов согласно планурасформирования

102. Работа ст. Инская по прибытию

103. ПАЛЛ ГОТ 11.10 ПАЛЛ ОТПР 11.10 В-БАС ПРИБ 11.10 Б-БАС ОТЦ 11.10 В-БАС ОТПР 11.1001.11 в-бас 272201.12 в-бас 272208.55 ПАЛЛ 272209.13 ашулу 2722 -0310.34 ACT-2 2010

104. Российские железные дорогиоткрытое акционерное общество «РОССИЙСКИЕ ЖЕЛЕЗНЫЕ ДОРОГИ» (ОАО «РЖД»)1. ФИЛИАЛ

105. ПРИВОЛЖСКАЯ ЖЕЛЕЗНАЯ ДОРОГА» Астраханское отделение Отдел перевозок

106. Беринга ул 1, г Астрахань, 414052 Тел. (8512) 32-26-691. На №1. От.1. АКТо проведении испытаиий, методов изложенных в кандидатской диссертационной работе

107. Борознова Владимира Олеговича

108. Решение задачи производилось в автоматическом режиме четырьмя методами: Генетический Алгоритм, ACS алгоритм, BV-метод и метод полного перебора После чего предлагалось лучшее решение — последовательности расформирования поездов.

109. При этом эффективность работы маневрового диспетчера осталась на высоком уровне.1. Тредседатель коЦгссии:

110. Начальник отдела перевозок Капустин Д.В.

111. Начальник станции Астрахань-2 Щеглов A.B.

112. Главный инженер станции Астрахань-2 Гущин ILA.

113. Зам начальника отдела перевозок по АСУ Кадралиева JI.M.