Вместо вступления Когда в России будут полностью налажены процессы сбора и переработки отходов, сказать сложно, но мне хотелось бы уже сейчас прекратить участие в пополнении свалок.
Поэтому во многих крупных городах так или иначе существуют волонтерские движения, занимающиеся, в частности, раздельным сбором.
В Новосибирске такая деятельность формируется вокруг акции «Зеленая белка», в рамках которой раз в месяц заботящиеся об окружающей среде граждане сносят накопившиеся вторсырьевые бытовые отходы в заранее определенные места в определенное время.
В это же время туда приезжает арендованный грузовик и вывозит собранное и отсортированное вторсырье на площадку, откуда оно перераспределяется между различными перерабатывающими предприятиями.
Акция существует с 2014 года, и с тех пор количество пунктов приема вторсырья, а также его объемы значительно увеличились.
Для маршрутизации грузовиков простого взгляда уже было недостаточно, и мы начали разрабатывать модели оптимизации, чтобы минимизировать транспортные расходы.
Данная статья посвящена первой из таких моделей.
В разделе 1 я подробно и с иллюстрациями опишу схему организации акции.
Далее в разделе 2 задача минимизации транспортных затрат будет формализована как задача маршрутизации гетерогенного парка транспортных средств с временными окнами.
Раздел 3 посвящен решению этой задачи с использованием свободно распространяемого пакета для решения смешанно-целочисленных задач линейного математического программирования GLPK.
1. Акция «Зеленая белка»
С 2014 года инициативная группа «Живая Земля» проводит ежемесячную акцию по раздельному сбору вторсырья «Зеленая белка» в Новосибирске.На момент написания статьи пластиковые отходы с маркировкой ПЭТ, П?, ПП, ПС, стекло, алюминий, железо, бытовая техника, макулатура и другое принимаются на переработку с рядом оговорок.
В подготовке и проведении мероприятия задействовано более 50 волонтеров.
Акция не является коммерческой, участие в ней бесплатное и не предполагает никакого денежного вознаграждения.
Точки Акция проводится в 17 точках города, расположенных друг от друга на расстояниях, преодолеваемых автомобилем за время от 15 до 90 минут. На фото одна из таких точек: слева вдоль стены стоят мешки для сбора различных фракций пластика, справа грузовик, в который все впоследствии загружается, а в центре волонтер с ушами.
Все мероприятия на точке организуются кураторами, имеющими временные рамки, в которые они готовы выполнять свои обязанности.
При планировании акции кураторы сообщают временной интервал, в течение которого акция должна произойти в их точке.
Также доступны данные о средних объемах вторсырья, собранного в каждом месте.
Маршруты Точки организованы в маршруты, последовательно проходимые грузовиком.
Передвижение грузовых автомобилей контролируется кураторами маршрутов, которые следят за оперативной обстановкой и принимают решения по проведению специальных мероприятий.
Грузовики
Сдаются на общих основаниях в рамках предложений по почасовой аренде грузового транспорта.
Уплотнить пластик на месте невозможно, поэтому основным параметром, характеризующим грузовик, является объем кузова.
Грузоподъемность в нашем случае не является ограничивающим фактором.
Основные затраты акции связаны с оплатой аренды грузовых автомобилей, поэтому ее снижение имеет решающее значение для существования и развития нашей акции, приобретающей институциональное значение в плане формирования идей об ответственном потреблении.
Далее будет описан подход к решению данного вопроса, основанный на использовании методов дискретной оптимизации, а именно математического программирования.
2. Формализация
При построении математической модели мы останемся в рамках линейных смешанно-целочисленных программ, для понимания которых достаточно знаний алгебры 7 класса.Единственная трудность может быть связана с использованием в формулах абстрактных обозначений и знаков суммирования.
Надеюсь, это не отпугнет читателей, нечасто встречающихся с математическими текстами.
Модель оптимизации можно разделить на четыре компонента:
- формирование групп точек, составляющих отдельный маршрут;
- определение схемы обхода для каждой из групп;
- соблюдение требований ко времени прибытия грузового автомобиля в каждую точку;
- определение типа грузовика, необходимого для обслуживания каждого маршрута.
Формирование групп точек
Позволять 
есть много указателей пунктов приема вторсырья, и площадки, куда потом вывозят собранное вторсырье - назовем ее депо — имеет индекс 0. Положим 
Каждая группа точек образует отдельный маршрут. Через 
обозначим множество номеров маршрутов.
Пусть значение 
равно единице, если точка 
включен в маршрут с номером 
, и ноль в противном случае.
Тогда требование, чтобы точка 
должен войти в один из маршрутов, можно записать как 
Депо должно быть включено во все маршруты: 
Тонкости К сожалению, такое обозначение создает вычислительные проблемы, связанные с симметрией допустимой области.
Его можно устранить, добавив ряд ограничений, обеспечивающих выбор лексикографически минимального разбиения.
Подробнее об этом можно прочитать на русском языке, например, здесь .
Определение схемы объезда
Маршруты представляют собой чередующуюся последовательность точек и переходов между ними.
Формально все они начинаются в одной из точек множества 
и заканчиваются в депо, но проще было бы предположить, что все маршруты циклические.
Это предположение не меняет сути, но делает все вершины одинаковыми: в этом случае конечных вершин нет, все они транзитные.
За баллы 
и маршрут 
давайте создадим переменную 
, равный единице, если маршрут с номером
грузовик движется с точки
точно 
, и ноль в противном случае.
Тогда потребуем, во-первых, чтобы грузовик, движущийся по маршруту,
посетил точку
, если после разделения на группы она оказалась в номере группы
: 
Во-вторых, грузовик после прибытия на точку 
Я должен оставить ее.
Можно отметить, что эти ограничения допускают значения
установить маршруты, которые представляют собой набор непересекающихся циклов.
Маршруты такого рода, конечно, не имеют смысла, и чтобы этого избежать, необходимо ввести ряд ограничений.
Об исключении подциклов Одним из способов могло бы быть введение вспомогательных неотрицательных величин.
Набор отношений, записанный с использованием этих значений, исключает комбинации значений.
, определяя маршруты, которые не являются связным циклом.
Эти отношения определяют поток из депо в другие точки маршрута.
В каждой промежуточной точке поглощается единица потока, поэтому для того, чтобы в сети был поток мощности, равный числу точек минус один, маршрут должен быть связным.
Удовлетворение требований ко времени прибытия фуры в каждую точку Другими словами, посещать точки необходимо только в указанные кураторами временные окна.
Через 
И 
обозначим соответственно начало и конец временного интервала, в котором куратор точки
может присутствовать на нем.
Для отслеживания соблюдения этих ограничений нам понадобится информация о времени, проведенном грузовиком при остановке и движении по маршруту.
Через 
обозначаем продолжительность погрузки в точке
и через 
- время в пути от пункта
точно
Оговоримся, что 
для всех
и вообще может быть выполнено 
для любого 
Введем неотрицательные переменные 
И 
, равный временам прибытия и ожидания в точке
при движении по маршруту
, соответственно.
Для введенных значений должны соблюдаться следующие отношения.
Время ожидания не может быть меньше времени, необходимого для загрузки.
и равен нулю, если точка не принадлежит маршруту
Время прибытия в точку
рассчитывается через соответствующие времена для предыдущей точки
Здесь имеется довольно большая константа 
используется для устранения ненужных зависимостей при перемещении между
И
не выполнено.
Прибытие и выезд фуры должны быть в пределах интервала, указанного куратором.
Определение типа грузовика, необходимого для обслуживания каждого маршрута.
Обозначим множество типов грузовых автомобилей, доступных в аренду, через 
Тип грузовика 
характеризуется объемом тела 
и стоимость почасовой аренды 
Минимальное время аренды для типа грузовика 
обозначить через 
Объем вторсырья, собранного на пункте
обозначить через 
Давайте введем переменные 
, равный единице, если грузовик относится к типу
присвоен номер маршрута обслуживания
, и ноль в противном случае.
Целочисленные переменные 
установить время аренды для типа грузовика
номер маршрута обслуживания
Для каждого маршрута
, вам необходимо назначить тип грузовика: 
В соответствии с разделением точек между маршрутами некоторые маршруты могут оказаться тривиальными, то есть содержащими только депо.
Если маршрут
нетривиально, то закрепленный за ним грузовик арендуется минимум за
часы.
При этом продолжительность аренды также должна превышать общую продолжительность остановок и пересадок по маршруту следования.
Добавим ограничения, обеспечивающие свойство: если грузовик типа
не назначен маршруту
, время его аренды равно нулю.
Все вторсырье, собранное в точках маршрута, должно помещаться в кузов грузовика.
Наконец, наша цель – минимизировать стоимость аренды грузового автомобиля, которая в введенных обозначениях записывается как 
Поиск решения
Легко проверить, что все выражения, участвующие в модели оптимизации, являются линейными функциями переменных, поэтому для поиска точных и приближенных решений можно использовать стандартные пакеты для решения задач смешанно-целочисленного программирования, такие как Гуроби , Комплексный комплекс , Экспресс , ORtools , SCIP , БЛИС и т. д. Напишем модель минимизации транспортных расходов на GMPL. Это позволит нам использовать свободно распространяемый пакет для наших целей.ГЛПК .
Для написания кода и отладки модели будет удобно скачать среду разработки.
ГУСЕК , который уже содержит в своем составе ГЛПК.
ГУСЕК выглядит так: 
Слева мы видим описание модели, а справа окно с информацией о ходе вычислений, которую решатель предоставит после запуска.
Полное описание модели
Теги: #математика #Экология #транспорт #математическое программирование #математическое программирование #раздельный сбор мусора #оптимизация затратparam numOfPoints > 0, integer;
-
«Белтелеком» Переходит На Хостинг
19 Oct, 24 -
Комментарий – Это Единица Смысла
19 Oct, 24 -
Мобитехфест
19 Oct, 24
