pith. sign in

arxiv: 2603.20766 · v2 · submitted 2026-03-21 · 🧮 math.OC

A reliability-aware randomized simheuristic for the stochastic team orienteering problem

Michele Circelli This is my paper

Pith reviewed 2026-05-15 06:58 UTC · model grok-4.3

classification 🧮 math.OC
keywords stochastic team orienteeringsimheuristicreliability-aware selectionrandomized heuristictravel time uncertaintyorienteering problemvehicle routingmetaheuristic
0
0 comments X

The pith

A simpler reliability-aware simheuristic competes with complex VNS-based methods on stochastic team orienteering instances.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a randomized simheuristic for the stochastic team orienteering problem where travel times follow a lognormal distribution and a route earns nothing if it exceeds the time budget. It builds a savings-based constructive procedure around three elements: Top-Ltop randomization of candidate insertions, stochastic screening of the savings parameter, and an explicit reliability threshold used to pick final solutions. The central claim is that this lighter architecture matches the quality of a stronger VNS-based simheuristic on a useful share of the Chao benchmark set, especially on two-vehicle long-route cases where the reliability filter offsets the lack of neighborhood search. The result matters because many practical routing decisions under time uncertainty could be solved with simpler, easier-to-maintain code rather than heavy metaheuristics.

Core claim

The reliability-aware simheuristic, built from a savings heuristic plus Top-Ltop randomization, stochastic screening of the savings parameter, and an explicit reliability threshold, produces results competitive with the VNS-based simheuristic of Panadero et al. on a non-trivial subset of Chao instances; the largest gains occur on two-vehicle sub-families with long routes, where the reliability filter compensates for the absence of VNS-style exploration, while on larger multi-vehicle instances the simpler design is outperformed.

What carries the argument

The explicit reliability threshold for final solution selection, used together with Top-Ltop randomization and stochastic screening inside a savings-based constructive heuristic.

If this is right

  • On two-vehicle instances with long routes the reliability threshold improves solution quality without requiring VNS neighborhood moves.
  • The simpler architecture offers a practical alternative whenever implementation effort or maintenance cost must stay low.
  • On larger multi-vehicle instances the absence of advanced exploration produces a measurable performance gap.
  • The three design elements together allow direct handling of all-or-nothing rewards under travel-time uncertainty on the tested benchmark set.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Varying the reliability threshold across different route-length regimes could further improve results on specific sub-families.
  • Embedding the same randomization and screening steps into other vehicle-routing variants might yield similar simplicity-performance trade-offs.
  • Running the method on instances whose travel times come from real GPS traces would test whether the lognormal assumption limits applicability.
  • Comparing wall-clock times directly with the VNS approach on identical hardware would quantify the claimed simplicity advantage.

Load-bearing premise

The Chao benchmark instances and the lognormal travel-time model represent real-world stochastic behavior well enough that the chosen reliability threshold generalizes beyond the tested cases.

What would settle it

If the proposed method shows markedly worse performance than the VNS baseline when run on the same Chao instances but with travel times drawn from a different distribution such as normal or gamma, the competitiveness claim would be falsified.

read the original abstract

We study a stochastic variant of the Team Orienteering Problem with lognormal travel times and an all-or-nothing reward policy, under which the reward of a route is lost if its travel time exceeds the available budget. We propose a reliability-aware simheuristic that combines a savings-based constructive heuristic with three specific design elements: a Top-$L_{\mathrm{top}}$ randomization mechanism, stochastic screening of the savings parameter, and an explicit reliability threshold for solution selection. Computational experiments on the Chao et al. benchmark show that the method is competitive with the VNS-based simheuristic of Panadero et al. (2020) on a non-trivial subset of instances using a significantly simpler architecture, with the largest gains on two-vehicle sub-families with long routes where the reliability-aware selection compensates for the absence of VNS-style exploration. On larger multi-vehicle instances the simpler architecture is outperformed, and this trade-off is discussed explicitly.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes a reliability-aware randomized simheuristic for the stochastic team orienteering problem with lognormal travel times and an all-or-nothing reward policy. It augments a savings-based constructive heuristic with three elements: Top-L_top randomization, stochastic screening of the savings parameter, and an explicit reliability threshold for solution selection. Computational experiments on the Chao et al. benchmark instances indicate that the method is competitive with the VNS-based simheuristic of Panadero et al. (2020) on a non-trivial subset of instances, particularly two-vehicle sub-families with long routes, while employing a simpler architecture; performance degrades on larger multi-vehicle instances.

