| Article ID: | iaor1989403 |
| Country: | United Kingdom |
| Volume: | 16 |
| Start Page Number: | 589 |
| End Page Number: | 600 |
| Publication Date: | Oct 1989 |
| Journal: | Computers and Operations Research |
| Authors: | Pearn Wen Lea |
| Keywords: | heuristics, vehicle routing & scheduling |
The capacitated arc routing problem (CARP), is a capacitated variation of the arc routing problems in which there is a capacity constraint associated with each vehicle. Due to the computational complexity of the problem, recent research has focussed on developing and testing heuristic algorithms which solve the CARP approximately. This paper reviews some of the existing solution procedures, analyses their complexity, and presents two modifications of the existing methods to obtain near-optimal solutions for the CARP. Extensive computational results are presented and analyzed.