acceptodds
Under review as a conference paper at ICLR 2027

On Fair Team Orienteering Problem

Abstract

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 to , while reducing the total reward R by only on average. Our code and datasets are available at: https://github.com/route-research/FLOG.

Primary area:
reinforcement learning
Keywords:
team orienteering problem, fairness, reinforcement learning, multi-agent routing, combinatorial optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_SBqnOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the Fair Team Orienteering Problem. The authors propose FLOG, a graph-based reinforcement learning framework. Experiments demonstrate significant improvements.

Critical strengths
  1. The proposed framework considers both reward fairness and overall efficiency.
  2. The experimental results demonstrate substantial improvements.
Critical weaknesses
  1. The optimization objective is not fully consistent with the problem formulation.
  2. The contribution of RL is not sufficiently demonstrated.
Questions for authors
  1. Why does FLOG primarily optimize RFR in the experiments while the formal fTOP objective is to maximize the minimum agent reward?
  2. How much of the performance improvement comes from the learned policy rather than the heuristic fairness mechanisms?
2 comments

We appreciate your valuable feedback and support of our work.

To Weakness 1& Question 1:

We apologize for not clearly stating our guiding principle in the manuscript: to substantially improve the minimum agent reward with limited loss of total reward. We have clearly stated this guiding principle in the revised manuscript, including the Abstract on Page 1 and the Introduction on Page 2.

The reason for choosing min R as the formal objective: because the min R objective improves the fairness by directly improving the worst reward, and maintain the total reward by indirectly maintaining or improving other agents' rewards. This is consistent with our guiding principle as stated above. In contrast, RFR is a relative ratio that can be improved by lowering the maximum agent reward, potentially producing fair but low-reward solutions. For example, NSGA-II (Gross et al., 2025) achieves a perfect RFR (close to 1), but substantially lower min R and R, as shown in Tables 2–3 and 8–11.

The reason for using RFR in FLOG design and experiments: While our objective is to maximize the reward of the single worst-reward agent, multiple agents may be under-served during route construction, so FLOG prioritizes a group of under-rewarded agents instead of the single worst-rewarded one, as described in Sec. 4.2 on Page 5. We use RFR threshold to identify the under-rewarded agents with their rewards below $ \rho \times R_{\max} $. As an alternative, we also considered a min-reward-oriented rule, which selected the bottom ratio (e.g.30%) of agents ranked by reward. This min-reward-oriented ratio rule does not reliably identify the under-rewarded agents: the under-rewarded agent proportion may exceed or be below the ratio (e.g.30%) in different cases. In the experiments, min R is the core metric. Since RFR is used in FLOG design, as stated above, and it directly reflects fairness, we also use it as an important (but not the core ) metric in the experiments. We provide an explanation of this on Page 7.

To Weakness 2& Question 2:

To quantify the individual contributions of the learned policy and the heuristic fairness mechanisms, we have added controlled experiments in Sec. 5.5 on Page 9 and Appendix J on Page 22.

Specifically, we added three baselines: Water-filling, Round-robin, and Uniform Random selection, which retain the heuristic fairness mechanisms but replace the learned action-selection policy. The baselines are also recommended by Reviewer GYEP. FLOG outperforms the 3 baselines by 4.3%, 4.2%, and 21.7% in R; 11.9%, 11.8%, and 30.7% in min R; and 0.043, 0.044, and 0.036 in RFR, respectively, which shows that the learned policy contributes significantly to FLOG. The evaluation results are summarized in Tables 15 and 16 on Page 23. The FLOG-NoRR variant in Table 4 on Page 9 contains the learned policy but removes the residual reward recovery component of the heuristic fairness mechanisms. FLOG surpasses FLOG-NoRR by 328.0% and 323.3% in terms of R and min R. This validates the significant contribution of heuristic residual reward recovery to FLOG.

Table 15: Controlled Policy Comparisons on Synthetic Datasets.

Method⟨5,50⟩ R⟨5,50⟩ min R⟨5,50⟩ RFR⟨10,500⟩ R⟨10,500⟩ min R⟨10,500⟩ RFR⟨20,1000⟩ R⟨20,1000⟩ min R⟨20,1000⟩ RFR
FLOG (ours)19.8873.3120.720165.98813.8730.723403.61615.8580.671
Water-filling18.3512.8920.669159.96012.5780.671385.80514.2280.652
Round-robin18.3402.8850.668160.51312.6240.672386.25314.2820.651
Random17.1082.7550.684121.3859.0250.652250.8168.7220.650

