Logistics of the action for separate collection of recyclables

Instead of joining


When the processes of waste collection and processing are fully adjusted in Russia, it is not easy to say, but I want to not participate in the replenishment of landfills now. Therefore, in many large cities, one way or another, there are volunteer movements engaged in particular separate collection.

In Novosibirsk, such an activity is formed around the Green Squirrel campaign, in which once a month environmental townspeople bring accumulated recyclable household waste to predetermined places at a certain time. By the same time, a rented truck arrives there, which takes the collected and sorted recyclable materials to the site, from where it is redistributed between various processing enterprises. The action has existed since 2014, and since then the number of collection points for recyclables, as well as its volumes, has significantly increased. For truck routing, just a gaze was not enough, and we began to develop optimization models to minimize transportation costs. The first of these models is the subject of this article.

In section 1, I will describe in detail and with illustrations the scheme for organizing the action. Further, in Section 2, the task of minimizing transport costs will be formalized as the task of routing heterogeneous vehicles fleet vehicle routing problem with time windows. Section 3 is devoted to solving this problem using a freely distributed package for solving mixed integer linear mathematical programming problems GLPK.

1. The action "Green Squirrel"


Since 2014, the Living Earth initiative group has been conducting a monthly campaign to separate the collection of recycled Green Squirrel in Novosibirsk. At the time of writing, recycling with a number of reservations is accepted plastic waste labeled PET, PE, PP, PS, glass, aluminum, iron, household appliances, waste paper and more. More than 50 volunteers participate in the preparation and conduct of the action. The action is not commercial, participation in it is free and does not imply a monetary reward.

Points

The action is held at 17 points of the city, located from each other at distances covered by the car in a period of 15 to 90 minutes. One of these points in the photo: bags on the left along the wall to collect various fractions of plastic, on the right - a truck, in which everything is loaded in the future, and in the center - a volunteer with ears.

image

All activity at the point is organized by curators who have restrictions on the time at which they are ready to fulfill their duties. When planning an action, curators report the time interval within which the action must pass at their point.

There is also data on the average volumes of recyclables collected at each point.

Routes

Points are organized into routes that are successively driven by a truck. Truck movements are monitored by route supervisors who monitor the operational environment and make decisions on handling special events.

image

Trucks

Are rented on a common basis within the framework of proposals for hourly rental of freight vehicles. It is not possible to compact the plastic in place, therefore the main parameter characterizing the truck is the volume of the body. Carrying capacity in our case is not a limiting factor.

The main expenses of the action are connected with the payment of truck rental, therefore, its reduction is critical for the existence and development of our share, which acquires institutional significance in the sense of forming ideas about responsible consumption. Next, an approach to solving this issue will be described, based on the application of discrete optimization methods, namely, mathematical programming.

2. Formalization


In constructing the mathematical model, we will remain within the framework of linear mixed-integer programs, for which understanding knowledge of class 7 algebra is sufficient.

The only difficulty can be associated with the use of abstract notation and summation signs in formulas. I hope this does not scare away readers who have infrequent encounters with mathematical texts.

In the optimization model, four components can be distinguished:

  • the formation of groups of points that make up a separate route;
  • definition of a detour scheme for each of the groups;
  • meeting the requirements for the time of arrival of the truck at each point;
  • determination of the type of truck needed to service each of the routes.

We consider each of the parts, introducing the necessary notation as necessary.

The formation of groups of points

Let$ V = \ {1, \ dots, n \} $there are many indexes of collection points for recyclable materials, and the site where collected recyclables are then transported - we will call it a depot - has an index of 0. Put$ \ bar {V} = V \ cup \ {0 \} $

Each group of points forms a separate route. Through$ R $denote the set of route numbers.

Let the quantity$ z_ {ir}, i \ in I, r \ in R $ equals one if the point $ i $ included in the route with the number $ r $, and zero otherwise. Then the requirement that the point$ i \ in V $ must enter one of the routes can be written as

$ \ sum_ {r \ in R} z_ {ir} = z_ {i1} + z_ {i2} + \ dots + z_ {in} = 1. $


Depot must enter all routes: $ z_ {0r} = 1, r \ in R $

