Information Relaxation Bounds for Dynamic Decisions on Time-Space Networks

The dynamic management of large-scale service networks has motivated the development of a number of algorithms that re-configure or repair such networks at the operational, tactical and near real-time scales. These algorithms re-allocate resources across the networks as information about demands, service times or disruptions is revealed over time. Performance evaluation frameworks for these algorithms, on the other hand, are nearly always based on offline or omniscient bounds for these systems. In this paper, we present a novel methodology to construct tighter performance bounds for dynamic resource allocation problems modeled on time-space networks. Specifically our approach expands upon the theory of penalized information-relaxation bounds developed by Brown et al. (2010), which generalizes the work of Rogers (2002), Andersen and Broadie (2004) and Haugh and Kogan (2004); to the setting of large-scale network-based resource allocation, by avoiding the need to compute penalty functions for each possible state of the system. We apply our approach to a large-scale airline disruption management problem and demonstrate that our new bounding approach improves upon existing omniscient bounds and allows for better evaluation of other dynamic resource allocation algorithms