cs.DSNov 16, 2026
SaveBeyond 4: Improved Competitive Traveling Repairperson
Organizations: Kent State University
Abstract
With 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 for every . 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.
Figures & tables
| Variable | Description |
| A TRP request with release time , location , and weight | |
| Depot, located at | |
| Distance between locations and | |
| Earliest possible service time of request | |
| Initial time scale: | |
| Phases , , and horizons |
Table 1: Important variables used in Sections 2 and 3 and their descriptions
Figure 1: An illustration of three possible outcomes of executing the capped route at phase- horizon : ( a ) An emergency cut stops executing at elapsed time ( b ) A scheduled cut stops executing at elapsed time (i.e., absolute time ). ( c ) No cut executes fully until elapsed time . Solid blue, dashed orange, and dotted black segments, respectively, denote the route execution, return to the depot, and waiting at the depot. marks the arrival of the server at the depot. Return durations are for each of the three cases with their respective value. Phase- horizon is the absolute time after either emergency or scheduled cut, and is after no cut. An emergency cut can happen only in the time interval , the scheduled cut can only happen at time . Additionally, in phase , there will be at most a single cut (emergency or scheduled). If no cut, then executes fully until absolute time (the elapsed time ).
More in this topic
Vehicle Routing
Vehicle routing studies how to assign and sequence trips for fleets while meeting capacity, time, energy, and service constraints.
See all 146 papers