Minimax Models for Diverse Routing

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 ef.cient 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.