Table 16: Controlled Policy Comparisons on Real-World Datasets at Scale ⟨10,500⟩.

MethodDenver RDenver min RDenver RFRLA RLA min RLA RFRSeattle RSeattle min RSeattle RFR
FLOG (ours)85.7926.7680.69198.5068.0540.69766.9525.6570.741
Water-filling82.7576.2080.66894.5857.0530.65766.1815.0660.669
Round-robin82.8016.1910.66694.5857.0310.65666.2955.0970.668
Random81.7416.3890.67592.7587.2090.67063.5395.1140.695

Thank you for the clarification and the new policy comparisons. I am still unsure how selecting the final solution by RFR affects performance on the stated objective of maximizing the minimum agent reward, so I am keeping my rating.

Reviewer_GYEPOpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper defines the Fair Team Orienteering Problem (fTOP), in which multiple agents with start/end locations and a common travel budget jointly select and route through candidate nodes, and the objective is replaced from total reward (Eq. 1) to the max-min agent reward (Eq. 4), subject to per-agent budget and node-exclusivity constraints. The authors note that existing fairness-aware TOP variants are either evolutionary (Gross et al., 2025), greedy (Sánchez-Yepez et al., 2023), or branch-and-cut with prohibitive runtime (Boyer et al., 2026), and propose FLOG, a graph-attention reinforcement-learning constructor with three components: (i) a multi-directional latent-field encoder over node-node, node-to-agent, and agent-agent interactions; (ii) fairness-guided sequential insertion, in which a hand-coded filter prioritizes zero-reward agents, protects an agent's sole feasible positive-reward node, and restricts actions to agents below θ·R_max until the reward fairness ratio RFR = min R / (max R + ε) reaches a threshold θ = 0.65; and (iii) a deterministic, non-learned recovery pass that fills residual budget while preserving the attained fairness. Training uses an advantage-weighted log-likelihood over S = 12 sampled rollouts (Eq. 28). At inference FLOG samples K candidates (K unspecified), applies deterministic recovery to each, and selects the highest-RFR candidate whose total reward is at least ρ_R = 0.90 of the best.

Evaluation covers 14 synthetic scales (training range M ∈ [5,10], N ≤ 100; generalization to N = 1000) and three K-means-clustered urban incident datasets (Denver, LA, Seattle), against GRIP, GCB, OR-Tools, and LKH-3 in reward-maximizing (R) and fairness-oriented (F) variants, plus NSGA-II. The headline claim is that average RFR rises from 0.235 to 0.743 relative to GRIP at a 1.3% cost in total reward, with FLOG attaining the highest minimum agent reward in 91.1% of evaluated settings.

Critical strengths

The paper takes the fairness objective seriously enough to build fairness-optimizing baselines, which most work in this area does not. It implements (F) variants of GCB, OR-Tools, and LKH-3 with the minimum agent reward as the stated objective, and it reports per-instance distributional results (ECDFs in Fig. 1 and Appendix G.1) rather than headline means alone. This is consequential because it means the honest comparison the paper currently avoids can be made from data the authors already have: the (F) baselines are in Tables 2, 8, and 9–11, and a per-scale min-R comparison against them can be extracted today. A revision that reframes around that comparison does not require a new experimental programme, only a new framing and a correct abstract.

Critical weaknesses

