Разработка моделей и методов оптимизации для транспортных сетей с низкой проходимостью тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Васильев, Олег Вячеславович

• Васильев, Олег Вячеславович
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Васильев, Олег Вячеславович

Введение

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 Railways»

4.1. Основа программного комплекса

4.2 Модуль «TransportTask»

4.3 Модуль «BarrierMap»

4.4 Модуль «WaveMap» 116 Заключение 121 Литература

Введение диссертации (часть автореферата) на тему «Разработка моделей и методов оптимизации для транспортных сетей с низкой проходимостью»

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

Ярким представителем данного класса задач является транспортная задача, классическую постановку которой изучали такие ученые, как П.Н. Коробов, И.Я. Бирман, А. В. Кузнецов, Н. И. Холод, H.A. Орехов, JI. С. Кос-тевич, Е.А. Горбунов. Стремление к учету некоторых дополнительных ограничений и условий приводит к специальным постановкам: транспортной задаче с фиксированными доплатами (Каменецкий JI.E., А.Г. Левин, Корбут

A.A.) и задаче со случайными коэффициентами (Еремин И.И., Х.А. Taxa,

B.И. Малыхин). Интервальная и нечеткая постановка данной задачи рассматриваются в работах П.Н. Коробова и H.A. Орехова. Существует определенная взаимосвязь транспортной задачи с задачами потокового программирования (Д.Р. Фалкерсон), для решения которых используются алгоритмы теории графов.

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

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

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

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

Для достижения поставленной цели решались следующие задачи:

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

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

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

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

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

Научная новизна.

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

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

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

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

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

Практическая значимость работы.

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

Область исследования.

Содержание диссертации соответствует следующим пунктам паспорта специальности 05.13.18 «Математическое моделирование, численные методы и комплексы программ».

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

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

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

Реализация и внедрение результатов работы.

Теоретические результаты диссертации используются в учебном процессе Воронежского государственного технического университета при чтении спецкурсов, выполнении дипломных проектов. Полученные в диссертации теоретические результаты и программный комплекс «CyberAnalysis Railways» используются для оптимизации и мониторинга перевозок в ООО «ТрансИнформ».

Апробация работы.

Основные результаты, полученные в диссертационной работе, докладывались и обсуждались на международных и всероссийских конференциях: Всероссийская конференция «Новые технологии в научных исследованиях, проектировании, управлении, производстве» (Воронеж, 2008-2011гг.); VIII - XI Международная научно-методическая конференция «Информатика: проблемы, методология, технологии» (Воронеж, 2008-2011гг.); а также на научных конференциях Воронежского государственного технического университета и Воронежского государственного университета.

Публикации. Основные результаты диссертации опубликованы в 13 научных работах, в том числе 2 - в изданиях, рекомендованных ВАК РФ.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, содержащего 72 наименования. Основная часть работы изложена на 123 страницах, и содержит 42 рисунка и 13 таблиц.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Васильев, Олег Вячеславович

Выводы.

1. Разработан программный комплекс «CyberAnalysis Rail Ways», предназначенный для оптимизационных расчетов для маршрутов грузоперевозок на карте низкой проходимости.

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

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

121

ЗАКЛЮЧЕНИЕ

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

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

В качестве практически-прикладного результата был разработан программный комплекс, реализующий^предложенные алгоритмы: создание плана перевозок, его оптимизацию, построение графиков движения вагонов по результатам расчетов. Данный программный комплекс «СуЬегАпа1уз1з ЯаП\Уауз» может быть использован в качестве прототипа АИС промышленного назначения. В данное время он используется для оптимизации и мониторинга железнодорожных перевозок в ООО «Трансинформ».

122

Список литературы диссертационного исследования кандидат технических наук Васильев, Олег Вячеславович, 2011 год

1. Агаев Р. П. Модели обобщенного интервального выбора : Диссертация . канд. техн. наук: 05.13.10. -М.: ИЛУ РАН, 1995.-153 с.

2. Алескеров Ф.Т. Пороговая полезность, выбор и бинарные отношения // Автоматика и телемеханика. — 2002. № 3. С. 8-27.

3. Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления. М.: Мир, 1987.-360 с.

4. Алтунин А.Е., Семухин М.В. Модели и алгоритмы принятия решений в нечетких условиях. Тюмень: Изд-во ТГУ, 2000. 352 с.

