*Если не читали первую часть, то советую ознакомиться: https://habr.com/ru/articles/803697/
Предисловие
Всем привет, на связи снова Арсений Елисеев! Продолжаем работу над созданием веб-приложения для управления бронью ЭЗС, которое мы начинали ранее. Сейчас мы обратим внимание на практические аспекты: построение математической модели метода, его программная реализация и экономическое обоснование разработанного ИТ-решения.
Построение математической модели
И вот настало время для построения самой математической модели. Можно выделить 3 основных повторяющихся во времени процесса, стоимостные издержки протекания которых должны быть оптимизированы:
1) Прохождение частей маршрута от начальной точки/текущей зарядной станции до конечной точки/следующей подходящей зарядной станции;
2) Ожидание доступности зарядной станции;
3) Осуществление процедуры зарядки.
Попробуем представить их с помощью самого верхнего уровня целевой функции:
Стоимостное выражение времени, затрачиваемого во время прохождения частей маршрута с учетом дорожно-транспортных условий, ожидания освобождения ЭЗС и зарядки на ней, будет рассчитано путем его отождествления с упущенным расстоянием, которое могло бы быть преодолено электрокаром в этот временной промежуток, выраженным в количестве энергии для осуществления этого с переводом в конечную стоимость согласно усредненному тарифу. По этой причине стоит ввести константы: средняя скорость легкового транспортного средства в современном мегаполисе, согласно исследованию, равняется 55 км/ч, а средний тариф исходя из агрегированных данных за потребление 1 кВт-ч электротранспортным средством на зарядной станции – 15 рублей. Также после прохождения каждой части пути нужно проверять достаточность объема имеющейся электроэнергии для определения возможности достижения какого-либо из следующих пунктов маршрута для приближения к конечному пункту назначения:
Вспомним исследование румынских экспертов (Radu Flocea et al., 2022), из которого следует, что наиболее допустимым периодом времени, в течение которого пользователь может планировать бронирование слотов зарядных станций под свои нужды, равен 2-ум неделям. Для удобства наименьшим периодом, доступным для бронирования слота зарядной станции, можно принять равным 15 минутам с добавлением 5 дополнительных минут для проведения мероприятий, которые будут после завершения процедуры зарядки. В связи с тем, что мы не можем сказать, какое фактическое время ожидания будет у водителя при подъезде к слоту ЭЗС или фактическое время подготовки к инициализации сессии зарядки, то tj,m(wait) может быть смоделировано путем выбора случайного значения на отрезке от 60 до 300 секунд (потом это должно быть переведено в часы) для добавления «щепотки» стохастичности. Вместе с декомпозицией переменной ti,j(dist) и tj,m(charge) целевая функция приобретает следующий вид:
Как и говорилось ранее, совокупность ЭЗС с начальной и финальной точками маршрута представляют из себя ориентированный граф. Вполне очевидно, что нет смысла брать во внимание его вершины, географически расположенные на Урале, если поездка происходит в пределах условной Москвы. В связи с этим необходимо проводить фильтрацию слотов ЭЗС, которые будут участвовать при моделировании маршрута. Для этого я предлагаю специально разработанный подход, заключающийся в поиске середины отрезка между начальной и конечной точками маршрута и заключении в область фильтрации тех зарядных станций, чье евклидово расстояние между их координатами местоположения и координатами середины отрезка между начальной и конечной точками маршрута не более 120% евклидового расстояния половины отрезка, разделенного ранее упомянутой срединной точкой. Те самые 20% дают возможность в некотором маневре: например, можно сдать немного назад для подзарядки электромобиля с целью последующего следования уже по намеченному маршруту. Графическая интерпретация такого подхода выглядит следующим образом:
Помимо этого, необходимо исключить логические ошибки, связанные с теорией графов, по типу движения из одной вершины в ту же самую, возвращения к стартовой вершине и продолжения движения из финальной вершины. Теперь наконец-то:
Именно эта математическая модель будет использована для суммы весов граней ориентированного графа (стоимостей прохождения отрезков маршрута), а также будет служить в качестве функции приспособленности для выбора лучшей хромосомы (маршрута) при использовании генетических алгоритмов:
Также для построения альтернативного субоптимального маршрута будет использоваться метод, заключающийся в поочередном исключении зарядных станций, включенных в оптимальный маршрут, из сети по возрастанию чиса доступных у них временных окон для брони и построения нового маршрута с целью обеспечения сохранения большого выбора периодов для резервации.
Разработка веб-приложения
Этап 1. Структура и стек
*Ссылка на Github-репозиторий с открытым кодом данного веб-приложения указана в конце статьи.
Веб-сервис строится на базе контейнезированного приложения, выбор которого обуславливается его возможностью развертывания в любом окружении и операционной системе, что заметно облегчает его дистрибуцию и повышает уровень отказоустойчивости. В качестве контейнеризатора приложений традиционно используется Docker. Таким образом, служба веб-сервиса обеспечивается работой 4-х контейнеров:
1) java-application:
Основная часть бэкенда веб-приложения, на которую приходится выполнение вычислительных алгоритмов для осуществления функции маршрутизации и бронирования. Помимо этого, она также содержит логику взаимодействия с базой данных для работы с зарядными станциями и временными окнами брони. Разработана на фреймворке Spring для Java-платформы, выбор которого обуславливается скоростью языка программирования Java, удобством и популярностью в сфере веб-разработки.
2) python-application:
Вспомогательная часть бэкенда веб-приложения, которая берет на себя одну из функций основой части по расчету продолжительности сессии быстрой зарядки. Разработана на фреймворке fastAPI для Python-платформы, выбор которого обуславливается своей «легковесностью», подходящей для веб-сервиса такого размера, а также общей адаптированностью языка программирования Python для решения задач в области машинного обучения и, в частности, для создания и использования pickle-моделей.
3) frontend:
Фронтенд часть веб-приложения, которая берет на себя функции пользовательского интерфейса и связанных с ним компонентов. Разработана на фреймворке jQuery для JavaScript-платформы, выбор которого обусловлен наличием Legacy-кода других модулей.
4) postgres:
База данных веб-приложения, которая обеспечивает протекание транзакций записи, хранения и удаления информации для обсечения работы его функций. Реализована на привычной СУБД PostgreSQL. Главным образом нужна для работы с объектами зарядных станций и временных окон брони.
Этап 2. Фронтенд часть приложения
Наилучшей репрезентацией фронтенд части приложения является непосредственная демонстрация внешнего вида интерфейса и его функционала. Достижение этих целей может быть обеспечено GIF-изображением:
Можно увидеть, что при бронировании временных окон на следующий день не предлагаются периоды с 18:00 до 19:00. Теперь забегая немного в бэкенд, а точнее в базу данных, мы можем увидеть, что эти варианты были уже ранее забронированы кем-то другим:
Также внимания достоин и функционал, связанный с поиском альтернативного субоптимального маршрута. Его работа также может быть продемонстрирована GIF-изображением:
Этап 3. Бэкенед часть приложения
Для краткого разбора бэкенд части приложения для начала посмотрим на эндпоинты, присутствующие в нем:
1) /weather/getTemperature:
По данному эндпоинту возвращается округленная средняя температура в течение конкретного выбранного пользователем дня и координат его текущего местоположения или выбранной им локации. Получение данной информации обеспечивается запросом к API сервиса «Open-Meteo»;
2) /schedule/getTimeWindows:
По этому эндпоинту происходит получение из базы данных списка уже забронированных временных окон для каждого слота зарядной станции на ранее выбранную пользователем дату совершения маршрута. Этот список необходим для последующей фильтрации в интерфейсе только доступных для брони временных окон;
3) /weather/saveTimeWindows:
По данному эндпоинту происходит сохранение выбранных временных окон брони для каждого слота зарядной станции в маршруте в базу данных вместе с выданным кодом брони;
4) /routing/getFilteredStations:
По этому эндпоинту возвращается список слотов ЭЗС, удовлетворяющих параметрам, выбранным пользователем во вкладке «Сведения», для последующего нанесения меток на интерактивную карту и построения маршрута;
5) /routing/getRoute:
По данному эндпоинту возвращается список пунктов маршрута вместе с их координатами и дополнительными параметрами в виде расстояния от стартовой точки маршрута до этого пункта, продолжительности пути от стартовой точки до этого пункта и продолжительности сессии зарядки (если пункт является слотом ЭЗС). Маршрутизация осуществляется путем обращения к API сервиса «OpenRouteService». Стоит отметить, что в бесплатной версии этого API, которая и используется в демоверсии этого приложения, интервал между запросами составляет 2 секунды.
Подробнее остановимся на последнем методе. Именно в его пределах реализуется один из ранее упомянутых разрешающих алгоритмов поиска оптимального пути: метод Дейкстры или генетические алгоритмы. Для реализации работы этих подходов необходима матрица смежности ориентированного графа, и в рамках их программной реализации она представляется в виде ассоциативного массива, где ключом является id зарядного слота ЭЗС, а значением – ассоциативный массив с ключом в виде id следующего возможного для достижения слота зарядной станции и значением в виде ассоциативного массива характеристик этого пункта маршрута. Наиболее простым объяснением структуры будет ее непосредственная демонстрация:
В рамках выбора наиболее предпочтительного алгоритма для нахождения оптимального пути проводятся 5 тестов, суть которых заключается в построении 5-и отдельных маршрутов при разных условиях с последующей фиксацией их значений критериев эффективности для каждого из отобранных методов. Результаты тестирования могут быть представлены следующей таблицей:
Результаты экспериментов показывают, что по всем введенным критериям, кроме условной стоимости маршрута, где наблюдается паритет, алгоритм Дейкстры демонстрирует большее число баллов. В связи с этим, именно он будет являться разрешающим и будет использоваться в демоверсии веб-приложения.
Экономическое обоснование разработанного веб-приложения
Рассчитаем экономический эффект, оказываемый предлагаемым веб-приложением, на финансовое состояние компании на основе расчета одного из важнейших показателей, демонстрирующего эффективность внедряемого ИТ-решения на каком-либо предприятии: доходности собственного капитала (ROE). Он определяет, какой объем чистой прибыли приносит компания на вложенный капитал. Для этого будет использоваться популярная модель стратегической прибыли от консалтинговой компании «DuPont», основывающаяся на данных из бухгалтерского баланса, а также отчета о прибылях и убытках от 2023 года. Этот инструмент предоставляет возможность в наглядной презентации взаимозависимостей между финансовыми показателями предприятия и влияния изменений их значений в связи с внедрением разработанного веб-приложения на ранее указанный важный индикатор.
В связи с необходимостью сохранения конфиденциальности финансовой информации компании расчет статей потенциальных доходов и расходов, связанных с внедрением и эксплуатацией веб-сервиса, пропускается. Рассмотрим непосредственные результаты цепных подстановок в модели стратегической прибыли:
Из предложенной модели можно сделать вывод, что себестоимость реализованной продукции увеличивается в связи инвестициями, вложенными в веб-приложение, в то время как валовые поступления от продаж увеличиваются ввиду предложения новой услуги по бронированию слотов зарядных станций. В связи с этими изменениями в показателях происходит увеличение валовой прибыли, и при неизменных величинах общих затрат из-за отсутствия влияния на структуру постоянных и переменных издержек она увеличивает значение подоходного налога. Данная цепочка изменений влечет за собой увеличение чистой прибыли, что увеличивает маржу чистой прибыли на примерно 0.01%. В связи с отсутствием влияния внедрения веб-приложения на структуру баланса холдинга и увеличением валовых поступлений от продаж значение коэффициента оборачиваемости активов увеличивается на примерно 0.00008. Ввиду данной цепочки изменений величина доходности активов возрастает на примерно 0.01%, что при неизменном финансовом рычаге из-за отсутствия изменений в структуре баланса холдинга приводит к увеличению доходности собственного капитала на примерно 0.01%. Таким образом, целевой показатель модели действительно увеличивается после внедрения рассматриваемого веб-приложения, что доказывает приносимый им положительный экономический эффект для компании.
Итоги
В рамках этой работы удалось пройти сквозь процесс создания приложения: от теоретических основ до программной реализации. Надеюсь, что представленный материал будет полезен коллегам, которые работают в сфере электротранспорта в России. Расскажите, как вы решаете различные задачи в этой области, а также делитесь мнением о данной работе в комментариях. Всем добра!
*Репозиторий с открытым кодом приложения: https://github.com/yelis-alt/research/tree/prod/stations_booking_service
