Article ID: | iaor201112935 |
Volume: | 18 |
Issue: | 3 |
Start Page Number: | 401 |
End Page Number: | 423 |
Publication Date: | May 2011 |
Journal: | International Transactions in Operational Research |
Authors: | Buriol Luciana S, Resende Mauricio G C, Ritt Marcus, Reis Roger |
Keywords: | heuristics: genetic algorithms, programming: dynamic, combinatorial optimization |
Interior gateway routing protocols like Open Shortest Path First (OSPF) and Distributed Exponentially Weighted Flow Splitting (DEFT) send flow through forward links toward the destination node. OSPF routes only on shortest-weight paths, whereas DEFT sends flow on all forward links, but with an exponential penalty on longer paths. Finding suitable weights for these protocols is known as the weight setting problem (WSP). In this paper, we present a biased random-key genetic algorithm for WSP using both protocols. The algorithm uses dynamic flow and dynamic shortest path computations. We report computational experiments that show that DEFT achieves less network congestion when compared with OSPF, while, however, yielding larger delays.