The Team Orienteering Problem with Nonidentical Agents and Balanced Score (TOPNB) is a challenging problem, inspired by a real-world situation from a Mexican telecommunications company, where equitable resource allocation and agent heterogeneity are critical. This paper presents a novel Branch-and-Cut (B&C) algorithm designed to maximize the minimum score collected by any agent, thereby ensuring a balanced distribution of rewards across a heterogeneous fleet. Our approach features a new mixed-integer linear programming formulation (MILP), strengthened by dedicated valid inequalities and an efficient primal heuristic, all integrated within a robust B&C framework. Extensive computational experiments on established benchmark instances demonstrate the effectiveness and scalability of the proposed method: the algorithm solves 348 out of 353 instances to optimality, contributes 153 new optimal solutions, and improves 95 previously best-known results. The B&C algorithm also achieves significant reductions in computational time compared to existing MILP and heuristic approaches. These results highlight the practical value of our method for large-scale, balanced routing and scheduling problems, such as those encountered in workforce management, logistics, and service operations. Our findings offer actionable insights for practitioners and researchers seeking effective solutions for balanced, heterogeneous agent routing problems.
