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

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

Бухаров Дмитрий Сергеевич

МЕТОДИКА РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ РЕГИОНАЛЬНОЙ ТРАНСПОРТНО-ЛОГИСТИЧЕСКОЙ ИНФРАСТРУКТУРЫ

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

Автореферат

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

г 3 11АП 2013

Иркутск-2013

005059951

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

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

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

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

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

доктор физико-математических наук

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

доктор физико-математических наук, профессор, Федеральное государственное бюджетное учреждение науки Омский филиал Института математики им. С. Л. Соболева СО РАН, заведующий лабораторией

Попков Владимир Константинович,

доктор физико-математических наук, профессор, Федеральное государственное бюджетное учреждение науки Институт вычислительной математики и математической геофизики СО РАН, главный научный сотрудник

Федеральное государственное бюджетное учреждение науки Институт математики и механики УрО РАН

Зашита состоится 18 июня 2013 года в 17 часов на заседании диссертационного совета Д 003.061.02 на базе Федерального государственного бюджетного учреждения науки Института вычислительной математики и математической геофизики Сибирского отделения Российской академии наук (ИВМиМГ СО РАН) по адресу: 630090, г. Новосибирск, проспект академика Лаврентьева, 6. Тел. (383)330-71-59.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Института вычислительной математики и математической геофизики СО РАН.

д , 13 МАЙ 2013

Автореферат разослан «_»_20_г.

Ученый секретарь диссертационного совета, доктор физико-математических наук

Сорокин Сергей Борисович

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

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

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

Решению задачи организации коммуникаций посвящено большое количество работ отечественных и зарубежных ученых. Можно отметить следующих авторов: Варшалл С., Беллман Р., Форд Л., Штейнер Я., Лукинский B.C., Кормен Т., Ченцов А.Г., Нечаев Ю.Б., Гордеев Э.Н., Михалевич B.C., Лотарев Д.Т., Ольшевский А.И., Ранвей К., Попков В.К., Гутин Г., Берг М., Овермарс М.

Решением задачи оптимального размещения логистических объектов занимались следующие авторы: Лукинский B.C., Гаджинский A.M., Забудский Г.Г., Курейчик В.М., Бабич O.A., Кононов A.B., Васильев И.Л., Майника Э., Дилип P.C., Колоколов A.A., Свеженцева О.В., Никел С., Фарахани Р., Кобел А.

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

В работах представителей научной школы академика Красовского H.H.: чл.-корр. РАН Ушакова В.Н. и его учеников Лебедева П.Д., Успенского A.A., Матвийчука А.Р.1 подобный подход применяется при решении задач управления подвижными объектами в условиях фазовых ограничений на конечном промежутке времени, а также в целях исследования различных особенностей построения волновых фронтов. Данные исследования имеют прямой выход на задачи

1 Лебедев П.Д., Успенский A.A. Геометрия и асимптотика волновых фронтов // Известия высших учебных заведений. Математика, 2008. №3. С. 27-37.

Лебедев П.Д., Успенский A.A., Ушаков В.Н. Построение минимаксного решения уравнения типа эйконал // Труды института математики и механики, 2008. № 2. С. 182-191.

Матвийчук А.Р., Ушаков В.Н. О построении разрешающих управлений в задачах управления с фазовыми ограничениями // Известия РАН. Теория и системы управления, 2006. № 1. С. 5-20.

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

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

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

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

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

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

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

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

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

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

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

Объект и предмет исследования. Объектом исследования является региональная транспортно-логистическая инфраструктура. Предмет исследования - математические модели региональных транспортно-логистических систем и численные методы их исследования.

Методы исследования. При проведении диссертационного исследования применялись методы математического моделирования и непрерывной оптимизации при построении моделей оптимизации региональной транспортно-логистической инфраструктуры, геометрической оптики и вычислительной математики при разработке методов исследования построенных математических моделей. Также применялись методы системного анализа для выявления специфических особенностей транспортно-логистических систем и проведения комплексного исследования. Для реализации программного комплекса использована среда разработки Delphi7 (язык программирования Object Pascal).

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

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

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

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

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

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

