EP2666737B1 - Method for the removal of waste from a network of waste inlets - Google Patents

Description

• The present invention relates to a method for the removal of waste from a network of waste inlets in an automated waste collection system, said inlets being adapted to be loaded with at least one type of waste fraction, said network having a root node where the collection facility is. A network of pipes connect the waste inlets to the root node.
• The invention also relates to a system and a computer program for the removal of waste from a network of waste inlets in an automated waste collection system, suitable for carrying out such a method.
BACKGROUND ART
• Disposal of waste products, such as inorganic and organic refuse and the like, by means of air waste disposal systems is a known technology in which waste is conveniently driven through a pipe system into a collection facility. Air waste disposal systems are usually used in inner city, private communities, building areas, hospitals, hotels, industrial facilities, airports, etc. and places in general where waste is produced in large amounts, this being a rapid, clean and efficient technique for centrally disposing of waste products.
• In such a disposal system, a network of fixed waste inlets where refuse is to be selectively placed is distributed on a determined area. Each of the inlets is connected to waste pipes leading to a common air transport pipe system through corresponding discharge valves. Waste products are driven through the air transport pipe system by an air stream (typically at vacuum conditions) drawing them to at least one collection facility for treating, recycling or disposal.
• The inlets are emptied when a volume of waste considered to be sufficient to be discharged into the collection station is detected. This may be carried out by level sensors associated to the inlets which output a level-indication signal to control means for opening the corresponding discharge valve.
• Since a plurality of inlets exists in the network of inlets, a control system has to be provided in order to improve performance, especially in large networks. For example, emptying can be performed on a first to come first to serve basis or by forming groups of inlets according to a priority value that represents the relative importance of collecting waste from the group.
• In the European patent EP2022731 , waste is collected from a plurality of waste inlets through waste pipes leading to transport pipes. The transport pipes comprise several branches and at least one inlet is connected to each branch through a corresponding waste pipe for driving refuse to at least one collection facility. The waste is collected by emptying a first inlet; establishing the inlet being emptied as a reference inlet; selecting a new inlet to be analyzed; determining whether at least one emptying condition is met, said condition depending on said reference inlet and said new inlet; if said condition is met, emptying the selected inlet, establishing said inlet as a new reference inlet, and selecting again a new inlet to be analyzed; and if said condition is not met, selecting another new inlet to be analyzed and then determining again whether said condition is met.
• This method has been proved to be efficient, but there is still scope to reduce the energy consumption involved in the pneumatic transportation of waste.
SUMMARY OF THE INVENTION
• It is an object of the present invention to provide a method that reduces the energy consumption of automated waste collection systems.
• The invention proposes the use of machine learning techniques and linear programming algorithms for the planning operations of automatic waste collection plants. The objective is to achieve optimal operation plans, at any time, based on the current state of the system and on previous experiences, that minimizes energy consumption subject to pre-established service quality standards. An optimal operation plan includes selecting a sequence of inlets to be emptied after the last selected sequence has been emptied.
• The method has at least two levels. First, to determine an optimal emptying decision at a given instant of time (i.e., the next ordered sequence of inlets to be emptied) by applying mixed integer linear programming techniques to a parametric model of the system. Second, to learn from experience by recording historical data and current decisions and by applying machine learning techniques to compute, within a time horizon, an optimal operation plan that includes, at each interval of time, the determination of the optimal emptying decision according to the first level.
• Optimal planning decisions will depend on the system status as well as on the future behaviour of the users. This stochastic component can be captured employing dynamic programming and machine learning techniques. The system dimensionality (number of states, time granularity and decisions) can be defined so as to allow an offset training based on a corpus data (i.e. historical data from existing plants). Once the dynamic programming algorithms have been properly trained, optimal decisions can be achieved at each time slot, on real time, according to the current status of the system, and new feedback can be added to the trained values.
• According to an aspect of the invention, the system comprises at least one valve that defines at least two sectors, any sector comprising the root node and the inlets connected thereto under one condition of the valve, either open or closed, and the method comprises the steps of:
• ordering all the inlets of the waste collection system;
• selecting the next sequence of inlets from which waste is to be unloaded and transported to the root node, said selection being the result of an optimization problem that comprises the minimization of a cost function under at least one operational constraint, the cost function being a function of at least two variables, one variable being an estimation of the cost of the energy consumed in the transport of waste from the inlets to the root node, and another variable being a penalty related to not unload inlets that are loaded with waste at a level above their assigned capacity, and one operational constraint being that only inlets from at most one sector can be unloaded in any distinct unloading sequence;
• transporting the unloaded waste from the inlets of the selected sequence to the root node.
• Optimization algorithms are applied to a model of the parameters of the system. Said model is encoded and solved as a linear program. The resulting decisions (sequences of inlets to be unloaded) manage to reduce the time the absorption or aspiration engine (provided at the collection facility -i.e. root node) is working, thus increasing the treatment capacity of the plant, and of course reducing the energy consumption thereof.
• The step of selecting the next sequence of inlets to be unloaded may be performed in parallel with the step of transporting the waste from the inlets of the last selected sequence.
• In some embodiments, the estimation of the cost of the consumed energy may be made separately for the transitory energy consumed when changing, from one sequence to the next, the sector where the unloading is to take place or the air speed to be applied to the unloaded waste, and for the stationary energy consumed during the actual waste transportation. The air speed may be different for different types of waste fraction.
• The transitory energy can be of around 10% of the stationary energy, and the latter can be of the order or 20 megajoule.
• In some embodiments, the cost function comprises the sum of said at least two variables, and it may comprise the sum of the estimation of the cost of said transitory energy and the estimation of the cost of said stationary energy. For example, the cost function may be the sum of an estimation of the cost of energy and a penalty, or it may be the sum of an estimation of the cost of transitory and stationary energy and a penalty.
• The estimation of the cost of the transitory energy may be a function of at least the respective types of waste fraction transported in two consecutive unloading sequences, the respective air speeds for the waste transportation in two consecutive unloading sequences, and the amount of air to be removed in one unloading sequence before the actual waste transportation is started.
• The estimation of the cost of the stationary energy may be a function of at least the air speed for the waste transportation in an unloading sequence, the amount of waste to be transported in an unloading sequence, and the inlets included in an unloading sequence and the order in which said inlets are to be unloaded.
• The network of waste inlets can be represented by a graph, and said graph may be a tree, that is, a rooted graph without loops.
• In some embodiments, the step of ordering the inlets may comprise the substeps of:
• ordering the inlets on each branch starting from the farthest from the root node and ending in the nearest to the root node;
• ordering the branches that joins a junction node in the descending order of the distance from the last inlet of each branch to the root node;
• iterating over all the junction nodes of the tree until all the inlets are ordered.
• So, inlets of a single branch may be ordered starting from the most upstream (the farthest from the root node) and ending in the most downstream. Then branches joining a junction node may be ordered by combining the inlet sequences of all these branches. For each branch, the distance from the last inlet of its sequence to the root node is considered, ordering the sequences by descending order of such distances. These steps are iterated until the complete ordering for the whole tree is obtained. This ordering gives preference to starting always at the farthest inlet, because the energy needed for transporting the waste of a sequence of inlets down to the root node is more sensitive to the distance from the last inlet to the root node.
• In some embodiments, at least one of the following is another operational constraint in the minimization of the cost function:
• only one type of waste fraction can be unloaded in the next unloading sequence;
• at most one sector is active in the next unloading sequence;
• inlets belong to at least one sector;
• a least one inlet is active if a sector is active;
• not more than a maximum quantity can be transported for each type of waste fraction;
• the air speed is upper and lower bounded for each type of waste fraction;
• only inlets loaded at a level above a threshold can be unloaded.
• The method may comprise modelling the waste collection system and encoding the resulting model as a constraint integer program. The minimization of the cost function may comprise using an algorithm to solve said constraint integer program.
• The method may also comprise the step of planning the future unloading sequences with a time horizon of at least one hundred such sequences. Each sequence typically lasts a few minutes, so a convenient time horizon may be of half a day or, preferably, of a day.
• In some embodiments, said planning may comprise assigning a value to each state of the waste collection system, any such state being a selectable distinct unloading sequence. Said assignation may be based on historical data compiled from the past operation of the waste collection system. Said values are of a stochastic nature.
• In some embodiments, said planning may comprise defining and solving a problem of dynamic programming, in which the solving step might include said minimization of the cost function given the current state of the waste collection system and the value assigned to each state thereof.
BRIEF DESCRIPTION OF THE DRAWINGS
• Some particular embodiments of the present invention will be described in the following, only by way of non-limiting example, with reference to the appended drawings, in which:
  the sole figure is a schematic diagram of a simplified automatic vacuum waste collection plant.
