@techreport{StieberFuegenschuh2019, author = {Stieber, Anke and F{\"u}genschuh, Armin}, title = {Dealing with time in the multiple traveling salesmen problem with moving targets}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-4824}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-48245}, year = {2019}, abstract = {The multiple traveling salesmen problem with moving targets is a generalization of the classical traveling salesmen problem, where the targets (cities or objects) are moving over time. Additionally, for each target a visibility time window is given. The task is to find routes for several salesmen so that each target is reached exactly once within its visibility time window and the sum of all traveled distances of all salesmen is minimal. We present different modeling formulations for this TSP variant. The time requirements are modeled differently in each approach. Our goal is to examine what formulation is most suitable in terms of runtime to solve the multiple traveling salesmen problem with moving targets with exact methods. Computational experiments are carried out on randomly generated test instances to compare the different modeling approaches. The results for large-scale instances show, that the best way to model time requirements is to directly insert them into a formulation with discrete time steps.}, subject = {Dynamic traveling salesmen problem; Moving targets; Time-relaxation; Integer linear programming; Second-order cone programming; Travelling-salesman-Problem}, language = {en} } @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} }