6. Не имеющий аналогов программный комплекс «ВИГОЛТ», новизна которого обеспечивается реализованными в ней новыми математическими моделями (пункты 1,2) и оригинальными численными методами и алгоритмами (пункты 3,4). Программный комплекс предназначен для автоматизации расчетов при решении задач оптимизации региональной транспортно-логистической инфраструктуры.

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

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

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

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

Результаты диссертационной работы использованы при выполнении научно-исследовательских работ по разработке транспортной модели Иркутской области: государственный контракт № 13-ОК/12 от 12.09.2012.

Результаты диссертационной работы использованы при выполнении научно-исследовательских работ по грантам РФФИ проекты №11-07-00245 (2011-2013 гг.), №12-07-31080 (2012-2013 гг.), №12-07-13116 (2012-2013 гг.), №12-07-33045 (2012-2013 гг.). Диссертационная работа поддержана именной стипендией Губернатора Иркутской области.

Апробация результатов исследования. Основные результаты диссертационной работы докладывались и обсуждались на следующих научных конференциях: Всероссийская школа-конференция «Современные проблемы математики» (Екатеринбург, 2011, 2012гг.); Всероссийская конференция «Винеров-ские чтения» (Иркутск, 2011,2013гг.); Байкальская Всероссийская конференция «Информационные и математические технологии в науке и управлении» (Иркутск, 2011, 2012гг.); Прибайкальская школа-семинар молодых ученых «Моделирование, оптимизация и информационные технологии» (Иркутск, 2012г.); Межвузовская научно-практическая конференция молодых ученых «Проблемы информационного и математического моделирования сложных систем - 2012» (Иркутск, 2012г.); VI Международный научный семинар «Обобщенные постановки и решения задач управления» (Геленджик, 2012г.).

Результаты диссертационной работы докладывались на семинаре отдела динамических систем Института математики и механики УрО РАН (2012г.), кафедры Информационные системы Иркутского государственного университета путей сообщения (2012г.), лаборатории прикладных систем Института вычислительной математики и математической геофизики СО РАН (2013г.), а также неоднократно докладывались на научных семинарах кафедры Автоматизированных систем Иркутского государственного технического университета.

Результаты диссертационной работы опубликованы в 14 научных работах, из них 5 статей в изданиях, входящих в Перечень ВАК. Выдано свидетельство о государственной регистрации программы для ЭВМ № 2013613246 (2013г.).

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

Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения и списка литературы из 137 наименований. Объем работы составляет 157 страниц, 98 рисунков и 11 таблиц.

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

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

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

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

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

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

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

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

высокоскоростной магистрали Екатеринбург-Челябинск.

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

В диссертационной работе предложена математическая модель оптимальной организации коммуникаций с ограничениями на маршруты. Пусть в ограниченной области DczR2 заданы т точек Ak(xk,yk) е D (к = \,т), и кусочно-непрерывная функция у> f(x,y)> О, определенная на D. Требуется определить кратчайшее дерево, связывающее точки Ак(хк,ук)

Г(Га) = тш \dTlf{x,y), (1)

m—1

ХПГа)->тт, (2)

i=i

где r.,eG (к = \,m\k Ф i) - кривая, соединяющая Aj(xi,yi) и Ак(хк,ук) и доставляющая минимум интегральному функционалу (1), G - множество всевозможных кривых, соединяющих заданные точки.

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

Построим математическую модель определения оптимального маршрута с ограничением на кривизну. Пусть в некоторой ограниченной области DczR2 с кусочно-гладкой границей заданы точки Дх,,^) е D, В(х2,у2) е D.

Требуется определить кривую Г* е G, соединяющую точки А и В

Г* = arg min je/Г/ f(x, у), (3)

г

