Multi-Period Routing Problem in Satellite Networks

Speaker: Dr. Raghu Raghavan, Univeristy of Maryland, College Park
Abstract: We introduce a traffic routing problem over an extended planning horizon that appears in geosynchronous satellite networks. Unlike terrestrial (e.g., fiber optic) networks, routing on a satellite network is not transparent to the customers. As a result, a route change is associated with significant monetary penalties that are usually in the form of discounts (up to 40%) offered by the satellite provider to the customer that is affected. The notion of these re-routing penalties requires the network planners to look at routing decisions over multiple time periods and introduces novel challenges that have not been considered previously in the literature. We develop a branch-and-price-and-cut procedure to solve this problem and describe an algorithm for the associated pricing problem. Our computational work demonstrates that the use of a multi-period optimization procedure as opposed to a myopic period-by-period approach can result in cost reductions between 7% and 11% under nominal problem parameters and can reach more than 24% when the rerouting penalty is higher. These cost reductions correspond to potential savings of several hundred million dollars for large satellite providers. (joint work with Ioannis Gamvros, University of Maryland)
Biography: S. "Raghu" Raghavan is Associate Professor of Management Science at the Robert H. Smith School of Business, University of Maryland, and an Affiliate Faculty member at the Institute for Systems Research. He joined the Smith School in 1998 after several years in the telecommunications industry. He has published on a wide variety of topics (including telecommunications, electronic markets, and data mining) and numerous academic outlets such as Management Science, Operations Research, Decision Support Systems, and the INFORMS Journal on Computing. He holds two patents, and has won numerous awards for his work. These include (i) the Dantzig award for the best doctoral dissertation, (ii) the INFORMS Computing Society Prize for innovative contributions to the field of data mining, (iii) 2nd Prize in the INFORMS Junior Faculty Paper Competition, and (iv) Finalist for the Wagner Prize for Excellence in Operations Research Practice. He has edited three books titled Telecommunications Network Design and Management (Kluwer Academic Press 2003), Telecommunications Planning: Innovations in Pricing, Network Design, and Management (Springer 2006), and The Next Wave in Computing, Optimization, and Decision Technologies (Springer 2005). Dr. Raghavan obtained his Ph.D. in Operations Research from the EECS Dept at the Massachusetts Institute of Technology.
Presentation On: Friday,7 April, 2006,
11:00 a.m. in room 1115, CSIC
Video: QuickTime streaming video