On the transition to the waste collection management using an intellectual system by "Smart City" project.

Dolinina Ol'ga Nikolaevna PhD in Technical Science Associate Professor, Department of Applied Information Technologies, Gagrin Saratov State Technical University 410054, Russia, Obl Saratovskaya oblast', g. Saratov, ul. Politekhnicheskaya, 77 odolinina09@gmail.com

Pechenkin Vitalii Vladimirovich Doctor of Sociology Professor, Department of Applied Information Technologies, Gagrin Saratov State Technical University 410054, Russia, Obl Saratovskaya oblast', g. Saratov, ul. Politekhnicheskaya, 77 pechv@mail.ru

Введение

Разработка алгоритмов и систем для управления вывозом твердых бытовых отходов из крупных мегаполисов является актуальной по причине как увеличения количества этих отходов, так и увеличения трафика в городах. В каждом городе существуют специальные организации, ответственные за сбор и вывоз бытовых отходов на полигоны или специализированные предприятия по их переработке. График вывоза отходов формируется либо на регулярной основе, либо по запросу. Вполне реальной является ситуация, когда специализированный грузовой автомобиль (СГА), использующий регулярную схему составления расписания, прибывает на площадку с контейнерами для сбора бытовых отходов (КП), но контейнеры оказываются незаполненными. Происходит и обратная ситуация – контейнеры на КП полностью заполнены, но прибытие транспорта по расписанию предусматривает более поздние посещения и вывоз отходов. Это происходит по причине отсутствия актуальной информации о наполненности контейнеров. Сама постановка задачи является частью общей проблемы формирования комфортного и безопасного окружения в современных городах и связана с направлением «Умный город» (Smart City) ^[1]. «Среда умного города» рассматривается как часть технологии «Умный город».

Существует много определений понятия »Умный город» ^[2]. Важной составляющей этой концепции является использование целого ряда современных информационных технологий, но основной фокус делается на использовании мобильных решений. Суть самой концепции можно определить таким образом «комбинация информационно–коммуникационных технологий и технологии Web 2.0 в комплексе с другими организационными, проектными подходами для упрощения и ускорения управленческих процессов и поддержки инновационных решений при управлении городом с целью повышения устойчивости и комфортности городского пространства» ^[3].

В литературе описаны специальные программные и аппаратные средства, целью которых является составление расписаний по вывозу бытовых отходов, используются детекторы, позволяющие получать актуальную информацию о наполненности контейнеров и всей площадке в целом ^[4-8]. Однако, одной из важных проблем продолжает оставаться статический характер таких решений, отсутствие учёта текущего трафика дорожной сети и ее особенностей в конкретном городе и/или районе города. В настоящее время отсутствуют комплексные решения, которые используют одновременно несколько оптимизационных критериев и учитывают всю имеющуюся информацию о динамическом состоянии всей системы. В статье предлагается подход использования гибридной интеллектуальной системы принятия решения, сочетающей оптимизационный алгоритм построения системы кратчайших путей, такие динамически меняющиеся параметры системы, как: степень заполнения контейнеров, трафик дорожной сети, рекомендации экспертов по составлению расписаний, а также экспертные знания о возможных дорожных ситуациях в различных точках маршрутов.

Описание предлагаемого подхода

Гибридная интеллектуальная система «Чистый город», разработанная для оптимизации процесса вывоза бытовых отходов позволяет решать следующие задачи:

1. генерировать специальные сообщения, которые позволяют контролировать степень наполненности контейнеров для бытовых отходов;

2. управлять процессом обмена информацией со специализированными грузовыми автомобилями, координируя их работу и формируя запросу на обслуживание контейнеров только в случае их заполнения;

3. формировать систему расписания по вывозу отходов в городе;

4. оптимизировать маршрут для грузовых автомобилей;

5. предлагать варианты рационального размещения контейнеров на основе анализа имеющихся массивов статистических данных.

Система «Чистый город» позволяет решать следующие задачи, которые являются по своей сути не только экономическими, но и социальными:

- повысить экономическую эффективность (экономия горючего, расходных материалов, оптимизация графика занятости персонала, сокращение времени на вывоз отходов) специализированного предприятия, занимающегося вывозом бытовых отходов;

- улучшение общей санитарной и эпидемиологической ситуации в городах.

Компонентами системы «Чистый город» являются как программное обеспечение, так и специальное оборудование, которое осуществляет мониторинг ситуации на КП. Используется следующее оборудование:

- оборудование, установленное на КП;

- оборудование, установленное на СГА.

Каждая КП оборудуется двумя типами электронных устройств: ресивер трансмиттер, принимающий информацию от контейнеров и сенсоры, установленные на каждом контейнере для передачи данных о степени его наполненности.

