mlsanityData to 14 Oct 2026

Learning to Solve Orienteering Problem with Time Windows and Variable Profits

arXiv 2603.06260 ↗First posted 6 Mar 2026cs.LG cs.AIcited by 0

Not on the map. Why?

Abstract (arXiv)

The orienteering problem with time windows and variable profits (OPTWVP) is common in many real-world applications and involves continuous time variables. Current approaches fail to develop an efficient solver for this orienteering problem variant with discrete and continuous variables. In this paper, we propose a learning-based two-stage DEcoupled discrete-Continuous optimization with Service-time-guided Trajectory (DeCoST), which aims to effectively decouple the discrete and continuous decision variables in the OPTWVP problem, while enabling efficient and learnable coordination between them. In the first stage, a parallel decoding structure is employed to predict the path and the initial service time allocation. The second stage optimizes the service times through a linear programming (LP) formulation and provides a long-horizon learning of structure estimation. We rigorously prove the global optimality of the second-stage solution. Experiments on OPTWVP instances demonstrate that DeCoST outperforms both state-of-the-art constructive solvers and the latest meta-heuristic algorithms in terms of solution quality and computational efficiency, achieving up to 6.6x inference speedup on instances with fewer than 500 nodes. Moreover, the proposed framework is compatible with various constructive solvers and consistently enhances the solution quality for OPTWVP.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 41 of its 63 references that are in the map. First posted on arXiv 6 Mar 2026.

Builds on

41 of 63 references.

References · 41

  1. 2021Convex optimizationcited by 2,515
  2. 2018Attention, Learn to Solve Routing Problems!cited by 656
  3. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 348
  4. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 221
  5. 2023Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalizationcited by 142
  6. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 129
  7. 2022Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimizationcited by 119
  8. 2021Learning to Delegate for Large-scale Vehicle Routingcited by 109
  9. 2021NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problemcited by 103
  10. 2021Matrix Encoding Networks for Neural Combinatorial Optimizationcited by 91
  11. 2023GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-timecited by 85
  12. 2022Simulation-guided Beam Search for Neural Combinatorial Optimizationcited by 84
29 more
  1. 2023BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimizationcited by 82
  2. 2023Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Optcited by 81
  3. 2023RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmarkcited by 71
  4. 2024MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Expertscited by 70
  5. 2023Robust Scheduling with GFlowNetscited by 69
  6. 2022Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillationcited by 62
  7. 2023Unsupervised Learning for Solving the Travelling Salesman Problemcited by 58
  8. 2024RouteFinder: Towards Foundation Models for Vehicle Routing Problemscited by 55
  9. 2024Ant Colony Sampling with GFlowNets for Combinatorial Optimizationcited by 53
  10. 2024UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problemscited by 47
  11. 2025Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimizationcited by 45
  12. 2023A GNN-Guided Predict-and-Search Framework for Mixed-Integer Linear Programmingcited by 41
  13. 2023Combinatorial Optimization with Policy Adaptation using Latent Space Searchcited by 41
  14. 2023Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNetscited by 40
  15. 2023Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learningcited by 37
  16. 2024PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimizationcited by 35
  17. 2024Learning to Handle Complex Constraints for Vehicle Routing Problemscited by 29
  18. 2025Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programmingcited by 16
  19. 2025Neural Deconstruction Search for Vehicle Routing Problemscited by 15
  20. 2023Distributed Constrained Combinatorial Optimization leveraging Hypergraph Neural Networkscited by 13
  21. 2023Learning To Dive In Branch And Boundcited by 10
  22. 2023Combinatorial Optimization enriched Machine Learning to solve the Dynamic Vehicle Routing Problem with Time Windowscited by 10
  23. 2024Looking Ahead to Avoid Being Late: Solving Hard-Constrained Traveling Salesman Problemcited by 8
  24. 2023RLOR: A Flexible Framework of Deep Reinforcement Learning for Operation Researchcited by 4
  25. 2024Fast and Interpretable Mixed-Integer Linear Program Solving by Learning Model Reductioncited by 3
  26. 2025Learning Constraints-Based Adaptive Hypergraph Neural Networks for Solving Vehicle Routing Problemscited by 3
  27. 2023Balanced Line Coverage in Large-scale Urban Scenecited by 1
  28. 2024An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problemcited by 1
  29. 2024BaSeNet: A Learning-based Mobile Manipulator Base Pose Sequence Planning for Pickup Taskscited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025A survey of the orienteering problem: model evolution, algorithmic advances, and future directions ↗
  2. 2026N(CO)2: Neural Combinatorial Optimization with Chance Constraints to Solve Stochastic Orienteering
  3. 2026Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular Orienteering
  4. 2024DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems
  5. 2025Solving the Min-Max Multiple Traveling Salesmen Problem via Learning-Based Path Generation and Optimal Splitting
  6. 2025COMPASS: Benchmarking Constrained Optimization in LLM Agents
  7. 2026Step-by-Step Optimization-like Reasoning in LLMs over Expanding Search Spaces
  8. 2025Inverse Optimization Latent Variable Models for Learning Costs Applied to Route Problems