טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentSimhon Eran
SubjectTraveling Salesman Problem in Dynamic Environment
DepartmentDepartment of Industrial Engineering and Management
Supervisors Dr. Liron Yedidsion
Dr. Shraga Shoval
Full Thesis textFull thesis text - English Version


Abstract

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.