On Fair Team Orienteering Problem

Team Orienteering Problem (TOP) has a wide range of applications, ranging from logistics and human/robot patrolling to door-to-door marketing. In TOP, each agent must jointly select an appropriate node subset and plan a feasible route connecting all its selected nodes, constrained by its route budget. Existing TOP solutions mainly focus on the efficiency tailored to maximize the selected node reward of all agents. Yet, studies in the social psychology literature have shown that fair task assignment is crucial for various multi-agent applications. However, existing literature fall short on modeling and solving the TOP with fairness consideration. In this work, we leverage the max-min reward among the agents as the fairness objective in TOP and formalize the new challenge as Fair TOP (fTOP). We propose FLOG (Fairness-aware Latent Orienteering based on Graph), a novel fTOP solution framework integrating spatial reward fields and policy learning to enable fairness-aware node selection and route planning. Across synthetic and real-world datasets, FLOG substantially improves the reward fairness over the state-of-the-art efficiency-oriented (SOTA) TOP solver, while maintaining competitive total reward. Specifically, compared with the SOTA solver, FLOG improves the average min-to-max reward ratio from $0.235$ to $0.743$, while reducing the total reward R by only $1.3\%$ on average. Our code and datasets are available at: https://github.com/route-research/FLOG.