Subtleties
Unfortunately, such a record creates computational problems associated with the symmetry of the admissible region. It can be eliminated by adding a number of restrictions ensuring the choice of lexicographically minimal decomposition. You can read more about this in Russian, for example, here .

$ 1-z_ {ir} \ leq \ sum_ {j = 1} ^ {i-1} \ left (1- \ sum_ {k = 1} ^ {r-1} z_ {jk} \ right) + \ sum_ { k = 1} ^ {r-1} z_ {ik}, \ quad i \ in I, r \ in R, r \ leq i. $



Definition of a detour scheme

Routes are an alternating sequence of points and crossings between them. Formally, they all begin at one of the points of the set$ V $and end in the depot, however, it will be easier to assume that all routes are cyclic. This assumption does not change the essence, but makes all the vertices the same: in this case there are no end vertices, they are all transit.

For points$ i, j \ in \ bar {V} $ and route $ r \ in R $ set up a variable $ x_ {ijr} $equal to one if in the route with number $ r $ truck moving from point $ i $ exactly $ j $, and zero otherwise.

Then we require, firstly, that the truck moving along the route$ r \ in R $ visited the point $ i \ in V $if she, after dividing into groups, fell into the group with the number $ r $:

$ \ sum_ {j \ in \ bar {V}} x_ {jir} = z_ {ir}, \ quad i \ in \ bar {V}, r \ in R. $


Secondly, the truck after arriving at the point $ i \ in \ bar {V} $ must leave her.

$ \ sum_ {j \ in \ bar {V}} x_ {jir} = \ sum_ {j \ in \ bar {V}} x_ {ijr}, \ quad i \ in \ bar {V}, r \ in R . $



You may notice that these restrictions allow the quantities $ x_ {ijr} $Define routes that are a set of disjoint loops. Routes of this kind, of course, do not make sense, and a number of restrictions are required to avoid this.

About eliminating subcycles
One way could be to introduce auxiliary non-negative quantities $ f_ {ijr}, i, j \ in \ bar {V}, r \ in R $ The set of relations recorded using these quantities eliminates combinations of values $ x_ {ijr} $defining routes that are not a connected loop.

$ \ sum_ {i \ in V} f_ {0jr} = \ sum_ {i \ in V} z_ {ir}, \ quad r \ in R, $


$ f_ {ijr} \ leq nx_ {ijr}, \ quad i \ in \ bar {V}, j \ in \ bar {V}, r \ in R, $


$ \ sum_ {j \ in \ bar {V}} f_ {jir} = \ sum_ {j \ in \ bar {V}} f_ {ijr} + z_ {ir}, \ quad i \ in V, r \ in R. $


These ratios specify the flow from the depot to the rest of the route points. At each intermediate point, a unit of flow is absorbed, so in order for the network to have a power flow equal to the number of points minus one, it is necessary that the route be connected.

Satisfying the requirements for the time of arrival of the truck at each point

In other words, you must visit the points only inside the time windows indicated by the curators. Through$ B_i $ and $ E_i $ denote, respectively, the beginning and end of the time interval in which the curator of the point $ i $may attend it.

To track the implementation of these restrictions, we need information about the time spent by the truck during stops and crossings on the route. Through$ L_i, i \ in V $ denote the duration of loading at the point $ i $, and through $ D_ {ij}, i, j \ in \ bar {V} $ - time of moving from a point $ i $ exactly $ j $ We make a reservation that $ D_ {0i} = 0 $ for all $ i \ in \ bar {V} $, and generally can be performed $ D_ {ij} \ neq D_ {ji} $ for any $ i \ neq j $

We introduce non-negative variables $ a_i, i \ in \ bar {V} $ and $ w_ {ir}, i \ in \ bar {V}, r \ in R $equal to arrival times and waiting times at the point $ i $ when driving along a route $ r $, respectively. For the entered values, the following relations should be satisfied.

The waiting time cannot be less than the time required for loading

$ w_ {ir} \ geq L_iz_ {ir}, \ quad i \ in \ bar {V}, r \ in R, $


and equal to zero if the point does not belong to the route $ r $

$ w_ {ir} \ leq Mz_ {ir}, \ quad i \ in \ bar {V}, r \ in R, $


