| Article ID: | iaor20042814 |
| Country: | Netherlands |
| Volume: | 9 |
| Issue: | 5 |
| Start Page Number: | 429 |
| End Page Number: | 445 |
| Publication Date: | Nov 2003 |
| Journal: | Journal of Heuristics |
| Authors: | Minoux Michel, Gabrel Virginie, Knippel Arnaud |
In this paper, approximate solutions algorithms for discrete cost multicommodity network optimization problems are presented and compared. Firstly, extensions of classical greedy heuristics, based on link-rerouting and flow-rerouting heuristics, are presented in detail. Secondly, a new approximate solution algorithm, which basically consists of a heuristic implementation of the exact Benders-type cutting plane generation method, is proposed. All these algorithms are extensively compared on randomly generated graphs up to 50 nodes and 90 links. It clearly appears that this new Benders-type approach is very promising since it produces the best heuristic solutions.