The reported gain does not distinguish the learned constructor from rule-based fairness masking plus greedy recovery, and the headline metric is partly a restatement of a hand-set threshold. Three facts combine. First, construction terminates when RFR_t ≥ θ (Alg. 1, line 3; Eq. 9) and inference then selects the highest-RFR candidate among K rollouts, so the reported RFR should sit near θ by construction; it does, at roughly 0.66–0.85 across every dataset and scale, and essentially identically across synthetic and real-world data — the paper reports 0.743 overall and 0.744 real-world-only — despite radically different geometry. Table 12 confirms the mechanism directly: sweeping θ from 0.50 to 0.75 moves RFR from 0.589 to 0.762 almost one-for-one. "RFR ≥ 0.659 in all settings" is therefore a consequence of θ = 0.65, not a finding. Second, the ablation does not isolate the learned component. FLOG-NoRR collapses to total reward 8.690 at (5,50) and 19.288 at (10,500), against 19.914 and 165.280 for the full model — an order-of-magnitude drop that indicates the learned construction phase alone collects almost nothing and that the deterministic recovery pass supplies most of the reward, which is also the pass that encodes the fairness constraint. There is no ablation of the encoder (the paper's headline architectural contribution), the dynamic state z_j,t, the action feature c(·), the zero-reward prioritization rule, or the unique-node protection rule, and no control in which the attention scores are replaced by uniform random or by a water-filling/round-robin heuristic under the same filter. Third, the abstract's comparison is against GRIP, a total-reward maximizer, not against the paper's own fairness-optimizing baselines. Against OR-Tools(F) the min-R margin is +2.0% at (5,50) and +5.1% at (5,100) — indistinguishable from a tie without variance — while FLOG's total reward is 8.6% and 4.7% below OR-Tools(F) at those scales. Similarly, at (20,1000) the text reports total reward improving "from 404.919 to 412.483" against GRIP, but GCB(R) reaches 419.970 and GCB(F) reaches 413.708 at that scale. The "only 1.3% cost" figure is a point on a θ-tunable curve measured against the weakest reference. The paper's title, abstract, and framing all claim a learned latent-field solver; nothing in the evidence rules out "any insertion heuristic with an RFR ≥ θ rule and this recovery pass."

Questions for authors
  1. What are K, ε in Eq. 9, and the two weights in the training utility of Eq. 14? K and ε are absent from Appendix D's otherwise detailed hyperparameter list, and ε enters the denominator of the headline metric. Given that several real-world cells report min R near 0.000–0.021 (e.g. Seattle and Denver at (10,100) for the OR-Tools and GCB variants), how much does the choice of ε move the reported RFR?

  2. Is there a train/validation/test split, and on which instances were θ = 0.65 and ρ_R = 0.90 selected? Were the instances reported in Tables 2 and 8 used for that selection? Relatedly, why do Table 12 and Table 2 disagree at the same setting (θ = 0.65, (10,100)) — different instance sample, different checkpoint, or nondeterminism?

1 comment

We appreciate your valuable feedback and support of our work.

To Critical Weaknesses:

The reviewers raise 3 concerns here, we would reply in order.

First, the mechanism for selecting under-rewarded agents based on ρ=0.65 indeed helps FLOG to achieve the desired fairness RFR>=0.65. The advantages and contribution of FLOG are 3-fold:

  1. Across the 14 testing scales, the lowest mean RFR is 0.659, and 7 cases exceed 0.8 and 0.848. Namely, FLOG could guarantee the desired fairness (0.65), as well as significantly improve it. Please refer to Tab. 8-11 on Page 18-21.
  2. Despite achieving remarkable fairness, the total reward loss is only 1.3%, which is negligible in most real-world applications.
  3. NSGA-II (the only observed baseline for fairness aware TOP) demonstrates that achieving high fairness can come at a significant loss of total reward, as in Tab.2 and 3 on Page 8. Our results are inspiring and different from that of NSGA-II. Namely, for TOP-type problems, future researchers could consider to achieve remarkable performance in both fairness and reward, instead of reward only.

Second, to distinguish the learned constructor from rule-based fairness masking plus greedy recovery, we have added controlled experiments. We added three baselines: Water-filling, Round-robin, and Uniform Random selection, which retain rule-based fairness masking plus greedy recovery but replace the learned constructor's action-selection policy. These baselines are also recommended by Reviewer GYEP. FLOG outperforms the 3 baselines by 10.1%, 18.1%, and 0.041 in terms of R, min R, and RFR, respectively. Namely, the learned constructor contributes significantly to FLOG. The experiments details and results are respectively in Sec. 5.5 on Page 9 and Tab.15-16 on Page 23. Besides, the FLOG-NoRR contains the learned constructor but removes the greedy recovery. FLOG surpasses FLOG-NoRR by 328.0% and 323.3% in terms of R and min R. This validates the significant contribution of greedy recovery to FLOG. Please refer to FLOG-NoRR in Table 4 on Page 9 for details.

Third, across all 14 testing synthetic scales, FLOG outperforms OR-Tools(F) by an average of 27.4% in terms of min R, while improving total reward by an average of 4.8%. FLOG achieves a higher min R at every scale, with an 88.5% increase in mean min R and a 2.8% increase in mean total reward compared with OR-Tools(F). At ⟨20,1000⟩, FLOG outperforms GCB(F) and GCB(R) by 47.3% and 87.4% in terms of min R, respectively, with only 0.3% and 1.8% losses in total reward, respectively. Please refer to Tab. 8-11 on Page 17 for details.

To Question 1:

We have specified K = 10, ε = 10⁻⁸, and both weights in Eq. (14) equal to 1. The impact of ε on the reported RFR is practically negligible. According to Eq. (9), the absolute deviation is: ∣RFRcalc−RFRtrue∣=∣min⁡Rmax⁡R+ϵ−min⁡Rmax⁡R∣=ϵmin⁡Rmax⁡R(max⁡R+ϵ)|RFR_{\text{calc}}-RFR_{\text{true}}| = \left|\frac{\min R}{\max R+\epsilon}-\frac{\min R}{\max R}\right| = \frac{\epsilon \min R}{\max R(\max R+\epsilon)}

For illustration, consider the Seattle ⟨10, 100⟩ case for GCB(R), where the reported mean values are min R ≈ 0.007 and R = 14.480. We have max R ≥ R/10 = 1.448. Thus,

∣RFRcalc−RFRtrue∣≤10−8×0.0071.448(1.448+10−8)≈3.34×10−11|RFR_{\text{calc}}-RFR_{\text{true}}| \le \frac{10^{-8}\times 0.007}{1.448(1.448+10^{-8})} \approx 3.34\times 10^{-11}

Therefore, ε = 10⁻⁸ has a negligible effect on RFR, with an illustrative deviation below 3.34 × 10⁻¹¹. Please refer to Appendix D on Page 17 for details.

To Question 2:

FLOG is trained on freshly generated synthetic instances at each training step, with the agent number M ∈ [5, 10] and candidate node numbers N ∈ [5M, 100]. In the test, both the synthetic and real-world testing instances cover 14 scales, divided into Normal Testing (NT), which includes 4 scales within the training range (M ∈ [5, 10] and N ∈ [5M, 100]), and Generalization Testing (GT), which includes 10 larger scales beyond the training range to evaluate scalability. We have added a Training and Evaluation Protocol paragraph in Sec. 5.1 on Page 6 to clarify the data split and evaluation scales.

  • Yes, ρ = 0.65 (denoted θ by the reviewer) and ρ_R = 0.90 were selected using the synthetic instances reported in Tables 2 and 8.

  • Different checkpoints caused the discrepancy between Tables 12 and 2 at ρ = 0.65 and ⟨10, 100⟩.

Reviewer_GP4vOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper presents a Fair Task Assignment method in Team Orienteering Problem, rlevant in logistics, human robot teaming and marketing. The main argument is based on social psychology literature that workload of the task assignment is crucial and not modelled in prior work in robot teaming. The presented Fairness-aware Latent Orienteering based on Graph model integrates spatial reward fields and policy learning, and is made up of a Latent Fielkd Econding, a sequential route construction and residual reward recovery while accounting for fairness, improving over the SOTA solvers.

Critical strengths
  1. Technical contribution:
    • The paper presents a method of balancing workload in teaming problems, showing improvement over baselines on at least one metric being evaluated.
  2. Empirical strength:
    • Experimental setup is well documented, with Training and testing in different scales, with synthetic and real-world datasets, multiple baselines and 4 evaluation metrics. Though the actual results are unclear on how much the proposed model actually improves in synthetic and real world datasets.
  3. Relevance and impact:
    • The presented problem has been stated to have a large range of applications, with the proposed model outperforming baselines on a subset of the metrics.
Critical weaknesses
  1. The paper is unclear on how much of the method's success is a result of Reward Engineering and how much of it is the contribution of the model.
  2. Missing a dedicated Limitations section that can improve the quality of the paper and clarify the results.
  3. It is unclear how many seeds the model was trained on, and if the learned policy generalizes.
Questions for authors
  • What exactly is the difference between the Fair Top Problem and other Constraint-based Optimization problems? What makes methods that are prevalent in RL4OPT literature not a good fit for the specific problem being solved?
  • While the justification is presented from social psychology perspective on the need for fairness in task assignment, it is unclear if this work is meant for human teams, robot teams or a mix of human-robot teams. Could the authors present an argument on why the fairness that is presented to be significant for humans is more important than fast and efficient task assignment to maximize an overall objective without care for fairness?
1 comment

We appreciate your valuable feedback and support of our work.

To Critical Weaknesses 1:

To quantify the contributions of the learned model and Reward Engineering, we added three baselines: Water-filling, Round-robin, and Uniform Random selection, which retain Reward Engineering but replace the learned model's action-selection policy. The baselines are also recommended by Reviewer GYEP. FLOG outperforms the 3 baselines by 4.3%, 4.2%, and 21.7% in R; 11.9%, 11.8%, and 30.7% in min R; and 0.043, 0.044, and 0.036 in RFR, respectively, which shows that the learned model contributes significantly. Details are in Sec. 5.5 on Page 9, Appendix J on Page 22, and Tables 15-16 on Page 23. The FLOG-NoRR variant in Table 4 on Page 9 contains the learned model but removes the residual reward recovery component of Reward Engineering. FLOG surpasses FLOG-NoRR by 328.0% and 323.3% in terms of R and min R. This validates the significant contribution of Reward Engineering to FLOG.

To Critical Weaknesses 2:

We discuss limitations in Sec. 6 Conclusion and Limitations on Page 10: ”Our current fTOP formulation assumes identical travel budgets to provide a controlled evaluation of reward fairness. The applicability of FLOG to heterogeneous agents with different budgets remains unexplored. Given the non-identical budgets across agents, a novel fairness objective should be defined, and novel node selection and routing mechanisms for FLOG are needed.”

To Critical Weaknesses 3:

FLOG was trained with seed 0 in Sec. 5.1 on Page 7. We further trained seeds 1 and 2 to assess robustness. Across the three seeds, the maximum relative deviations in R, min R, and RFR are only 1.33%, 2.71%, and 2.77%, respectively. Thus, FLOG is consistent across different seeds. See Appendix I on Page 21 and Tables 13-14 on Page 22

FLOG shows strong generalization across problem scales and data distributions.

  • Across scales: FLOG is trained only on freshly generated synthetic instances, with the agent number M ∈ [5, 10] and candidate node number N ∈ [5M, 100]. In the test, both the synthetic and real-world instances cover 14 scales, divided into Normal Testing (NT), which includes 4 scales within the training range, and Generalization Testing (GT), which includes 10 larger scales beyond the training range to evaluate scalability. FLOG raises mean RFR from 0.235 (GRIP) to 0.743 with only 1.3% lower total reward. FLOG improves min R over OR-Tools(F) by 27.4% on average across the 14 synthetic scales. The results show the strong generalization capacity of FLOG across problem scales. See Tab. 2-3, 8-11 on Page 8 for details.

  • Across distributions: we quantify spatial distribution shifts between the synthetic training and real-world test nodes using MMD² (Borgwardt et al., 2006; Gretton et al., 2012). A larger MMD² value indicates greater dissimilarity between the synthetic training and real-world test node distributions. FLOG's relative min R gains over GRIP against MMD² at three scales are in Fig. 2 on Page 17. As MMD² increases, FLOG generally maintains substantial improvements in min R, demonstrating its better suitability for distribution dissimilarity of nodes over GRIP.

To Question 1:

The key distinction of fTOP is its max-min reward objective under budget-constrained multi-agent routing. Unlike knapsack-style selection with additive costs (Chen et al., 2024), fTOP involves route-dependent costs. Unlike cardinality-constrained max-min subset optimization (Spaeh & Miyauchi, 2025), fTOP jointly selects, assigns, and routes reward-bearing nodes. Conventional TOP instead maximizes aggregate reward.

Existing RL4OPT methods are not directly applicable to fTOP due to differences in problem settings and optimization objectives. For example, Equity-Transformer (Son et al., 2024) minimizes the longest route without budget-constrained reward-node selection, while GRIP (Hu et al., 2026) maximizes aggregate rather than minimum agent reward.

To Question 2:

FLOG is not limited to human, robot, or mixed human–robot teams. Following the typical established combinatorial optimization models (e.g., Kool et al., 2019; Kwon et al., 2020; Fuertes et al., 2025; Hu et al., 2026), we represent agents by their locations and travel budgets, and tasks by spatial nodes and rewards, without specifying agent types. Similar to these models, FLOG fits any form of agent team fitting the constrained multi-agent routing setting.

Fairness can support long-term team effectiveness for human, robot, and mixed human–robot teams. Fairness can support equitable compensation and participation in human teams (Zhao et al., 2021; CAFE, 2025), reduce workload concentration in robot teams (Wilde & Alonso-Mora, 2026), and promote balanced human–robot collaboration (Fuster et al., 2025).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.