Multi-depot periodic capacitated arc routing problem with intermediate facilities for waste collection

This study addresses the Multi-Depot Periodic Capacitated Arc Routing Problem with Intermediate Facilities (MDPCARPIF), considering a fleet of homogenous vehicles. A novel optimization model is proposed to formulate the problem, minimizing the total cost of vehicle deployment and travelled distances. Due to the NP-hard nature of the problem, Adaptive Large Neighbourhood Search (ALNS) and Parallel Adaptive Large Neighbourhood Search (PALNS) are utilized to tackle large-sized instances. However, CPLEX solver/GAMS software is used to treat small-sized instances. The results demonstrate that in 7 out of 10 small-sized instances where the CPLEX solver obtains the optimal solution, both the ALNS and PALNS reach the optimal solution. In the remaining three instances, the proposed algorithms achieve average gaps of 0.83% and 0.53% relative to the optimal solutions, respectively. Furthermore, for 25 large-sized instances, the proposed algorithms attain average relative gaps of 1.75% and 0.05%, respectively, when compared to the best solution found across all algorithm runs. Considering the solution quality and computational time, the proposed PALNS algorithm reveals its acceptable applicability for real-world waste collection planning by municipal authorities.