Beyond 4: Improved Competitive Traveling Repairperson

Bibek Maharjan, Gokarna SharmaarXiv 2026 · arXiv

TL;DR

This paper breaks the long-standing "barrier of 4" for the online Traveling Repairperson Problem (TRP), introducing a deterministic algorithm with a competitive ratio of 3.877. By making the standard "capped-route" framework interruptible, the authors allow servers to adaptively abort current routes in favor of newly arrived high-priority requests, nearly reaching the theoretical lower bound for specific problem variants.

What Problem Does This Paper Address?

The online Traveling Repairperson Problem (TRP) is a classic challenge in routing and scheduling. Imagine a repairperson at a depot who receives service requests at various locations over time. Each request has a release time, a location, and a weight (priority). The goal is to visit every location to minimize the total weighted completion time.

Unlike the more famous Traveling Salesperson Problem (TSP), which focuses on the maximum time taken (the "makespan"), TRP prioritizes average responsiveness. This makes it highly relevant for real-world applications like emergency services, ride-hailing, or on-site technical support.

The central tension in online TRP is the "wait-or-go" dilemma: Should the server commit to a route for currently known requests, or wait for potentially more urgent requests that haven't arrived yet? For years, the best deterministic algorithm for this problem on arbitrary metric spaces had a competitive ratio of 4, meaning it could perform up to four times worse than an optimal offline algorithm that knows all future requests in advance.

Methods

The authors introduce the interruptible capped-route framework. This builds upon the existing "capped-route" approach, which operates in phases of geometrically increasing time horizons. In each phase, the algorithm computes an optimal route that minimizes weighted completion times while penalizing unserved requests.

The key innovation here is that the server is no longer "blindly" committed to its plan for the duration of a phase. Instead, the framework monitors incoming requests and employs two adaptive interruption mechanisms:

  1. Emergency Interruption: If a significant amount of new request weight arrives while the server is mid-route, the server immediately aborts its current path and returns to the depot to re-plan.
  2. Scheduled Interruption: At a specific "checkpoint" in the phase, the algorithm compares the weight of requests remaining in the current route's "tail" against the weight of requests revealed outside the route. If the outside weight is sufficiently high, the route is cut early.

The timing and thresholds for these cuts are governed by a parameter $\alpha \in (1/2, 1)$. By carefully tuning $\alpha$, the authors balance the cost of traveling back to the depot against the benefit of serving new requests sooner.

Figure 1: An illustration of three possible outcomes of executing the capped route Pj at phase-j horizon hj: (a) An emergency cut stops executing Pj at elapsed time u < αhj, α ∈(1/2, 1). (b) A scheduled cut stops executing P at elapsed time u = αhj (i.e., absolute time tc = (1+α)hj). (c) No cut executes Pj fully until elapsed time u = hj. Solid blue, dashed orange, and dotted black segments, respectively, denote the route execution, return to the depot, and waiting at the depot. R marks the arrival of the server at the depot. Return durations are ≤u for each of the three cases with their respective u value. Phase-(j + 1) horizon is the absolute time hj+1 = qhj = (1 + 2α)hj after either emergency or scheduled cut, and is hj+1 = 3hj after no cut. An emergency cut can happen only in the time interval (hj, (1 + α)hj), the scheduled cut can only happen at time (1 + α)hj. Additionally, in phase j, there will be at most a single cut (emergency or scheduled). If no cut, then Pj executes fully until absolute time 2hj (the elapsed time u = hj).

Datasets

Not discussed in the paper. As a theoretical work in competitive analysis, the results are proven mathematically for arbitrary metric spaces, meaning they hold true regardless of the specific underlying geometry (e.g., Euclidean planes, road networks, or simple lines).

Key Insights and Ideas

  • Adaptivity is Key: The "aha moment" was realizing that the previous state-of-the-art was limited by its inability to change course mid-phase. Introducing interruptions allows the algorithm to be more "responsive," which is exactly what the TRP objective function rewards.
  • The Power of Zero-Residual Instances: The authors identify a special class of "zero-residual" instances where the interruption rules are never triggered (or the loss from cutting a route is zero). For these well-behaved scenarios, the competitive ratio drops significantly to $3 + \epsilon$.
  • Unified Analysis for $k$ Servers: The framework naturally extends from a single server to $k$ servers ($k$-TRP) and even to the Dial-A-Ride Problem (DARP), where requests involve moving passengers from a source to a destination. The same 3.877 ratio holds for uncapacitated $k$-DARP.

Key Results

  • Improved Competitive Ratio: The main result is a 3.877-competitive deterministic algorithm for $k$-TRP on arbitrary metrics, improving upon the previous best of 4.
  • Optimal for Zero-Residual: For zero-residual instances, the ratio improves to $3 + \epsilon$. This is particularly notable for the capacitated 1-DARP variant, where it almost matches the known lower bound of 3.
  • Parameter Optimization: The authors show that the optimal value for their interruption parameter is $\alpha^* \approx 0.892$. Interestingly, setting $\alpha = 1$ (disabling interruptions) recovers the previous state-of-the-art ratio of 4.

Limitations and Future Work

  • Computational Complexity: Computing the "optimal capped route" in each phase is an NP-hard task. While the paper establishes a strong information-theoretic bound on performance, implementing this in real-time for large numbers of requests would require efficient approximation heuristics for the capped objective.
  • The Gap Remains: Even at 3.877, there is still a gap between this upper bound and the best-known lower bounds (e.g., $\approx 2.414$ for 1-TRP). The authors suggest that further improvements might require radically different non-phase-based approaches.
  • Randomization: This paper focuses on deterministic algorithms. Exploring randomized interruption policies—perhaps by randomizing the phase offsets—could potentially lead to even better expected competitive ratios.

Summary updated

Abstract

With $k\geq 1$ repairpersons starting initially from a depot, we present a 3.877-competitive deterministic algorithm for the fundamental online traveling repairperson problem on an arbitrary metric. For the special class of zero-residual instances, we improve the ratio to $3+ε$ for every $ε>0$. We also extend these results to some variants of the related so-called online dial-a-ride problem. The state-of-the-art is the 4-competitive deterministic algorithm for both problems.
BibTeX
@misc{maharjan2026beyond,
  author = {Bibek Maharjan and Gokarna Sharma},
  title = {{Beyond 4: Improved Competitive Traveling Repairperson}},
  year = {2026},
  eprint = {2611.21943},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.21943},
}
Figure