Time-dependent traveling salesman problems: a case study in waste management

The rapid rise of the population, together with the rising concentration of people in cities and the growing volume of daily trash, are all factors that are pushing to its limit the ability of Nature to absorb waste. Traditionally, solid trash collection was done without first studying demand or vehicle routes, and route selections were decided by the drivers, despite the fact that the solutions were far from ideal. However, with the advent of the Internet of Things and smart waste management ideas, the concept of static waste collection resource optimization and more specifically vehicle routing problem are being exposed to a fortunate mutation. Hence, the aim of this work is to help municipalities better schedule their garbage pickup. The goal of algorithm is to reduce the cost of garbage collection by minimizing the distance traveled by a vehicle to collect rubbish from a container and therefore saving fuel consumption. In particular, we propose a solution that solves two fundamental difficulties that a garbage collection service faces: determining which containers should be collected and visiting them in the most cost-effective sequence. The first goal is reached by exploiting machine learning techniques and time series analysis. As a result, the decision is taken according to a given criterion based on the predictions and estimated bin filling levels. The second purpose is obtained by formulating the Time Dependent Traveling Salesman Problem. Indeed, waste collection is also one of the numerous real-life applications of the vehicle routing problem (VRP), that can be considered as a generalization of the Traveling Salesman Problem. Specifically, we address a Time Dependent TSP, since the travel times in cities are typically time-dependent; e.g., when a vehicle starts during morning or evening peak hours, its travel time is generally longer than when it starts in non-peak hours. The original contribution of our approach is the estimation of the TDTSP cost matrix. Indeed, given the stochastic nature of the environment, the matrix is experimentally determined based on previous data and driving patterns. In particular, in this work, we show the features of our predictive system, illustrating its operation with a real case study in the city of Turin.