Significance. If the competitiveness claim is substantiated with detailed numerical evidence, the work is significant for stochastic combinatorial optimization. It illustrates how targeted reliability mechanisms can offset reduced search intensity relative to VNS-style methods on specific instance classes, offering a simpler alternative that may be preferable in practice for stochastic routing problems where implementation effort and computational overhead matter. The explicit discussion of the performance trade-off on multi-vehicle instances adds useful insight into the limits of the approach.

major comments (2)
  1. [§4] §4 (Computational Experiments): The central claim of competitiveness with Panadero et al. (2020), including largest gains on two-vehicle long-route sub-families, is load-bearing yet unsupported by any referenced tables, average objective values, percentage gaps, instance counts, or statistical tests. Without these data the compensation argument for the reliability-aware selection cannot be verified.
  2. [§3] §3 (Algorithm Description): The reliability threshold and savings-parameter screening are listed as free parameters; if their selection is instance-dependent or requires tuning on the test set, this undermines the implied simplicity advantage over VNS and must be quantified with a clear selection procedure or sensitivity analysis.
minor comments (2)
  1. Define all acronyms (STOP, VNS, etc.) at first use in the abstract and introduction.
  2. [§3] Ensure consistent mathematical formatting for L_top (as L_{top} or L_{mathrm{top}}) across text and equations.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments, which help clarify the presentation of our results. We address each major comment below and will revise the manuscript to incorporate the requested details.

read point-by-point responses

  1. Referee: [§4] §4 (Computational Experiments): The central claim of competitiveness with Panadero et al. (2020), including largest gains on two-vehicle long-route sub-families, is load-bearing yet unsupported by any referenced tables, average objective values, percentage gaps, instance counts, or statistical tests. Without these data the compensation argument for the reliability-aware selection cannot be verified.

    Authors: We agree that explicit numerical support is needed to substantiate the competitiveness claims. The experiments section contains tables with per-instance results, but these are not sufficiently cross-referenced in the text. In the revision we will add direct citations to the tables, report average objective values and percentage gaps (with standard deviations) over the two-vehicle long-route sub-family and the full set, specify the exact instance counts per category, and include a brief statistical comparison (e.g., Wilcoxon signed-rank test) against Panadero et al. (2020). This will make the compensation argument for the reliability-aware selection verifiable. revision: yes

  2. Referee: [§3] §3 (Algorithm Description): The reliability threshold and savings-parameter screening are listed as free parameters; if their selection is instance-dependent or requires tuning on the test set, this undermines the implied simplicity advantage over VNS and must be quantified with a clear selection procedure or sensitivity analysis.

    Authors: The parameters were fixed after preliminary calibration on a small, disjoint training subset drawn from the Chao instances (distinct from the final test set). To remove any ambiguity we will add an explicit subsection describing the calibration procedure, the chosen values, and a sensitivity analysis over a modest range of the reliability threshold and screening probability. The analysis will show that performance remains competitive within a small neighborhood of the selected values, thereby preserving the claimed simplicity advantage. revision: yes

Circularity Check

0 steps flagged

No circularity: heuristic combines standard components with explicit new design choices and external benchmark comparison

full rationale

The paper defines a reliability-aware simheuristic via three concrete algorithmic elements (Top-L_top randomization, stochastic screening of the savings parameter, and explicit reliability threshold) applied to a savings-based constructive heuristic. These are presented as design choices rather than derived quantities. The central competitiveness claim is supported by direct comparison to the external VNS simheuristic of Panadero et al. (2020) on the Chao et al. benchmark set, with no equations, fitted parameters, or self-citations that reduce the reported performance to inputs defined inside the paper. The derivation chain consists of algorithmic construction followed by empirical evaluation; no step collapses by construction to a renaming, self-definition, or load-bearing self-citation.

Axiom & Free-Parameter Ledger

2 free parameters · 2 axioms · 0 invented entities

The approach rests on standard domain assumptions about travel-time distributions and reward policies plus a small number of tunable heuristic parameters; no new entities are postulated.

free parameters (2)
  • reliability threshold
    Explicit selection criterion whose value must be chosen or tuned for the method to operate.
  • savings parameter
    Subject to stochastic screening, implying parameterization that affects route construction.
axioms (2)
  • domain assumption Travel times are independent and follow a lognormal distribution
    Stated as part of the stochastic problem definition.
  • domain assumption All-or-nothing reward policy applies to each route
    Core modeling choice for the stochastic variant.

pith-pipeline@v0.9.0 · 5453 in / 1398 out tokens · 54837 ms · 2026-05-15T06:58:56.654415+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

38 extracted references · 38 canonical work pages

  1. [1]

    Metaheuristics for the Team Orienteering Prob- lem

    Claudia Archetti, Alain Hertz, and Maria Grazia Speranza. “Metaheuristics for the Team Orienteering Prob- lem”. In:Journal of Heuristics13.1 (2007), pp. 49–76

    work page 2007

  2. [2]

    A learnheuristic approach for the team orienteering problem with aerial drone motion constraints

    Christopher Bayliss et al. “A learnheuristic approach for the team orienteering problem with aerial drone motion constraints”. In:Applied Soft Computing92 (2020), p. 106280.doi:10.1016/j.asoc.2020.106280

    work page doi:10.1016/j.asoc.2020.106280 2020

  3. [3]

    An Optimal Solution Procedure for the Multiple Tour Maximum Collection Problem Using Column Generation

    Seamus E. Butt and David M. Ryan. “An Optimal Solution Procedure for the Multiple Tour Maximum Collection Problem Using Column Generation”. In:Computers & Operations Research26.4 (1999), pp. 427– 441

    work page 1999

  4. [4]

    Rich Vehicle Routing Problem: Survey

    Jos´ e C´ aceres-Cruz et al. “Rich Vehicle Routing Problem: Survey”. In:ACM Computing Surveys47.2 (2015), 32:1–32:28

    work page 2015

  5. [5]

    The Orienteering Problem with Stochastic Travel and Service Times

    Ann Melissa Campbell, Michel Gendreau, and Brian W. Thomas. “The Orienteering Problem with Stochastic Travel and Service Times”. In:Annals of Operations Research186.1 (2011), pp. 61–81

    work page 2011

  6. [6]

    A Fast and Effective Heuristic for the Orienteering Problem

    I-Ming Chao, Bruce L. Golden, and Edward A. Wasil. “A Fast and Effective Heuristic for the Orienteering Problem”. In:European Journal of Operational Research88.3 (1996), pp. 475–489.doi:10 . 1016 / 0377 - 2217(95)00035-6

    work page 1996

  7. [7]

    The Team Orienteering Problem

    I.-Ming Chao, Bruce Golden, and Edward Wasil. “The Team Orienteering Problem”. In:European Journal of Operational Research88.3 (1996), pp. 464–474

    work page 1996

  8. [8]

    An Effective PSO-Inspired Algorithm for the Team Orienteering Problem

    Duc-Cuong Dang, Rabi N. Guibadj, and Aziz Moukrim. “An Effective PSO-Inspired Algorithm for the Team Orienteering Problem”. In:European Journal of Operational Research229.2 (2013), pp. 332–344

    work page 2013

  9. [9]

    A Two-Stage Approach to the Orienteering Problem with Stochastic Weights

    Lianne Evers et al. “A Two-Stage Approach to the Orienteering Problem with Stochastic Weights”. In: Computers & Operations Research43 (2014), pp. 248–260

    work page 2014

  10. [10]

    Solving the Team Orienteering Problem: Developing a Solution Tool Using a Genetic Algorithm Approach

    Jo˜ ao Ferreira, Alexandre Quintas, and Jos´ e Oliveira. “Solving the Team Orienteering Problem: Developing a Solution Tool Using a Genetic Algorithm Approach”. In:Soft Computing in Industrial Applications. Vol. 223. Advances in Intelligent Systems and Computing. Springer, 2014, pp. 365–375

    work page 2014

  11. [11]

    The Orienteering Problem

    Bruce L. Golden, Lawrence Levy, and Ravindra Vohra. “The Orienteering Problem”. In:Naval Research Logistics34.3 (1987), pp. 307–318

    work page 1987

  12. [12]

    A Simheuristic Algorithm for Solving the Arc Routing Problem with Stochastic Demands

    Sergio Gonz´ alez-Mart´ ın et al. “A Simheuristic Algorithm for Solving the Arc Routing Problem with Stochastic Demands”. In:Journal of Simulation12.1 (2018), pp. 53–66

    work page 2018

  13. [13]

    Biased Randomization of Heuristics Using Skewed Probability Distributions: A Survey and Some Applications

    Aleix Grasas et al. “Biased Randomization of Heuristics Using Skewed Probability Distributions: A Survey and Some Applications”. In:Computers & Industrial Engineering110 (2017), pp. 216–228

    work page 2017

  14. [14]

    A Variable Neighborhood Search Simheuristic for the Multiperiod Inventory Routing Problem with Stochastic Demands

    Ariane Gruler et al. “A Variable Neighborhood Search Simheuristic for the Multiperiod Inventory Routing Problem with Stochastic Demands”. In:International Transactions in Operational Research27.1 (2020), pp. 314–339

    work page 2020

  15. [15]

    Supporting Multi-Depot and Stochastic Waste Collection Management in Clustered Urban Areas via Simulation-Optimization

    Ariane Gruler et al. “Supporting Multi-Depot and Stochastic Waste Collection Management in Clustered Urban Areas via Simulation-Optimization”. In:Journal of Simulation11.1 (2017), pp. 11–19

    work page 2017

  16. [16]

    Orienteering Problem: A Survey of Recent Variants, Solution Approaches and Applications

    Aldy Gunawan, Hoong Chuin Lau, and Pieter Vansteenwegen. “Orienteering Problem: A Survey of Recent Variants, Solution Approaches and Applications”. In:European Journal of Operational Research255.2 (2016), pp. 315–332

    work page 2016

  17. [17]

    Determining Reliable Solutions for the Team Orienteering Problem with Probabilistic Delays

    Erika M. Herrera et al. “Determining Reliable Solutions for the Team Orienteering Problem with Probabilistic Delays”. In:Mathematics10.20 (2022), p. 3788.doi:10.3390/math10203788

    work page doi:10.3390/math10203788 2022

  18. [18]

    The Orienteering Problem with Stochastic Profits

    Tuba Ilhan, S. M. R. Iravani, and Mark S. Daskin. “The Orienteering Problem with Stochastic Profits”. In: IIE Transactions40.4 (2008), pp. 406–421

    work page 2008

  19. [19]

    A Review of Simheuristics: Extending Metaheuristics to Deal with Stochastic Combi- natorial Optimization Problems

    Angel A. Juan et al. “A Review of Simheuristics: Extending Metaheuristics to Deal with Stochastic Combi- natorial Optimization Problems”. In:Operations Research Perspectives2 (2015), pp. 62–72

    work page 2015

  20. [20]

    Pareto Mimic Algorithm: An Approach to the Team Orienteering Problem

    Liang Ke et al. “Pareto Mimic Algorithm: An Approach to the Team Orienteering Problem”. In:Omega61 (2016), pp. 155–166

    work page 2016

  21. [21]

    Dynamic Stochastic Orienteering Problems for Risk-Aware Applications

    Hoong Chuin Lau et al. “Dynamic Stochastic Orienteering Problems for Risk-Aware Applications”. In:Pro- ceedings of the 22nd International Conference on Automated Planning and Scheduling (ICAPS). 2012, pp. 150– 158

    work page 2012

  22. [22]

    Solving the Team Orienteering Problem Using Effective Multi-Start Simulated Annealing

    Shu-Ping Lin. “Solving the Team Orienteering Problem Using Effective Multi-Start Simulated Annealing”. In:Applied Soft Computing13.2 (2013), pp. 1064–1073. 16 REFERENCES

    work page 2013

  23. [23]

    A Simheuristic Approach for the Stochastic Team Orienteering Problem

    Javier Panadero et al. “A Simheuristic Approach for the Stochastic Team Orienteering Problem”. In:Pro- ceedings of the 2017 Winter Simulation Conference. 2017, pp. 3208–3217.doi:10.1109/WSC.2017.8248039

    work page doi:10.1109/wsc.2017.8248039 2017

  24. [24]

    Combining Parallel Computing and Biased Randomization for Solving the Team Ori- enteering Problem in Real-Time

    Javier Panadero et al. “Combining Parallel Computing and Biased Randomization for Solving the Team Ori- enteering Problem in Real-Time”. In:Applied Sciences11.24 (2021), p. 12092.doi:10.3390/app112412092

    work page doi:10.3390/app112412092 2021

  25. [25]

    Maximising Reward from a Team of Surveillance Drones: A Simheuristic Approach to the Stochastic Team Orienteering Problem

    Javier Panadero et al. “Maximising Reward from a Team of Surveillance Drones: A Simheuristic Approach to the Stochastic Team Orienteering Problem”. In:European Journal of Industrial Engineering14.4 (2020), pp. 485–516.doi:10.1504/EJIE.2020.108581

    work page doi:10.1504/ejie.2020.108581 2020

  26. [26]

    Solving the stochastic team orienteering problem: comparing simheuristics with the sample average approximation method

    Javier Panadero et al. “Solving the stochastic team orienteering problem: comparing simheuristics with the sample average approximation method”. In:International Transactions in Operational Research31.5 (2024), pp. 3036–3060.doi:10.1111/itor.13302

    work page doi:10.1111/itor.13302 2024

  27. [27]

    The Stochastic Team Orienteering Problem with Position-Dependent Rewards

    Javier Panadero et al. “The Stochastic Team Orienteering Problem with Position-Dependent Rewards”. In: Mathematics10.16 (2022), p. 2856.doi:10.3390/math10162856

    work page doi:10.3390/math10162856 2022

  28. [28]

    Objective Function Evaluation Methods for the Orienteering Problem with Stochastic Travel and Service Times

    Vasileios Papapanagiotou, Roberto Montemanni, and Luca M. Gambardella. “Objective Function Evaluation Methods for the Orienteering Problem with Stochastic Travel and Service Times”. In:Journal of Applied Operations Research6.1 (2014), pp. 16–29

    work page 2014

  29. [29]

    A Sim-Learnheuristic for the Team Orienteering Problem: Applications to Un- manned Aerial Vehicles

    Mohammad Peyman et al. “A Sim-Learnheuristic for the Team Orienteering Problem: Applications to Un- manned Aerial Vehicles”. In:Algorithms17.5 (2024), p. 200.doi:10.3390/a17050200

    work page doi:10.3390/a17050200 2024

  30. [30]

    A Biased-Randomized Learnheuristic for Solving the Team Orienteering Problem with Dynamic Rewards

    L. Reyes-Rubiano et al. “A Biased-Randomized Learnheuristic for Solving the Team Orienteering Problem with Dynamic Rewards”. In:Transportation Research Procedia47 (2020), pp. 680–687.doi:10 . 1016 / j . trpro.2020.03.147

    work page 2020

  31. [31]

    A Tabu Search Heuristic for the Team Orienteering Problem

    Huaying Tang and Elise Miller-Hooks. “A Tabu Search Heuristic for the Team Orienteering Problem”. In: Computers & Operations Research32.6 (2005), pp. 1379–1407

    work page 2005

  32. [32]

    Algorithms for a Stochastic Selective Travelling Salesperson Problem

    Huaying Tang and Elise Miller-Hooks. “Algorithms for a Stochastic Selective Travelling Salesperson Problem”. In:Journal of the Operational Research Society56.4 (2005), pp. 439–452

    work page 2005

  33. [33]

    A Learnheuristic Algorithm Based on Thompson Sampling for the Heteroge- neous and Dynamic Team Orienteering Problem

    Antonio R. Uguina et al. “A Learnheuristic Algorithm Based on Thompson Sampling for the Heteroge- neous and Dynamic Team Orienteering Problem”. In:Mathematics12.11 (2024), p. 1758.doi:10 . 3390 / math12111758

    work page 2024

  34. [34]

    The Orienteering Problem: A Survey

    Pieter Vansteenwegen, Wouter Souffriau, and Dirk Van Oudheusden. “The Orienteering Problem: A Survey”. In:European Journal of Operational Research209.1 (2011), pp. 1–10

    work page 2011

  35. [35]

    Optimization Approaches for Solving Chance-Constrained Sto- chastic Orienteering Problems

    Pradeep Varakantham and Akshat Kumar. “Optimization Approaches for Solving Chance-Constrained Sto- chastic Orienteering Problems”. In:Algorithmic Decision Theory. Vol. 8176. Lecture Notes in Computer Science. Springer, 2013, pp. 387–398

    work page 2013

  36. [36]

    Solving the Stochastic Time-Dependent Orien- teering Problem with Time Windows

    C. Verbeeck, P. Vansteenwegen, and El-Houssaine Aghezzaf. “Solving the Stochastic Time-Dependent Orien- teering Problem with Time Windows”. In:European Journal of Operational Research255.3 (2016), pp. 699– 718

    work page 2016

  37. [37]

    Robust Team Orienteering Problem with Decreasing Profits

    Qinxiao Yu, Chun Cheng, and Ning Zhu. “Robust Team Orienteering Problem with Decreasing Profits”. In: INFORMS Journal on Computing34.6 (2022), pp. 3215–3233.doi:10.1287/ijoc.2022.1240

    work page doi:10.1287/ijoc.2022.1240 2022

  38. [38]

    A Priori Orienteering with Time Windows and Stochastic Wait Times at Customers

    Shun Zhang, Jeffrey W. Ohlmann, and Brian W. Thomas. “A Priori Orienteering with Time Windows and Stochastic Wait Times at Customers”. In:European Journal of Operational Research239.1 (2014), pp. 70–79

    work page 2014