5. Афанасьев В.Н., Колмановский В.Б., Носов В.Р. Математическая теория конструирования систем управления : Учебник для вузов М.: Высшая школа, 1998.-574 с.

6. Ашманов С.А. Линейное программирование. М.: Наука, 1981. 304с.

7. Ащепков JT.T. Редукции интервальной задачи нелинейного программирования // Журн. вычисл. матем. и матем. физики. 2006. Т. 46. — № 7.-С 1248-1256.

8. Ащепков Л.Т., Гуторова C.B., Карпачев A.A., Ли С. Интервальные матричные игры // Дальневосточный математический журнал. 2003. Т.4. -N2.-C. 276-288.

9. Ащепков Л.Т., Давыдов Д.В. Показатель интервального неравенства: свойства и применение // Вычислительные технологии. 2006. Том 11. — №4.-С. 13-22.

10. Ащепков Л.Т., Давыдов Д.В. Редукции интервальных некооперативных игр // Журн. вычисл. матем. и матем. физики. — 2006. — Т. 46. — № 11. С. 2001-2008.

11. Ащепков Л.Т., Давыдов Д.В. Стабилизация линейной стационарной системы управления с интервальными коэффициентами // Дальневосточный математический сборник. 1999. № 8. - С. 32-38.

12. Ащепков Л.Т., Давыдов Д.В. Стабилизация наблюдаемой линей-ной.системы управления с постоянными интервальными коэффициентами // Изв. ВУЗов. Математика. 2002. № 2 (477). - С. 11-17.

13. Ащепков Л:Т., Давыдов Д.В. Универсальные решения интервальных задач оптимизации исправления. М.: Наука; 2006. -151 с.

14. Ащепков Л.Т., Долгий Д.В. Управление линейными многошаговыми системами в условиях неопределенности // Дальневосточный математический сборник. 1997. Вып. 4. - С. 95-104.

15. Ащепков Л.Т., Колпакова Г.Э., Стегостенко Ю.Б. Стабилизация нестационарной линейной дискретной системы управления с интервальными коэффициентами по наблюдениям фазовых состояний // Автоматика и телемеханика. 2002. № 5. - С. 3-11.

16. Ащепков Л.Т., Косогорова И:Б. Минимизация квадратичной функции с интервальными коэффициентами^// Журн. вычисл. матем. и матем. физики. -2002. Т.42. № 5. - С. 653-664;

17. Ащепков Л.Т., Стегостенко Ю.Б. Стабилизация линейной дискретной системы управления с интервальными коэффициентами // Изв. вузов. Математика. 1998. -№ 12 (439). С. 3-10.

18. Ащепков Л.Т., Стегостенко Ю.Б. Стабилизация наблюдаемой'линейной дискретной системы с интервальными коэффициентами^// Автоматика и телемеханика. 1999. № 7. - С. 85-95.

19. Боровков A.A. Теория вероятностей: — М.: Наука, 1986. 432 с.

20. Бирман И.Я. Транспортная задача линейного программирования. — М.: Экономиздат, 1959. 346 с.

21. Бирман И.Я. Транспортная.задача линейного программирования.

22. М.: Экономиздат, 1959. 346 с.

23. Бирман И.Я. Оптимальное программирование. — М.: Экономика, 1968.- 152 с.

24. Бирман И.Я. Методология оптимального планирования. —М.: Экономика, 1968. 281 с.

25. Бирман И.Я. Применение математики и электронной техники в планировании. — М.: Изд-во экономической литературы, 1961. 129 с.

26. Бирман И.Я. Методические указания по определению оптимальных схем перевозок, снабжения и размещения предприятий с помощью линейного программирования. — М.: Экономика, 1964. 410 с.

27. Бирман И.Я. Математические методы и проблемы размещения производства. — М.: Экономика, 1963. 385 с.

28. Бирман И.Я. Оптимальный план отрасли. — М.: Экономика, 1970.- 267 с.

29. Булавский В .А., Звягина P.A., Яковлева М.А. Численные методы линейного программирования. М.: Наука, 1977. 367 с.

30. Вагнер Г. Основы исследования операций :: В 3-х тт. —М.: Мир, 1972. -Т.1.-336 с.

31. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Факториал, 1998.- 176 с.

32. Васильев О.В., Леденева Т.М. Транспортная задача с интервальными входными данными // Вестник БГТУ им. В'.Г. Шухова. 2011. - № 5 -С. 39-47.

