Сетевое издание
Современные проблемы науки и образования
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 1,006

РАЗРАБОТКА ПРОГРАММЫ ДЛЯ ПЛАНИРОВАНИЯ МАРШРУТОВ МУСОРОВОЗА

Егоров В.И. 1 Михайлов А.В. 1 Мельберт А.А. 1
1 ФГБОУ ВПО «Алтайский государственный университет им. И.И. Ползунова»
Транспортировка является одним из ключевых этапов процесса сбора отходов. Разработка маршрутов для вывоза ТБО ввиду большого объема исходных данных не имеет простого и очевидного решения. Суммарная протяженность маршрутов мусоровозов в крупном городе составляет тысячи километров в день, поэтому их эффективное планирование является трудоемкой задачей. Анализ ситуации в сфере обращения с ТБО выявил необходимость в разработке алгоритмов сбора и транспортировки ТБО с территории населенных пунктов, используя технологии ГИС. Нами был разработан программный комплекс для нахождения оптимальных маршрутов при сборе отходов с территории города. Программный комплекс помогает строить корректные маршруты для оптимизации работы транспортных компаний, что позволит увеличить эффективность работы мусоросборочной техники и сократить затраты на транспортировку.
геоинформационная система
транспортировка
отходы
1. Алгоритмы: построение и анализ / Т.Х. Кормен [и др.]. – 2-е изд. – М. : Издательский дом «Вильямс», 2007. – С. 1296.
2. Вопросы и ответы // API Яндекс.Карты [Электронный ресурс] : офиц. сайт. – [2013]. – Режим доступа: http://api.yandex.ru/maps/faq.xml. – Загл. с экрана.
3. McDonough W. The Next Industrial Revolution // Atlantic Monthly [Электронный ресурс]. –Режим доступа: http://www.theatlantic.com/magazine/archive/1998/10/the-next-industrial-revolution /304695/. – Загл. с экрана.
4. RU:Map Features // Open Street Map: Wiki [Электронный ресурс] : сайт. – Режим доступа: http://wiki.openstreetmap.org/wiki/RU. – Загл. с экрана.
5. Sahni S. P-Complete Approximation Problems / S. Sahni, T. Gonzalez // Journal ol the Association for Computing Machinery. – № 3. - Vol. 23. - P. 555 – 565.

Несвоевременность вывоза и высокие затраты на транспортировку – основные проблемы, связанные с вывозом ТБО. В связи с этим необходимо решить оптимизационную задачу транспортировки таким образом, чтобы компании, занимающиеся вывозом отходов, могли самостоятельно получать маршруты для мусоровозов. Уменьшение длины маршрутов поможет уменьшить время, требуемое для сбора отходов, и снизить затраты на транспортировку.

Для формирования алгоритма сбора отходов требуются исходные данные: координаты контейнерных площадок и объем образующихся на них отходов (таблица 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).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1,674