THE CHASING REPAIRMAN

In the well-known Traveling Repairman Problem (TRP), we seek a tour that visits a set of customers, such that it minimizes the sum of latencies seen by the customers. The problem is also known as the Minimum Latency Problem (MLP) and is considered as a particular case of the Time-Dependent TSP (TDTSP). However, despite its similarities to the TSP, the TRP is different from the TSP in two aspects: firstly, its objective is oriented to benefit the customer by reducing their loss/damages, contrary the classical TSP which is oriented to benefit the agent. Secondly, the TRP found to be sensitive for local changes, thus even the smallest modification of the initial conditions might lead to a highly non-local effect. Hence, in the computational point of view, the TRP seems to be less “well-behaved” and more resilient to progress. For an instance, even with current state-of-the-art exact methods, solving consistently instances with 150 customers is most challenging, contrary to the TSP, where instances with thousands of customers are solved routinely.

Recently, a new generalization of the TRP was considered in the literature, where each customer is on motion during the repairman`s tour while the repairman must chase down each customer for serving them, hence we regard this variant as the Chasing Repairman Problem (CRP). As its former is already found sensitive to even a small local modification, the CRP seems to be much harder to solve, as its input points inherently, vary over time. From that, each possible tour will probably hold its own distance-matrix, thus it is not realistic to assume that in real-life applications, a distance-matrix for each possible tour is pre-computed.

As the CRP objective is to reduce the customers` loss/damages due to latency, many of its real-life applications arise from distribution systems or coping with life-threatening scenarios such as in spreading wildfire, treating wounded population during evacuation or even spreading attacks from multiple drones.

Our research interest is to develop a simple and effective heuristic algorithm. To the best of our knowledge, such an algorithm has not been presented yet. In this work, we would like to present some insights about the CRP properties, such as possible basic strategies in different scenarios. Furthermore, we would like to present our initial approach for developing such an algorithm. We believe that it is possible to find relations between the travel-functions of the customers and the repairman, such that we are able to determine dynamically the probable best next customer to chase and later, a dynamic and simple way to define temporal neighborhoods for large scales instances.