Введение
Глава 1. Анализ известных методов решения задач маршрутизации и расписания движения городского транспорта. общая постановка задачи 5
1.1. Актуальность работы 5
1.2. Цель диссертационной работы, её научная новизна, достоверность и практическая ценность 7
1.3. Научная новизна и практическая ценность работы, её достоверность 8
1.4. Общая постановка задачи 10
Глава 2. Разработка алгоритма определения траектории движения одного ТС между двумя остановками с учетом ограничений проезда в городе 14
2.1. Постановка задачи построения траектории проезда автобуса между двумя остановками в городском квартале 14
2.2. Описание алгоритма определения множества допустимых точек траектории проезда с помощью метода вороного (диаграмма вороного) 17
2.3. Выбор траектории проезда между двумя остановками по критерию минимального пути 22
2.4. Моделирование на эвм алгоритма определения траектории движения тс, проходящий через выбранное множество допустимых точек 33
Глава 3. Решение задачи маршрутизации движения группы ТС при заданной матрице расстояний между остановками 37
3.1. Анализ известных алгоритмов маршрутизации и выбор метода дейкстры для определения оптимального маршрута 37
3.1.1. Метод ветвей и границ 37
3.1.2. Метод ближайшего соседа 44
3.1.3. Волновой алгоритм 45
3.1.4. Алгоритм поиска в глубину (ширину) 46
3.1.5. Алгоритм Беллмана-Форда 49
3.1.6. Алгоритм Дейкстры 52
3.1.7. Алгоритм Джонсона 64
3.1.8. Алгоритм Флойда-Уоршелла 67
3.2. Модификация алгоритма дейкстры для задачи многомерной маршрутизации 69
Глава 4. Определение графика движения тс по заданным маршрутам, обеспечивающего максимальную прибыль 75
4.1 Постановка задачи оптимизации составления расписания 75
4.2. Формирование параметрического критерия оценки дохода от пассажирских перевозок 77
4.3. Идентификация параметров критерия оценки прибыли пассажирских перевозок при одновременном выезде транспортных средств 80
4.4. Выбор опорного решения задачи определения оптимальных моментов выезда в рейс в линейной постановке задачи 82
4.5. Уточненное субоптимальное решение задачи на базе линейного программирования 84
4.6. Описание численного алгоритма приближенного решения задачи составления расписания 88
4.7. Оценка эффективности предложенного алгоритма с помощью моделирования на эвм 89
Заключение 93
Приложение 94
Список литературы 107
