Планирование расписания и управление движением пассажирского транспорта с использованием моделирующей среды тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Чжо Мьо Хан

• Чжо Мьо Хан
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Чжо Мьо Хан

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

ТРАНСПОРТА. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ.

§1.1. Актуальность работы.

§ 1.2. Цель диссертационной работы, её научная новизна, достоверность и практическая ценность.

§ 1.3. Научная новизна и практическая ценность работы, её достоверность.

§ 1.4. Общая постановка задачи.

§1.5. Выводы по главе 1.

ГЛАВА 2. РАЗРАБОТКА АЛГОРИТМА ОПРЕДЕЛЕНИЯ ТРАЕКТОРИИ ДВИЖЕНИЯ ОДНОГО ТС МЕЖДУ ДВУМЯ ОСТАНОВКАМИ С УЧЕТОМ ОГРАНИЧЕНИЙ ПРОЕЗДА В ГОРОДЕ.

§2.1. Постановка задачи построения траектории проезда автобуса между двумя остановками в городском квартале.

§2.2. Описание алгоритма определения множества допустимых точек траектории проезда с помощью метода Вороного (диаграмма

Вороного).

§2.3. Выбор траектории проезда между двумя остановками по критерию минимального пути.

§2.4. Моделирование на ЭВМ алгоритма определения траектории движения ТС, проходящий через выбранное множество допустимых точек.

§2.5 Выводы по главе 2.

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

§3.1. Анализ известных алгоритмов маршрутизации и выбор метода

Дейкстры для определения оптимального маршрута.

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

§3.1.2. Метод ближайшего соседа.

§3.1.3. Волновой алгоритм.

§3.1.4. Алгоритм поиска в глубину (ширину).

§3.1.5. Алгоритм Беллмана-Форда.

§3.1.6. Алгоритм Дейкстры.

§3.1.7. Алгоритм Джонсона.

§3.1.8. Алгоритм Флойда-Уоршелла.

§3.2. Модификация алгоритма Дейкстры для задачи многомерной маршрутизации.

§3.3. Выводы по главе 3.

ГЛАВА 4. ОПРЕДЕЛЕНИЕ ГРАФИКА ДВИЖЕНИЯ ТС ПО ЗАДАННЫМ МАРШРУТАМ, ОБЕСПЕЧИВАЮЩЕГО МАКСИМАЛЬНУЮ ПРИБЫЛЬ.

§4.1 Постановка задачи оптимизации составления расписания.

§4.2. Формирование параметрического критерия оценки дохода от пассажирских перевозок.

§4.3. Идентификация параметров критерия оценки прибыли пассажирских перевозок при одновременном выезде транспортных средств.

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

§4.5. Уточненное субоптимальное решение задачи на базе линейного программирования.

§4.6. Описание численного алгоритма приближенного решения задачи составления расписания.

§4.7. Оценка эффективности предложенного алгоритма с помощью моделирования на ЭВМ.

§4.8 Выводы по главе 4.

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

§1.1. Актуальность работы.

Задачи маршрутации и планирования расписания движения по маршруту нескольких транспортных средств (ТС) с целью повышения эффективности их использования являются актуальными для различных видов пассажирского транспорта. [1,5,45] При известных маршрутах движения и пунктах их пересечения возникает задача выбора таких интервалов движения между ТС, чтобы некоторый критерий эффективности принимал оптимальное значение. В качестве такого критерия в данной работе принята максимальная прибыль с учетом затрат на эксплуатацию ТС. Это позволит не тратить лишние ресурсы (топливо), уменьшить другие затраты (время, зарплата), увеличить число обслуживаемых пассажиров, садящихся на остановках и приобретающих билеты за проезд [3,14,18,37,45].

Однако заранее неизвестны как некоторые параметры этого критерия, так и то, что задача составления расписания не имеет точного аналитического решения, которое зачастую принимается экспертом за счет опыта и навыков о том, как стоит изменить интервалы движения в заданные пункты маршрута. Известные трудности возникают и при выборе маршрутов движения группы ТС.[5,9,33]

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

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