DESCRIPTION OF PARTICULAR EMBODIMENTS
• An automated waste collection system (AWCS) typically uses air suction on a closed network of underground pipes, covering an area of a few square kilometres, to transport waste from the drop off points scattered throughout the city to a central collection point, reducing greenhouse gas emissions and the inconveniences of conventional methods (odours, noise, . . . ), as well as allowing better waste reuse and recycling.
• The pipe network may always be represented as a graph, frequently rooted and tree shaped, that is, a graph with at least one root node and no loops; the central collection point is located at the root node.
• This central collection point has the means to split the collected waste by fraction (organic fraction, paper, etc.), and is where waste is packed for disposal in containers that are then transported with trucks to a landfill area for recycling or mechanical/biological treatment. The network usually has sector valves located on some of the branch junctions that can isolate one of the branches (to reduce the volume of air that will be suctioned). The drop-off points are located along the branches, and contain inlets for the different waste fractions. There are also air valves that act as air entry points that help produce the air flow when the suction starts. Air valves can be located next to inlets, although it is not mandatory to have an air valve in each drop off point.
• An AWCS system has a control software that includes the implementation of a method for deciding when and what inlets, corresponding to a same fraction, should be emptied during a time interval (time slot) taking into account a number of constraints (e.g., full inlets should be emptied, inlets should be emptied at least once a day, air speed, . . . ). Since a significant part of the cost of operating AWCS systems is energy consumption, it is important to devise ways to minimize it.
• An underground automated waste collection system is modelled as a set {

  

  ,

  

  ,

  

  , $V^{\mathrm{a}}$

  

  , $V^{\mathrm{s}}$

  

  }. In some embodiments,

  

  (

  

  ,

  

  ) is a rooted tree with nodes (

  

  ) representing either waste inlets (I) or pipe junctions, and edges (

  

  ) corresponding to union pipes between nodes.

  

  represents the set of fractions waste is divided into. Air valves $\left(V^{\mathrm{a}}\right)$

  

  , located at some inlets, create air streams able to empty downstream inlets. Sector valves $\left(V^{\mathrm{s}}\right)$

  

  are disposed along the tree in order to segment the whole tree structure, defining isolated sectors (s), making a more efficient transport for the inlets comprised in the corresponding sector. Sectors are subtrees of

  

  , always containing the root node and a subset of

  

  $\left(I^{\mathrm{s}}\right)$

  

  .
• Each inlet in

  

  is denoted by I[f,i], f∈

  

  and i∈

  

  , while $\mathrm{v}\left[\mathrm{a}\mathrm{,j}\right]\in V^{\mathrm{a}}$

  

  and $\mathrm{v}\left[\mathrm{s}\mathrm{,j}\right]\in V^{\mathrm{s}}$

  

  denote the j^th air and sector valves, respectively. The status of any valve is open (o) or closed (c). The sole figure is a small example of such a system, with 3 types of fraction (f₁, f₂, f₃), 5 inlets (two of them handling 2 types of fraction, so one can consider having 7 inlets), 4 air valves and 3 sector valves; the root node is denoted by RN. Note that in this case, only 5 combinations of $V^{\mathrm{s}}$

  

  out of the 8 possible are valid, giving 5 different sectors (following the notation (v[s,1], v[s,2], v[s,3]), {(c; c; c), (c; o; c)} are not valid assignments and {(c; c; o), (c; o; o)} give the same sector configuration).
