Open Access

Anke Stieber, Armin Fügenschuh

• 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.
• Das Problem des multiplen Handlungsreisenden mit bewegten Zielen ist eine Verallgemeinerung des Problems des klassischen Handlungsreisenden (TSP), bei dem sich die Ziele (Städte oder Objekte) im Laufe der Zeit bewegen. Zusätzlich wird für jedes Ziel ein Sichtbarkeitszeitfenster angegeben. Die Aufgabe besteht darin, Routen für mehrere Handlungsreisende zu finden, so dass jedes Ziel innerhalb seines Sichtbarkeitszeitfensters genau einmal erreicht wird und die Summe aller zurückgelegten Entfernungen aller Handlungsreisenden minimal ist. Wir präsentieren verschiedene Modellformulierungen für diese TSP-Variante. Die Zeitrestriktionen werden in jedem Ansatz unterschiedlich modelliert. Unser Ziel ist es zu untersuchen, welche Formulierung in Bezug auf die Laufzeit am besten geeignet ist, um das Problem mit mehreren Handlungsreisenden mit bewegten Zielen mit exakten Methoden, welche globale Optimalität garantieren, zu lösen. Computerversuche werden an zufällig generierten Testinstanzen durchgeführt, um die verschiedenen ModellierungsansätzeDas Problem des multiplen Handlungsreisenden mit bewegten Zielen ist eine Verallgemeinerung des Problems des klassischen Handlungsreisenden (TSP), bei dem sich die Ziele (Städte oder Objekte) im Laufe der Zeit bewegen. Zusätzlich wird für jedes Ziel ein Sichtbarkeitszeitfenster angegeben. Die Aufgabe besteht darin, Routen für mehrere Handlungsreisende zu finden, so dass jedes Ziel innerhalb seines Sichtbarkeitszeitfensters genau einmal erreicht wird und die Summe aller zurückgelegten Entfernungen aller Handlungsreisenden minimal ist. Wir präsentieren verschiedene Modellformulierungen für diese TSP-Variante. Die Zeitrestriktionen werden in jedem Ansatz unterschiedlich modelliert. Unser Ziel ist es zu untersuchen, welche Formulierung in Bezug auf die Laufzeit am besten geeignet ist, um das Problem mit mehreren Handlungsreisenden mit bewegten Zielen mit exakten Methoden, welche globale Optimalität garantieren, zu lösen. Computerversuche werden an zufällig generierten Testinstanzen durchgeführt, um die verschiedenen Modellierungsansätze zu vergleichen. Die Ergebnisse für umfangreiche Instanzen zeigen, dass der beste Weg, um Zeitanforderungen zu modellieren, darin besteht, sie in diskreten Zeitschritten direkt in die Formulierung einzufügen.…