Третья задача выбора маршрута движения транспортных средств является оптимизационной задачей, часто возникающей на практике. Она может быть сформулирована следующим образом: для некоторой группы пунктов с заданными расстояниями между ними требуется найти кратчайшие маршруты группы ТС с посещением каждого города один или несколько раз и с возвращением в исходную точку. Было доказано[24,26,28], что эта задача принадлежит большому множеству задач, называемых «МР-полными» (недетерминистски полиномиальными). Для ЫР-полных задач не известно лучшего метода решения, чем полный перебор всех возможных вариантов, и, по мнению большинства математиков, маловероятно, чтобы лучший метод был когда-либо найден. [56] Так как такой полный поиск практически неосуществим для большого числа городов, то эвристические методы используются для нахождения приемлемых, хотя и неоптимальных решений.

В основе составления расписания лежат элементы общей теории расписаний. Технологию разработки расписания следует воспринимать не только как трудоемкий технический процесс, содержащий объект автоматизации с использованием ЭВМ, но и как акцию оптимального управления. Таким образом, это - проблема разработки оптимальных расписаний движения ТС. [42,49]

Задачу составления расписания не стоит рассматривать только как некую программу, реализующую функцию составления расписания на начальном этапе, на которой ее (программы) использование и заканчивается. Экономический эффект от более эффективного использования ТС может быть достигнут в результате работы по управлению интервалами между ними. Расписание здесь является лишь инструментом такого управления, и для наиболее полного его использования необходимо, чтобы программа сочетала в себе не только средства для составления оптимального расписания, но и средства для поддержания его оптимальности в случае изменения некоторых входных данных, которые на момент составления расписания считались постоянными. Многокритериальность этой задачи и сложность объекта, для которого строится математическая модель, обуславливает необходимость серьезного математического исследования объекта для увеличения функциональных возможностей алгоритмов составления расписаний без значительного усложнения модели и, как следствие, увеличения объемов используемой памяти и времени решения задачи. [24,25,35,36]

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

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

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Чжо Мьо Хан

§4.8 Выводы по главе 4

В результате проведенных исследований можно сделать следующие выводы:

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

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

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

-провести покоординатное дискретное уточнение времен выхода автобусов в рейс.

2.Полученые результаты моделирования подтвердили правильность предложенного подхода, и показали, что при принятых допущениях улучшение эффективности транспортных перевозок достигает 2СН-25%.

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

Рис. 4.6. Полная структурная алгоритма маршрутизации и планирования движения нескольких ТС

ЗАКЛЮЧЕНИЕ

На основании проведенных исследований можно сделать следующие выводы:

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

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

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

4. Найдена структура эвристического алгоритма многомерной маршрутизации с учетом особенностей движения автобусов в городском районе.

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