где Г е G - кривая, соединяющая точки А и В, на радиус кривизны R которой накладываются ограничения, имеющие в случае явного у = у(х) задания кривой Г вид (С — минимальный разрешенный радиус кривизны)

Ä = ^(l + [y(x)]2)3/f/(x)|>C. (4)

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

Оптико-геометрический подход основан на том, что с точки зрения геометрической оптики выражение (1) определяет время, за которое свет, выпущенный из точки А, достигает точки В, двигаясь в оптически неоднородной среде с местной скоростью /(х,у). Согласно принципу Гюйгенса, каждая точка, которой достигает фронт волны, становится самостоятельным источником света. Таким образом, выпустив световую волну из точки А, можно построить траекторию ее движения и зафиксировать момент времени, когда волна достигнет точки В. Поскольку, согласно принципу Ферма, луч света в своем движении выбирает путь, минимизирующий оптическую длину пути, можно, двигаясь в обратном направлении по времени, восстановить траекторию, которая и будет искомой кривой Г*. Вычислительный алгоритм, реализующий данный подход, описан ниже.

Пусть задана ограниченная область Б, в каждой точке которой (х,у) е Б определено значение проницаемости среды /(х,у), изменяющее скорость прохождения светового луча. Указанная скорость тем выше, чем больше значение проницаемости среды /(х,у). Пусть задана точка А е Б, являющаяся источником светового возбуждения. Как уже отмечалось, каждая точка области Б, достигнутая фронтом волны, становится самостоятельным источником света. ШАГ №1. Из точки А в начальный момент времени /0 = 0 в / направлениях (в наших расчетах обычно / = 32) с заданным малым шагом А/ откладываются вектора длиной Д.? = /(_т,_у)Д/, угол между соседними векторами равен Р = 2пП. Координаты концов векторов образуют множество точек

=10+ Ы, являющихся множеством вторичных источников. На основе кривых Безье строится огибающая вторичных источников, таким образом, определяется фронт Ф(/,) волны в момент времени .

ШАГ №2. От каждой точки множества К{А,11) откладывается вектор внешней нормали к фронту Ф(7,) длиной Д.? = /(х,у)&. Координаты концов построенных векторов образуют множество вторичных источников К{А^2), /,=/,+ Д/ и строится фронт волны Ф(/2) в момент времени ¡2.

