On Combining Conventional Point-To-Point and Automated Waste Collection Systems

The global demand for sustainable waste management has spurred initiatives to improve the efficiency of urban waste collection, discussing the advantages and disadvantages of different systems. We analyze a new combined waste collection problem that uses two systems simultaneously: a point-to-point system, in which waste is collected using trucks, and an automated system, where waste from inlets is transported through a network of pipes. The resulting combined waste collection problem is a two-stage decision problem: At the first stage, for each collection point, it must be decided whether it is served by truck or the pneumatic system. At the second stage, a Capacitated Vehicle Routing Problem (CVRP) must be solved for the collection points served by truck, and a cost-minimal tree must be determined for the collection points assigned to the pneumatic system. Both stages and the respective problems are interdependent, making the optimization of the whole system a difficult task. We develop a holistic solution approach based on a set-partitioning formulation utilizing route and tree variables. Because of the large number of variables, we solve the formulation heuristically using a column-generation-based matheuristic. The resulting subproblems are an elementary shortest-path problem with capacity constraints and a variant of the node-weighted Steiner tree problem. Our approach is empirically evaluated on two datasets, an extended variant of the well-known CVRP benchmark and real-world data from Vienna. The results indicate that the proposed matheuristic can provide high-quality solutions to realistic instances of the combined waste collection problem.