Вместо вступления
Когда в России полноценно наладятся процессы сбора и переработки отходов, сказать непросто, а хочется уже сейчас не участвовать в пополнении свалок. Поэтому во многих крупных городах так или иначе существуют волонтерские движения, занимающиеся в частности раздельным сбором.
В Новосибирске такая деятельность формируется вокруг акции «Зеленая белка», в рамках которой раз в месяц обеспокоенные экологией горожане приносят накопленные перерабатываемые бытовые отходы в заранее определенные места в известное время. К этому же времени туда подъезжает арендованный грузовик, который отвозит собранное и рассортированное вторсырье на площадку, откуда оно перераспределяется между различными перерабатывающими предприятиями. Акция существует с 2014 года, и с того времени значительно увеличилось число точек сбора вторсырья, а также его объемы. Для маршрутизации грузовиков одного лишь пристального взгляда стало не хватать, и мы начали разрабатывать оптимизационные модели для минимизации транспортных затрат. Первой из таких моделей и посвящена данная статья.
В разделе 1 я подробно и с иллюстрациями опишу схему организации акции. Далее, в разделе 2, задача минимизации транспортных затрат будет формализована в виде задачи маршрутизации разнородных транспортных средств с временными окнами (heterogenious fleet vehicle routing problem with time windows). Раздел 3 посвящен решению данной задачи с использованием свободно распространяемого пакета для решения смешанно-целочисленных линейных задач математического программирования GLPK.
Читать полностью »