An exact branch-price-and-cut algorithm for integrated waste collection system: Elementary shortest path and hop constraint Steiner Tree Problems

This is the authors' abstract. We don't add key points for this paper.

This paper presents an exact solution approach to a waste collection problem, which combines traditional truck-based collection with an automated pneumatic pipe network. The problem jointly determines (i) whether each collection point is assigned to truck service or to the automated system, and (ii) the corresponding truck routes and a cost-minimizing pneumatic tree. The truck component is modeled as a Capacitated Vehicle Routing Problem, while the pneumatic tree is represented by a variant of the Steiner Tree Problem. Our main contribution is the development and comparison of two decomposition strategies within a branch-price-and-cut framework. In the full decomposition, routing and tree generation are handled independently in two pricing problems. On the contrary, in the partial decomposition, the tree structure is modeled directly in the master problem, and column generation is applied only to the routing part. For the tree-part, we adapt two state-of-the-art formulations, resulting in four distinct branch-price-and-cut algorithms. Computational experiments on benchmark data sets with up to 80 nodes reveal apparent performance differences between the decomposition strategies depending on instance characteristics, demonstrating the substantial impact of modeling choices on solvability, scalability, and overall computational efficiency.