ШАГ №3. Производится «дискретизация» фронта волны Ф(72): каждый фрагмент кривой Безье, соединяющий вторичные источники, разделяется на четыре равные части, за счет чего образуется новое множество точек К (А,(2). Определяется кратчайшее расстояние от каждой новой точки множества К (Д/,) до точек множества К(А,^) и строится соответствующий вектор. От каждой точки множества К*(А,12) откладывается вектор внешней нормали к фронту Ф(/2), определяется множество вторичных источников К(А,Ц), /3 = /2 + Д/ и строится фронт волны Ф(/3) в момент времени (г.

И так далее: построение векторов и фронтов повторяется аналогично шагу 3 до тех пор, пока целевая точка В не окажется внутри области с границей Ф(1к ), 1к = + А/ = А:Д/. После этого точка В приближенно отождествляется с ближайшей точкой множества ).

Направление построения каждого вектора нормали известно и каждая точка фронта является одновременно концом и началом построенных векторов, что используется при построении кривой (3): точка фронта Ф(^) соединяется с точкой фронта Ф(7Ы) и определяется отрезок искомой кривой. Далее точка фронта соответственно, соединяется с точкой фронта Ф(^_2) и опреде-

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

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

При конструировании фронта волны возможна потеря гладкости2 кривой при значительном удалении от базисного многообразия. В некоторой точке фронта происходит разрыв производной, что приводит к образованию «ласточкиного хвоста» (рис. 1). Данная проблема решена посредством отслеживания точек пересечения перпендикуляров к фронту на каждом шаге.

Описанный алгоритм отличается от волнового алгоритма Ли возможностью строить фронты волны в неоднородной среде /(х,у), учитывая при этом как частично, так

и полностью непроходимые для световой Рис 1 _ фронты волны-

волны области, а также ограничения на кри- а _ элл^пс> б _Рфра™ент кривой визну (4) определяемой кривой (3).

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

ШАГ№1. Из заданного множества точек Ак выбирается одна и маркируется. ШАГ №2. Из маркированной точки выпускается световая волна (строятся фронты световой волны вышеописанным способом). В момент времени t световая волна достигает ближайшую немаркированную точку. ШАГ №3. Достигнутая волной точка маркируется и соединяется кривой (дугой дерева) с точкой-источником. Если достигается две или более немаркированных точек, то маркируется одна. Если немаркированная точка достигается двумя или более волнами, то выбирается любая из соответствующих точек-источников и строится кривая.

ШАГ №4. Из каждой маркированной точки выпускается световая волна. В некоторый момент времени / одна из световых волн достигает ближайшую немаркированную точку. Если немаркированных точек две или более, то выполняется шаг №3. В противном случае достигнутая волной точка маркируется и соединяется кривой с точкой-источником.

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

Данный алгоритм построения кратчайшего дерева, фактически, является

2 Арнольд В.И. Особенности каустик и волновых фронтов. М.: ФАЗИС, 1996. 334 с.

10

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

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

В качестве области D взят прямоугольник, протяженностью 223 км и шириной 167 км, охватывающий города Екатеринбург, Челябинск. Размеры области были определены ПО согласо- Рис- 2 - Трехмерная модель оптимального маршрута BC1V ванию со специалистами-транспортниками (к.т.н. М.А. Журавская). Значение функции fix,у) определяется как высота над уровнем моря в точке (х,у). Кроме того, мы предполагаем, что в точках расположения населенных пунктов, озер, болот f(x,y) = 0 (непроходимая область). Минимальный допустимый радиус кривизны R = 4 км (что соответствует мировой практике), также учитывался перепад высот на местности (не более 10 м на один км).

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

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

В диссертационной работе предложена математическая модель оптимального размещения нескольких логистических объектов. Пусть в некоторой ограниченной области D <^R2 с кусочно-гладкой границей заданы п потребителей, расположенных в точках е D (г = 1,и), количество логистических объектов 1 <т<п. Минимальные затраты на доставку из М eD в вычисляются по формуле

7;.(Г,.(М))= тт Г ¿Г,.(М)//(х, >>), (5)

ГАМ) •

ГДМ)

где Т,{М) <= О (г=1,и) - кривая, соединяющая точки В1 и М и доставляющая минимум интегральному функционалу (5).

Требуется определить оптимальное расположения складов (х'к,у'к) и разбиение множества потребителей на т подмножеств, определив номера 1к = потребителей, обслуживаемых складом Ак(хк,ук) (к = \,т), та-

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

т__

к=\ ,-е/,

При этом разбиение множества потребителей на т подмножеств обеспечивается сегментацией области Б и определением в каждой области Бк е £) соответствующих номеров потребителей 1к = {¡к1,...,1ь}

Г;.(М)= шш [ с!Гк(М)/Дх,у), (7)

