O problema de alocação de pontos de controle

Abstract

We formally introduce the Multi-period Checkpoint Allocation Problem with Conflicts (PAPCMC), which allocates indivisible, mobile control units to discrete locations over a finite time horizon, maximizing the total weight of allocations under exclusivity, compatibility, and movement constraints. We show that PAPCMC can be reduced to an Assignment Problem with Conflicts (APC). Additionally, we prove that the problem is NP-hard even with only two periods, via a polynomial reduction from the (3,B2)-SAT problem. We present two alternative integer linear programming formulations for the problem: BLP1, which encodes a solution as a maximum independent set, and BLP2, which represents PAPCMC as a maximum-cost flow problem with conflict constraints. We show that BLP2 has a linear relaxation at least as tight as that of BLP1 and can be solved in polynomial time when all teams share identical schedules. Moreover, its block structure enables decomposition into per-team subproblems, inspiring efficient heuristics. We designed three main heuristics—HGC, HGE, and HL—as well as versions inspired by methods GRASP and ACO. We created a set of 15198 realistic instances based on public data from New York City. In tests with a 2-minute time limit, HGC outperformed HGE in 96.3% of the instances in terms of objective value; HL reached optimality in more than half of the instances and reduced the average gap to 1%. Incorporating the heuristics’ lower bounds proved effective. Specifically, BLP2 achieved optimal solutions in 94.1% of the instances, reduced average computation time by 40%, and decreased the integrality gap by 35% relative to BLP1. Even with a 1-hour execution limit on difficult cases, BLP2 maintained superiority in the number of optimal solutions found. We conclude that integrating lower bounds from heuristics reduces total computation time and increases the number of instances solved to optimality: adopt HGC when the goal is to find an optimal solution and HL for stronger lower-bound guarantees. Given its overall performance, BLP2 is the recommended approach in operational scenarios.