| Article ID: | iaor19931967 |
| Country: | Singapore |
| Volume: | 9 |
| Issue: | 2 |
| Start Page Number: | 155 |
| End Page Number: | 175 |
| Publication Date: | Nov 1992 |
| Journal: | Asia-Pacific Journal of Operational Research |
| Authors: | Hirabayashi Ryuichi, Saruwatari Y., Nishida N. |
| Keywords: | graphs, networks, programming: travelling salesman |
In this paper, the authors consider an exact algorithm for the capacitated arc routing problem. Heuristic algorithms and lower bounding procedures have been developed, yet no exact algorithm has been developed due to the complexity of the problem. The present algorithm is based upon a branch and bound method and the authors use the node duplication lower bounding procedure to calculate lower bounds for subproblems. It also follows the tour construction method which is often seen in algorithms for the travelling salesman problems. Finally, the authors show the computational results for randomly generated networks.