6. Моделирование на ЭВМ показало, что в целом оптимизация выбора маршрутов и расписания движения автобусов позволит повысить эффективность пассажирских перевозок на 2(К25% .

Список литературы диссертационного исследования кандидат технических наук Чжо Мьо Хан, 2010 год

1. А. Ахо, Д. Хопкрофт, Д. Ульман. Структуры данных и алгоритмы. М.: «Вильяме», 2000.

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

3. Банди Б. Методы оптимизации: Вводный курс. М.: Радио и связь, 1988.

4. Васильев Ю.Л., Ветухновский Ф.Я., Глаголев В.В. и др. Дискретная математика и математические вопросы кибернетики. М.: Наука, 1974.

5. Васильева Е.М., Игудин Р.В., Лившиц В.Н. и др. Оптимизация планирования и управления транспортными системами М. «Транспорт», 1987.

6. Вентцель Е.С. Введение в исследование операций. Изд-во «Советское радио», 1964.

7. Верж К. Теория графов и ее применения. М.: ИЛ, 1962.

8. Вирт Н. Систематическое программирование. М.: Мир, 1978.

9. Гасс С. Линейное программирование. -М.: Физматгиз, 1961.

10. Гладков Л.А., Курейчик В.М., Курейчик В.В. Основы теории алгоритмов: Учебное пособие по курсу «Математическая логика и теория алгоритмов». — Изд-во ТРТУ, 2002.

11. Глушков В. М., Летичевский A.A. Теория дискретных преобразователей // Избр. Вопр. Алгебры и логики. Новосибирск: Наука, 1973.

12. Глущков В. М., Цейтлин Г.Е., Ющенко Е. Л. Алгебра, языки, программирование. Киев: Наук, думка, 1985.

13. Гришанин Ю.С., Лебедев, Г.Н., Липатов A.B., Степаньянц Г.А. Теория оптимальных систем. — М.: Изд-во МАИ, 1999.

14. Гроссман И., Магнус В. Группы и их графы. М.: Мир, 1971.

15. Емеличев В.А., Мельников О.И. и др. Лекции по теории графов. М.: Наука, 1990.

16. Еремин И.И., Астафьев H.H. Введение в теорию линейного и выпуклого программирования. -М.: Наука, 1976.

17. Ермаков С.М., Жиглявский A.A. Математическая теория оптимального эксперимента. -М.: Наука, 1987.

18. Зуховицкий С.И., Авдеева Л.И. Линейное и выпуклое программирование. — М.: Наука, 1964.

19. Клини С. Введение в метаматематику. М.: ИЛ, 1957.

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

21. Куратовский К., Мостовский А. Теория множеств. М.: Мир, 1970.

22. Курош А.Г. Теория групп. М.: Наука, 1967.

23. Лавров И. А., Максимова Л. Л. Задача по теории множеств, математической логике и теории алгоритмов. М.: Наука, 1975.

24. Левитин A.B. Алгоритмы: введение в разработку и анализ. М.: «Вильяме», 2006.

25. МакКоннелл Д. Основы современных алгоритмов. — М.: Техносфера, 2004.

26. Малков В.П., Маркина М.В. Поэтапная параметрическая оптимизация. Учебное пособие. Н.Новгород: Издательство Нижегородского университета, 1998. 142 с.

27. Марков А. А., Нагорный H. М. Теория алгоритмов. М.: ФАЗИСТ, 1996.

28. Морз Ф.М., Кимбелл Д.К. Методы исследования операций Изд-во «Советское радио», 1956.

29. Ope О. Теория графов. М.: Наука, 1980.

30. Плохотников К.Э. Вычислительные методы. Теория и практика в среде MATLAB: курс лекций. Учебное пособие для вузов. М.: Горячая линия-Телеком, 2009.

31. Пономарев В.Ф. Дискретная математика для инженеров. Учебное пособие для вузов. М.: Горячая линия-Телеком, 2009.

32. Понтрягин Л.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф. Математическая теория оптимальных процессов. Физматгиз, 1961.

33. Ромакин М.И. Элементы линейной алгебры и линейного программирования. Изд-во «Высшая школа», 1963.

34. Солодовников А. Введение в линейную алгебру и линейное программирование. -М.: Просвещение, 1966.

35. Стенбринк П. Оптимизация транспортных сетей. М. «Транспорт», 1981.

36. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. -М.: Наука, 1986.

37. Таха X. Введение в исследование операций. М.: Мир, 1985.

38. Уилсон Р. Введение в теорию графов. М.: Мир, 1977.

39. Ф.Препарата, М.Шеймос. Вычислительная геометрия: Введение. М.: Мир, 1989.45. форд JI.P., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.

40. Френкель А., Бар-Хиллел И. Основания теория множеств. М.: Мир, 1966.

41. Харрари Ф. Теория графов. М.: Мир, 1973.

42. Харрари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977.

43. Эльсгольц Л.Э. Дифференциальные уравнения и вариационное исчисление. — М.: Наука, 1969.

44. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. Физматгиз, 1963.51. http://ru.wikiDedia.org/wiki/Алгоритм Дейкстры

45. Dijkstra Е. W. A note on two problems in connexion with graphs. // Numerische Mathematik. V. 1 (1959), pages 269-271.53. http://ru.wikipedia.org/wiki/MeTQд ветвей и границ54. http://ru.wikipedia.org/wiki/Алгоритм поиска А*

46. Ravindra К. Ahuja, Kurt Mehlhorn, James В. Orlin and Robert E. Tarjan. Faster Algorithms for the Shortest Path Problem. Journal of the ACM, 37:213-223, 1990.