It is well-known that the tight lower bounds determine the effectiveness of the branch and bound method for the NP-hard problems. In this paper, we present a new lower bounding procedure for the capacitated arc routing problem (CARP), one of the arc routing problems. They give the tight lower bounds and it is easy to develop an exact algorithm using their network structures.
No takes yet. Share an insight, caveat, or question.
Saruwatari et al. (1992) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: