@phdthesis{Stieber2022, author = {Stieber, Anke}, title = {The multiple traveling salesperson problem with moving targets}, editor = {F{\"u}genschuh, Armin}, doi = {10.26127/BTUOpen-6110}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-61104}, school = {BTU Cottbus - Senftenberg}, year = {2022}, abstract = {Military installations and objects in out-of-area missions, e.g., an air base or a field camp, must be protected from incoming hostile rockets, artillery or mortar fire. Lasers as directed energy weapons are able to destroy those targets within seconds. Generally, the laser is assigned to a target, that applies the smallest movement of its direction unit to aim at it. The goal is to minimize the damage and thus, to destroy all incoming targets. We model the problem as a multiple traveling salesperson problem with moving targets, where the salespersons correspond to the lasers. The targets move over time on continuous trajectories. Additionally, each target is given a visibility time window. We investigate if exact methods are able to solve real-world instances in reasonable time. On that account, we address the problem from two sides, offline and online. One essential aspect studied in this work is to find an appropriate formulation to model the time requirements. We present five different modeling approaches, where the time aspect is handled in different ways: discrete, continuous, directly or via sub-problems. Our randomly generated test instances consider 6 to 20 targets and 1 to 6 salespersons. Computational experiments with linear and non-linear trajectories are performed. The best model can solve instances up to 10 targets within 3 seconds. For online experiments the two familiar strategies REPLAN and IGNORE are adapted to our problem. Another important aspect of this work is our contribution to competitive analysis, a method to evaluate the quality of online algorithms. Here, we restrict the problem considered so far to one salesperson and address the online moving targets traveling salesperson problem on the real line. We prove a lower bound for the competitive ratio regarding this problem. Then, we develop an online algorithm and present its competitive ratio with the corresponding proof. The competitive ratio depends on the speed ratio of salespersons and targets and outperforms a comparable online algorithm from the literature for certain speed ratios. The theoretical results obtained for the online moving target traveling salesperson problem on the real line are new in this research area.}, subject = {Multiple traveling salesperson problem; Moving targets; Modeling of time; Online algorithms; Competitive analysis; Multiples Handlungsreisendenproblem; Bewegliche Ziele; Modellierung von Zeit; Online-Algorithmen; Kompetitivit{\"a}tsanalyse; Competitive analysis; Travelling-salesman-Problem}, language = {en} }