На внутренней стороне каждого контейнера устанавливается специальное вандалоустойчивое устройство, которое позволяет фиксировать превышение определённого уровня его заполнения. Сенсор (инфракрасный или ультразвуковой) уровня предназначен для сигнализации о заполнении контейнера. Сенсор передает информацию по радиоканалу на ресивер–трансмиттер, установленный на каждой КП. Все устройства имеют автономные источники питания. Для экономии энергии устройства, управляемые микроконтроллерами, работают в определённые периоды времени.

Информация от контейнеров передается общим трансмиттером серверу системы, используя встроенный GSM модуль.

Функциями клиентской части системы являются:

- регистрация СГА в качестве участника системы с определённым назначаемым статусом;

- представление текущего состояния контейнеров на КП;

- автоматическая авторизация в системе с возможностью получения информации о назначенных системой заданий для СГ;

- графическое представление возможных маршрутов движения на экране мобильного устройства;

- периодическое формирование запросов на обновление информации на сервере о позиции и статусе СГА.

Функции серверной части приложения:

- хранение информации о КП: адрес, координаты, число и ёмкость контейнеров, дата последнего обслуживания;

- хранение информации о СГА: тип, идентификаторы мобильного устройства, ёмкость;

- обеспечение процессов сбора и обработки информации с различных КП;

- мониторинг актуального состояния контейнеров на КП, выработка запроса на обслуживание КП;

- назначение СГА на обслуживание КП при её заполнении, во внимание принимается текущая позиция СГА;

- формирование нескольких вариантов маршрута с учётом текущего трафика и передача их на мобильное устройство шофера СГА;

- хранение и обработка информации, которая поступает с КП;

- формирование статистических отчетов.

Программно–аппаратный комплекс обеспечивает интерфейс между системой, формирующей расписание, контейнерными площадками и грузовыми автомобилями для вывоза отходов следующим образом:

1. Информация о состоянии контейнеров на КП (степень наполненности) передается серверному приложению, которое вычисляет оптимальное расписание движения. Если КП заполнена на 70% или более в системе формируется запрос на её обслуживание.

2. КП добавляется в список на обслуживание.

3. КП представлены в системе как вершины сети (далее эта сеть будет определена). При обработке поступающей информации происходит обновление параметров сети. Один из параметров дуг сети представляет текущий на данный момент трафик и состояние отрезка дороги. Данные о дорожной сети запрашиваются у онлайн навигационных сервисов.

Серверное приложение вычисляет несколько вариантов оптимального маршрута для обслуживания КП, которые оцениваются экспертной системой и передаются на мобильное устройство водителя СГА. Водитель видит варианты маршрута движения при обслуживании КП и выбирает один из них. Статус СГА изменяется в системе. Структура системы представлена на рис. 1.

Предложенные далее формализация задачи и метод построения решения обладают научной новизной по следующим причинам. Во-первых, сетевая модель имеет динамическую природу ^[9]. Во-вторых, при формировании плана обслуживании контейнеров учитывается автоматически собираемая информация об их наполнении. В-третьих, в системе учитываются динамические параметры загруженности дорожной системы. И наконец, последнее – полученные решения оцениваются экспертной системой и представляются на выбор водителю СГА. Учёт всех перечисленных факторов позволяет назвать построенную систему гибридной системой управления.

Рис. 1. Структура системы «Чистый город»

Формализация задачи построения динамического оптимального маршрута

Формальной моделью при решении задачи является взвешенная сеть, имеющая ориентированные дуги и неориентированные рёбра

G=(V, E, f, g, w) (1)

где:

V – множество вершин сети;

E – множество дуг и ребер (далее будем говорить только о рёбрах), соответствующее дорожной сети города, они соединяют позиции на карте, содержащие КП, полигоны для вывоза отходов, гаражи СГА;

f : V `xx` T `->` R – функция веса вершин в момент времени t, определяет время необходимое для проезда СГА через эту вершину;

g : E `xx` T `->` R – функция веса ребер в момент времени t, определяет время необходимое СГА для проезда по участку дорожной сети, связанному с этим ребром;

w : V `xx` T `->` R – функция веса вершин в момент времени t, определяет количество заполненных контейнеров, требующих обслуживании, на КП, соответствующей конкретной вершине сети.

Вершины сети отображаются на карту города и представляют позиции на ней, а ребра – дорожную сеть. Множество V определяется следующим образом

V = V₁ `uu` V₂ `uu` V₃ `uu ` V₄, (2)

где:

V₁– вершины, соответствуют КП;

