Article ID: | iaor20072325 |
Country: | United Kingdom |
Volume: | 33 |
Issue: | 12 |
Start Page Number: | 3363 |
End Page Number: | 3383 |
Publication Date: | Dec 2006 |
Journal: | Computers and Operations Research |
Authors: | Prins Christian, Benavent Enrique, Lacomme Philippe, Belenguer Jos-Manuel |
Keywords: | heuristics, networks: flow |
This paper presents a linear formulation, valid inequalities, and a lower bounding procedure for the mixed capacitated arc routing problem. Moreover, three constructive heuristics and a memetic algorithm are described. Lower and upper bounds have been compared on two sets of randomly generated instances. Computational results show that the average gaps between lower and upper bounds are 0.51% and 0.33%, respectively.