Разработка моделей и методов оптимизации для транспортных сетей с низкой проходимостью

• Автор: Васильев, Олег Вячеславович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Воронеж
• Количество страниц: 122 с. : ил.

СОДЕРЖАНИЕ
Введение

1. Оптимизация железнодорожных перевозок

1.1 Сущность проблемы перевозок

1.2 Алгоритмы для оптимизации маршрутов перевозок

1.3 Цели и задачи исследования

2. Реализация поиска кратчайшего пути

2.1 Волновой алгоритм

2.2 Реализация анализа препятствий и их обхода

2.3 Муравьиные алгоритмы в поиске оптимального пути

3. Транспортная задача в оптимизации маршрутов перевозок
3.1 Математическая модель транспортной задачи
3.2 Нахождение опорного плана транспортной задачи
3.3 Оптимизация опорного плана
3.4 Нечеткая и трехиндексная транспортная задача
4. Программный комплекс «CyberAnalysis Rail Ways»
4.1. Основа программного комплекса
4.2 Модуль «TransportTask»
4.3 Модуль «BarrierMap»
4.4 Модуль «WaveMap»
Заключение
Литература

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

ставлении задача математического программирования (оптимального планирования), методы решения которой весьма разнообразны и зависят от типа множества Z), свойств целевой функции и функций, определяющих ограничения задачи. Если эти функции линейные, то имеем.задачу линейного программирования, которая являетсяюсновой для решения многих задач, возникающих не только в приложениях, но и в теоретических исследовани- , ях. Данная задача имеет ряд важных модификаций, для которых разработаны еще более эффективные алгоритмы, чем. симплексный метод. Одна из модификаций - это задачи целочисленной дискретной оптимизации, порождаемые такими факторами как неделимость ресурсов, наличие логических. отношений и связей между переменными.
Ярким представителем данного класса задач является транспортная задача, классическую постановку которой изучали такие ученые, как П.Н. Коробов, И.Я. Бирман, А. В. Кузнецов, Н. И. Холод, H.A. Орехов, JI. С. Кос-тевич, Е.А. Горбунов. Стремление к учету некоторых дополнительных ограничений и условий приводит к специальным постановкам: транспортной
задаче с фиксированными доплатами (Каменецкий JI.E., А.Г. Левин, Корбут
A.A.) и задаче со случайными коэффициентами (Еремин И.И., Х.А. Таха,
B.И. Малыхин). Интервальная и нечеткая постановка данной задачи рассматриваются в работах П.Н. Коробова и Н'.А. Орехова. Существует определенная взаимосвязь транспортной задачи с задачами потокового программирования (Д.Р. Фалкерсон), для решения которых используются алгоритмы теории графов.
Значительный интерес представляет транспортная задача на карте с низкой проходимостью. К ее основным приложениям относится оптимизация железнодорожных перевозок, а карта железных дорог может рассматриваться как транспортная сеть с низкой проходимостью. Данная задача обладает и другими особенностями: большая размерность; наличие приоритетов в исполнении заявок; влияние неопределенности, которая является следствием как «человеческого фактора», так и случайных факторов, обусловленных влиянием внешних обстоятельств. С практической точки зрения, решение данной задачи позволит снизить расходы на перевозки по карте с низкой проходимостью и уменьшить риски принимаемых управленческих решений.
Таким образом, актуальность диссертационного исследования,обусловлена необходимостью разработки модельных и алгоритмических решений, учитывающих перечисленные факторы как в постановке транспортной задачи; так и в подходах к ее решению.
Тематика диссертационной работы соответствует одному из основных научных направлений Воронежского государственного технического университета - «Вычислительные комплексы и проблемно-ориентированные системы управления».
Целью диссертационной работы является разработка комплекса моде-

В режиме редактирования пользователь может самостоятельно задать свойства клеток и расположить их на карте. По умолчанию существует 5 типов клеток: «Дорога» (стоимость прохода - 2 единицы), «Земля» (4 единицы), «Песок» (6 единиц), «Лес» (10 единиц), «Препятствие» (проход невозможен). Стоимость движения равна соответствующему числу только при проходе по вертикали или горизонтали. В случае движения по диагонали стоимость движения возрастает в два раза.
В режиме поиска пути пользователь задает начальную и конечную точки (с помощью кликов мышки по необходимым квадратам), после чего автоматически начинает работать алгоритм поиска.
На первом шаге пользователь задает начальную и конечную точки, помеченные на рисунке 2.1 красным и синим цветом соответственно.
Рис. 2.1. Шаг первый: определение ключевых точек