V₂ – вершины, соответствуют полигонам;

V₃ – вершины, соответствуют позициям гаражей для СГА;

V₄ – вершины, соответствуют соединительным позициям на дорожной сети (перекрёстки, площади).

Отображение f определяется следующим образом.

Вес вершин определяется как время, необходимое для проезда СГА через неё. Определение веса зависит от того, к какому блоку разбиения принадлежит вершина и от текущих параметров системы:

f(v, t)– время необходимое для обслуживания контейнеров на КП для v `in` V₁;

f(v, t) – время необходимое для разгрузки на полигоне для v `in` V₂;

f(v, t) = 0 для v `in` V₃;

f(v, t)– величина, которая характеризует время, необходимое для проезда СГА через перекрёсток, площадь (зависит от текущего трафика дорожной сети), эта величина определяется, исходя из статистического анализа экспериментальных данных или запросом к онлайн сервису для v `in` ` ` V₄.

Отображение g определяется следующим образом. (временные характеристики участков дороги)

Для каждого ребра e `in` ` ` E g(e, t) – величина времени, необходимая для проезда по сегменту дорожной сети (зависит от ограничений скорости, состояния дороги, длины участка, трафика) в момент времени t.

Последнее отображение w определяет количество наполненных контейнеров для вершин, соответствующих КП. Для всех вершин из блоков разбиения V₂, V₃, V₄ и для любого момента времени t значение w(v,t) равно 0.

Для вершин, соответствующих КП значение этой функции возвращает количество заполненных контейнеров на этой площадке в момент времени t.

Значения весов для всех вершин и рёбер сети в момент времени t называется разметкой сети. В момент времени t = 0 мы называем разметку начальной. Динамические параметры сети зависят от дорожной ситуации (трафика) и меняющегося по времени заполнения контейнеров. Эти изменения приводят к изменению разметки сети.

Пусть СГА вмещает содержимое L контейнеров. В начальный момент времени (t=0) на КП v_j имеется K_j заполненных контейнера, содержимое которых необходимо вывезти на полигон. Ясно, что K_j = w(v_j,0). Следовательно, СГА должен посетить полигоны по крайней мере S_j раз, где

(3)

Общее число циклов загрузка–разгрузка в этом случае будет равно

Общее число заполненных контейнеров равно

Предположим, что единственный СГА должен обслужить все КП и вывезти отходы на полигон. В этом случае может быть предложено несколько возможных оптимизационных критериев. В этой работе рассматривается только оптимизация по затраченному на обработку отходов времени. Одним из возможных критериев оптимизации может быть, например, максимизация обработанного объема отходов.

Обозначение. Пусть P – маршрут в сети G, U `sube` V . Обозначим |P| длину маршрута P, и |P|_U– число вхождений вершины из множества U в P. Ясно, что для любого маршрута в сети |P| = |P|_V .

Формулировка задачи для одного СГА

Для данной динамической сети найти маршрут

P = v₀, v₁, v₂, ... , v_m

такой, что

1.v₀ = v_m ; v₀ `in` V₃ (СГА выезжает из гаража в момент начала работы и возвращается в этот же гараж по её окончании);

2. (каждая КП посещается столько раз, сколько необходимо для вывоза заполненных контейнеров);

3. (полигоны посещаются S раз – требуемое количество посещений полигонов для разгрузки СГА);

4. , где минимум берётся по всем маршрутам, которые удовлетворяют условиям 1, 2, 3.

Моменты времени t_iсоответствуют времени посещения вершин сети. Ясно, что

t₁ < t₂ < …< t_m

Обобщение формулировки задачи для n СГА

Пусть количество используемых СГА равноn. Для данной динамической сети необходимо построитьn маршрутов

(i=1,n)

И следующие условия удовлетворяются

1., ( все СГА выезжают из гаража в момент начала работы и возвращаются в этот же гараж по её окончании);

2. (каждая КП посещается столько раз, сколько необходимо для вывоза заполненных контейнеров);

3. (полигоны посещаются S раз – требуемое количество посещений полигонов для разгрузки СГА);

4. , где минимум берётся по всем маршрутам, которые удовлетворяют условиям 1, 2, 3.

tⁱ_j соответствуют времени посещения вершин сети i-м СГА. Ясно, что для любого i=1,n

Если необходимо обеспечить равномерную загрузку всех СГА, добавляется ещё одно условие

5. Пусть , тогда