Г,(ЛО

где Г4(М) е б (& = 1,тя) - кривая, соединяющая точки Ак и М.

В диссертационной работе разработаны два метода, являющихся модификациями метода РОКЕЬ3: метод последовательного улучшения с использованием мультистарта и метод последовательного улучшения с выделением активной зоны. В указанных модификациях построение фронтов волны позволяет сократить число вычислений за счет снятия необходимости подбора наилучшего радиуса, определив границы сегментов обслуживания за одну итерацию вычисления, и разместить логистические объекты на рельефной местности. Нахождение глобального решения не гарантируется.

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

Сегментация зон обслуживания (7) производится на основе модификации метода построения диаграммы Вороного4.

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

3 Загоруйко Н.Г. Прикладные методы анализа данных и знаний. Новосибирск: Изд-во Ин-та Математики С.Л. Соболева СО РАН, 1999. 270 с.

4 Препарата Ф., Шеймос М. Вычислительная геометрия. М.: Мир, 1989.478 с.

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

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

В главе 4 представлено описание программного комплекса и вычислительного эксперимента. Программный комплекс «ВИГОЛТ» имеет следующую структуру: набор настроек, повышающих гибкость системы, и четыре взаимосвязанных модуля:

• Модуль «Среда»: предназначен для работы с функцией среды /(х,у). Задать значения функции /{х,у) можно в специальной таблице или загрузив их из Ехсе1-файла.

• Модуль «Волна»: предназначен для реализации распространения световой волны в заданной среде и хранения списка волн, выпущенных из различных источников.

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

• Модуль «Волна с границы»: реализует алгоритмы, основанные на распространении световой волны с границы заданной области.

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

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

В главе 5 в целях проверки работоспособности предложенных в диссертационной работе численных методов, а также разработанного на их основе программного комплекса «ВИГОЛТ», были решены следующие задачи: идентификация и сегментация логистических зон утилизации старых автомобилей в Иркутской и Свердловской областях; определение оптимального расположения социальных логистических объектов в городе Саянск (Иркутская область).

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

В качестве области Б взята территория соответствующего региона, в каждой точке (х,у)&И определена плотность населения. Значения функции /(х,у) определяются как /(х,у) = 1 / л^р , где р - плотность населения. Число пунктов утилизации (восемь) определено в соответствии с информацией сайта Министерства промышленности и торговли РФ.

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

Под оптимальным расположением логистических объектов (при заданном количестве) понимается такое, при котором суммарное время достижения этих объектов населением будет минимальным. В качестве исходных данных используется информация о городской инфраструктуре. Настоящее расположение аптечных пунктов существенно отличается от оптимального (=30,7%).

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

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

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

1» Ш|нШ

«Р ЕВ

Г - а б

Рис. 3 - Решение задачи сегментации: а - Свердловская область, б - Иркутская область

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

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

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

6. Проведена экспериментальная проверка разработанного программно-математического обеспечения на ряде модельных и прикладных задач, показавшего свою эффективность. С использованием программного комплекса «ВИГОЛТ» решены следующие прикладные задачи: прокладка оптимального маршрута высокоскоростной магистрали Екатеринбург-Челябинск; идентификация и сегментация логистических зон утилизации старых автомобилей в Иркутской и Свердловской областях; определение оптимального расположения социальных логистических объектов в г. Саянск.

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

Издания, входящие в Перечень ВАК РФ:

1. Бухаров Д.С. Определение оптимального количества и расположения логистических центров: математическая модель и численный метод // Вестник ИрГТУ. 2012. №4. С. 8-14.

2. Бухаров Д.С., Казаков А.Л. Программная система «ВИГОЛТ» для решения задач оптимизации, возникающих в транспортной логистике // Вычислительные методы и программирование. 2012. Раздел 2. С. 65-74 (http://num-meth.srcc.msu.ru/).

3. Лемперт A.A., Казаков А.Л., Бухаров Д.С. Математическая модель и программная система для решения задачи размещения логистических объектов // Управление большими системами. 2013. Выпуск 41. С. 270-284.

4. Казаков А.Л., Лемперт A.A., Бухаров Д.С. Об одном численном методе решения некоторых задач оптимизации, возникающих в транспортной логистике // Вестник ИрГТУ. 2011. №6. С. 6-12.

5. Журавская М.А., Казаков А.Л., Лемперт A.A., Бухаров Д.С. О методе решения задачи оптимальной прокладки высокоскоростных железнодорожных магистралей с учетом региональных особенностей // Транспорт: наука, техника, управление. 2012. №2. С. 41-44.

Издания, включенные в РИНЦ:

6. Бухаров Д.С., Казаков A.JI. Применение оптико-геометрического подхода для решения прикладных задач вариационного исчисления // Проблемы информатики. 2012. №3. С. 22-32.

Свидетельство о государственной регистрации программы для ЭВМ

7. Бухаров Д.С., Казаков A.JL, Лемперт A.A. Программная система «ВИ-ГОЛТ» // Свидетельство о государственной регистрации программы для ЭВМ №2013613246. М.: Федеральная служба по интеллектуальной собственности (Роспатент). 2013.

Прочие издания:

8. Бухаров Д.С. Численный метод решения специальных задач транспортной логистики и его программная реализация // Молодежный вестник ИрГТУ. №3. 2011. (http://www.mvestnik.istu.edu/).

9. Бухаров Д.С. Построение и численное исследование математических моделей некоторых задач транспортной логистики // Современные проблемы математики: тезисы Международной (43-й Всероссийской) молодежной школы-конференции. Екатеринбург: Институт математики и механики УрО РАН, 2012. С. 354-356.

Ю.Бухаров Д.С. О методах решения задачи размещения нескольких логистических объектов на полигоне обслуживания // Моделирование, оптимизация и информационные технологии: тезисы XII Прибайкальской школы-семинара молодых ученых. Иркутск: Институт динамики систем и теории управления СО РАН, 2012. С. 16.

П.Казаков А.Л., Бухаров Д.С., Лемперт A.A. Решение некоторых прикладных задач оптимизации с использованием методов геометрической оптики // Информационные и математические технологии в науке и управлении: Труды XVI Байкальской Всероссийской конференции. Т.2. Иркутск: ИСЭМ СО РАН, 2011. С. 99-106.

12.Казаков А.Л., Бухаров Д.С., Лемперт A.A. О двух задачах оптимального размещения объектов логистической инфраструктуры // Информационные и математические технологии в науке и управлении: Труды XVII Байкальской Всероссийской конференции. Т.1. Иркутск: ИСЭМ СО РАН, 2012. С. 118-125.

13.Казаков А.Л., Лемперт A.A., Бухаров Д.С. О решении задач оптимизации, возникающих в транспортной логистике // Современные проблемы математики: тезисы 42-й Всероссийской молодежной школы-конференции. Екатеринбург: Институт математики и механики УрО РАН, 2011. С. 31-33.

14.Казаков А.Л., Лемперт A.A., Бухаров Д.С. О задаче оптимального размещения логистического объекта для обслуживания непрерывно распределенных потребителей [электронный ресурс] // VI Международный научный семинар «Обобщенные постановки и решения задач управления» (GSSCP-2012). Геленджик, 2012. С. 39-42.

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

Лицензия ИД № 06506 от 26.12.2001 Иркутский государственный технический университет 664074, г. Иркутск, ул. Лермонтова, 83

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «ИРКУТСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

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

й4?оі ^і^.нбА

Бухаров Дмитрий Сергеевич

МЕТОДИКА РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ РЕГИОНАЛЬНОЙ ТРАНСПОРТНО-ЛОГИСТИЧЕСКОЙ ИНФРАСТРУКТУРЫ

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

Диссертация

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

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

доктор физико-математических наук

А.Л. Казаков

Иркутск - 2013

СОДЕРЖАНИЕ

Введение.......................................................................................................................4

Глава 1. Современное состояние исследований в области математического моделирования в транспортной логистике.............................................................13

1.1 Математические модели в задачах транспортной логистики....................13

1.2 Задачи вариационного исчисления и методы их решения.........................32

1.3 Применение оптико-геометрического подхода для решения задач вариационного исчисления..................................................................................44

Глава 2. Задача оптимальной организации коммуникаций с ограничениями на маршруты...................................................................................................................46

2.1 Оптимальная организация коммуникаций...................................................46

2.2 Определение оптимального маршрута с ограничением на кривизну.......49

2.3 Описание оптико-геометрического подхода................................................51

2.4 Алгоритм определения оптимального маршрута........................................57

2.5 Прокладка оптимального маршрута высокоскоростной магистрали Екатеринбург-Челябинск......................................................................................61

Глава 3. Задача оптимального размещения логистических объектов и сегментация логистических зон...............................................................................65

3.1 Оптимальное размещение нескольких логистических объектов...............65

3.3 Оптимальное количество логистических объектов.....................................72

3.2 Оптимальное размещение одного логистического объекта.......................74

3.4 Сегментация логистических зон обслуживания..........................................77

3.5 Модификация оптико-геометрического подхода........................................80

3.6 Оптимальное размещение логистического объекта при непрерывно распределенных потребителях............................................................................82

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

Глава 4. Программный комплекс «ВИГОЛТ» и вычислительный эксперимент 87 4.1 Программный комплекс «ВИГОЛТ»............................................................87

4.2 Аппроксимации распространяющейся волны.............................................96

4.3 Решение задач маршрутизации......................................................................99

4.4 Размещение логистических объектов и сегментация зон обслуживания 106

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

Глава 5. Прикладные задачи..................................................................................125

5.1 Идентификация и сегментация логистических зон утилизации старых автомобилей.........................................................................................................125

5.2 Определение оптимального расположения социальных логистических объектов в городе Саянск...................................................................................129

Заключение..............................................................................................................144

Список литературы.................................................................................................146

Введение

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

Определение оптимальных маршрутов [3, 39, 77, 92, 93, 123] (организация коммуникаций) и оптимального места расположения логистических объектов [101, 6, 7, 85, 77, 41] - фундаментальные задачи транспортной логистики, решение которых, как правило, приводит к построению различного рода дискретных математических моделей. Однако, существует ряд прикладных задач, решение которых в дискретной постановке затруднено, так как, например, возможна потеря существенной части информации при дискретизации.

Решению данной задаче посвящено большое количество работ отечественных и зарубежных ученых. Можно отметить следующих авторов: Флойд Р., Варшалл С., Беллман Р., Форд JL, Штейнер Я., Лукинский B.C., Кормен Т., Чеблоков И.Б., Ченцов А.Г., Нечаев Ю.Б., Ипатов A.B., Гордеев Э.Н., Панюков A.B., Щербакова В.А., Сидоренко А.Ф., Михалевич B.C., Лотарев Д.Т., Емельянов В.В., Романовский И.В., Ольшевский А.И., Ранвей К., Лин Л., Гутин Г., Берг М, Овермарс М. и др.

Решением задачи оптимального размещения логистических объектов занимались следующие авторы: Лукинский B.C., Гаджинский A.M., Забудский Г.Г., Береснев В.Л., Курейчик В.М., Михалевич B.C., Бабич O.A., Кононов A.B., Васильев И.Л., Майника Э., Дилип P.C., Кристофидес Н., Алексеева Е.В., Све-женцева О.В., Никел С., Фарахани Р., Чен Ю., Кобел А.

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

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

В работах представителей научной школы академика H.H. Красовского: чл.-корр. РАН В.Н. Ушакова и его учеников Лебедева П.Д., Успенского A.A., Матвийчука А.Р. [67, 68, 81, 111] подобный подход применяется при решении задач управления подвижными объектами в условиях фазовых ограничений на конечном промежутке времени, а также в целях исследования различных особенностей построения волновых фронтов. Данные исследования имеют прямой выход на задачи безопасности судоходства, эффективной посадки летательных аппаратов, а также противовоздушной, противоракетной и противокорабельной обороны. Также подобный подход применялся при решении задач оптимизации системы физической защиты охраняемого объекта и обезвреживания нарушителя (Башуров В.В.) [9, 10], каждая из которых сводилась к поиску оптимального маршрута.

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

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

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

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

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

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

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

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

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

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

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

Объект и предмет исследования. Объектом исследования является региональная транспортно-логистическая инфраструктура. Предмет исследования - математические модели региональных транспортно-логистических систем и численные методы их исследования.

Методы исследования. При проведении диссертационного исследования применялись методы математического моделирования и непрерывной оптими-

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

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

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

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

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

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

5. Оригинальная методика решения задач оптимизации региональной

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

6. Не имеющий аналогов программный комплекс «ВИГОЛТ», новизна которого обеспечивается реализованными в ней новыми математическими моделями (пункты 1,2) и оригинальными численными методами и алгоритмами (пункты 3,4). Программный комплекс предназначен для автоматизации расчетов при решении задач оптимизации региональной транс-портно-логистической инфраструктуры.

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

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

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

Результаты диссертационной работы использованы при выполнении научно-исследовательских работ по разработке транспортной модели Иркутской области: государственный контракт № 13-ОК/12 от 10.09.2012.

Результаты диссертационной работы использованы при выполнении научно-исследовательских работ по грантам РФФИ: проект №11-07-00245 «Мно-гоагентная интеллектуальная логистическая система на основе стохастических и динамических моделей транспортных потоков» (2011-2013 гг.), проект №128

07-31080 «Интеллектуальная технология решения проблемы развития инфраструктуры региона с использованием системного анализа и методов математического моделирования» (2012-2013 гг.), проект №12-07-13116 «Разработка и интеграция математических моделей, методов и интеллектуальных информационных технологий для оптимизации инфраструктуры железнодорожного транспорта и повышения эффективности использования подвижного состава» (20122013 гг.), проект №12-07-33045 «Информационно-вычислительные технологии поддержки принятия решений в транспортно-логистических системах на основе моделей и методов непрерывной и дискретной оптимизации» (2012-2013 гг.).

Диссертационная работа поддержана именной стипендией Губернатора Иркутской области.

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

- 42-ая Всероссийская молодежная школа-конференция «Современные проблемы математики» (Екатеринбург, Институт математики и механики УрО РАН, 2011г.);

- IV Всероссийская конференция «Винеровские чтения» (Иркутск, Иркутский государственный технический университет, 2011г.);

- XVI Байкальская Всероссийская конференция «Информационные и математические технологии в науке и управлении» (Иркутск, Институт систем энергетики им. Л.А. Мелентьева СО РАН, 2011г.);

- Международная (43-я Всероссийская) молодежная школа-конференция «Современные проблемы математики» (Екатеринбург, Институт математики и механики УрО РАН, 2012г.);

- XII Прибайкальская школа-семинар молодых ученых «Моделирование, оптимизация и информационные технологии» (Иркутск, Институт динамики систем и теории управления СО РАН, 2012г.);

- Межвузовская научно-практическая конференция молодых ученых «Проблемы информационного и математического моделирования сложных сис-

тем - 2012» (Иркутск, Иркутский государственный университет путей сообщения, 2012г.);

- XVII Байкальская Всероссийская конференция «Информационные и математические технологии в науке и управлении» (Иркутск, Институт систем энергетики им. Л.А. Мелентьева СО РАН, 2012г.);

- VI Международный научный семинар «Обобщенные постановки и решения задач управления» (Геленджик, Институт проблем управления РАН, 2012г.);

- Всероссийская молодежная научно-практическая конференция «Малые Винеровские чтения» (Иркутск, Иркутский государственный технический университет, 2013г.).

Результаты диссертационной работы докладывались на семинаре отдела динамических систем Института математики и механики УрО РАН (2012г.), кафедры Информационные системы Иркутского государственного университета путей сообщения (2012г.), лаборатории прикладных систем Института вычислительной математики и математической геофизики СО РАН (2013г.), а также неоднократно докладывались на научных семинарах кафедры Автоматизированных систем Иркутского государственного технического университета.

Результаты диссертационной работы опубликованы в 14 научных работах, из них 5 статей в изданиях, входящих в Перечень ВАК: «Управление большими системами», «Вычислительные методы и программирование», «Транспорт: наука, техника, управление», «Вестник ИрГТУ». Выдано свидетельство о государственной регистрации программы для ЭВМ № 2013613246 (2013г.).

Ли