The Problem of Multiple Traveling Salesmen with Backup Coverage - A Discrete-Time Model

The Multiple Traveling Salesmen Problem with Backup Coverage (MTSP-BC) is a generalization of the Multiple Traveling Salesmen Problem (MTSP), which involves determining routes for multiple travelers who start from a common origin, visit a set of cities, and return to the starting point, minimizing the total travel cost.

The main feature of the MTSP-BC is the addition of a coverage constraint, where vehicles must maintain a distance below a predefined value — the coverage radius — throughout the execution of the routes. This constraint creates interdependence between routes, making it difficult to treat each route independently.

A practical example is police patrol planning, where units must stay close enough to respond to emergencies from other units within an acceptable time frame. Even small local adjustments in a route can render a solution infeasible.

The mCA(2024) model proposes an improvement to the MTSP-BC formulation by introducing arcs indexed not only by the start and end vertices but also by the start and end times of the traversal. A preprocessing step identifies the arcs that provide coverage to each vertex and associates each arc with the minimum and maximum times a vehicle must be present to ensure coverage.

The new model defines binary variables for arc selection, considering the start time, end time, and the responsible traveler. However, the model requires an upper bound for the maximum time assigned to the longest route. While it is reasonable to assume that a route from the TSP could provide this bound, a counterexample will be presented to demonstrate that this association is not valid for the MTSP-BC.