• Three important subtrees that will deeply impact the system dynamics arise from the system topology: emptying, air and vacuum subtrees. The emptying subtree (

  

  [E,i]) is unique for each inlet, and is defined as the path that waste must follow from inlet i to the root node. Of course,

  

  [E,i] must not contain closed sector valves on it. The air subtree (

  

  [A,i]) is the path followed by the air stream in charge of waste transport along

  

  [E,i]. Note that

  

  [E,i] is a subset of

  

  [A,i], being equal if inlet i has an air valve, otherwise, the airflow must come from an upstream inlet. The vacuum subtree (

  

  [V,s]) is unique for each sector and represents the total amount of air to be moved before proceeding to waste transport. Let's denote by d(

  

  ) the total length of a tree.
• As an example, let's consider inlet number 2 (I[f₃,2]) of the sole figure. In this case, d(

  

  [E,2]) = d(e₁)+d(e₂)+ d(e₃) and d(

  

  [A,2]) = d(

  

  [E,2]) + d(e₄), where e_k denote the k^th edge. Inlet 2 can be emptied by 2 sectors: s[2,3] and s[2,3] (v[s,2] = o, v[s,3] = c and v[s,2] = o, v[s,3] = o, respectively). For the first case, d(

  

  [V,s[2,3]]) = d(e₁) + d(e₂) + d(e₃) + d(e₄) + d(e₅).
• When inlets are additionally indexed by time, I[f,i,t] indicates their waste occupancy at a given time, capturing this way the stochastic behaviour of users. At any time, one can define an emptying sequence (

  

  [f,s,t]) as an ordered sequence of loads to be transferred from inlets corresponding to sector s and type of fraction f, subject to a maximum transfer capacity (L[f,max]) per sequence depending on type of fraction. That is,

  

  [f,s,t] = {L[f,i,t] | L[f,i,t] ≤ I[f,i,t], $\mathrm{I}\left[\mathrm{f}\mathrm{,i}\right]\in I^{\mathrm{s}}$

  

  , ${\displaystyle {\sum }_{\mathrm{I}\left[\mathrm{f}\mathrm{,i}\right]\in I^{\mathrm{s}}}\mathrm{L}\left[\mathrm{f}\mathrm{,i}\mathrm{,t}\right]\le \mathrm{L}\left[\mathrm{f}\mathrm{,max}\right]}$

  

  }. Emptying sequences can not overlap in time and can be null (nothing to do).
