The two-echelon multi-commodity capacitated arc routing problem

The shift from traditional waste treatment methods to recycling has introduced complexities in waste collection and transportation, as well as in the design of waste management networks. To maximize routing efficiency and minimize logistical costs, it is beneficial to introduce intermediate dumping sites with multi-waste stream skips between the collection area and distant treatment plants. To that end, we introduce the Two-Echelon Multi-Commodity Capacitated Arc Routing Problem. In the first-echelon, multi-compartment vehicles collect different waste streams and then unload their compartments into skips at one or more dumping sites. In the second-echelon, skips are transported by tractors to their respective treatment plants and brought back. The problem aims to minimize the transportation costs of first- and second-echelon, as well as the cost of locating skips at dumping sites. We present a mathematical formulation for the problem and a two-phase matheuristic. The first phase, the vehicle mix selection phase, selects a subset of cost-attractive vehicle assignments, which is given as input to the second phase. In the second phase, a novel two-echelon multi-commodity location-routing tour splitting algorithm is presented. The proposed solution is tested on 60 real-life instances from five Danish regions. Our comprehensive computational experiments and analyses demonstrate that the proposed matheuristic efficiently yields high-quality solutions. Finally, several managerial insights are provided regarding the number and location of dumping sites, skip usage with varying degrees of sorting, and the interaction between the routing costs of each echelon.