|M.Sc Student||Simhon Eran|
|Subject||Traveling Salesman Problem in Dynamic Environment|
|Department||Department of Industrial Engineering and Management||Supervisors||PROF. Liron Yedidsion|
|DR. Shraga Shoval|
|Full Thesis text|
The Travelling Salesman Problem (TSP) is a classical problem in operations research, in which the task is to find an optimal route that visits a given set of locations (targets). Over the years many dynamic versions of the problem has been studied. In those versions, the target may appear; disappear; or change their cost of visit over time.
In the last 20 years there has been a growing interest in Moving Target Traveling
Salesman Problem (MT-TSP) which is a dynamic version of TSP in which, the targets can move at fixed velocities rather than be stationary (as assumed in the standard problem).
In this research we study several variants of MT-TSP. First we study special cases of the model in which all the targets are confined to a single line and have the same speed. We analyze two optimization problems of minimizing the completion time (makespan). In the first problem, each target has its own release time while in the second, each target as a deadline. For both problems we suggest optimal polynomial time algorithms based on dynamic programming methods with complexity of O(n4logn) and O(n4) respectively.
Next we study an online version of the problem, where data on each target is revealed only upon arrival. First we find a lower bound of the competitive ratio of the problem and then we suggest two online greedy algorithms which outperform each-other in different speed ranges.
Finally, we study the Resupply MT-TSP. In this version of the problem, the agent must visit the origin after each interception. We first prove, by a reduction to a 3-partition problem that the online version of the problem is strongly NP-hard even if all targets are confined to a single line. Then we show the equivalence of some special cases of the problem, in which all targets are moving directly away or toward the origin (without reaching it) to scheduling problems with deteriorating jobs. And finally, we prove that the competitive ratio of the online version is unbounded even if all targets are confined to a single line and moving at the same speed and direction.