• As the objective will be to define optimal emptying sequences for a time interval (i.e. a day), some dynamic elements of the model must be defined. Air speed operation is an important one, being crucial to determine sequences duration and, consequently, energy consumptions. It is assumed that the air speed (v_t) is constant during an emptying sequence. Due to structural reasons, v_t has a maximum (V_M). Furthermore, each inlet is characterized by a minimum air speed operation (V[f,i]) to avoid pipe obstructs.
• The second element is the operation time (T[t]), which is defined as the required time to operate an emptying sequence, depending on the sequence itself, the air speed of operation v_t, and the previous operation state of the system. Such a previous operation state can be: operating an emptying sequence for type of fraction f' and sector s' at speed v_t-1 or idle (v_t-1 = 0). The operation time is divided into two phases: a transitory phase (T^tr[t]) in which the previous speed (v_t-1) changes progressively to the current speed (v_t), and a stationary phase (T^st[t]) devoted to emptying the chosen sequence. T^tr[t] is a function of three types of parameters. First, the previous and the current operational air speed. Second, the type of fraction, because if there is a change of type of fraction among the previous and actual emptying sequences, the air speed must be dropped to a low value due to operational requirements; otherwise, it is enough to increase or decrease the air speed from the previous value (v_t-1) to the current one (v_t). Third, the total amount of air to be adapted, which depends on the vacuum paths of the previous sector (s') and the current sector (s), and can be obtained as

  

  [V,s] -

  

  [V,s]∩

  

  [V,s']. It can expressed: $$\mathrm{f}=\mathrm{f}\prime :{\mathrm{T}}^{\mathrm{tr}}\left[\mathrm{t}\right]={\mathrm{c}}^{\mathrm{tr}}\left[1,\mathrm{t}\right]\cdot \left|{\mathrm{v}}_{\mathrm{t}}-{\mathrm{v}}_{\mathrm{t}-1}\right|+{\mathrm{c}}^{\mathrm{tr}}\left[2,\mathrm{t}\right]\cdot \left(\mathrm{d}\left(T\left[\mathrm{V},\mathrm{s}\right]\right)-\mathrm{d}\left(T\left[\mathrm{V},\mathrm{s}\right]\cap T\left[\mathrm{V},\mathrm{s}\prime \right]\right)\right)$$

  

  $$\mathrm{f}\ne \mathrm{f}\prime :{\mathrm{T}}^{\mathrm{tr}}\left[\mathrm{t}\right]={\mathrm{c}}^{\mathrm{tr}}\left[1,\mathrm{t}\right]\cdot \left|{\mathrm{v}}_{\mathrm{t}}+{\mathrm{v}}_{\mathrm{t}-1}\right|+{\mathrm{c}}^{\mathrm{tr}}\left[2,\mathrm{t}\right]\cdot \left(\mathrm{d}\left(T\left[\mathrm{V},\mathrm{s}\right]\right)-\mathrm{d}\left(T\left[\mathrm{V},\mathrm{s}\right]\cap T\left[\mathrm{V},\mathrm{s}\prime \right]\right)\right)$$

  

  where c^tr[1,t] and c^tr[2,t] are constants for a given system, as detailed below.
• Once the transitory phase ends and the new air speed is reached, the stationary operation can be started in order to proceed with the emptying sequence. An emptying sequence consists of two operations that iterate over the ordered sequence of inlets; first, to empty an inlet over the transport pipes, and second, to proceed to waste transport. The transport of waste and the empty phase of the next inlet can overlap in time if and only if the inlet to be emptied is upstream the estimated position of the waste being transported. Under these assumptions:

  

  $${\mathrm{T}}^{\mathrm{st}}\left[\mathrm{t}\right]\left(\mathrm{i},\mathrm{j}\right)={\mathrm{c}}^{\mathrm{st}}\left[1,\mathrm{t}\right]\cdot \mathrm{L}\left[\mathrm{f},\mathrm{i},\mathrm{t}\right]+\left(\mathrm{d}\left(T\left[\mathrm{E},\mathrm{i}\right]\right)-\mathrm{d}\left(T\left[\mathrm{E},\mathrm{i}\right]\cap T\left[\mathrm{E},\mathrm{j}\right]\right)\right)/{\mathrm{v}}_{\mathrm{t}}$$

  

  where next() is the following element in the ordered sequence

  

  [f,s,t]. And next() of the last element in the sequence is the root node. Note that if I[f,j] is upstream I[f,i], then $$\mathrm{d}\left(T\left[\mathrm{E},\mathrm{i}\right]\right)-\mathrm{d}\left(T\left[\mathrm{E},\mathrm{i}\right]\cap T\left[\mathrm{E},\mathrm{j}\right]\right)=0,$$

  

  meaning that once I[f,i] has been emptied, we can proceed to empty I[f,j].
• Energy is closely related to the operation time, and can also be splitted into two parts: transitory and stationary. It is easy to understand that, for the transitory case, there is only energy consumption for the process of increasing air speed but not for decreasing it. The transitory energy can then be expressed as follows: $$\mathrm{f}=\mathrm{f}\prime :{\mathrm{E}}^{\mathrm{tr}}\left[\mathrm{t}\right]={\mathrm{c}}^{\mathrm{tr}}\left[1,\mathrm{e}\right]\cdot {\left|{\mathrm{v}}_{\mathrm{t}}-{\mathrm{v}}_{\mathrm{t}-1}\right|}^{+}+{\mathrm{c}}^{\mathrm{tr}}\left[2,\mathrm{e}\right]\cdot \left(\mathrm{d}\left(T\left[\mathrm{V},\mathrm{s}\right]\right)-\mathrm{d}\left(T\left[\mathrm{V},\mathrm{s}\right]\cap T\left[\mathrm{V},\mathrm{s}\prime \right]\right)\right)$$

  

  $$\mathrm{f}\ne \mathrm{f}\prime :{\mathrm{E}}^{\mathrm{tr}}\left[\mathrm{t}\right]={\mathrm{c}}^{\mathrm{tr}}\left[1,\mathrm{e}\right]\cdot {\mathrm{v}}_{\mathrm{t}}+{\mathrm{c}}^{\mathrm{tr}}\left[2,\mathrm{e}\right]\cdot \left(\mathrm{d}\left(T\left[\mathrm{V},\mathrm{s}\right]\right)-\mathrm{d}\left(T\left[\mathrm{V},\mathrm{s}\right]\cap T\left[\mathrm{V},\mathrm{s}\prime \right]\right)\right)$$

  

  where $${\left|\mathrm{x}\right|}^{+}=0,\mathrm{x}<0;{\left|\mathrm{x}\right|}^{+}=\mathrm{x},\mathrm{x}\ge 0.$$

  
• For the stationary part of the energy the air path plays an important role. For the same emptying path, the minimum transport energy is obtained when the shortest air path is employed, that is, by opening the upstream air valve closest to the inlet being emptied. The type of fraction also affects the power requirements, needing more energy those types of fraction that are more dense. Under these considerations, it is assumed that, during the stationary phase, power consumption is a linear function of the air path, c^st[1,e](r)+c^st[2,e](r)· d(

  

  [A,i]), with coefficients depending on the type of fraction. The stationary energy can be expressed as follows: $${\mathrm{E}}^{\mathrm{st}}\left[\mathrm{t}\right]={\displaystyle {\sum }_{\mathrm{L}\left[\mathrm{f},\mathrm{j}\right]=\mathrm{next}\left(\mathrm{L}\left[\mathrm{f},\mathrm{i}\right]\right)}\left({\mathrm{c}}^{\mathrm{st}}\left[1,\mathrm{e}\right]\left(\mathrm{f}\right)+{\mathrm{c}}^{\mathrm{st}}\left[2,\mathrm{e}\right]\left(\mathrm{f}\right)\cdot \mathrm{d}\left(T^{\mathrm{A}}\left[\mathrm{i}\right]\right)\right)\cdot {\mathrm{T}}^{\mathrm{st}}\left[\mathrm{t}\right]\left(\mathrm{i},\mathrm{j}\right),\mathrm{L}\left[\mathrm{f},\mathrm{i}\right]\in \left[\mathrm{f},\mathrm{s},\mathrm{t}\right]}.$$

  
• The objective is to find a set of emptying sequences and air speed operations, {

  

  [f,s,t]} × {v_t}, 0 ≤ t ≤ T, for an operative period of time T (e.g. a day), that minimizes the energy cost, Σ_0≤t≤T f_c(t) · (E^tr[t]+E^st[t]) , subject to the following constraints:
• I[f,i,0], ∀ I[f,i] ∈
  
  . Constant giving the initial inlet loads.
• I[f,i,t] = I[f,i,t-1] + d[f,i,t-1] - L[f,i,t-1], ∀ I[f,i] ∈
  
  , 0<t≤T. Inlets volume update. Random process d[f,i,t] denotes user waste disposal into I[f,i] during time slot t.
• I[f,i,T] ≤ ε[f,i], ∀ I[f,i] ∈
  
  . Inlets residual load.
• I[f,i,t-1] > th[f,i] ==> I[f,i,t] ≤ th[f,i], V I[f,i] ∈
  
  , 0<t≤T . Inlets over load threshold must be included.
• 
  [f,s,t] = {L[f,i,t] | 0<t≤T, L[f,i,t]≤I[f,i,t], $\mathrm{I}\left[\mathrm{f},\mathrm{i}\right]\in I^{\mathrm{s}}$
  
  , ${\displaystyle {\sum }_{\mathrm{I}\left[\mathrm{f},\mathrm{i}\right]\in I^{\mathrm{s}}}\mathrm{L}\left[\mathrm{f},\mathrm{i},\mathrm{t}\right]\le \mathrm{L}\left[\mathrm{f},\max \right]}$
  
  }, 0<t≤T. Emptying sequence maximum load per inlet and maximum transfer load.
• ${\max }_{\mathrm{I}\left[\mathrm{f},\mathrm{i}\right]\in I^{\mathrm{s}}}\left(\mathrm{V}\left[\mathrm{f},\mathrm{i}\right]\right)\le {\mathrm{v}}_{\mathrm{t}}\le {\mathrm{V}}_{\mathrm{M}}$
  
  ; 0<t≤T. Range of operational air speed.
• The energy cost (f_c(t)) depends on time and on the energy fares.
• The system has a stochastic behaviour, that is, the way the users dispose waste into the inlets has a random component. This randomness can be described by a list of real world disposals (d[f,i,t]) or by a parameterized random function for arrival times and waste amount for any inlet.
• The problem described above can be tackled by different dynamic programming approaches. All of them will require, at some point, an optimization step. It is presently describe how a single problem instance can be encoded as a Constraint Integer Program (CIP). Such an instance is specified by the system status at the end of a time slot, before performing an optimal decision.
• A CIP is defined by a set of variables (integer and real valued), constraints (among the variables) and an objective function. From the system model {

  

  ,

  

  , $V^{\mathrm{a}}$

  

  , $V^{\mathrm{s}}$

  

  }, the disposition of the sector valves $\left(V^{\mathrm{s}}\right)$

  

  determine a set of sectors (

  

  ).
• For determining the emptying sequence of any chosen subset of inlets, it is necessary to provide a total ordering of such inlets. This is an important step towards minimizing the energy needed for emptying a subset of inlets. A possible ordering algorithm is presently described; it orders once all the inlets of the plant and the resulting total order is then used for ordering any subset of inlets chosen at any execution of the optimization algorithm.
• Notation and auxiliary functions used in the ordering algorithm:
• 
  : set of inlets.
• 
  (
  
  ,
  
  ): binary tree where nodes can be of different classes:
  • Root node: the node with the absorption engine (collection facility), that is connected with either a junction node or with an internal inlet node.
  • Junction node: an internal node with two upstream pipes and one downstream pipe. The two son nodes of a junction node n are denoted as sonl(n) and son2(n).
  • Internal inlet node: an internal node with an inlet with a downstream pipe and an upstream pipe. The son on an internal inlet node n is denoted as son(n).
  • Leaf node: a leaf node can either contain an inlet or simply an air valve.
• getfarthest(
  
  (
  
  ,
  
  ), r): a function that gets the farthest inlet node fn of the subtree $T_{\mathrm{r}}$
  
  , and its distance d from the root of
  
  (
  
  ,
  
  ) in the pair (fn, d), or return (null, 0) if there is no inlet in $T_{\mathrm{r}}$
  
  .
• The ordering algorithm is defined recursively for a plant tree, or plant subtree, and the ordering it gives depends on the following possible cases for the plant tree:
1. 1. leaf inlet node: in this base case the ordering contains only the inlet node.
2. 2. internal inlet node: all the inlet nodes of the subtree attached to the node will be inserted first in the ordering, and then the inlet node.
3. 3. junction node: all the inlet nodes of the subtree that contains the farthest node from the root node will be inserted first, and then the inlet nodes of the other subtrees.


• Before defining the variables and constraints, the following parameters not mentioned before are defined:
• pu[f,i] ∈
  
  , f = 1 ... |
  
  |, i = 1 ... |
  
  |, is the penalty cost due to left unloaded the inlet I[f,i] above a given threshold of its maximum capacity (th[f,i]).
• L[f,i] ∈
  
  , is the load of I[f,i] at the beginning of the time slot being optimized (I[f,i,t]).
• s' ∈ {1 ... |
  
  |}, denotes the previous active sector.
• f' ∈ {1 ... |
  
  |}, denotes the previous active fraction.
