Планирование расписания и управление движением пассажирского транспорта с использованием моделирующей среды

• Автор: Чжо Мьо Хан
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 111 с. : ил.

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

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

ДОСТОВЕРНОСТЬ И ПРАКТИЧЕСКАЯ ЦЕННОСТЬ.

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

достоверность.

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

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

ГЛАВА 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 Выводы ПО ГЛАВЕ
ЗАКЛЮЧЕНИЕ
ПРИЛОЖЕНИЕ
СПИСОК ЛИТЕРАТУРЫ


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