Проектирование маршрутных сетей городского пассажирского транспорта на основе эвристических алгоритмов

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

Введение ………………………………………………………………………………………………….. 15

1. Анализ предметной области …………………………………………………………………. 16

1.1. Описание маршрутной сети ………………………………………………………….. 16

1.2. Описание модели оптимизации …………………………………………………….. 16

1.3. Обзор алгоритмов для решения задачи маршрутизации ГПТ ………… 18

1.3.1. Метод ветвей и границ …………………………………………………………… 19

1.3.2. Метод ветвей и отсечений ………………………………………………………. 20

1.3.3. Метод ветвей и ценообразования ……………………………………………. 21

1.3.4. Метод ветвей и ценообразования и отсечений ………………………… 22

1.3.5. Метод сбережений …………………………………………………………………. 22

1.3.6. Метод заметания ……………………………………………………………………. 23

1.3.7. Алгоритм Фишера и Джайкумара …………………………………………… 24

1.3.8. Алгоритм лепестков……………………………………………………………….. 24

1.3.9. Улучшения внутри маршрута …………………………………………………. 25

1.3.10. Улучшения между маршрутами ……………………………………………. 26

1.3.11. Моделируемый отжиг …………………………………………………………… 27

1.3.12. Поиск с запретами ………………………………………………………………… 28

1.3.13. Управляемый локальный поиск ……………………………………………. 28

1.3.14. Поиск с переменным соседством ………………………………………….. 29

1.3.15. Адаптивный поиск в большой окрестности …………………………… 29

1.3.16. Итеративный локальный поиск …………………………………………….. 30

1.3.17. Генетический алгоритм ………………………………………………………… 30

1.3.18. Рассеянный поиск ………………………………………………………………… 31
1.3.19. Пересоединение путей ………………………………………………………….. 31

1.3.20. Алгоритм на основе муравьиных колоний…………………………….. 32

1.3.21. Алгоритм на основе пчелиного роя ………………………………………. 33

1.3.22. Алгоритм на основе роя частиц …………………………………………….. 33

1.4. Описание муравьиного алгоритма, адаптированного для решения
задачи проектирования маршрутных сетей ГПТ ……………………………………….. 34

2. Проектирование и разработка приложения ……………………………………………. 40

2.1. Описание средств разработки ……………………………………………………….. 40

2.2. Описание функциональности приложения ……………………………………. 40

2.3. Описание макроархитектуры приложения …………………………………….. 41

2.4. Описание микроархитектуры приложения ……………………………………. 42

2.5. Описание бизнес-логики приложения …………………………………………… 43

2.6. Описание пользовательского интерфейса приложения ………………….. 45

2.7. Анализ результатов работы приложения ………………………………………. 48

3. Финансовый менеджмент, ресурсоэффективность и ресурсосбережение .. 51

3.1. Предпроектный анализ …………………………………………………………………. 51

3.1.1. Потенциальные потребители результатов проекта ………………….. 51

3.1.2. Анализ конкурентных технических решений ………………………….. 51

3.1.3. SWOT-анализ…………………………………………………………………………. 53

3.2. Инициация проекта ………………………………………………………………………. 55

3.2.1. Цели и результат проекта ……………………………………………………….. 55

3.2.2. Организационная структура проекта ………………………………………. 56

3.2.3. Ограничения и допущения проекта ………………………………………… 56

3.3. Планирование управления проектом …………………………………………….. 57

3.3.1. Структура работ проекта ………………………………………………………… 57
3.3.2. План проекта………………………………………………………………………….. 57

3.3.3. Бюджет проекта ……………………………………………………………………… 58

3.3.3.1. Расчет материальных затрат проекта ………………………………… 58

3.3.3.2. Основная заработная плата исполнителей ………………………… 59

3.3.3.3. Дополнительная заработная плата исполнителей ……………… 61

3.3.3.4. Отчисления во внебюджетные фонды (страховые отчисления)
………………………………………………………………………………………………………………… 62

3.3.3.5. Накладные расходы …………………………………………………………. 62

3.3.3.6. Формирование бюджета затрат проекта ……………………………. 62

3.4. Определение ресурсной, финансовой, бюджетной, социальной и
экономической эффективности проекта ……………………………………………………. 63

3.4.1. Оценка сравнительной эффективности проекта …………………… 63

4. Социальная ответственность ………………………………………………………………… 65

4.1. Правовые и организационные вопросы обеспечения безопасности . 66

4.1.1. Специальные правовые нормы трудового законодательства ……. 66

4.1.2. Организационные мероприятия при компоновке рабочей зоны .. 66

4.2. Производственная безопасность …………………………………………………… 67

4.2.1. Анализ опасных и вредных производственных факторов ………… 68

4.2.1.1. Вредные вещества ……………………………………………………………. 68

4.2.1.2. Повышенный уровень производственного шума ………………. 69

4.2.1.3. Повышенный уровень электромагнитного излучения ……….. 69

4.2.1.4. Недостаточная освещенность рабочей зоны ……………………… 70

4.2.1.5. Отклонение показателей микроклимата……………………………. 75

4.2.1.6. Поражение электрическим током …………………………………….. 76

4.2.1.7. Короткое замыкание ………………………………………………………… 76
4.2.1.8. Статическое электричество………………………………………………. 77

4.2.2. Обоснование мероприятий по снижению уровней воздействия
опасных и вредных факторов на работника ………………………………………………. 78

4.3. Экологическая безопасность…………………………………………………………. 78

4.3.1. Анализ воздействия продукта на окружающую среду …………….. 78

4.3.2. Обеспечение экологической безопасности ……………………………… 79

4.4. Безопасность в чрезвычайных ситуациях ……………………………………… 79

4.4.1. Перечень возможных ЧС………………………………………………………… 79

4.4.2. Меры по предупреждению и ликвидации пожара……………………. 80

4.5. Заключение по социальной ответственности…………………………………. 81

Заключение ……………………………………………………………………………………………… 82

Список использованных источников ………………………………………………………… 83

Приложение А …………………………………………………………………………………………. 91

Приложение Б ………………………………………………………………………………………….. 93

Приложение В………………………………………………………………………………………….. 95

Приложение Г ………………………………………………………………………………………….. 96

Приложение Д………………………………………………………………………………………….. 98

В результате выполнения выпускной квалификационной работы было
спроектировано, создано и протестировано приложение для проектирования
маршрутных сетей ГПТ на основе муравьиного алгоритма. Приложение
написано в среде Visual Studio на языке C# с использованием шаблона Windows
Forms.
Разработанное приложение предназначено для использования на
предприятиях, отвечающих за проектирование маршрутных сетей ГПТ.
Внедрение разработанного приложения позволит значительно сократить
время проектирования маршрутных сетей городского пассажирского
транспорта, сократив трудозатраты, а также учитывать при проектировании
интересы всех участников городского пассажирского транспорта (городская
администрация, перевозчики и пассажиры).
Работа приложения была проверена на примере маршрутной сети города
Томска. Маршрутная сеть, спроектированная с использованием приложения,
удовлетворила тот же спрос на пассажирские перевозки, что существующая
маршрутная сеть города, при этом значительно превзошла ее по плотности
пассажиров прямого сообщения, то есть позволила лучше учесть интересы
всех участников ГПТ.