Minimax models for diverse routing

Minimax models for diverse routing

0.00 Avg rating0 Votes
Article ID: iaor20032587
Country: United States
Volume: 14
Issue: 1
Start Page Number: 81
End Page Number: 95
Publication Date: Jan 2002
Journal: INFORMS Journal On Computing
Authors: ,
Keywords: programming: linear, programming: network, programming: multiple criteria
Abstract:

An important task in the management and administration of communication networks is constructing routes for messages to follow from source to destination. A common approach is to route along the shortest available path connecting the source to the destination, where link lengths can be defined in a variety of ways (e.g., time, cost, impact on average queueing delay, or capacity required). This paper presents a family of novel minimax models for determining a set of paths from the source to the destination that are reasonably short in length while also reasonably diverse (disjoint). The overall goal is to design a routing scheme that is both efficient and robust, resulting in greater network reliability. Several models are investigated and a column-generation approach is proposed for exact solution. Computational results show that this exact technique can be applied effectively to moderate sized networks. For even larger networks, heuristic methods are developed and tested.

Reviews

Required fields are marked *. Your email address will not be published.