In 2011, FAO estimated that about one third of the total production of edible food for human consumption, gets lost or wasted, globally. In industrialized countries, more than 40% of the food losses occur at retail and consumer levels. A considerable part of the wasted food can be reused. The SORT project aims at \recycling" food in excess by converting it into animal feed or fuel for biogas/biomass power plants. During this process of reconditioning it is necessary to make choices in order to minimize the costs and maximize the earnings. However, due to the extremely complex nature of the process, it is not possible for a human being to make these choices at runtime and in an optimal manner. In these cases, Decision Support Systems (DSS) can be of help. In this paper we propose a DSS based on the Constraint Logic Programming (CLP) paradigm and ontology reasoning for nding the optimal solution. The information about feed processing and feed categories were extracted from Regulation (EU) 2017/1017 and stored into an ontology. Finally, we provide an evaluation of our system on several synthetic datasets with di erent search settings.
Food loss refers to losses of edible food mass throughout the early stages of the supply chain. Food losses take place during the stages of production, harvesting, treatment, storage and processing. Food losses occurring at the end of the food chain (retail distribution and nal consumption) are called food waste, which depend on the behaviour of retailers and consumers. For instance, at retail level, large quantities of food are wasted due to appearance standards (e.g. dented but unbroken cans, fruit with imperfections, etc.).
In industrialized countries, more than 40% of the food losses are food waste. In particular, the quantity of food wasted at consumer level in industrialised countries amounts to 222 million tonnes, roughly equivalent to the food production available in sub-Saharan Africa (230 million tonnes) [3]. The European Commission estimated that in 2012 about 88 million tonnes of food loss and waste were produced, with a related cost of 143 billion euros [9].
A considerable part of the food waste (currently destined for land ll) can be reused. The SORT project4 aims at \recycling" food items in excess or no longer consumable by humans. The main goals of the SORT project are: { Recovering the packaging for subsequent recycling. { Reconditioning the to-be-wasted food into a sellable product that can be used as feed material for animals or as fuel for biogas/biomass power plants.
The process envisioned by SORT is complex and involves several parties and actors (retail companies, vehicles, machinery for food processing, warehouses, animal feed factories, biogas/biomass power plants, etc.). In order to maximize the earnings and minimize the costs, several decisions must be made during the process, which must take into account several variables and purposes (food items used for reconditioning, maximizing pro t, the cost of using machinery for processing, storage costs, etc.). Given the extremely complex nature of the SORT process, a Decision Support Systems (DSS) can be used to aid the process manager to make choices.
In this paper we present a DSS for the SORT process developed using the Constraint Logic Programming (CLP) paradigm for nding the optimal solution. The knowledge about feed processes and categories was extracted from Regulation (EU) 2017/1017 and stored into an OWL ontology. Information represented in a logical formalism, such as OWL, enables the CLP engine to perform reasoning for nding the best solution.
The paper is organized as follows. Section 2 illustrates the processing of food
articles inside a SORT plant. Section 3 provides some background knowledge of
the technologies used for this DSS. In particular, it recalls the main concepts
of description logics and Constraint Logic Programming. Section 4 presents the
SORT Ontology, used to represent the feed materials and processes. Section 5
illustrates the CLP(FD) model of the DSS. Section 6 shows experimental results
on synthetic datasets. Section 7 concludes the paper.
4 The SORT project is promoted by the Italian Ministry of Education, Universities and
Research. Code: SCN 00367, Ministerial Act n. 2427 http://attiministeriali.
miur.it/anno-2015/ottobre/dd-28102015-(
The food articles to be reused are gathered at large retailers and collection centers, packaged and sent to the so-called SORT plants. Every box of food articles has an RFID chip for identi cation and tracking. The customers of a SORT plant are feed factories and biogas/biomass power plants, which can make di erent orders of feed materials.
Figure 1 shows the process chain of a SORT plant. When the boxes reach the SORT plant, they are opened and their contents are poured into an hopper. Then the Sorter machinery sorts the food articles into other boxes in order to create, if possible, homogeneous boxes, i.e. boxes that contain similar food articles. It is worth noting that, during this phase, the Sorter is not managed by the DSS. The boxes are then stored in an automated warehouse. This phase of the process chain is called input sorting.
In the warehouse we can have both homogeneous content boxes and heterogeneous content boxes. The presence of boxes with heterogeneous content certainly represents a complication, but also an interesting and stimulating challenge from a computational point of view.
If the articles contained in a box are selected by the DSS to satisfy an order, that box will be opened and its content will be poured into Sorter's hopper again and each article will be sent to one of the N regular output destinations or sent back, according to the guidelines speci ed by the DSS. At the end of each output destination there is a box that gathers all the sorted articles. This phase of the process chain is called output sorting . Finally, the selected articles are sent to machinery for unpacking and food processing or sent back to the warehouse. Example 1. Consider the case where the SORT plant received two orders, o1 and o2, that request two di erent types of feed materials and consider the situation depicted in Fig. 1. Moreover, let us suppose that both o1 and o2 must be satis ed. The DSS then assigns the rst output destination (out 1) to o1 and the second output destination (out 2) to o2 and, at the same time, assigns some of the food articles contained in the boxes with identi ers 5 and 17 to o1 and some of the articles contained in boxes 17 and 131 to o2. Boxes 5, 17 and 131 are then opened and their content is poured into the hopper. The Sorter then sends the articles chosen to satisfy o1 to out 1 and the articles chosen to satisfy o2 to out 2.
It should be noted that in the SORT plant, there is only one sorting line (for the time being). That means that the Sorter machinery depicted in Figure 1 on the left side of the warehouse (input sorting phase) is the same Sorter machinery on the right of the warehouse (output sorting phase). Consequently, during the output sorting phase, the Sorter will not be able to perform the input sorting step, i.e. it cannot process the boxes coming from large retailers and collection centers. 2.1
The envisaged user of the DSS is the manager of the SORT plant. Its job is to choose, day by day, which orders must be satis ed and which articles must be id:5 id:17 id:131
DSS go back out 2 out 3 out 4 . .
. out N Hopper
Sorter
Hopper
Sorter used to satisfy them in order to maximize the earnings, according to the available articles in the warehouse and to the received orders. These decisions are made with the help of the DSS.
One of the components of the DSS is a web-based application (still under development) which allows the user to perform the necessary operations to achieve the optimal solutions. We planned four use cases of the DSS: 1. Manual selection of orders and boxes The user selects which orders must be satis ed that day and which boxes must be used. The DSS assigns each user-selected order to an output destination and uses only the food articles contained in the selected boxes to satisfy them. 2. Manual selection of orders The user selects only the orders that must be satis ed that day. The DSS assigns each selected order to an output destination and uses the articles available in the warehouse to satisfy them. 3. Manual selection of boxes The user selects the boxes and the DSS, according to the optimization criterion, calculates which orders must be satised by using only the food articles contained in the selected boxes. 4. Automatic selection The DSS automatically selects the orders to satisfy, i.e. it automatically assigns an output destination to each chosen order, and chooses which articles must be used to satisfy them, according to the optimization criterion. 3 3.1
An ontology describes the concepts of the domain of interest and their relations with a formalism that allows information to be processable by machines. The Web Ontology Language (OWL) is a family of knowledge representation languages, based on description logics, for authoring ontologies or knowledge bases. OWL 2 [11] is the last version of this language and is a W3C recommendation since 2012. We used this logical formalism to represent the knowledge about feed processes and categories.
Description Logics (DLs) are fragments of FOL languages used for modeling knowledge bases (KBs) that exhibit nice computational properties such as decidability and/or low complexity [1].
There are many di erent DL languages that di er in the constructs that are allowed for de ning concepts (sets of individuals of the domain) and roles (sets of pairs of individuals). Below we illustrate the ALC DL, which is one of the most common fragments and it is the basis for many other DLs.
Let us consider a set of atomic concepts C, a set of atomic roles R and a set of individuals I. In ALC a concept C is either C1 2 C, ?, >, (C2 u C3), (C2 t C3), :C, 9R:C or 8R:C, where C2 and C3 are concepts and R 2 R.
A TBox T is a nite set of concept inclusion axioms C v D, where C and D are concepts. An ABox A is a nite set of concept membership axioms a : C, role membership axioms (a; b) : R, equality axioms a = b and inequality axioms a 6= b, where C 2 C, R 2 R and a; b 2 I. A ALC KB K = (T ; A) consists of a TBox T and an ABox A. It is usually assigned a semantics in terms of interpretations I = ( I ; I ), where I is a non-empty domain and I is the interpretation function, which assigns an element in I to each a 2 I, a subset of I to each concept and a subset of I I to each role. 3.2
A Constraint Satisfaction Problem (CSP) is de ned by a set of variables X = fX1; : : : ; Xng and a set of constraints C = fC1; : : : ; Cmg [8]. Each variable Xi has a domain Di of possible values. A constraint de nes a restriction over the possible combinations of values of a subset of variables. A solution of a CSP is an assignment of values to all variables that satis es all the imposed constraints. Constraint solving means nding a solution to a given CSP.
Constraint Programming (CP) is a programming paradigm where the relations among the variables are expressed in the form of constraints. In CP, the user states the constraints and a general purpose constraint solver tries to solve them. Constraint Logic Programming (CLP) is a paradigm of programming languages that merges two declarative paradigms: Logic Programming (LP) and CP.
A CLP language is de ned by the class (sort ) of allowable variable domains and constraints. A CLP language over a constraint class X is denoted as CLP(X) [4]. For instance, CLP(R) is a CLP language in which variables can range on the reals [5], whereas in CLP(FD) variables range on nite domains.
In CLP(X) the constraints of class X can be added to the body of the usual logic programming clauses. During Selective Linear De nite (SLD) resolution, the constraint are not resolved, but they are added to a special data structure, called the constraint store. The store is then processed by an external solver, called constraint solver. The constraint solver checks whether the conjunction of constraints is satis able and, in case, modi es the store in order to obtain a simpli ed state of the variables. The act of modifying the constraint store is known under the term of propagation.
Besides variables and constraints, the user can also de ne an objective function: a function that the solver tries to maximize or minimize without violating any constraint. If an objective function is de ned, like in our case, then the problem becomes an optimization problem.
We modelled our problem in Constraint Logic Programming on nite domains (CLP(FD)). Finite domain constraints are usually intended to be arithmetic constraints over nite integer domain variables. Therefore a CLP(FD) language needs a constraint system that is able to handle (i.e. store and propagate) this type of constraints.
There exist several implementations of logic programming and CLP(FD). For this project we decided to adopt ECLiPSe [7]5, which features a library for nite domains called gfd. This library interfaces ECLiPSe with Gecode's constraint solver [10]. To nd the optimal solution we use ECLiPSe's branch-and-bound approach. 4
Communion Regulation (EU) 2017/1017 is the legislative text in the European Union regarding the production of animal feed. It contains the list of all processes and the list of all categories of feed materials. The list of the processes that feed materials may undergo is illustrated in Part B of the regulatory text, whereas the catalogue of feed materials is given in Part C.
As already mentioned in Section 3.1, we used the logical formalism OWL 2, based on DLs, to represent the knowledge about feed processes and categories. In particular, we used this regulation to generate an OWL 2 KB, called SORT Ontology, which can be used by the DSS to check the compatibility between an order and a food article. 4.1
Given the large number of processes and categories, we developed a simple program written in Java that parses the XML version of the aforementioned European regulation, and automatically outputs the SORT Ontology.
The tool allows the SORT system to be easily updated to future regulatory and legal developments. Moreover the ontology supports several languages6.
Figure 2 shows an excerpt from the SORT Ontology in OWL 2 RDF/XML.
Representing the knowledge about feed materials and processes by means of an ontology allows to exploit a reasoner to check if an article can be used to 5 http://eclipseclp.org 6 Currently supported: Italian, English, Spanish, French and German. <owl : Class rdf : about =" #1 " > < rdfs : subClassOf rdf : resource ="# Feed "/ > < rdfs : label xml : lang =" en " > Cereal grains and products derived thereof </ rdfs : label > < rdfs : label xml : lang =" it " > Cereali e prodotti derivati </ rdfs : label > ... </ owl : Class > <owl : Class rdf : about =" #1.1.1 " > < rdfs : subClassOf rdf : resource =" #1 "/ > < rdfs : comment xml : lang =" en " > Grains of Hordeum vulgare L. < / rdfs : comment > < rdfs : comment xml : lang =" it " > Grani di Hordeum vulgare L. </ rdfs : comment > < rdfs : label xml : lang =" en " > Barley </ rdfs : label > < rdfs : label xml : lang =" it " > Orzo </ rdfs : label > ... </ owl : Class > satisfy an order (see Compatible function in Eq. 1 Section 5). Moreover, it allows to obtain new information about food articles by exploiting other ontologies (see the Open Food Facts project (https://world.openfoodfacts.org/).
In this section we illustrate the CLP model of the DSS and the Prolog implementation of some constraints. 5.1
The variables of our model are the list of orders O = fo1; : : : ; oKg and the list of food articles A = fa1; : : : ; aM g, where K and M are the number of orders and articles, respectively. As we mentioned in Section 2, the sorting line, during the output sorting phase, can have N regular outputs (plus a special output for articles that should go back to the warehouse), therefore the domain of an order variable is
8i 2 f1; : : : ; Kg oi 2 f0; : : : ; N g where 0 means that the order will not be satis ed.
Each article, instead, can be used to satisfy one and only one order. Therefore the domain of an article variable contains the order indices plus the values -1 and 0:
8j 2 f1; : : : ; M g aj 2 f 1; : : : ; Kg where 0 means \stay", i.e. the article is not associated with any order and stays in the warehouse without moving, whereas -1 represents \go back", i.e. the article goes through the Sorter but it will be sent back to the warehouse.
For instance, aj = i with i > 0 means that the j-th food article will be used to satisfy the i-th order. aj = 0 means that the j-th food article will not be used, whereas aj = 1 means that the box which contains aj will be opened, some of its articles will be used to satisfy some orders, but the j-th article will not be used and it should go back in the warehouse. 5.2
We can split the constraints of our model into three categories: article constraints, order constraints and constraints for symmetry breaking. Article Constraints Here we illustrate the constraints relating food articles to the boxes that contain them. In particular, these constraints are used to maintain the consistency of the warehouse.
The rst article constraint simply states that articles can't be associated with
incompatible orders
8j 2 f1; : : : ; M g 8i 2 f1; : : : ; Kg :Compatible(aj ; oi) ) aj 6= oi
(
In the SORT environment, each order consists of a requested quantity of only one feed material and each article belongs to only one feed category. For this scenario, our DSS does not perform any reasoning task, at least for now. Function Compatible checks if feed category of the order matches with the feed category of the article. However, in the future, for more complex scenarios, ontological reasoning might be necessary.
The following constraint is fundamental to preserve the consistency of the boxes contained in the warehouse. In fact, once a box is opened, all of its contents are poured into the hopper before the Sorter and therefore all the items contained in that box must be sorted by the Sorter (one of the possible destinations could be back to stock). It is not possible to have situations in which an article present in a box goes through the Sorter while the other articles contained in the same box remain in storage.
8j 2 f1; : : : ; M g aj > 0 ) (8k 2 f1; : : : ; M g Box (aj ) = Box (ak) ) ak 6= 0)
(
The following constraint, instead, states that if an article is associated with
an order, then that order must have a destination greater than 0
8j 2 f1; : : : ; M g (aj = i; i > 0) ) oi > 0
Order Constraints The following constraint states that is not possible for two
distinct order to share the same destination if they will be both satis ed
8i 2 f1; : : : ; Kg oi > 0 ) 8k 2 f1; : : : ; Kg oi 6= ok
This constraint was implemented by imposing an atmost/3 constraint to the
order variables for each possible destination
(
If the i-th order must be satis ed (oi > 0), then enough food product must be available 8i 2 f1; : : : ; Kg oi > 0 )
(
If there is not enough food product to satisfy an order, then the order is unsatis able and for sure its destination will be \stay" 8i 2 f1; : : : ; Kg
X Compatible(aj;oi)
Quantity(aj) < Quantity(oi) ) oi = 0
(
The following constraint xes an upper limit of food product that must be used to satisfy an order. It states that the sum of the quantities of food product contained in the articles used to satisfy an order must not exceed the quantity requested by an order plus a surplus quantity of food.
8i 2 f1; : : : ; Kg oi > 0 )
X Quantity(aj) aj=i
(
Symmetry Breaking Constraints In order to improve the search, we prune the search space by imposing the following \symmetry breaking" constraints which remove equivalent or symmetric solutions.
Example 2 (Equivalent solutions). Consider the case where we have three order variables: o1; o2 and o3 and the number of regular outputs of the Sorter is N . Suppose there exists a feasible solution
fo1 = 1; o2 = 0; o3 = 0g Since we can associate an order with any output of the Sorter, other solutions could be
fo1 = 2; o2 = 0; o3 = 0g : : : fo1 = N; o2 = 0; o3 = 0g We have N equivalent solutions.
To prune the search space and avoid situations like the one described in
Example 2, we impose that the maximum destination value that an order variable
can have is the number of orders that are going to be satis ed (i.e. the number
of order variables greater than 0)
oi>0
X 1 = S = max oi
i
(
fo1 = 1; o2 = 2; o3 = 0g A solution symmetric w.r.t. the one above is
fo1 = 2; o2 = 1; o3 = 0g
Symmetries like the one described in Example 3 can be broken by imposing
a total order to the order variables
8i; j 2 1; : : : ; K i < j; oi > 0; oj > 0 ) oi < oj
(
where NDest is the number of possible destinations. 5.3
The aim of the DSS user is maximize the earnings and minimize the costs. In particular the user wants to maximize the incomes obtained by satisfying the orders, while minimizing the storage costs, the penalties that must be paid if the orders are not delivered on time and the processing cost, i.e. the cost for using machinery for sorting, unpacking and food processing. So far, to compute the processing cost, only the sorting cost is taken into account.
In order to obtain an optimal solution, we de ne in our model the following objective function that should be maximized
Profit = X Income(oi) oi>0
UnusedArticlesCost LatePenalty
SortingPenalty where the function Income(oi) returns the income obtainable by satisfying the i-th order. UnusedArticlesCost is the cost of keeping the unused articles one more day in the storage and it is de ned as
UnusedArticlesCost =
X StorageCost(aj) where StorageCost (aj) is a function which returns the daily storage cost of the j-th article.
LatePenalty is the cost of not satisfying not even today those order whose deadlines were missed and it is de ned as
LatePenalty =
(12) where LateOrders is the set of orders with expired deadline, LateOrderPenalty(oi) is a function which returns the penalty for being one day late to satisfy the i-th order and DaysLate(oi) returns the number of delay days.
SortingPenalty is a penalty for all those articles that must \go back" and therefore should go through the sorter machine once again. So far, this is the only cost taken into account. It is de ned as
X ArticleSortingPenalty (aj) aj= 1
X oi2LateOrders where ArticleSortingPenalty (aj) returns the penalty of sorting once more the j-th article. 5.4
To nd the optimal solution we use the predicate bb_min/3, which performs a branch-and-bound algorithm. We separated the search for article and order variables, in order to allow the use of di erent heuristics for the two lists of variables.
bb_min ( ( gfd_search : search ( OrderDestinations , 0,
SelectOrderVars , ChoiceOrderVars , MethodOrderVars
, []) ,
(
SelectArticleVars , ChoiceArticleVars ,
MethodArticleVars , []) ) , Cost , bb_options { timeout : Timeout , delta : Delta , strategy :
Strategy } )
In the two predicates gfd_search:search/6, SelectOrderVars and SelectArticleVars are the variable selection methods for orders and articles respectively; ChoiceOrderVars and ChoiceArticleVars are the choice methods; MethodOrderVars and MethodArticleVars are the search methods. Among the available options of bb_min we have Timeout, that is the timeout of the optimization process (its default value is 0, i.e. in nite time), Delta, which is the minimal absolute improvement of Cost required for each step (default value is 10000), and Strategy, which is the optimization strategy used to nd the best solution.
In order to improve the performances of the search, we developed a custom variable selection method, called select_income. Considering that the system sorts the list of orders in descending order by pro t, if this heuristics is chosen for order variables, the order with the least value greater than zero is selected, which corresponds to the order with the greatest income. If this heuristics is chosen for article variables, the article that can be used for the most pro table order is selected.
select_income ( Var , Elem ) :get_domain_as_list ( Var , Domain ) , first_gt_zero ( Domain , Elem ).
first gt zero/2 uni es Elem with the rst value in the domain greater than 0, if there is not such values it uni es Elem with 0. 6
A prototypical plant is under development in the SORT project. In the meanwhile, since real data about orders and article is still not available, to test the system we generated synthetic random datasets with 30 orders whose incomes vary from 10,000 to 500,000 and an increasing number of articles. The size of the datasets is expressed in number of articles. The quantity of food product of each article randomly varies from 500 g to 5 kg. Whereas the quantity of requested feed material for each order varies from 50 kg to 100 kg.
We performed two types of experiments. In the rst a complete search in the space of solutions is performed, by taking into account di erent con gurations and strategies. In the second we set a timeout of 15 seconds and the obtained solutions are compared with the optimal solutions found with complete search. For all the experiments we set the sorting penalty to 0 and in the predicate bb_min/3 we set the option delta to 10,000.
In these tests we evaluated our system by combining several heuristics and strategies for search and optimization. However, due space limitations it was impossible to show the results for each heuristics combination. Table 1 shows some of the heuristics combinations used in our tests whose results are reported in this paper7.
All the tests were performed on the HPC System Marconi8 equipped with Intel Xeon E5-2697 v4 (Broadwell) @ 2.30 GHz, using 1 core for each test. Test 1: complete search We consider a number of articles from 100 to 400 in steps of 100 and, for each number of articles, we generated 5 datasets.
Table 2 reports the average CPU time in seconds for nding the optimal solution for 5 di erent random datasets with the combinations of heuristics illustrated in Table 1. We set a timeout of 1 hour, so the cells with \{" indicate that the timeout occurred at least in one dataset.
The results showed that the adopted heuristics a ect the computational time. In particular, among all the heuristics combinations used for Test 1 only Comb. 1 and 2 were able to scale up to 500 articles and both combinations use the custom variable selection method select_income for the article variables. 7 The results for other combinations are shown here: https://goo.gl/J4DWiu. 8 http://www.hpc.cineca.it/hardware/marconi Test 2: search with timeout It might be infeasible for the user to wait too long for the best solution. Sometimes a solution which is suboptimal but obtained quickly is the best thing for rapid decision making. To evaluate the behaviour of our system in these scenarios, for each dataset we run the CLP engine twice. In the rst execution the optimal solution is found by performing a complete search by using Comb. 1 (Table 1) and a timeout of 24 hours. In the second one, instead, we set a timeout of 15 seconds and we bounded the backtracking search steps to 1000. Then the (suboptimal) solutions obtained in the second run are compared with the optimal solutions found with complete search in the rst run.
We consider a number of articles from 500 to 1000 in steps of 100 and, for each number of articles, we generated 5 datasets.
The suboptimal solutions are evaluated using the Mean Absolute Percentage Error (MAPE) as metrics. The MAPE between the optimal solution obtained with a complete search (Sioptimal) and the solution obtained with a search with timeout (Sitimeout) is given by
N M AP E = 100 X
N i=1
Soptimal i
Stimeout
i Soptimal i where N is the number of datasets in which the complete optimization search did not reach the timeout. In this paper we presented a DSS which exploits the Constraint Logic Programming paradigm and supports ontology reasoning for nding the optimal solution, given the availability of articles in the warehouse of the SORT plant.
The experiments showed that CLP is a valid approach for modelling and solving complex problems such as the SORT process.
In the future, we plan to integrate a DL reasoner in our DSS in order to tackle more complex scenarios (e.g. scenarios where orders can request mixtures of feed materials), complete the development of its web interface and test our DSS with real data on a prototype of the SORT plant. So far, in our model, every article has the same storage cost, however there are di erent type of warehouses (refrigerated, room temperature, etc.); in the future we plan to use di erent storage costs depending on the warehouse in which the article was stored. Moreover we will take into account costs for using machinery for unpacking and food processing. We would also like to extend our model by taking into account not only articles already in stock, but also those currently being transported to the SORT plant.
In our approach we used ECLiPSe for representing the constraints and Gecode to solve them, it could be interesting to encode our problem with MiniZinc [6] and compare the two approaches. A completely di erent approach could be to exploit (Mixed) Integer Programming methods: encode the problem as a linear problem and solve it with a linear optimiser, such as Gurobi [2]. We reserve the implementations of these di erent approaches as future work.
Acknowledgement This work was supported by the SORT project, promoted by the Italian Ministry of Education, Universities and Research. Code: SCN 00367, Ministerial Act n. 2427.