Arrival time at the point $ j $ calculated at appropriate times for the previous point $ i $ Here is a fairly large constant $ M $ used to eliminate unnecessary dependencies when moving between $ i $ and $ j $ not done.

$ a_i + \ sum_ {r \ in R} w_ {ir} + D_ {ij} \ leq a_j + M (1 - \ sum_ {r \ in R} x_ {ijr}), \ quad i \ in I, j \ in V, $


The arrival and departure of the truck must be within the interval indicated by the curator.

$ a_i \ geq B_i, \ quad i \ in V, $


$ a_i + \ sum_ {r \ in R} w_ {ir} \ leq E_i, \ quad i \ in V. $


Determining the type of truck required to service each of the routes.
We denote the many types of trucks available for rent by$ T $ Truck type $ t \ in T $ characterized by body volume $ C_t $ and the cost of an hour's rent $ P_t $ Minimum truck rental time $ t $ denote by $ U_t ^ 0 $ The amount of recyclables collected at the point $ i \ in V $ denote by $ G_i $

We introduce variables $ y_ {tr}, t \ in T, r \ in R $equal to one if truck type $ t $ assigned to service route with number $ r $, and zero otherwise.

Integer variables$ u_ {tr}, t \ in T, r \ in R $ set the time of renting a truck type $ t $serving the route with number $ r $
For each route, $ r \ in R $, you must assign the type of truck:

$ \ sum_ {t \ in T} y_ {tr} = 1, \ quad r \ in R $


In accordance with the breakdown of points between routes, some routes may turn out to be trivial, that is, contain only depots. If the route$ r $ non-trivial, then the truck assigned to it is rented at least $ U_t ^ 0 $ hours.

$ u_ {tr} \ geq U_t ^ 0 (y_ {tr} - \ sum_ {i \ in V} z_ {ir}), \ quad t \ in T, r \ in R. $


At the same time, the duration of the lease should also exceed the total duration of parking and moving along the route.

$ u_ {tr} \ geq \ sum_ {i \ in V} \ sum_ {j \ in \ bar {V}} D_ {ij} x_ {ijr} + \ sum_ {i \ in \ bar {V}} w_ { ir} -M (1-y_ {tr}), \ quad r \ in R, t \ in T. $


Add restrictions providing the property: if the truck is of type $ t $ not assigned to a route $ r $, its rental time is zero.

$ u_ {tr} \ leq My_ {tr}. $


All recyclables collected at route points should fit in the back of the truck.

$ \ sum_ {i \ in V} G_iz_ {ir} \ leq \ sum_ {t \ in T} C_ty_ {tr}, \ quad r \ in R. $


Finally, our goal is to minimize the cost of renting trucks, which, using the designations introduced, is written as $ \ sum_ {t \ in T} \ sum_ {r \ in R} P_tu_ {tr} $

Search for a solution


It is easy to verify that all the expressions involved in the optimization model are linear functions of variables, therefore, to find the exact and approximate solutions, you can use standard packages for solving mixed-integer programming problems such as Gurobi , CPLEX , Xpress , ORtools , SCIP , BLIS , etc.
We write a model for minimizing transportation costs in the GMPL language. This will allow us to use the free GLPK package for our purposes . To write code and debug the model, it will be convenient to download the GUSEK development environment , which already contains GLPK in its composition.

GUSEK looks as follows:

image

On the left we see a description of the model, and on the right there is a window for displaying information on the calculation progress, which the solver will supply after launch.

