Введение 3
Постановка задачи 5
Обзор литературы 6
Глава 1. Математические модели маршрутизации 7
1.1. Классическая задача коммивояжёра 7
1.2. Классическая задача маршрутизации транспорта 9
1.3. Задача маршрутизации транспорта с временными окнами
(VRPTW) 12
1.4. Задача маршрутизации транспорта для оптимизации порядка реагирования аварийно-спасательных служб 14
Глава 2. Способы решения задач маршрутизации транспорта ... 17
2.1. Обзор и классификация методов 17
Глава 3. Распознование наледи посредством искусственных нейронных сетей 22
3.1. Персептрон Розенблатта 22
3.2. Многослойный персептрон 24
3.3. Сверточная нейронная сеть 29
Глава 4. Оптимизация порядка реагирования аварийно-спасательных
служб в зимнее время года 34
Заключение 40
Список литературы 41
Приложение 46
На сегодняшний день задачи маршрутизации транспорта используются повсеместно. От международных доставок товаров до доставок еды сервисами доставки. Нахождение оптимального пути дает компаниям возможность сэкономить, не используя невыгодные маршруты. Неизвестно, кто впервые рассмотрел задачу коммивояжера, но многие века она волновала множество ученых и интузиастов, а в последствие нашла свое продолжение в множествах других работ и вылилась в задачу маршрутизации транспорта, которая в современном мире является крайне важной темой, поскольку ввиду глобализации и технологических прорывов, локальные и международные передвижения стали повсеместными для многих компаний.
Одной из угроз жизни и здоровья граждан является падение наледи с крыш зданий. Согласно данным по здравоохранению Санкт-Петербурга [1], с 1 января 2019 года по 13 марта 2019 года из-за падения наледи с крыш в Петербурге пострадал 91 человек, один случай оказался смертельным. По данным официального сайта Администрации Санкт- Петербурга [2] за 2019 год из 13,5 тысяч кровель города 4,2 тысячи являются потенциально опасными, то есть находятся на пешеходных маршрутах и подвержены образованию наледи.
Возможным решением данной проблемы является проведение нормализации температурно-влажностного режима на кровлях зданий, однако основной путь борьбы с падением наледи - очистка крыш домов аварийными службами от снега и сосулек. Для решения вышеописанной проблемы была поставлена задача разработать программный комплекс, который по полученным изображениям и адресам зданий, классифицирует фотографию на наличие необходимости очистки здания и строит оптимальный маршрут для аварийно-спасательных служб, тем самым снижая риск получения ущерба здоровью граждан из-за несвоевременной очистки крыш от наледи.
В работе были рассмотрены различные задачи маршрутизации транспорта и возможные методы их решения, а также принципы работы искусственных нейронных сетей. В результате проделанной работы была програмно решена задача оптимизации порядка реагирования аварийно-спасательных служб на наличие необходимости проведения работ по очистки крыш зданий от наледи. На первом этапе программной реализации задачи была подробно изучена, описана и реализована сверточная нейронная сеть для классификации изображений зданий на наличие снежных покровов и наледи на крышах, на втором этапе - поставлена задача маршрутизации транспорта для оптимизации порядка реагирования аварийно-спасательных служб и ее ограничения, реализован программный метод ее решения.
Перспективы развития
Реализованный программный комплекс решает задачи, рассматриваемые без привязки к дорогам реальной местности, что дает возможность развивать разработку для конкретного населенного пункта с его особенностями транспортного потока и располагаемыми ресурсами. А также есть возможность более точной классификации объектов по срочности выполнения работ аварийно-спасательными службами, получая больше фотографий зданий.
