Decision Making and Analysis for Unexpected Road Blockages

Authors

Bing Su, School of Management, Xi’an Jiaotong University, Xi’an 710049, ChinaFollow
Yinfeng Xu, School of Management, Xi’an Jiaotong University, Xi’an 710049, China and The State Key Lab for Manufacturing Systems Engineering, Xi’an 710049, ChinaFollow

Document Type

Article

Abstract

The unexpected road blockage problem (URBP for short) is considered for the case when some blockages occur on the road at certain times and such blockages would be revealed only upon reaching them. Papadimitriou and Yannakakis proved that devising a strategy that guarantees a given competitive ratio is PSPACE-complete if the number of edges that might be blocked is not fixed; Bar-noy and Schieber considered the deterministic and stochastic variations of the recoverable-URBP in the worst-case criterion. In this paper, we present an offline algorithm for the recoverable-URBP optimal solution and the complexity of the algorithm is 2 O n( )( n is the number of nodes). Two online strategies, waiting strategy and the Greedy strategy, are proposed and the competitive ratios of the two strategies are given. Furthermore, we compare the two strategies based on competitive ratio analysis.

Recommended Citation

Su, Bing and Xu, Yinfeng, "Decision Making and Analysis for Unexpected Road Blockages" (2004). ICEB 2004 Proceedings (Beijing, China). 207.
https://aisel.aisnet.org/iceb2004/207