A hierarchical integrated exact algorithm for multi-level capacitated arc routing problem in waste collection

This paper explores a practical waste collection system where manually operated vehicles and compressor-equipped vehicles interact at waste collection huts. A multi-level capacitated arc routing problem is studied within this context to integrate the optimisation of travel costs for both types of vehicles. To address this issue, a flow-based mixed-integer linear programming model is established. Then, we develop a hierarchical integrated exact algorithm that leverages the structure of logic-based Benders decomposition. The problem is decomposed into a master problem, which determines the trips for manually operated vehicles, an assignment problem that constructs the multi-trip routes, and a subproblem that determines the routes for compressor-equipped vehicles. Logic-based feasibility cuts and optimality cuts are generated from the assignment problem and the subproblem, respectively, to restrict the master problem. To tackle complex subproblems, we design an elaborate branch-and-price algorithm. Additionally, several dedicated acceleration strategies are implemented to further enhance the algorithm. The experimental results are conducted on 225 instances derived from two types of well-known benchmarks. The proposed algorithm efficiently solves this problem and significantly outperforms the commercial optimisation software. The results also demonstrate that the acceleration strategies notably reduce computation time.