Mourão, M. CândidaAlmeida, M. Teresa2023-06-052023-06-052000Mourão, M. Cândida and M. Teresa Almeida. (2000). “Lower-bounding and heuristic methods for a refuse collection vehicle routing problem”. European Journal of Operational Research. Vol. 121, No. 2: pp. 420-434. (Search PDF in 2023).0377-2217http://hdl.handle.net/10400.5/27884A set of routes that minimizes the total collecting cost of the household refuse in a quarter of Lisbon may be obtained solving a Capacitated Arc Routing Problem (CARP) with side constraints. The CARP is known to be an NP-hard problem. We present two lower-bounding methods, both based on the transportation model, in which we have been able to incorporate some of the side constraints. We also present a three-phase heuristic to generate a near-optimal solution from the solution obtained with the first lower-bounding method. For the relative gap between the heuristic solution value and its associated lower bound value we give a theoretical worst-case bound and computational experience obtained with a set of test problems.engRoutingLower BoundsHeuristicsjournal article