Несвоевременность вывоза и высокие затраты на транспортировку – основные проблемы, связанные с вывозом ТБО. В связи с этим необходимо решить оптимизационную задачу транспортировки таким образом, чтобы компании, занимающиеся вывозом отходов, могли самостоятельно получать маршруты для мусоровозов. Уменьшение длины маршрутов поможет уменьшить время, требуемое для сбора отходов, и снизить затраты на транспортировку.
Для формирования алгоритма сбора отходов требуются исходные данные: координаты контейнерных площадок и объем образующихся на них отходов (таблица 1), а также параметры используемой техники (таблица 2).
Таблица 1 – Исходные данные: координаты контейнерных площадок и объем образующихся на них отходов
Координата X |
Координата Y |
Объем V |
X1 |
Y1 |
V1 |
X2 |
Y2 |
V2 |
… |
… |
… |
Xn |
Yn |
Vn |
Таблица 2 – Исходные данные: используемая техника
Объем кузова K1 |
Коэффициент сжатия с |
Вместимость кузова vi |
K1 |
c1 |
v1 |
K1 |
c2 |
v2 |
|
… |
… |
K1 |
cn |
vn |
У исходных данных есть значения Xmin, Xmax, Ymin, Ymax, а также ΔX и ΔY. Рабочая координатная ось будет ограничена прямоугольником (рисунок 1).
Предлагаемый алгоритм поиска маршрутов объединяет алгоритм кластеризации К-средних (k-means) [3], алгоритм Свира и классический жадный алгоритм:
Рисунок 1 – Рабочая координатная ось
1. Найдем потребность в транспорте. От суммарного объема собираемых отходов последовательно отнимаем объемы используемых мусорозов. При этом мусоровозы способны совершить за рабочий день два рейса, поэтому отнимаем объем каждого мусоровоза дважды до тех пор, пока остаток не станет отрицательным. Получим требуемое значение рейсов A, необходимых для транспортировки. Объемы автомобилей попарно равны: v1= v2, v3= v4 и т.д.
2. Реализации алгоритма k-средних требуются координаты начальных точек-центроидов. Находим центроиды:
· если A=1, то единственный центроид будет находиться в центре координатной оси:
[Cx1;Cy1]=; (1)
· если A>1, необходимо расположить центроиды в различных, равноудаленных от центра точках. При этом угол . По рисунку 1 видим, что координаты i-го центроида равны:
[Cxi;Cyi]=. (2)
3. Согласно алгоритму k-средних производим кластеризацию начальных точек [Xn;Yn] с числом центроидов, равным A, и координатами [Cxi;Cyi]. В результате нескольких итераций алгоритма получим принадлежность:
. (3)
4. Поочередно рассматриваем мусоровозы и центроиды vi и Сi:
· если vi < Сi, то по алгоритму Свира (дворника-стеклоочистителя) выбираем первые точки, чтобы вместить их в автомобиль i объемом vi. Оставшиеся контейнерные площадки переходят в общую массу точек для повторной кластеризации с оставшимися точками. В свою очередь, включенные точки формируются в маршрут на основе применения жадного алгоритма с точками, включенными в маршрут;
· если vi > Сi, то ищем ближайшие к Сi точки в количестве, необходимом для заполнения мусоровоза. Найдя ближайшие точки в достаточном количестве, маршрут между ними строим также на основе жадного алгоритма. Оставшиеся пункты повторно кластеризуются.
Таким образом, создаем маршрут для всех автомобилей.
Ввиду того что в зависимости от исходных данных предложенный алгоритм не всегда может показывать оптимальный результат, рекомендуется сверять полученные результаты с помощью классического жадного алгоритма [5] и алгоритма Джонсона [1].
Для облегчения расчетов перспективным способом решения задачи является использование геоинформационной системы. В России представлены программные комплексы, имеющие хорошую детализацию и актуальность представленных данных:
- Google Maps;
- Яндекс.Карты;
- Дубль Гис;
- Open Street Maps;
- М@il.Карты.
Однако API (Application Programming Interface — набор готовых классов, процедур, функций, структур и констант, предоставляемых приложением, библиотекой или сервисом для использования во внешних программных продуктах) для сторонних разработчиков предоставляют не все перечисленные продукты.
Дубль ГИС может предоставить данные для решения нашей задачи в универсальном векторном формате для хранения объектов shape. Карты компании «Дубль ГИС» имеют несколько слоев (границы населенных пунктов, реки, железнодорожные полотна, улицы, проезжая часть, контуры зданий, мосты и т.д.). Однако стоимость таких данных высока. Лицензионное соглашение [2] сервиса «Яндекс.Карты» не позволяет использовать данные в приложениях для персональных компьютеров. Схожей политики придерживается и картографический сервис от Google.
Open Street Map (OSM) – некоммерческий веб-картографический проект, созданный и поддерживаемый силами сообщества участников - пользователей Интернета. Для создания карт используются данные с персональных GPS-трекеров, аэрофотографии, спутниковые снимки и панорамы улиц, предоставленные некоторыми компаниями. С 12 сентября 2012 г. данные проекта OSM распространяются [4] на условиях свободной лицензии Open Database Licence (ODbL), в рамках которой возможно использование данных сервиса в приложениях для ПК.
Данные, предоставляемые OSM, это сведения о текущем расположении следующих объектов города:
- дороги, улицы, тропы, нумерация;
- жилые зоны и дворовые проезды;
- здания;
- нематериальные характеристики (границы, прилегающие районы, свойства объектов и пр.).
На базе OSM нами разработано приложение, автоматизирующее процесс планирования маршрутов. Для работы приложения необходимо, чтобы пользователь внес сведения о расположении контейнерных площадок, а также об используемой технике. Внесенные сведения сохраняются в базу данных через соответствующие формы в приложения (рисунок 2).
Рисунок 2 – Введенные в приложение данные
После ввода данных в приложение контейнерные площадки отразятся в главном окне приложения (рисунок 3) на карте OSM.
Рисунок 3 – Введённые контейнерные площадки в главном окне приложения
Предусмотрена возможность сравнения алгоритмов, а также выбор алгоритма с минимальной длиной маршрутов (рисунок 4).
Рисунок 4 – Выбор алгоритма для вычисления маршрутов и результат сравнения различных алгоритмов построения маршрутов
На рисунке 4 представлен пример расчета маршрутов. В начальных данных были заданы контейнеры и мусоровозы двух разных объемов – 0,75 м3 и 1,1 м3. Расчет по разным объемам производится раздельно.
Рисунок 5 – Список путевых листов и пример одного из сформированных маршрутных листов
В начальных условиях для сбора и транспортировки были даны 6 мусоровозов. Как мы видим из рисунка 5 (слева), для сбора заданного количества отходов требуются лишь три мусоровоза. Пример одного из сформированных маршрутных листов представлен на рисунке 5 (справа).
На основе разработанного алгоритма создан программный продукт, предназначенный для решения задачи транспортировки ТБО. Данный программный продукт универсален и может быть использован на территории любого населенного пункта благодаря использованию данных, предоставленных OSM.
Рецензенты:
Волынкина Е.П., д.т.н., профессор кафедры теплоэнергетики и экологии СибГТУ, г. Новокузнецк.
Еремина Т.В., д.т.н., профессор кафедры ЭБЖ, ВСГУТУ, г. Улан-Удэ.
Библиографическая ссылка
Егоров В.И., Михайлов А.В., Мельберт А.А. РАЗРАБОТКА ПРОГРАММЫ ДЛЯ ПЛАНИРОВАНИЯ МАРШРУТОВ МУСОРОВОЗА // Современные проблемы науки и образования. – 2014. – № 2. ;URL: https://science-education.ru/ru/article/view?id=12755 (дата обращения: 09.12.2024).