# Smart Waste Collection System with Low Consumption LoRaWAN Nodes and Route Optimization
## 2 State of the Art
### Cvrp  
Regarding the selection of the waste collection route in a smart waste system, the search for an ideal waste collection route(s) is considered an optimization problem which requires the reduction of collection costs. These costs are related to the covered distance of each truck and the required number of trucks. This kind of problem is known in the literature as a Vehicle Routing Problem (VRP) [56; 57]. This name is used for a whole type of problems aimed at finding a number of routes for a group of vehicles placed in a depot. They must meet the demands of a specific number of customers who are geographically spread. The purpose of a VRP is to specify the distribution/collection routes for these customers (each one has a specific demand) while reducing the cost of the vehicles' routes, which start and end at the same depot. The original VRP is also known as the Capacited Vehicle Routing Problem and includes constraints, for example, every vehicle in one fleet has a permanent and uniform load and there is one depot. The original problem has several variants [57; 58] which add constraints regarding real life problems, such as collections and deliveries (VRP with Pickups and Delivery [59]), time windows (VRP with Time Windows [60]), heterogeneous fleets (Heterogeneous Fleet VRP or Mixed Fleet VRP [61]) and more. Figure 1 shows the approach of a classic CVRP with a homogeneous fleet. This is formally defined with the following description: given \(G(V,A)\), an undirected graph where \(V\) indicates a set of \(n+1\) vertices. \(A\) is a set of arcs, defined as \(A=\left\{\left(p_{i},v_{j}\right):\,v_{i},v_{j}\in V,\,i\
eq j\,\right\}\). \(V\) is a set (\(V=\{0,1,2,\ldots,n\}\)) that defines the number of customers (in this case, containers). Each \(\left(v_{i},v_{j}\right)\) of set \(A\) has an associated cost (not negative) (\(C_{ij}\)). Each customer of the set \(\{1,\ldots,n\}\) has a demand (in this case, the quantity of waste) (\(q_{i}\)) that must be collected and transported to the depot (\(q_{0}\)). The demand of the depot is always 0, so \(q_{0}=0\). A set (\(m\)) of vehicles with the same capacity (\(Q\)) (if the fleet has different capacities, the problem would be another kind of VRP problem) must be employed to collect waste of \(n\) customers (containers). The \(m\) vehicles must start and end their routes in the depot. A route is defined as a lower cost cycle of the graph (\(G\)) that passes through the depot and the total demand of the set of vertices must not exceed the total capacity of the vehicle. The purpose of the problem is to reduce the distance, time or cost of the \(m\) vehicles while meeting the following requirements: (1) the depot is the start and end point of every route; (2) every customer is visited only once by just one vehicle; and (3) the total demand of each route does not exceed the capacity (\(Q\)). The classic CVRP is stated as follows:  
\[\min\sum c_{ij}x_{ij}, \tag{1}\]  
with \((i,j)\in V\), \(V=\{0,1,2,3\ldots,n\}\), \(x_{ij}\in\{0,1\}\), subject to  
\[\sum x_{0j}=m, \tag{2}\]  
\[\sum x_{i0}=m, \tag{3}\]  
\[\sum_{j=1}x_{ij}=1\ (i=1,\ldots,n), \tag{4}\]  
\[\sum_{j=1}x_{ij}=1\ (j=1,\ldots,n), \tag{5}\]  
\[m\geq 1. \tag{6}\]The target function, Equation (1), is the total cost of the solution. The constraints of Equations (2) and (3) indicate that \(m\) is the number of vehicles employed for the solutions and state that all those vehicles must return to the depot. The constraints of Equations (4) and (5) turn each client into intermediate nodes of a route, and the constraint of Equation (6) states that the vehicle fleet employed must be greater than 1. Regarding the solution, VRP and its derivatives are NP-hard problems, which means that the bigger the problem is, the greater the computational complexity to resolve it becomes. There are several solution-searching methods for these problems in the literature [62], such as (1) exact approaches which explore exhaustively explore the search space until the best solution is found.