J. J. Salazar González, E. Tresoldi, R. Wolfer Calvo
The Overnight Security Service Problem is motivated by a real-world application consisting in optimizing the routes of a fleet of guards that should check a set of buildings in a urban area for security reasons. This paper describes several mathematical formulations and analyses the relation to another problem known in the literature as the multi-color Travelling Salesman Problem. This other problem is of academic nature and can be seen as the Overnight Security Service problem with one guard, no depot, and identical time cost for all roads. It is a variant of the classical Travelling Salesman Problem where each point has a color, and the goal is to find a Minimum Cost Hamiltonian Cycle bounding the number of other visits between consecutive points with the same color. Since the formulations involve an exponential number of constraints, we describe constraint-generation procedures to be used within a Branch-and-Cut framework. We discuss computational results on real-world instances.
Keywords: Travelling Salesman Problem, Branch and Cut, Multistar inequalities
Scheduled
GT10 Transport II
June 7, 2022 3:30 PM
A15