• v' ∈
  
  , denotes the previous operational speed.
• Ind : {0 ... |
  
  |} → {0 ... |
  
  |}, is a function that orders the set
  
  U Ø according to the above definition, Ø being the root node.
• Vp : {(1 ... |S|) × (1 ... |S|)} →
  
  , Vp(s, s') = d(
  
  [V,s]) - d(
  
  [V,s] ∩
  
  [V,s']), is the vacuum path.
• Ep : {(0 ... |
  
  |) × (0 ... |
  
  |)} →
  
  , Ep(i, j) = d(
  
  [E,i]) - d(
  
  [R,i] ∩
  
  [E,j]), is the emptying path.
• Ap : {(1 ... |
  
  |} →
  
  , Ap(i) = d(
  
  [A,i]), is the air path.
• In the CIP model there are decision variables over which the search is performed, and auxiliary variables in order to make a more readable set of constraints. The following decision variables are defined:
• si ∈ {0, 1}, i = 1... |S|, indicates whether a sector is activated for emptying.
• f_i ∈ {0, 1}, i = 1 ... |
  
  |, determines the fraction.
• 
  [s,f,i] ∈ {0, 1}, s = 1 ... |S|, f = 1 ... |
  
  |, i = 1 ... |
  
  |, indicates whether inlet I[f,i] is going to be emptied with sector s. It is assumed that inlets can not be partially emptied.
• v ∈
  
  . Operational air speed.
• The auxiliary variables are:
• b[f,i] = Σ_1≤s≤|S|
  
  [s,f,i] ∈ {0, 1}, f = 1 ... |
  
  |, i = 1 ... |
  
  |, indicates whether an inlet I[f,i] is active regardless of the sector being considered.
• p[s,f,i,j] ∈ {0, 1}, s = 1 ... |S|, f = 1 ... |
  
  |, i = 1 ... |
  
  |, Ind(i) < Ind(j). It is a pair of inlet indicators, keeping track active inlets and their corresponding following up. It helps to compute energy.
• v^tr ∈
  
  , is the air speed value to be considered in the transitory phase for energy calculation, depending on the fraction to be transported.
• ${\mathrm{E}}^{\mathrm{tr}}={\mathrm{c}}^{\mathrm{tr}}\left[1,\mathrm{e}\right]\cdot {\mathrm{v}}^{\mathrm{tr}}+{\mathrm{c}}^{\mathrm{tr}}\left[2,\mathrm{e}\right]\cdot {\displaystyle {\sum }_{1\le \mathrm{i}\le \left|\mathrm{s}\right|}{\mathrm{s}}_{\mathrm{i}}}\cdot \mathrm{Vp}\left(\mathrm{i},\mathrm{s}\prime \right)\in ℝ$
  
  , is the transitory energy.
• ${\mathrm{T}}^{\mathrm{st}}\left[\mathrm{i},\mathrm{j}\right]={\displaystyle {\sum }_{1\le \mathrm{s}\le \left|\mathrm{s}\right|}{\displaystyle {\sum }_{1\le \mathrm{f}\le \left|\mathrm{F}\right|}\left({\mathrm{c}}^{\mathrm{st}}\left[1,\mathrm{t}\right]\cdot l\left[\mathrm{s},\mathrm{f},\mathrm{i}\right]\cdot L\left[\mathrm{f},\mathrm{i}\right]+\left(\mathrm{p}\left[\mathrm{s},\mathrm{f},\mathrm{i},\mathrm{j}\right]\cdot \mathrm{Ep}\left(\mathrm{j},\mathrm{i}\right)\right)/\mathrm{v}\right)}\in ℝ}$
  
  , i = 1 ... |
  
  |, j = 1 ... |
  
  |, is the stationary time.
• ${\mathrm{c}}^{\mathrm{st}}\left[\mathrm{i}\mathrm{,e}\right]={\displaystyle {\sum }_{1\le \mathrm{j}\le \left|F\right|}{\mathrm{c}}^{\mathrm{st}}\left[\mathrm{i;e}\right]}\left(\mathrm{j}\right)\cdot {\mathrm{f}}_{\mathrm{j}}\in ℝ$
  
  , i ∈ {1, 2}, determines the coefficients for the stationary energy calculation.
• ${\mathrm{E}}^{\mathrm{st}}={\displaystyle {\sum }_{1\le \mathrm{i}\le \left|I\right|}{\displaystyle {\sum }_{1\le \mathrm{i}\le \left|I\right|,\mathrm{Ind}\left(\mathrm{i}\right)<\mathrm{Ind}\left(\mathrm{j}\right)}\left({\mathrm{c}}^{\mathrm{st}}\left[1,\mathrm{e}\right]+{\mathrm{c}}^{\mathrm{st}}\left[2,\mathrm{e}\right]\cdot \mathrm{Ap}\left(\mathrm{j}\right)\right)\cdot {\mathrm{T}}^{\mathrm{st}}\left[\mathrm{i}\mathrm{,j}\right]\in ℝ}}$
  
  , is the stationary energy.
• $\mathrm{P}={\displaystyle {\sum }_{1\le \mathrm{i}\le \left|I\right|}{\displaystyle {\sum }_{1\le \mathrm{f}\le \left|F\right|}\mathrm{pu}\left[\mathrm{f}\mathrm{,i}\right]\cdot \left(1-\mathrm{b}\left[\mathrm{f}\mathrm{,i}\right]\right)\in ℝ}}$
  
  , is the penalty due to leave unloaded inlets above a given threshold.
• The constraints are:
• ${\displaystyle {\sum }_{1\le \mathrm{i}\le \left|S\right|}{\mathrm{s}}_{\mathrm{i}}\le 1}$
  
  . At most one active sector.
• ${\displaystyle {\sum }_{1\le \mathrm{i}\le \left|F\right|}{\mathrm{f}}_{\mathrm{i}}\le 1}$
  
  . At most one active fraction.
• ┐ s_j ==> ┐
  
  [j,f,i], ∀ i = 1 ... |
  
  |, j = 1 ... |
  
  |, f = 1 ... |
  
  |. Inactive sector propagation.
• ┐ f_k ==> ┐
  
  [s,k,i],
  
  i = 1 ... |
  
  |, s = 1 ... |S|, k = 1 ... |
  
  |. Inactive fraction propagation.
• Σ_s,f,i
  
  [s,f,i] ·L[f,i] ≤ L[f,max]. Maximum transfer load per fraction.
• ${\max }_{\mathrm{i}=1\dots \left|I\right|}\left(\mathrm{V}\left[\mathrm{f}\mathrm{,i}\right]\cdot \mathrm{b}\left[\mathrm{f}\mathrm{,i}\right]\right)\le \mathrm{v}\le {\mathrm{V}}_{\mathrm{M}}\in ℝ$
  
  . Operational air speed.
• ${\displaystyle {\sum }_{1\le \mathrm{i}\le \left|I\right|}\mathrm{p}\left[\mathrm{s}\mathrm{,f}\mathrm{,0}\mathrm{,i}\right]\le 1,{\sout{\mathrm{V}}}_{\mathrm{s}}=1}\dots \left|S\right|,\mathrm{f}=1\dots \left|F\right|$
  
  . Root node (Ø) has at most one follow up inlet.
• ┐
  
  [s,f,i] ==> (┐ p[s,f,i,j] Λ ┐ p[s,f,j',i],
  
  s = 1 ... |S|, f = 1 ... |
  
  |, i = 1 ... |
  
  |, j = 1 ... |
  
  | : i < j, j' = 0 ... |
  
  | : j' < i. Inactive inlet propagation.
• $\mathrm{\iota }\left[\mathrm{s}\mathrm{,f}\mathrm{,i}\right]==>{\displaystyle {\sum }_{0\le \mathrm{j}\le \left|I\right|,\mathrm{Ind}\left(\mathrm{j}\right)<\mathrm{Ind}\left(\mathrm{i}\right)}\mathrm{p}\left[\mathrm{s}\mathrm{,f}\mathrm{,j}\mathrm{,i}\right]=1}$
  
  , V s = 1 ... |
  
  |, f = 1 ... |
  
  |, i = 1
  
  ... |I|. Exactly one follow down inlet.
• (s_j Λ f_k ==> ∑_1≤i≤|I| b[j,k,i] ≥ 1, V j = 1 ... |
  
  |, f = 1 ... |
  
  |. At least one active inlet for active sector and fraction.
• f_f' ==> (v^tr = |v - v' |⁺). Speed contribution to transitory energy when fraction to be transported remains the same.
• ┐ f_f' ==> (v^tr = v). Speed contribution to transitory energy when fraction to be transported changes.
• L[f,i] < ε[f,i] ==> ┐ b[f,i], V i = 1 ... |
  
  |, f = 1 ... |
  
  |. Don't empty inlets below a residual threshold.
• The objective is to minimize the energy consumption plus the penalty for leaving unloaded inlets above a threshold of their maximum capacity, i.e., to minimize the objective function (E^tr + E^st +

  

  ): $$\min \left({\mathrm{E}}^{\mathrm{tr}}+{\mathrm{E}}^{\mathrm{st}}+\mathrm{P}\right)$$

  
• This provides the immediately optimal decision. As an automated vacuum waste collection plant operates nonstop, and it being a strong requirement that all the inlets must be emptied at least once a day, one can think on planning operations with a time horizon of, e.g., a day.
• Planning algorithms can be based on dynamic programming techniques and should take optimal decisions at each time slot, according to the above process. The time granularity (time duration of a time slot) will be lower bounded by the time required to take these decisions and will be determined by the encoding and the optimization solver performance. Considering that in a real scenario the time duration of an emptying sequence is in the order of a few minutes, the solver should give an optimal result in a matter of minutes, which is feasible (see below).
• The status of the system, beyond being deterministic, is subject to the stochastic behaviour of users, so that, at each time slot, the system value depends on the value of the next time slot plus the cost of operation for the decisions taken on the current time slot. One possible approach is to use machine learning mechanisms to train the system, using dynamic algorithms that learn from historical data of existing plants (corpus data) about the values of the system. This training process has two main characteristics.
• Firstly, the states of the system are characterized. The inlet's status, even simplified to a few number of levels, makes unfeasible a wholesome approach. As an example, 50 inlets described by three filling levels lead to a huge number of states (~10²³). Thus, some kind of aggregation will be needed in order to reduce the dimensionality of the problem. In is proposed to aggregate inlet filling levels, so characterizing the system status by sector filling levels instead of inlets, and defining this way a more accurate number of levels for the sector. It is also proposed a non linear contribution to the sector filling level amount for inlets beyond a given threshold level of occupancy, making more relevant those states with high occupancy inlets.
• Secondly, the transition probabilities among the above mentioned states must be derived. As it is not feasible to characterize the stochastic behaviour of the inlets (users), it is proposed a learning schema based on approximate dynamic programming algorithms. In such algorithms, one trains the system by two different loops. First, the algorithm iterates through the time line, computing the system value for a given time slot, according to an optimal decision, and for a given realization of the stochastic input processes, namely input levels. As there are historic data with different realizations of the stochastic input process, the algorithm iterates in a second loop over all the possible realizations.
• In this way, the approximate values of the system at each time slot are considered in the optimization process, an optimal sequence is derived, and the computed results feedback the historical data for system readjustments. As already mentioned, considering that in a real scenario the time duration of an emptying sequence is in the order of a few minutes, the ability of the solver to give an optimal result in few minutes will determine its suitability for real time operation. With this objective in mind, three existing plants have been encoded as five real problems and optimal solutions have been computed under different load situations. Table 1 summarizes the results.
• The columns of Table 1 are:
• A problem name with its corresponding topology. Problem 2.1 and 2.2 correspond to the same plant with different sectorizations, as it is for problem 3.1 and 3.2.
• The number of drop-off points and inlets.
• The number of sections and fractions.
• The number of variables and constraints before and after pre-solving.
• Time to solve. A time limit of 5 minutes has been employed. This is a typical value for the emptying sequence time in a vacuum plant and gives the time limit for taking the next decision (i.e., while an emptying sequence is under way).
• The solution gap as the relative difference between the primal and dual bounds. This gives a measure of the accuracy of the solution hitherto obtained in relation to the optimal solution.
• The system load as the percentage of inlets with a load above the residual threshold. This parameter increases the number of variables and constraints after the pre-solving phase. Among the loaded inlets, roughly a 20% of them are loaded above the penalty threshold (th[f,i]).
Table 1

Problem	# drops	# inlets	# sect.	# fract.	# vars.		# const.		Time (s.)	Gap (%)	Load (%)
p1	39	54	6	2	26,910	94	35,443	264	84	0	10
p1	39	54	6	2	26,899	223	35,439	657	84	0	20
p1	39	54	6	2	26,910	513	35,434	1,413	88	0	30
p1	39	54	6	2	26,910	1,367	35,424	3,712	146	0	50
p2.1	30	102	4	4	21,708	119	28,661	336	7	0	10
p2.1	30	102	4	4	21,708	334	28,651	962	-	0.77	20
p2.1	30	102	4	4	21,708	679	28,640	1,941	-	1.45	30
p2.1	30	102	4	4	21,708	1,331	28,618	3,742	-	5.95	50
p2.2	30	102	9	4	32,086	198	42,835	568	16	0	10
p2.2	30	102	9	4	32,086	545	42,375	1,616	-	0.32	20
p2.2	30	102	9	4	32,086	1,134	42,364	3,261	-	2.38	30
p2.2	30	102	9	4	32,086	2,096	42,342	5,951	-	10.34	50
p3.1	53	109	4	2	40,126	89	52,836	211	135	0	10
p3.1	53	109	4	2	40,126	260	52,825	625	138	0	20
p3.1	53	109	4	2	40,126	658	52,816	1,609	-	0.61	30
p3.1	53	109	4	2	40,126	1,015	52,794	2,429	169	0	50
p3.2	53	109	5	2	15,549	49	20,540	133	23	0	10
p3.2	53	109	5	2	15,549	104	20,529	288	23	0	20
p3.2	53	109	5	2	15,549	284	20,520	746	24	0	30
p3.2	53	109	5	2	15,549	1,476	20,488	1,235	25	0	50

• The problems have been solved with SCIP version 2.1.1[3] with SoPlex 1.6 and default settings in a 2.66 GHz processor. The solving times are clearly suitable for real time operation.
• Although only a number of particular embodiments and examples of the invention have been disclosed herein, it will be understood by those skilled in the art that other alternative embodiments and/or uses of the invention and obvious modifications and equivalents thereof are possible. Furthermore, the present invention covers all possible combinations of the particular embodiments described. Reference signs related to drawings and placed in parentheses in a claim, are solely for attempting to increase the intelligibility of the claim, and shall not be construed as limiting the scope of the claim. Thus, the scope of the present invention should not be limited by particular embodiments, but should be determined only by a fair reading of the claims that follow.
• Further, although the embodiments of the invention described with reference to the drawings comprise computer apparatus and processes performed in computer apparatus, the invention also extends to computer programs, particularly computer programs on or in a carrier, adapted for putting the invention into practice. The program may be in the form of source code, object code, a code intermediate source and object code such as in partially compiled form, or in any other form suitable for use in the implementation of the processes according to the invention. The carrier may be any entity or device capable of carrying the program.
• For example, the carrier may comprise a storage medium, such as a ROM, for example a CD ROM or a semiconductor ROM, or a magnetic recording medium, for example a floppy disc or hard disk. Further, the carrier may be a transmissible carrier such as an electrical or optical signal, which may be conveyed via electrical or optical cable or by radio or other means.
• When the program is embodied in a signal that may be conveyed directly by a cable or other device or means, the carrier may be constituted by such cable or other device or means.
• Alternatively, the carrier may be an integrated circuit in which the program is embedded, the integrated circuit being adapted for performing, or for use in the performance of, the relevant processes.

Claims (17)

1. Method for the removal of waste from a network of waste inlets (I) in an automated waste collection system, said inlets being adapted to be loaded with at least one type of waste fraction (f_i), said network having a root node (RN) where the collection facility is, and said system comprising at least one valve (vs) that defines at least two sectors, any sector comprising the root node (RN) and the inlets connected thereto under one condition of the valve (vs), either open or closed, the method comprises, using machine learning techniques and linear programming algorithms:

   - ordering all the inlets (I) of the waste collection system by means of an ordering algorithm;

   - selecting the next sequence of inlets (I) from which waste is to be unloaded and transported to the root node (RN), said selection being the result of an optimization problem that comprises the minimization of a cost function under at least one operational constraint, the cost function being a function of at least two variables, one variable being an estimation of the cost of the energy consumed in the transport of waste from the inlets (I) to the root node (RN), and another variable being a penalty related to not unload inlets (I) that are loaded with waste at a level above their assigned capacity, and one operational constraint being that only inlets (I) from at most one sector can be unloaded in any distinct unloading sequence; and

   - transporting the unloaded waste from the inlets (I) of the selected sequence to the root node (RN).
2. Method according to claim 1, wherein the step of selecting the next sequence of inlets to be unloaded is performed in parallel with the step of transporting the waste from the inlets of the last selected sequence.
3. Method according to claim 2, wherein the estimation of the cost of the consumed energy is made separately for the transitory energy consumed when changing, from one sequence to the next, the sector where the unloading is to take place or the air speed to be applied to the unloaded waste, and for the stationary energy consumed during the actual waste transportation.
4. Method according to claim 3, wherein the cost function comprises the sum of the estimation of the cost of said transitory energy and the estimation of the cost of said stationary energy.
5. Method according to claim 3 or 4, wherein the estimation of the cost of the transitory energy is a function of at least the respective types of waste fraction transported in two consecutive unloading sequences, the respective air speeds for the waste transportation in two consecutive unloading sequences, and the amount of air to be removed in one unloading sequence before the actual waste transportation is started.
6. Method according to any of claims 3 to 5, wherein the estimation of the cost of the stationary energy is a function of at least the air speed for the waste transportation in an unloading sequence, the amount of waste to be transported in an unloading sequence, and the inlets included in an unloading sequence and the order in which said inlets are to be unloaded.
7. Method according to any of the preceding claims, wherein the network is tree-shaped.
8. Method according to claim 7, wherein the step of ordering the inlets comprises the substeps of:

   - ordering the inlets on each branch starting from the farthest from the root node and ending in the nearest to the root node;

   - ordering the branches that joins a junction node in the descending order of the distance from the last inlet of each branch to the root node;

   - iterating over all the junction nodes of the tree until all the inlets are ordered.
9. Method according to any of the preceding claims, wherein at least one of the following is another operational constraint in the minimization of the cost function:

   - only one type of waste fraction can be unloaded in the next unloading sequence;

   - at most one sector is active in the next unloading sequence;

   - inlets belong to at least one sector;

   - a least one inlet is active if a sector is active;
   not more than a maximum quantity can be transported for each type of waste fraction;

   - the air speed is upper and lower bounded for each type of waste fraction;

   - only inlets loaded at a level above a threshold can be unloaded.
10. Method according to any of the preceding claims, which comprises applying optimization algorithms to a model of the parameters of the system and encoding the resulting model as a constraint integer program.
11. Method according to any of the preceding claims, which comprises the step of planning the future unloading sequences with a time horizon of at least one hundred such sequences.
12. Method according to claim 11, wherein said planning comprises assigning a value to each state of the waste collection system, any such state being a selectable distinct unloading sequence.
13. Method according to claim 12, wherein said assignation is based on historical data compiled from the past operation of the waste collection system.
14. Method according to claim 12 or 13, wherein said planning comprises defining and solving a problem of dynamic programming, in which the solving step includes said minimization of the cost function given the current state of the waste collection system and the value assigned to each state thereof.
15. A computer program product comprising program instructions for causing a computer system to perform the method according to any of claims 1 to 14, for the removal of
    waste from a network of waste inlets in an automated waste collection system , said waste inlets adapted to be loaded with at least one type of waste fraction, said network having a root node where the collection facility is, and said system comprising at least one valve that defines at least two sectors, any sector comprising the root node and the inlets connected thereto under one condition of the valve, either open or closed.
16. A storage medium having stored thereon the computer program product of claim 15.
17. A carrier signal carrying the computer program product of claim 15.

Images