Article ID: | iaor19941072 |
Country: | Japan |
Volume: | 35 |
Issue: | 2 |
Start Page Number: | 119 |
End Page Number: | 133 |
Publication Date: | Jun 1992 |
Journal: | Journal of the Operations Research Society of Japan |
Authors: | Hirabayashi Ryuichi, Saruwatari Yasufumi, Nishida Naonori |
Keywords: | optimization, programming: integer |
It is well-known that the tight lower bounds determine the effectiveness of the branch and bound method for the NP-hard problems. This paper presents a new lower bounding procedure for the capacitated arc routing problem, 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.