M.Sc Student | Simhon Eran |
---|---|

Subject | Traveling Salesman Problem in Dynamic Environment |

Department | Department of Industrial Engineering and Management |

Supervisors | Dr. 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(n ^{4}*log

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.