Full description of the model
param numOfPoints > 0, integer;	#число точек
param numOfTypes > 0, integer;	#число типов грузовиков
param numOfRoutes = numOfPoints;#максимальное число маршрутов
set V := 1 .. numOfPoints;	#множество точек
set Vbar := V union {0};	#множество точек с пунктом разгрузки (депо)
set T := 1 .. numOfTypes;	#множество типов грузовиков
set R := 1 .. numOfPoints;	#множество маршрутов
#####Точки##########
param WDL >= 0, default 8;	#длительность рабочего дня
param B{i in Vbar} >= 0;	#начало временного окна
param E{i in Vbar} >= 0;	#конец временного окна
param L{i in Vbar} >= 0;	#минимальное время погрузки
param D{i in Vbar, j in Vbar} >= 0, <= WDL;	#время переезда
param G{i in V}, >= 0;	#объем вторсырья, м3
#####Грузовики#####
param C{t in T}, >= 0;	#вместительность кузова
param P{t in T}, >= 0;	#стоимость аренды за час
param U0{t in T}, >= 0;	#минимальное время аренды, часов
/**********************************************
*	Формирование групп точек
**********************************************/
var z{Vbar, R} binary;	#равняется единице, если точка включается в маршрут, и нулю в противном случае
s.t. pointToGroup 'point to group' {i in V}:  sum{r in R} z[i, r] == 1;
s.t. depotToGroup 'depot to group' {r in R}: z[0, r] == 1;
s.t. lexMinGroups 'lexicographycally minimal division' {i in V, r in R: r <= i}: 
	1 - z[i, r] 
	<= 
	sum{j in V: j <= i - 1}(1 - sum{k in R: k <= r - 1} z[j, k]) 
	+ 
	sum{k in R: k <= r - 1}z[i, k] ;
/**********************************************
*	Определение схемы объезда
**********************************************/
var x{Vbar, Vbar, R} binary;	#равна единице, если в маршруте c номером r грузовик совершает переезд из точки i в точку j, и нулю иначе.
s.t. visitPoint 'visit point' {i in Vbar, r in R}: sum{j in Vbar} x[i, j, r] = z[i, r];
s.t. keepMoving 'keep moving' {i in Vbar, r in R}: sum{j in Vbar} x[j, i, r] = sum {j in Vbar} x[i, j, r];
var f{Vbar, Vbar, R} >= 0;		#Потоки, устраняющие подциклы.
s.t. flowFromDepot 'flow from depot' {r in R}: sum{i in V} f[0, i, r] == sum{i in V} z[i, r];
s.t. flowAlongActiveArcs 'flow along active arcs' {i in Vbar, j in Vbar, r in R}: f[i, j, r] <= numOfPoints * x[i, j, r];
s.t. flowConservation 'flow conservation' {i in V, r in R}: sum{j in Vbar} f[j, i, r] == sum{j in Vbar} f[i, j, r] + z[i, r];
var a{i in V} >= 0;	#время прибытия грузовика на точку
var w{i in Vbar, r in R} >= 0;	#время нахождения грузовика на точке
s.t. wait 'wait'{i in Vbar, r in R}: w[i, r] >= L[i] * z[i, r];
s.t. dontWait 'dont wait'{i in Vbar, r in R}: w[i, r] <= (E[i] - B[i]) * z[i, r];
s.t. arrivalTime 'arrival time' {i in V, j in V}: a[i] + sum{r in R}w[i, r] + D[i,j] <= a[j] + 3 * WDL * (1 - sum{r in R} x[i, j, r]);
s.t. arriveAfter 'arrive after' {i in V}: a[i] >= B[i];
s.t. departBefore 'depart before' {i in V}: a[i] + sum{r in R}w[i, r] <= E[i];
/**********************************************
*	Определение типа грузовика, необходимого для обслуживания каждого из маршрутов
**********************************************/
var y{t in T, r in R}, binary;	#равные единице, если грузовик типа t назначается на обслуживание маршрута с номером r, и нулю иначе.
var u{t in T, r in R}, integer, >= 0;	#время аренды грузовика типа t, обслуживающего маршрут с номером r.
s.t. assignVehicle 'assign vehicle' {r in R}: sum{t in T} y[t,r] == 1;
s.t. rentTime 'rent time' {r in R, t in T}: u[t, r] >= sum{i in V, j in Vbar}D[i, j] * x[i, j, r] + sum{i in Vbar}w[i, r] - WDL * (1 - y[t, r]);
s.t. minRentTime 'minimal rent time' {r in R, t in T}: u[t, r] >= U0[t] * (y[t, r] - sum{i in V}z[i, r]);
s.t. noRent 'no rent' {t in T, r in R}: u[t, r] <= WDL * y[t, r];
s.t. fitCapacity 'fit capacity' {r in R}: sum{i in V} G[i] * z[i, r] <= sum{t in T} C[t] * y[t, r];
minimize rentCost: sum{t in T, r in R} P[t] * u[t, r];
solve;
/**********************************************
*	Вывод решения на экран
**********************************************/
printf{i in V, r in R} (if 0.1 < z[i,r] then "point %s to group %s\n" else ""), i, r, z[i,r];
printf{r in R, i in Vbar, j in Vbar} (if 0.1 < x[i, j, r] then "route %s: %s -> %s\n" else ""), r, i, j;
printf{i in V} "point %s arrive between %s and %s (actual = %s)\n", i, B[i], E[i], a[i];
end;


