Decision Making and Analysis for Unexpected Road Blockages

Bing Su, Yinfeng XuJournal of the Association for Information Systems 2004

Abstract

The unexpected road blockage problem (URBP) 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 with a complexity of $O(n^2)$ (where $n$ is the number of nodes). Two online strategies, the Waiting strategy and the Greedy strategy, are proposed and their competitive ratios are analyzed. Furthermore, we compare the two strategies based on competitive ratio analysis.

Introduction

Navigating a route where unexpected road closures—due to accidents or construction—are only discovered upon arrival is a common real-world challenge. This scenario defines the Unexpected Road Blockage Problem (URBP). This paper specifically investigates the recoverable version of URBP, where roads eventually reopen after a certain recovery time. The central dilemma for a traveler is whether to wait for the road to clear or to seek an immediate detour. While intuition often favors rerouting (the "Greedy Strategy"), this research demonstrates that simply staying put (the "Waiting Strategy") is often mathematically superior in worst-case scenarios.

Methodology

The study approaches URBP through two primary lenses:

  1. Offline Optimal Solution: The authors develop a modified version of Dijkstra’s algorithm to find the optimal path when all blockage and recovery times are known in advance. This algorithm operates with a complexity of $O(n^2)$, providing a baseline for evaluating online strategies.
  2. Competitive Ratio Analysis: To evaluate online performance, the "competitive ratio" is used—the ratio of the online strategy's travel time to the optimal offline travel time. Two strategies are analyzed:
  3. Waiting Strategy (WS): The traveler waits at a blockage until the road reopens.
  4. Greedy Strategy (GS): Upon encountering a blockage, the traveler chooses the path with the minimum expected time to the destination, considering both waiting and detouring.

Key Results and Insights

The core finding is the mathematical advantage of the Waiting Strategy over the Greedy Strategy. The performance of the Waiting Strategy is primarily dictated by the ratio of recovery time to travel time ($\alpha$) and remains stable regardless of the number of blockages encountered.

In contrast, the Greedy Strategy can fall into a "trap." Because it considers immediate detours, a traveler might be led into a sequence of new paths that are each subsequently blocked. This results in a competitive ratio that grows exponentially with the number of blockages ($k$).

Comparison of competitive ratios for Waiting and Greedy strategies under various recovery time assumptions.

As shown in the table above, the competitive ratio for the Waiting Strategy typically scales linearly or remains constant with respect to the number of blockages $k$, whereas the Greedy Strategy's ratio scales as $2^k$ or $(1+\alpha)^k$. This highlights the "stability" of the Waiting Strategy in unpredictable environments.

Discussion and Limitations

While the Waiting Strategy is mathematically more robust in the worst case, the authors acknowledge several practical considerations:

  • Human Psychology: Travelers generally prefer movement over standing still, even if it is less efficient.
  • Information Availability: The model assumes recovery times are known upon reaching a blockage, which is rarely the case in reality.
  • Model Scope: The current analysis focuses on edge blockages (roads). Future research is needed to address vertex blockages (intersections or cities).

The research underscores that in highly uncertain networks with multiple potential blockages, the simplest strategy—patience—can often be the most effective hedge against catastrophic delays.

Summary updated

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.
BibTeX
@article{su2004decision,
  author = {Bing Su and Yinfeng Xu},
  title = {{Decision Making and Analysis for Unexpected Road Blockages}},
  journal = {Journal of the Association for Information Systems},
  year = {2004},
}
Figure