Описанный далее алгоритм, строящий один из возможных маршрутов, учитывает динамический характер задачи, принимая во внимание изменение трафика Информация о необходимом времени для передвижения по городской дорожной сети может быть получена от онлайн картографических сервисов, которые учитывают степень загруженности сегментов маршрута. Одним из таких сервисов является Google Maps Directions API ^[10]. Этот сервис доступен для внешних систем через HTTP интерфейс, посредством формирования специальным образом построенных URL запросов. В качестве позиций можно задавать координаты (широта/долгота) точек маршрута или их имена, добавляя в строку ключевые поля, определённые в API. HTTP запрос к Google Maps Directions API может содержать полезные дополнительные параметры. Например, ключевое поле «waypoints» позволяет определить промежуточные пункты, через которые должен пройти маршрут. Таких точек может быть до 23 в бизнес приложениях. Точки, обозначенные как «avoid», будут, наоборот, исключены из строящегося маршрута.

Ключевое слово «mode» позволяет задать тип используемого транспортного средства. В качестве ответа пользователь сервиса получает JSON массив “routes”, содержащий один или более сегментов маршрута «legs», зависящих от наличия в запросе промежуточных точек. Каждый сегмент маршрута описывается набором параметров «distance» (длина сегмента в метрах), «duration» (время для проезда по сегменту в секундах), «duration_in_traffic» (время проезда по сегменту с учетом дорожной ситуации, трафика).

Эти параметры загружаются в сетевую модель при вычислении оптимальных маршрутов, определенных выше. Серверная часть системы определяет несколько кратчайших путей неукорачивающихся по времени, которые предъявляются водителю СГА.

В качестве примера опишем структуру алгоритма для СГА, который имеет статус «Готов к обслуживанию» и выдает запрос на определение и вычисление маршрута к КП – «ПОСТРОЕНИЕ МАРШРУТА ДЛЯ ОДНОГО СГА». Алгоритм предполагает следующие статусы для СГА и поступающие от него запросы:

- (Статус) Регистрация

- (Статус) Готов к обслуживанию

- (Статус) Неисправен

- (Статус) На маршруте

- (Запрос) Сформировать расписание и маршрут на весь день

- (Запрос) Сформировать задание и маршрут на обслуживание КП

- (Запрос) Сформировать оптимальный путь на полигон.

Алгоритм построения динамического оптимального маршрута

