Dealing with time in the multiple traveling salespersons problem with moving targets
- PDF / 1,406,944 Bytes
- 27 Pages / 439.37 x 666.142 pts Page_size
- 63 Downloads / 198 Views
Dealing with time in the multiple traveling salespersons problem with moving targets Anke Stieber1
· Armin Fügenschuh2
Accepted: 6 October 2020 © The Author(s) 2020
Abstract The multiple traveling salespersons problem with moving targets is a generalization of the classical traveling salespersons problem, where the targets (nodes or objects) are moving over time. Additionally, for each target a visibility time window is given. The task is to find routes for several salespersons so that each target is reached exactly once within its visibility time window and the sum of all traveled distances of all salespersons 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 salespersons 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. Keywords Dynamic traveling salespersons problem · Moving targets · Time-relaxation · Integer linear programming · Second-order cone programming
1 Introduction This research deals with a dynamic variant of the traveling salesperson problem (TSP), where the targets or nodes are not fixed. This TSP generalization is called multiple traveling salespersons problem with moving targets (MTSPMT). A possible application of the MTSPMT can be found in the defense sector. An area, e.g., an airport or
B
Anke Stieber [email protected] Armin Fügenschuh [email protected]
1
Helmut Schmidt University, Hamburg, Germany
2
Brandenburg University of Technology Cottbus-Senftenberg, Cottbus, Germany
123
A. Stieber, A. Fügenschuh
a military base, must be protected from incoming hostile rocket, artillery, or mortar (RAM) fire. Simultaneous attacks from different firing positions are considered. There is a radar system detecting targets and estimating their trajectories. With a battery of laser guns deployed within or nearby the protected area decisions have to be taken, which available laser gun to select for the countermeasures to protect the area. The selected laser gun then aims at the incoming target for a certain period of time to destroy it. We assume that each target can be destroyed by firing the same period of time regardless how far away it is. This period of time is set to one unit. Generally, the closest laser gun is assigned to a target, where “close” does not refer to the physical distance between laser gun and target, but to the angle the laser gun needs to traverse for aiming at the target. The closest laser gun is used to prefer small angles over large angles, because in case of failure (target is not destroyed) an adjustment of the laser gun is then more likely to succeed. The goal is to destroy all incoming R
Data Loading...
