The Traveling Repairman Problem on a Single Line with Release Times

The Traveling Repairman Problem (TRP) is a well-known NP-hard problem (also referred to in the literature as The Delivery Man Problem and The Minimum Latency Problem). In the classical TRP, a repairman has to visit each of n stationary targets exactly once, in order to minimize the sum of the targets flow times. Where the flow time of target is the time since the target appears till the time it is intercepted.

In this research we consider a special case of TRP where all targets are confined to a single line. However, some targets might not be available at time zero and appear later on. We denote this problem as the Single Line TRP (SL-TRP).

Algorithms for SL-TRP have real-life applications that can help civil and military needs. Consider a line of machines each one requires a delivery of raw material delivered by a robotic arm moving along a production line; or a border patrol unit that has to reach numerous check points along the border based on alerts of invasion. Note that the border does not have to be strait to be considered a "strait line" as long as the patrol unit travels alongside the border line. In both of these problems the robot or the border patrol unit has to visit each point exactly once and should complete its tour and minimize the sum of the targets flow times.

While it was indicated over two decades ago that the complexity of SL-TRP was unresolved, as far as we know, this problem has not been proven NP-hard as of yet. We use a reduction from a special case of the partition problem to prove that this problem is indeed NP-hard.