33. Васильев О.В., Леденева Т.М. Технология GoogleMaps в RRWMap // Информатика: проблемы, методология, технологии. Материалы XI международной научно-методической конференции — Воронеж: Воронежский государственный университет, 2011. — Т. 1. — С. 144—146.

34. Ватолин A.A. О задачах линейного программирования с интервальными коэффициентами // Журн. вычисл. матем. и матем. физики. 1984. -Т.24. -№ 11.-С. 1629-1637.

35. Ватолин A.A. О линейных моделях с неоднозначно заданной информацией / Методы выпуклого программирования и некоторые приложения : Сб. науч. трудов. — Свердловск, 1992. — С. 3-18.127 ■ .

36. Facc С. Линейное программирование (методы и приложения). М.: Физматгиз, 1961.-303 с.

37. Голылтейн ЕЛ'., Юдин Д.Б. Новые направления в линейном программировании. М.: Сов. радио, 1966. - 524 с.

38. Давыдов Д.В. Идентификация параметров линейных интервальных управляемых систем с интервальным наблюдением // Известия РАН. Теория и системы управления. -2008. -№ 6. С. 25-29.

39. Давыдов Д.В. Локальная,стабилизация»интервально наблюдаемой системы с неопределенными параметрами1// Вычислительные технологии. -2003.-Т. 8. -№ 1. С.44-51.

40. Давыдов Д.В. Локальная стабилизация интервально наблюдаемой системы с неопределенными параметрами / Конференция молодых ученыхпо математике, математическому моделированию и информатике.Тез. док»ладов. Новосибирск, 2001. С. 24.

41. Давыдов Д.В. Методология принятия экономических решений с позиций субъективной неопределенности // Вестник Российской экономической академии им. Г.В. Плеханова. 2009. № 2(26). - С. 111 -120.

42. Давыдов Д.В. Некоторые подходы к решению интервальной трансIпортной задачи / III Всероссийская конференция^«Проблемы оптимизации и экономические приложения». Тезисы докладов. Омск, 2006. -С. 86.

43. Люгер Д; Интеллект машины. — М.: Мир, 2003. — 690 с.

44. Катречко С.Л». От логических исчислений к интеллектуальнымсистемам. — М.: МГУ, 2006. — 183 с.

45. Кононенко И.С., Сидорова Е.А. Обработка и распознавание изображений. —7 М.: "Логос", 2004. — 115 с.

46. Кузин Е. С. Концепция информационной'технологии функцио-нально-ориентирован-ного проектирования прикладных информационных систем. — М.: МГУ, 2006. — 183 с.

47. Найман B.C., Скрылев В.В. GPS-навигация. М: NT Press, 2010.384 с.

48. Седжвик Р. Фундаментальные алгоритмы на С. Алгоритмы на графах. — СПб.: ДиаСофтЮП, 2003. — 480 с.

49. Стокман Д, Шапиро Л.Компьютерное зрение. — М.: Бином, 2006. — 752 с.

50. Bonavear Е., Dorigo M. Swarm Intelligence: from Natural to Artificial Systems.- Oxford University Press, 1999.- 307 c.

51. Caro G. D., Dorigo M. Anet: a Mobile Agents Approach to Adaptive Routing. Technical Report IRIDA 97-12. IRIDA Universite Libre de Brusseles.-Brussels, Belgium, 1997.- 27 c.

52. Cherix D. Note préliminaire sur la structure, la phenologie et le regime alimentaire d'une super-colonie de Formica lugubris Zett. // Insects Sociaux 27, 1980. c. 226-236.

53. Corne D., Dorigo M., Glover F. New Ideas in Optimization.- McGrav-Hill, 1999.

54. Dorigo M. Swarm Intelligence, Ant Algorithms and Ant Colony Optimization// Reader for CEU Summer University Course «Complex System».- Budapest, Central European University, 2001.- с. 1-38.

55. Reimann M. Ant Based Optimization in Good Transportation. PhD Thesis. University of Vienna.- Vienna, Austria, 2002.- 149 c.

56. ОБЩЕСТВО С ОГРАНИЧЕННО ОТВЕТСТВЕННОСТЬЮ «Транс Информ» (ООО «Транс Информ»)1. T*F>AHCZ І/іНФар1. НФОРМ

57. Почтовый адрес: 394030, г. Воронеж, ул. Пограничная, 2 тел. [phone]; факс [phone] e-mail: [e-mail]