Models and Algorithms for Integer Multi-Commodity Network Routing Applications
Advisor: Dr. Jeffery L. Kennington
Ph. D. Defense
Tuesday, April 21, 2009 - 1:30 p.m.-3:00 p.m.
Huitt-Zollars Pavilion, Embrey Building
All interested persons invited and welcome
Abstract: This dissertation presents two applications of multi-commodity network routing problems, one in the area of telecommunication network operation and one in the area of cash management for the banking industry. For the telecommunication problem, the multiple commodities arise from the multiple origin-destination demand pairs that must share the capacity of a fiber optical link. For the cash management problem, the commodities are associated with the various denominations (ones, fives, tens, twenties, hundreds, and various coins) that share the capacity of armed trucks and storage vaults.
Dijkstra’s simple shortest path algorithm provided the building block for link-state routing protocols in data networks. The open shortest path first (OSPF) protocol uses this algorithm in a distributed procedure in an attempt to balance the trade-off between routing implementation complexity and optimal network utilization. Today, powerful optimization software tools are available that can be used by a central processor in an attempt to improve network performance via implementation of better routing strategies. Two environments can be considered. In the first case, the routing software remains unchanged and the central processor simply determines optimal link weights that are supplied to the routers. Each router uses the link weights and Dijkstra’s algorithm to determine its routing table. In the second environment, the routing software is modified to accept an optimal routing table. Chapter 2 of this dissertation presents both node-arc and arc-path optimization models for both environments, along with an empirical analysis of all four models.
Speaker Bio: Anusha Madhavan got her masters’ degree in computer information systems from Florida Institute of Technology, Melbourne, FL in 2000. Her research at SMU has been focused on developing mathematical models and heuristics algorithms for multi-commodity network routing applications. Anusha taught labs for EMIS courses (Introduction to Management Science, Operations Research etc..) at SMU. She is currently employed as an Operations Research and Analysis Specialist at MinMax Technologies, Dallas, TX.