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:
- 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.
- 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.
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