CHEMICAL ENGINEERING TRANSACTIONS VOL. 76, 2019 A publication of The Italian Association of Chemical Engineering Online at www.aidic.it/cet Guest Editors: Petar S. Varbanov, Timothy G. Walmsley, Jiří J. Klemeš, Panos Seferlis Copyright © 2019, AIDIC Servizi S.r.l. ISBN 978-88-95608-73-0; ISSN 2283-9216 Quantity-Predictive Vehicle Routing Problem for Smart Waste Collection Dušan Hrabeca,*, Preben Senlandb, Vlastimír Nevrlýc, Pavel Popelad, Arild Hoffb, Radovan Šomplákc, Martin Pavlasc a Faculty of Applied Informatics, Tomas Bata University in Zlín, T.G. Masaryka 5555, 760 01 Zlín, Czech Republic b Molde University College – Specialized University in Logistics, Britvegen 2, 6410 Molde, Norway c Institute of Process Engineering, Faculty of Mechanical Engineering, Brno University of Technology – VUT Brno, Technická 2896/2, 616 69 Brno, Czech Republic d Institute of Mathematics, Faculty of Mechanical Engineering, Brno University of Technology – VUT Brno, Technická 2896/2, 616 69 Brno, Czech Republic hrabec@utb.cz The current trends in the field of waste management involves the use of modern technologies such as wireless sensors. The smart waste management with Sensor Technology involves an integration of the so-called smart trash bins and containers into existing network by using sensors that fill level of the bins and containers. Apart from the technological aspects of the problem, this arrangement points to the need of development of new decision-making tools that allow collectors to make fast and smart operative decisions on the waste collection. The sensors from the waste containers read the current fill-height once a day and send the information to the central database. The central decision-maker appraises the data and makes the waste collection plan for an entire (e.g., one week) collection period; note that this improves existing models on the data available and used. The aim of this paper is to present complex modelling ideas, develop a simple mathematical model, discuss its complexity and propose/discuss a computational approach in order to solve the collection problem. The objective is to optimize the dynamic planning on daily garbage-truck schedules with respect to minimization of transportation costs that also reflects a positive environmental impact presented by savings in transportation/routing distance. The secondary objective is to optimally decide on early collection of partly-filled containers, especially those directly on or close to the optimum route linking the full ones considering waste production rates in the next days. The paper outlines some directions for further research such as the need of modifying the old-existing models into a form utilizing the newly available data. This leads to specific vehicle routing problems that request appropriate computational time requirements and the need of suitable heuristic methods development. 1. Introduction Municipal waste management is an extremely crucial issue due to its effect on environment, society and economy. Since waste collection in urban areas is a key activity in sustainable waste management, it has gained rapidly increasing attention in the last decade (Xue et al., 2019). Since the city’s population grows every year by 3-5 % worldwide, the waste generation will double every ten years (Esmaeilian et al., 2018). More specifically, waste collection is considered as a very economically demanding part of overall waste processing management (Gregor et al., 2018). Therefore, waste collection and its management are considered as one of the most important issues in sustainable and smart city logistics design (Farrokhi-Asl et al., 2018) that, moreover, allows integration of waste as raw materials in a circular economy (Barbosa-Póvoa et al., 2018). A comprehensive review of recent research challenges in municipal solid waste management is provided by Bing et al. (2016). The waste collection is more and more important business mostly performed by private companies that daily face high transportation costs and inefficient usage of their resources, as vehicles often visit waste bins that are only partially full (Ramos et al., 2018) following the fixed schedule. Dynamic vehicle routing problem was demonstrated in (Jiao and Ning, 2018). Modern devices, such as volumetric sensors and various global DOI: 10.3303/CET1976209 Paper Received: 15/03/2019; Revised: 30/04/2019; Accepted: 02/05/2019 Please cite this article as: Hrabec D., Senland P., Nevrly V., Popela P., Hoff A., Somplak R., Pavlas M., 2019, Quantity-Predictive Vehicle Routing Problem for Smart Waste Collection, Chemical Engineering Transactions, 76, 1249-1254 DOI:10.3303/CET1976209 1249 positioning systems (GPS), are seen as a possible way to grow effectiveness of collection systems regarding not only investments (fleet of vehicles) and operational (transportation and maintenance) costs, but also to reduce environmental costs (e.g., emissions and noise) (Faccio et al., 2011). Due to the low average speed of used vehicles and many stops during collection, they have a higher effect on congestion, air pollution and noise than other freight transportation vehicles (Johansson, 2006). A real-time monitoring of vehicles (Liu et al., 2018) might help in the waste collection planning. Recently, the sensor-based networks have been used to monitor the waste load in a container and the route of the waste collector to improve the collection efficiency in smart cities (Bong et al., 2018). Therefore, there is an increasing trend to equip bins and containers with level sensors and wireless communication devices that can provide a real-time information on the container level to the waste collectors (Johansson, 2006). According to Expósito and Velasco (2018), the EU 2020 strategy involves two mandatory goals: the need to decrease the total amount of mixed municipal waste, and the necessity to increase the separate collection of recyclable materials. Development and implementation of dynamic scheduling and routing models in waste collection utilizing the real-time data obtained from the sensors have already been intensively discussed during last years and bring a potential effective solution for the near future. Johansson (2006) concluded that the dynamic scheduling and routing policies lead to lower operating costs, shorter collection (distances) and collection of fewer containers regarding the static ones. Fadda et al. (2018) proposed a scheduling model for weekly waste collection for multiple types of waste without imposing periodic routes. However, no efficient utilization of available-historical data and usage of prediction is available in the recent models. This paper attempts to propose a new dynamic (scheduling and routing) modelling approach that eliminates this research gap and has an application perspective for similar collection problems considering sensor-equipped bins in urban areas. Herein, a single type of waste is considered within an artificial network data in order to test the proposed approach. The goal is also to prevent the overflow of bins which is performed through the historical data implementation. The objective is to optimize the dynamic planning on daily garbage-truck schedules with respect to minimization of transportation costs that also reflects a positive environmental impact presented by savings in transportation/routing distance. The secondary objective is to optimally decide on early collection of partly-filled containers, especially those directly on or close to the route linking the full ones considering waste production rates in the next days. The central decision-maker appraises the data and makes the waste collection plan for a one-week collection period. The main novelty of the proposed approach lies in improving the existing models on the effective usage of available data. The reminder of this paper is organized as follows. In Section 2, a description of the formulated waste collection problem is provided together with developed mathematical model and with explanation of the used notation. Then in Section 3, the model is implemented on our artificial data set and some preliminary computational results are provided. The paper concludes with Section 4 that provides a discussion of obtained results and specifies further research directions. 2. Mathematical model This section successively provides a general description of the considered smart waste collection problem in subsection 2.1 and a mathematical model together with a description of its particular parts in subsection 2.2. 2.1 Problem description The model presented below is formulated as a vehicle routing problem applied in waste collection, where the current fill level of bins is known to the decision-maker. It is considered that each bin is equipped with a sensor that measures its waste level, and this information is sent to the planner at certain intervals. In addition to giving information about the current levels, the readings can be used to estimate at what rate waste is accumulated in each bin. Therefore, the problem is partly deterministic (the current level) and partly stochastic (the future accumulation of waste). A time interval composing of the certain number of days is considered (e.g., one week). More specifically, the model is solved using the known fill levels for the day 1 while it also takes into consideration the estimated accumulation rate (amount) for upcoming days (2-7). The solution is a schedule of routes for days 1 until 7. This is then repeated and re-solved every day when new information is received. E.g., on the day 2 the fill levels are updated and the model is solved, yielding a schedule of routes for days 2 until 8. See Figure 1 for a simple illustration of the described dynamic model principle. There are two reasons why the scheduled routes might change. The first one is inherent to the problem and it is that the accumulation of waste is stochastic, i.e., it will vary around the estimated rate. The second reason is a consequence of how the model is built. There is no constraint in the model regarding fill rate at the end of the period. Because of this, the model will have solutions where fill rates are approaching bin capacities on the last days. 1250 a) Day 1: route 1 (realized today) and route 2 (trip planned for tomorrow based on prediction of waste amount) b) Day 2: updated route 2 (realized trip based on actual waste amount) Figure 1: Illustrative example of the proposed dynamic principle: day 1 and day 2 2.2 Notation, mathematical model and its description Table 1 provides a summary of used notation, i.e. sets, parameters and variables (either binary, integer or continuous). Then, the mathematical model, which consists of the objective function (Eq.1) minimizing the total cost and constraints in Eqs. (2) - (20), is developed and further presented. Table 1: Mathematical model related notation Type Symbol Description Sets Parameters Variables 𝑉 𝑉0 𝐷 𝐷0 𝑐𝑖𝑗 𝑎𝑑 𝑄 𝑞𝑖 𝑠𝑒𝑛𝑠𝑜𝑟 𝑞𝑖 𝑚𝑎𝑥 𝑏 𝑓 𝑑 𝑒 𝑀 𝑔𝑖 𝑥𝑖𝑗𝑑 𝑦𝑖𝑑 𝑢𝑖𝑑 𝑞𝑖𝑑 𝑤𝑖𝑑 𝑣𝑖𝑑 𝑡𝑑 nodes representing the bins all nodes for bins and the depot, 𝑉0 = 𝑉 ∪ {0} days in the planning period, 0 is first day of the planning period set 𝐷 excluding node 0 cost of travelling from i to j, 𝑖, 𝑗 ∈ 𝑉0 0-1 values, value of 1 indicates a working day, 0 non-working day, 𝑑 ∈ 𝐷 vehicle capacity measured level of the bins at the start of planning, 𝑖 ∈ 𝑉 bin capacity, 𝑖 ∈ 𝑉 limit on number of routes per day for the vehicle minimum number of times bins should be emptied during each planning period penalty for bin overflow penalty for each route above 𝑏 , overtime or outsourcing cost big M. A number sufficiently high used as limit on constraints. daily production of waste at each bin, 𝑖 ∈ 𝑉 0-1 variable, 1 indicates that the vehicle travels from i to j on day d, 𝑖, 𝑗 ∈ 𝑉0 , 𝑑 ∈ 𝐷 0-1 variable, 1 indicates that node i is serviced on day d, 𝑖 ∈ 𝑉, 𝑑 ∈ 𝐷 the load on the vehicle when leaving node i on day d, 𝑖 ∈ 𝑉, 𝑑 ∈ 𝐷 level of the bin at node i on day d, 𝑖 ∈ 𝑉, 𝑑 ∈ 𝐷 level of a bin’s overflow, 𝑖 ∈ 𝑉, 𝑑 ∈ 𝐷 used to linearize the calculation of the bin levels, 𝑖 ∈ 𝑉, 𝑑 ∈ 𝐷 number of routes above the daily b, 𝑑 ∈ 𝐷 1251 The mathematical model together with description of its particular components follows: Min ∑ ∑ ∑ 𝑐𝑖𝑗 𝑥𝑖𝑗𝑑 𝑑∈𝐷 + ∑ ∑ 𝑑𝑤𝑖𝑑 𝑑∈𝐷0𝑖∈𝑉 + ∑ 𝑒𝑡𝑑 𝑑∈𝐷0𝑗∈𝑉0 𝑖≠𝑗 𝑖∈𝑉0 (1) s.t. ∑ 𝑥0𝑗𝑑 ≤ 𝑏𝑎𝑑 + 𝑡𝑑 𝑗∈𝑉 ∀ 𝑑 ∈ 𝐷 (2) ∑ ∑  xijd ≥ 𝑓   d∈ D𝑖∈𝑉 𝑖≠𝑗 ∀𝑗 ∈ 𝑉 (3) ∑ 𝑥𝑖𝑗𝑑 𝑗∈V0 𝑖≠𝑗 = ∑ 𝑥𝑗𝑖𝑑 𝑗∈V0 𝑖≠𝑗 ∀𝑖 ∈ 𝑉0 , 𝑑 ∈ 𝐷 (4) 𝑢𝑖𝑑 − 𝑢𝑗𝑑 ≥ 𝑞𝑗𝑑 − 𝑄(1 − 𝑥𝑖𝑗𝑑 ) ∀𝑖, 𝑗 ∈ 𝑉 𝑖 ≠ 𝑗, 𝑑 ∈ 𝐷 (5) 𝑞𝑖0 = 𝑞𝑖 𝑠𝑒𝑛𝑠𝑜𝑟 ∀𝑖 ∈ 𝑉 (6) 𝑦𝑗𝑑 = ∑ 𝑥𝑖𝑗𝑑 𝑗∈𝑉 𝑖≠𝑗 ∀𝑗 ∈ 𝑉, 𝑑 ∈ 𝐷 (7) 𝑣𝑖𝑑 ≤ 𝑀(1 − 𝑦𝑖𝑑−1) ∀𝑖 ∈ 𝑉, 𝑑 ∈ 𝐷 0 (8) 𝑣𝑖𝑑 ≤ 𝑞𝑖𝑑−1 ∀𝑖 ∈ 𝑉, 𝑑 ∈ 𝐷 0 (9) 𝑣𝑖𝑑 ≥ 𝑞𝑖𝑑−1 − 𝑀𝑦𝑖𝑑−1 ∀𝑖 ∈ 𝑉, d ∈ 𝐷 0 (10) 𝑞𝑖𝑑 = 𝑣𝑖𝑑 + 𝑔𝑖 ∀𝑖 ∈ 𝑉, 𝑑 ∈ 𝐷 0 (11) 𝑤𝑖𝑑 ≥ 𝑞𝑖𝑑 − 𝑞𝑖 𝑚𝑎𝑥 ∀𝑖 ∈ 𝑉, 𝑑 ∈ 𝐷0 (12) 0 ≤ 𝑢𝑖𝑑 ≤ 𝑄 ∀𝑖 ∈ 𝑉, 𝑑 ∈ 𝐷 (13) 0 ≤ 𝑞𝑖𝑑 ∀𝑖 ∈ 𝑉, 𝑑 ∈ 𝐷 (14) 𝑥𝑖𝑗𝑑 ∈ {0,1} ∀ 𝑖, 𝑗 ∈ 𝑉0, 𝑖 ≠ 𝑗, 𝑑 ∈ 𝐷 (15) 𝑎𝑖𝑑 ∈ {0,1} ∀𝑖 ∈ 𝑉, 𝑑 ∈ 𝐷 (16) 0 ≤ 𝑤𝑖𝑑 ∀𝑖 ∈ 𝑉, 𝑑 ∈ 𝐷 0 (17) 0 ≤ 𝑣𝑖𝑑 ∀𝑖 ∈ 𝑉, 𝑑 ∈ 𝐷 0 (18) 𝑦𝑖𝑑 ∈ {0,1} ∀𝑖 ∈ 𝑉, 𝑑 ∈ 𝐷 0 (19) 𝑡𝑑 ∈ ℕ0 ∀ 𝑑 ∈ 𝐷 0 (20) The objective function (Eq.1) consists of three parts: the first one is cost for the total distance travelled while the second and third are penalty costs caused by exceeding the bin capacity and the necessity of driving extra routes, respectively. Alternatively, the penalty coefficients can be replaced by M in the case that breaking the capacities is strictly not allowed. The daily routes constraints (Eq.2) impose that there can be b routes per day without including another vehicle and crew. The ai parameter allows us to set the available routes to 0 on certain days, e.g. holidays. The minimum visits constraints (Eq.3) impose that each bin is emptied at least f times during the planning period. A positive f can be useful in a situation where a bin is not filling up but should still be emptied because of some other reason (e.g., smell). The combination of a short planning horizon and a positive f can lead to issues with infeasibility. The conservation of flow constraints (Eq.4) impose that a vehicle arriving at a vertex departs on the same day. The load constraints (Eq.5) eliminate sub-tours, as well as ensuring that the vehicle capacity is not exceeded. Constraints (Eq.6) set the bin levels for the first day. Constraints (Eq.7) state that if a bin is serviced one day, it needs to be visited by a vehicle the same day. This is used in the bin level constraints, (Eq.8) to (Eq.11), to reset the bin level if the bin has been emptied on the previous day. The overflow constraints (Eq.12) ensure that any overflow is accounted for, so that it can be included in the objective function. Finally, constraints in Eqs. (13) to (20) are bounds for the variables and so state domains for the variables. 3. Computations and simulations In this section, the developed model given by Eqs. (1) - (20) is tested on an artificial data set. 1252 3.1 Testing data description A seven-day planning horizon was considered for a network involving ten customer nodes (|V|=10) and one depot. One vehicle with a capacity 𝑄 = 10 t has to serve the bins that have capacity 𝑞𝑖 = 5 t. Initial level of waste in the bins is given by Table 2. Table 2: Initial level of waste in bins 1-10 Bin 𝑖 1 2 3 4 5 6 7 8 9 10 Level 𝑞𝑖0 [t] 5 5 4 4 3 3 2 2 1 1 Moreover, all of the bins have expected daily growth of waste 𝐸[𝑔𝑖 ] = 1 t ∀𝑖 ∈ 𝑉 (or expected production) while the simulated growth for each node is computed as max (0, 𝑛𝑜𝑟𝑚(1,0.3)). Note that 𝑀 was set to 𝑀 = 1,000, a default value for 𝑎 was set 𝑎𝑑 = 1 ∀𝑑 ∈ 𝐷, then 𝑏 = 2, 𝑓 = 1, 𝑑 = 50, 𝑒 = 300. Nodes are randomly (uniformly) between 0 and 1,000 m for both axes, and distances are Euclidean. 3.2 Simulation results The model was implemented in AMPL optimization program (Fourer et al., 2003) using solver CPLEX and was solved for a specified optimality gap that was set to 1 %. The program is run on the server of Molde University College. The server has up to 20 virtual cores clocked at 2.4 GHz and up to 60 GB of memory. The actual power depends on server activity and will naturally vary. However, even for such small data instance, it takes 1-5 h of computational time for each iteration. Figure 2 provides visual results regarding the level of waste in the bins: static approach – Figure 2a (model solved once at the first day for the whole period) and dynamic approach – Figure 2b (solving the model at each day of the seven-day planning period). a) Static approach – solved once b) Dynamic approach – solved daily Figure 2: Results of the simulation for bins 8, 9 and 10 and their fill-level in percentages for days 0-6 Irrespective of time of collection (during 8hr shift), waste generation is considered after routes finished for simplicity. Thus, the plot never gets below 20 % - some extra waste is always generated. In figures 2a and 2b, just bins 8, 9, and 10 are plotted due to illustrative reasons. During the week, there are 6 bins which overflow in the static approach, while only 3 in the dynamic approach with the worst one overflowing by about 5 %. The dashed line in Figure 2a shows the expected amount of waste in the bin. The servicing of bin 8 in four consecutive days is caused by rolling time horizon. It is also close to many containers and so the route including this container would not be any longer – the added cost of bin 8 is not so big. Bin 10 was originally scheduled for day 2, but in dynamic case, the service was moved to day 3. The dynamic case tries to prevent the overflow while it considers the moving time horizon of 7 days counting from the current day. The dynamic approach scheduled service 27 times while static 15 times and 7 bins overfilled or almost full at day 6 (model does not consider what happens on day which is outside the time horizon). 4. Conclusions and further research This paper has introduced a mathematical model on a recently very important topic – smart waste collection. A novel simulation approach was deduced and presented. It is mentioned that the presented approach has a potential to bring a new point of view to the modern smart waste collection systems utilizing recently available smart waste management technologies (in our case, bins equipped with sensors and wireless technology). A 1253 problem involving a single type of waste and a single vehicle was considered and applied in artificial testing network data. This simple model is studied in order to develop an effective model and solution approach for real large-scale networks (involving multiple types of waste, fleet of vehicles, etc.). Finally, results of the presented simulations are provided. The computations have shown applicability of the proposed approach in real large- scale waste collection problems that will be a subject of authors’ further research. As a next step, the model will be extended in order to solve more realistic collection problems. In principle this means that the model will be extended on some of the following components that are collected in practice: multiple types of waste, (either homogeneous or heterogeneous) fleet of (either single or multi compartment) vehicles, multiple trips, multiple depots and intermediate facilities, daily working hours, multiple types or sizes of waste bins, a security level (e.g., collecting 80 % full bins), etc. Simultaneously, the proposed approach will be compared with other existing approaches to see if any (alternatively, what) savings can be achieved by a more advanced approach. The comparison of the various approaches may span problems such as solving the problem every day as a single routing problem for the urgent visits that day, creating a plan for the fulltime horizon assuming that the filling rate is fixed, and, eventually, including the uncertainty and updating the plan when new information is received. Last but not least, the approach to the uncertainty for filling the bins can be further examined and extended. However, the problem scope leads to high computational time requirements and so the suitable heuristic method has to be developed. Acknowledgments The authors gratefully acknowledge financial support provided by ERDF within the research project No. CZ.02.1.01/0.0/0.0/16_026/0008413 "Strategic Partnership for Environmental Technologies and Energy Production" and by the project “Computer Simulations for Effective Low-Emission Energy” funded as project No. CZ.02.1.01/0.0/0.0/16 026/0008392 by Operational Programme Research, Development and Education, Priority axis 1: Strengthening capacity for high-quality research. References Barbosa-Póvoa A.P., da Silva C., Carvalho A., 2018. Opportunities and challenges in sustainable supply chain: An operations research perspective. European Journal of Operational Research, 268 (2), 399–431. Bing X., Bloemhof J.M., Ramos T.R.P., Barbosa-Póvoa A.P., Wong C.Y., van der Vorst J.G.A.J., 2016. Research challenges in municipal solid waste logistics management. Waste Management, 48, 584–592. Bong C.P.C., Lim L.Y., Lee C.T., Fan Y.V., Klemeš J.J. 2018. The role of smart waste management in smart agriculture. Chemical Engineering Transactions, 70, 661–666. Esmaeilian B., Wang B., Lewis K., Duarte F., Ratti C., Behdad S. 2018. The future of waste management in smart and sustainable cities: A review and concept paper. Waste Management, 81, 177–195. Expósito A., Velasco F., 2018. Municipal solid-waste recycling market and the European 2020 Horizon Strategy: A regional efficiency analysis in Spain. Journal of Cleaner Production, 172, 938–948. Faccio M., Presona A., Zanin G. 2011. Waste collection multi objective model with real time traceability data. Waste Management, 31, 2391-2405. Fadda E., Gobbato L., Perboli G., Rosano M., Tadei R. 2018. Waste collection in urban areas: A case study. Interfaces, 48 (4), 307-322. Farrokhi-Asl H., Makui A., Jabbarzadeh A., Barzinpour F. 2018. Solving a multi‑objective sustainable waste collection problem considering a new collection network. Operational Research, DOI: 10.1007/s12351-018- 0415-0. Fourer R., Gay D.M., Kernighan B.W., 2003. AMPL: a modelling language for mathematical programming, 2nd edn., Thomson, Stamford, United States. Gregor J., Kropáč J., Pavlas M. 2018. Sorting line modelling as an integral part of complex tools for decision- making in waste management. Chemical Engineering Transactions, 70, 1561–1566. Jiao X., Ning T., 2018. A dynamic logistics strategy for dangerous goods based on cloud computing. Chemical Engineering Transactions, 67, 685-690. Johansson O.M., 2006. The effect of dynamic scheduling and routing in a solid waste management system. Waste Management, 26, 875-885. Liu H., Li W., Han W., 2018. Development and application of real-time monitoring system for dangerous chemicals transport vehicles based on internet +. Chemical Engineering Transactions, 71, 535-540. Ramos T.R.P., de Morais C.S., Barbosa-Póvoa A.P. 2018. The smart waste collection routing problem: Alternative operational management approaches. Expert Systems with Applications, 103, 146–158. Xue Y., Wen Z., Bressers H., Ai N. 2019. Can intelligent collection integrate informal sector for urban resource recycling in China? Journal of Cleaner Production, 208, 307-315. 1254