/* В тексте алгоритма КП обозначается как AGC

GETOptimalRouteToAGC

Input: <Позиция на маршруте>, <Тип запроса>

Output: Optimal routine to AGC

If = then

/*Получение информации о состоянии контейнеров на КП

/*Возможные статусы: <Заполнена>, <Обслуживается>, <Не заполнена>

For all v ` ` V₁ get Status(v) EndFor

/*Получение информации о текущем трафике

UPDATEinfoong(e,)

/*Запрос на получение информации и наполнении контейнеров

AGC_SET := `O/`

For all AGC v `in` V₁ do

If Status(v) = <Заполнена> then

Update info on w(v,t)

AGC_SET := AGC_SET.Add(v)

EndIf

EndFor

/*Выбор оптимального маршрута согласно экспертным правилам

AGC_Next := GETOptimalAGC(AGC_SET)

AGC_Next_Path := GETOptimalRouteToAGC(AGC_Next)

Transfer data to the client application

Status(AGC_Next) := <Обслуживается>

End If

Рис. 2. Демонстрация наполненности контейнеров на экране клиентского мобильного приложения

Метод GETOptimalRouteToAGC строит k-кратчайших простых путей и является реализацией алгоритма Йена (ациклический, один источник) ^[11]. Этот алгоритм имеет вычислительную сложность O(kn³), где O(n²) – сложность вычисления кратчайшего пути. Здесь n обозначает количество вершин в сетевой модели дорожной системы. Величина k установлена в значение 5, исходя из эмпирических соображений. Все построенные маршруты ранжируются экспертной системой, основанной на базе знаний специалистов организации, занимающейся вывозом отходов. Одним из оснований ранжирования является экспертный опыт по оценке маршрутов в зависимости от рассматриваемого временного периода. Список маршрутов, оцененный по времени прохождения и экспертной оценке передаётся водителю СГА.

После выгрузки отходов из контейнеров на КП сенсоры, установленные на них, автоматически изменяют статус контейнеров в системе. В случае неисправности сенсора предусмотрена ручная установка статуса контейнера шофёром СГА и формирование отметки о необходимости замены или ремонта сенсора.

В системе «Чистый город» описанный алгоритм (и некоторые другие) строит оптимизированные по длине маршруты, которые оцениваются с помощью встроенной интеллектуальной подсистемы, продукционная база знаний которой содержит правила вида:

pr_i: r_i: v_i: Если a_j тогда v_k с уверенностью c_l иначе v_m (4)

где

r_i `in` R – множество правил,

pr_{i `in`} PR – множество приоритетов,

v_i, v_m `in` V – множество V, определённое в (2);

a_j` in` A – множество фактов, которые представляют текущую дорожную ситуацию,

c_l `in` C – множество лингвистических переменных,

Здесь C={‘возможно’, ‘вероятно’, ‘скорее всего}, c_l представляет нечёткую переменную, описанную с помощью трапециевидной функции принадлежности. Правила формируются экспертами (специалистами в области управления дорожным движением, сотрудниками организации, вывозящей отходы), которые хорошо знакомы с закономерностями возникновения пробок в городе. Например, при наличии аварии по пути следования и необходимости принятия решения об изменении маршрута интеллектуальная система при помощи нечеткого алгоритма Мамдани генерирует решение на основе экспертных знаний, учитывающих особенности различных участков маршрута, заключающееся либо в продолжении движения по маршруту, либо в его изменении. Важным является учет приоритетов правил, которые устанавливаются экспертами. При наличии приоритета выбор делается в пользу правила, имеющего приоритет выше 80 по 100-балльной шкале.

База знаний, например, содержит правила представленного ниже вида:

80: r₃₂ : v_i `in` V₄ : if status (СГА) = “На маршруте” AND f(v_i, t) > 50 then Пересчитать AGC_Next

100: r₅ : v_i `in ` V₄ : if status (v_i) =”Занят” then Продолжить путь с уверенностью “Скорее всего”

100: r₁₄ : v_i `in` V₄ : if status (v_i) =”Занят” then Рассчитать AGC_Next

Рис. 3. Структура системы принятия решений

3. Обсуждение

Для оценки эффективности предложенной модели был проведен вычислительный эксперимент со стохастической моделью реальной системы. В используемой модели рассматривался район города, в котором присутствует 56 контейнерных площадок с 250 контейнерами на них. В модели предусмотрено наличие двух полигонов, на которые вывозятся бытовые отходы. Каждый контейнер имеет вместимость до 100 кг., вместимость каждого СГА установлена в 5000 кг. (реальная вместимость зависит от степени сжимаемости и характера отходов). Количество СГА в моделируемой системе установлено равным 24. Результаты и параметры вычислительного эксперимента показаны на рис. 4.

Прототип системы «Чистый город» использовался для моделирования процесса вывоза бытовых отходов на примере Октябрьского района г. Саратова с население около 1 млн. человек. Пилотная эксплуатация и уточнение параметров системы осуществлялись с сентября 2015 года в течение одного года. Экономия времени при обработке бытовых отходов на синтетических данных достигает 21% по сравнению с использованием регулярных расписаний.

Рис.4. Результаты выполнения оптимизационного алгоритма

Можно отметить и наличие проблемных аспектов для представленной системы. Например, плотность и объем отходов в контейнерах могут иметь различную степень сжимаемости. Это может произойти, если в контейнере окажутся плотные строительные материалы, которые обладают существенным весом. В этом случае количество обработанных контейнеров на КП может существенным образом измениться. Если содержимое контейнеров содержит хорошо сжимаемые отходы, СГА сможет обработать большее их число. По этой причине количество наполненных контейнеров не полностью описывают ситуацию на КП и требуют учёта дополнительных параметров. Другим проблемным вопросом, который требует учёта в системе, является необходимость введения в рассмотрение лицензий на работу с конкретными полигонами для бытовых отходов.

4. Заключение

Система «Чистый город» является гибридной системой управления, которая базируется на совместном использовании нескольких технологий оптимизации расписания при вывозе бытовых отходов. Используются мобильные технологии, связывающие аппаратно–программные компоненты системы в единое целое, учитывается актуальное состояние дорожной сети, опыт экспертов применяется для оценки построенного расписания. Интеллектуальная часть системы представлена экспертной системой, база знаний которой содержит экспертные знания о дорожных ситуациях в различных точках маршрута, формализованные в виде нечетких правил. Варианты маршрута рассчитываются с помощью оптимизационного алгоритма построения нескольких вариантов кратчайшего пути. В статье представлен только один оптимизационный критерий для выбора маршрута движения при обслуживании КП – время необходимое для обслуживания площадок с бытовыми отходами. Очевидно, что динамический характер выбранной математической модели всей системы позволяет добавлять иные оптимизационные критерии. Таковыми могут быть расход горючего, материальных ресурсов, требование «равномерной» загрузки всех грузовых автомобилей при составлении расписания. Преимуществом описанной системы является одновременный учет ситуации с заполнением контейнеров для отходов, дорожной ситуации при прокладке маршрутов и экспертных правил.