For a quick start, I’ll also add data taken from my head prepared for use in the model:

Input data
data;
param numOfPoints := 9;	#число точек
param numOfTypes := 6;	#число типов грузовиков
#####Точки##########
param 	:	B	E	L :=
		0	0	8	1
		1	0	8	1
		2	0	8	1
		3	0	8	1
		4	0	8	1
		5	0	8	1
		6	0	8	1
		7	0	8	1
		8	0	8	1
		9	0	8	1;
param D default 0
:	0	1	2	3	4	5	6	7	8	9 :=
0	.	.	.	.	.	.	.	.	.	.
1	0.1	0.3	0.2	0.1	0.2	0.1	0.2	0.1	0.2	0.1
2	0.3	0.2	0.2	0.1	0.2	0.1	0.2	0.1	0.2	0.1
3	0.4	0.3	0.2	0.1	0.2	0.1	0.2	0.1	0.2	0.1
4	0.4	0.4	0.2	0.1	0.2	0.1	0.2	0.1	0.2	0.1
5	0.1	0.2	0.2	0.1	0.2	0.1	0.2	0.1	0.2	0.1
6	0.5	0.5	0.2	0.1	0.2	0.1	0.2	0.1	0.2	0.1
7	0.3	0.2	0.2	0.1	0.2	0.1	0.2	0.1	0.2	0.1
8	0.2	0.1	0.2	0.1	0.2	0.1	0.2	0.1	0.2	0.1
9	0.5	0.2	0.2	0.1	0.2	0.1	0.2	0.1	0.2	0.1;
param 	G	:=
	1	1
	2	2
	3	1
	4	2
	5	1
	6	2
	7	1
	8	2
	9	1;
#####Грузовики#####
param 	:	C	P :=
		1	8	500
		2	10	500
		3	14	600
		4	18	650
		5	25	700
		6	35	800;
param U0 default 2;	#минимальное время аренды, часов
end;


After copying the model code to a file with the name, for example, model.mod, and the input data to the data.dat file, everything is ready to run. We set a limit on the calculation time of 100 seconds (this is done using the key --tmlim [time in seconds]), transfer the path to the file with input data (using the key -d [file path]),

image

and press F5. If successful, messages will appear in the window on the right, and after a hundred seconds we will have the best solution that GLPK managed to find in the allotted time.

image

In the blue text, we are interested in the meaning after the inscription "mip =". As you can see, it decreases from time to time. All new solutions are in the process of work, the value of transport costs at the best of which is displayed in this column (there are 14700 so far). The next number is the lower bound for the best existing one, i.e.optimal solution. Initially, the estimate is significantly underestimated, but is refined over time, that is, increases. The values ​​on the left and on the right are converging, and the relative gap between them at the time of the screenshot is 54.1%. As soon as this number becomes zero, the algorithm will prove that the best solution found is the best possible. It is not always justified to wait for this event in practice, and not only because it is a long time, but it is important to make a reservation that, as a rule, a good solution is relatively quick, and the main time costs are associated with the refinement of the estimate required to prove the best possible.

Instead of a conclusion


Routing problems are extremely computationally complex, and with the increase in the number of points that need to be visited, the time required for a solver to find a solution and prove its optimality is growing rapidly. However, for fairly small examples, in a reasonable amount of time, the solver is able to build a successful set of routes and can be used to support decision-making. Analysis of the routing options proposed by the model helped us discover significant opportunities for cost reduction, and this is critical for the existence and development of the stock.

Our further efforts went towards work with uncertainty in the volumes of recyclables collected at the points. We are developing a number of stochastic programming models for making strategic and operational decisions in truck routing. If the topic turns out to be relevant and arouses interest, I will write about this too, because soon we all will have to significantly more thoroughly dive into environmental issues, which is what I wish us success in.

Also popular now: