M.Sc Student | Yaarit Cohen |
---|---|

Subject | The Traveling Repairman Problem on a Single Line with Release Times |

Department | Department of Industrial Engineering and Management |

Supervisor | Dr. Yedidsion Liron |

Full Thesis text |

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 time. Where the flow time of
target *i* (*F _{i}*) is the time since the target appears
till it is intercepted. Note that the TRP is different from the well-known
Traveling Salesman Problem (TSP). Unlike the TRP in which the objective is to
minimize the sum of the targets' flow time, in the TSP the objective is to
minimize the maximal completion time, where the completion time of target

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

We prove this problem to be *NP*-hard
by using a reduction of a special case of the partition problem. Next, we
suggest several heuristics for solving the SL-TRP. In addition we suggest an
exact Branch and Bound (*B&B*) algorithm.

We conduct an experimental study
in order to evaluate and compare the heuristics performances as well as the
efficiency of the *B&B* algorithm when using large instances. We show
empirically that for small number of targets, one of the heuristics outperforms
the other ones and matched the optimal solution in the majority of the
instances. For larger number of targets, where the optimal solution could not
be found in reasonable time, the heuristics were compared to one-another and
the same heuristic produced the lowest value in most of the cases.