טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentYaarit Cohen
SubjectThe Traveling Repairman Problem on a Single Line with
Release Times
DepartmentDepartment of Industrial Engineering and Management
Supervisor Dr. Yedidsion Liron
Full Thesis textFull thesis text - English Version


Abstract

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 (Fi) 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 i (Ci) is 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).

    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.