Learning to Solve Orienteering Problem with Time Windows and Variable Profits
Authors: Songqun Gao
Zanxi Ruan
Patrick Floor
Marco Roveri
Luigi Palopoli
Daniele Fontanelli
Venue: ICLR 2026 Poster (2026)
Keywords: Learning to optimize
vehicle routing problem
orienteering problem
Primary area: optimization

Abstract: 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.

Published as a conference paper at ICLR 2026
LEARNING TO SOLVE ORIENTEERING PROBLEM WITH TIME WINDOWS AND VARIABLE PROFITS
Songqun Gao Zanxi Ruan""; Patrick Floor?, Marco Roveri Luigi Palopoli Daniele Fontanelli
'Dpaarmmett of Industrial Engineering. Università di Trento, Trento, Italy Department of Information Engineering and Computer Science, Università di Trento, Trento, Italy 3 $Interdepartmental Robotics Labs (IDRA), Trento, Italy 4 *Department of Engineering for Innovation Medicine, Università di Verona, Verona, Italy 6 Pipple, Eindhoven, Netherlands songqun, gaoßunitn. it, zanxi. ruan@univr.it
ABSTRACT
The orienteering problem with time windows and variable profits (OPTWVP) is common many real-world applications and involves continuous time variables. Current approaches fail to develop efficient solver for this orienteering problem variant with discrete and continuous variables. In this paper, we propose learning- based two-stage DEcoupled discrete-Continus guided Trajectory (DeCoST), which aims to effectively decouple the discrete and continuous decision variables the OPTWVP problem, while enabling efficient and learnable coordination between them. In the first stage, parallel decoding structure employed to predict the path and the initial service time allocation. The second stage optimizes the service times through linear programming (LP) formulation and provides a long-howe 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- constructive solvers and the latest meta-heuristic algorithms in terms of solution quality and computational efficiency, achieving up to 6.6x inference speedup instances with fewer than 500 nodes. Moreover, the proposed framework is compatible with various constructive solvers and consistently enhances the solution quality for OPTWVP.
optimization with Service-time-
INTRODUCTION
The Vehicle Routing Problem (VRP) is one of the most fundamental and extensively studied combi- natorial optimization problems (COP), aiming to determine which nodes to visit and in what order under given constraints. The orienteering Problem (OP), important variant of VRP, assumes fixed total time budget and requires selecting a subset of nodes to visit in order to maximize the total collected reward, which has demonstrated significant potential in practical scenarios such factory scheduling (Gannouni et al. 2020), logistics transportation (Baty et al., (2024), robotic planning (Ding al., 2025 Naik al.) 2024). etc. However, many real-world tasks, the two basic assumptions of the OP often do not hold: fixed rewards and always-accessible nodes. In practice, rewards usually increase with longer service times (variable profit) (Khodadadian al. 2022 Wan et al.) 2204), and many nodes are only accessible within specific time windows (Chen et al. 2024). Thus, the optimizer must decide not only which nodes to visit, but also the service time at each node. These requirements naturally give rise to the Orienteering Problem with Time Windows and Variable Profits (OPTWVP)
(Mrzal & Sebastial 2024 Yu al. 2019), which simultancously involves discrete route planning and continuous service- terrice--immeaee allocation under fixed time budget maximize the total reward. Figure (a) illustrates a representative example of OPTWVP applications.
Compared with classical VRPs, VP represents realistic and challenging class of VRP in which discrete routing decisions and continuous service-time allocations are tightly coupled: Unlike
"Correponniigg authors.

---

Published as a conference paper at ICLR 2026
Problem Setup
How to Endd bestaenice trevn to
lo
l6
ell
H
Hight derarninn optimall Siree?
LOW
Worker ecoupied time
11
Time budget root,
(b)
DeCoST
NCO
Figure I: (a) Application of OPTWVP in industrial scenarios. A manipulator and human collaborating on a defect removal task on the assembly line. The robot has limited time to operate. cannot access the nodes outside the time windows for safety reasons, since the human might have collisions with the robot. Meanwhile, the reward depends on the service time spent handling the defect, with the defect size decreasing linearly over time (Wang et al. 2023). (b) Illustration of the challenge faced by NCO methods in allocating hybrid poecrete-contnuouss decisions and capturing continuous-varibbe representations.
classical VRPs that determine only the routing sequence, OPTWVP requires jointly optimizing the route and the service time spent at each node, because the reward depends directly on service times on vertices. A selected route dynamically shapes the feasible region of service time decisions through travel times and time window constraints, while the allocated service times, in turn, affect the obtained rewards and influence the overall route decisions. This bidirectional dependency prevents the two components from being optimized independently, causing exponential expansion of the joint search space.
At present, the main strategies for addressing OP/VRP variants can be generally divided into heuris- tic/metaheuristicc methods and learning-based neural combinatorial optimization (NCO) methods. Heuristic and metaheuristic algorithms typically follow multistage strategy, where initial feasible solution is first generated and subsequently refined with local search improvements (Nikzad et al., 2023 Frabán-Ramire'
al. 2022, Canca et al. 2024). Although these approaches demonstrate good performance on specific variants, their performances are often heavily limited by manually designed heuristics and exhaustive refinement procedures. On the other hand, the rapidly growing NCO methods (Kool et al.) [019 Kwon et al. (020)) seek to apply learning- beanning-based approaches to increase the search efficiency in classic VRPs. In pursuit of more practical applicability (Bi et al. 2024; Hottung et al.] 2025a: Wang et al.) 2025), more recent studies in NCO also explore VRP variants with constraints. They adopt problem deconstruction methods (Hottung et al., [0025b] Kuang al. 2024) to decompose the original problem by predicting certain number of variables and then performing search/optimizztion within their local neighborhoods. However, most NCO methods focus solely routing, while the joint optimization of routing and service-ting allocation remains under-explored. In these problems, such decomposition leads to shortsighted route predictions that cannot anticipate optimal service times, and the subsequent local adjustments are insufficient to correct the structural biases introduced the first stage. Unlike the above unsupervised NCO methods, current Mixed-Integer Programming (MIP) problem studies provide a similar solution to general MIP problems (Liu et al. 2025 Paulus & Krause 2023 HU et al. 2024), but most of these methods rely on annotated data, which limits their applications. Taken together, for problems like OPTWVP, where discrete routing decisions and continuous service- time allocation are inherently interdependent, achieving an efficient and high-quality solution remains unsolved.
optimization with Service-time -ine--iiie-ggedddd guided Trajectory (DeCoST), a saaming-based two-stage collaborative framework proposed for solving OPTWVP-like problems. Leveraging the structure of OP DeCoST decomposes OPTWVP into a routing problem and a service time allocation problem, which effectively decouples the searching process while enabling efficient and learnable coordination. In the first stage, DeCoST employs parallel decoder that integrates a routing decoder and a service time decoder (STD) to provide a trajectory generation strategy and an initial estimate of service times, which explicitly considers the influence continuous variables on the quality of the solution and provides an initial coordination between discrete path decisions and continuous service time allocations. In the second stage, based
In this paper, we propose DEcoupled
2

---

Published as a conference paper at ICLR 2026
on the fixed discrete path trajectory, the continuous decision variable optimization problem is further simplified to a linear programming (LP) problem. Especially, a service time optimization (STO) algorithm is applied in the second stage to guarantee parallel computation and maximize the total collected reward. We rigorously prove that the STO can obtain the global optimum. In this two-stage approach, we introduce repulsive supervisory index, profit-weighted time allocation ratio (pTTAR,, to provide a feedback signal for service time prediction. By preventing premature convergence to the deterministic conditional optimum, the model preserves flexibility in service-time prediction and improves the overall solution quality.
The overall contributions of this paper are as follows.
(I) We propose DeCoST, a learning-basee crete routing decisions and continuous service-time allocations are decomposed, realizing the joint optimization of routing and service time under the constraints of time windows and variable profits.
two-stage approach for solving OPTWVP, where dis-
(2) By leveraging parallel computation of STO and the cross- stage feedback mechanism, the proposed two-stage approach provides global long-bu horizon structure estimation in the early route decision stage, enabling us to search the route and service time efficiently.
(3) We conduct thorough experiments demonstrating that the proposed method outperforms not only existing sate-of-the-ard (SOTA) NCO approaches but also the latest metaheuristic algorithms in both solution quality and computational efficiency.
2 RELATED WORK
Heuristic and Meta- Heuristic Optimization of COPs with Time Constraints. Traditional heuris- tic and metaheuristic approaches typically employ a multistage strategy to solve COP variants with varying profits (Marzal & Sebastia 2024 Wan et al. 2024] Nikzad et al. 2023 Lamban-Ramirez et al. 2022, Canca et al.) 2024, Panadero et al.) 2022] Evers et al. 2014). Initially, greedy strategies are used to construct initial heuristic solutions, which are then refined through active search algorithms (Marzal & Sebastia 2024). Yu et al. (2019) also introduces a multi-phase approach to separately handle discrete and continuous decision variables. Although effective specific problems, these methods face inherent challenges in solving OPTWVP-like problems: they depend on manually designed heuristics. Moreover, any route change reshapes all nodes' feasible service-time intervals, which affects the overall objective. As a result, local operations cannot be evaluated using local information, and each neighborhood operation requires exhaustively solving continuous subproblems.
Neural Combinatorial Optimization. Recent advances in NCO methods have focused primarily
on improving solution quality (Kwon et al. 2021; Guo et al. 2024 Zhang et al. (023b),, scalability
(Qiu et al.) 2022 Ye et al., 2024 Zheng et al. 2024
Luo al. 2023 Li et al.) |021 [uu et al.)
2023
and generalizart lization (Kool et al., 2019; Kwon et al.
et al. 2023 Zhang et al. 2023a
Zhou et al. 2024 Berto et al. [025a Wan at. 2023 Kim et 2022 Drakulic et al.) 2023 Li al.
2025a Bi et al., 2022] Berto et al. 2025b). NCO approaches can be categorized into autoregressive
(AR) and -ooreerooreeesssvve (NAR) methods. AR methods adopt an end-to-end generative approach to solve COPs (Chalumeau et al. 2002). In contrast, NAR methods (Ma et al., (023) focus on learning structural information directly to guide the construction of solutions (Min et al. 2023, Xin al.. 2021: Sun & Yang 2023] Li et al. (224) by generating intermediate representations, which are then used to guide meta-heuristic algorithms (Heydaribení et al., 20224) Choo el al. 2022). However, these algorithms are not directly applicable because they lack the ability to effectively handle constraints.
NCO with Constraints. Recent NCO studies incorporate exploring more realistic and complex constraints in variants of COPs (Huang et al. 2023). For example, time-window constraints have been introduced in COP formulations (Chen et al. 2024 Bi et al. (024), where multistep estimation strategies are adopted to ensure feasibility. byperg approaches are also applied to deal with constrained COPs (Wang et al. 2025). However, most NCO methods focus solely on routing, while the joint optimization of routing and service-time allocation remains under-explored, leading to shortsighted routing that overlooks nodes' interconnection with service times. In MIP settings. coupled conerrte- decision variables are dealt with through model reductions approach (Li et al. 2025b), hybrid reinforcement learning (Zhang et al. 2024), contrastive learning (Han et al.
3

---

Published as a conference paper at ICLR 2026
Stage
Stage 2
Linear
Dicoder
Routing
Optimization
Service Time
Pretectu
as
Coocina
Oodare
SEEAR -frank srammtt)
Service Time Optimization
Procpaiin
1 22
4- 46
Figure 2: An overview of the DeCoST approach. The upper part illustrates the two-stage collaborative optimization process, while the lower part presents the details of the STO Algorithm
2023 Huang et al. 2024) and However, most of these methods rely on annotated data, which limits their generalization scenarios without supervised data.
PRELIMINARIES
undirected complete graph E(V,E) with n vertices, where fei, ji E V). The vertex Up represents the start depot and the end depot. All vertices U, and f/ E V are connected by the edge ei,,, and the corresponding travel time from node i to node j is denoted as 4ig. r V + R is the reward function associated with each vertex. The OPTWVP aims to find path 7 = {uD, (1), ..... (((-2), 2n (of length 1) and the corresponding service time d E R., where all intermediate vertices e) E V \ {vo} } are visited only once, and maximize the total reward Egjer r(v,) collected along the path T, subject to:
An OP instance can be explained
V == fuo. "1, 1n
Time limit: The total travel and service time must not exceed the given time limit max,;
(2) Service time boundaries: The service time d, of each visited vertex must satisfy d,
(0, di max];
(3) Time window constraints: The start time s; of each visited vertex must lie in the time window [sT s5 i.e., 8, E s;];
(4) Time varying profits: Each vertex has a corresponding unit profit p.. The profit of each vertex related to the service time d, and the unit profit p. of the node, which is defined by [(d, p:)
p:dk
Several classical OP variants, including the OP, OP with variable profits (OPVP), and OP with time windows (OPTW), are special cases of OPTWVP See Appendix C for details and mathematical representation of OPTWVP (Maraal & Sebastia 2024).
4 METHODOLOGY
To enable the adoption of RL techniques, we cast the OPTWVP as constrained Markov Deci- sion Process (CMDP) defined by the tuple AS, P,C, R). S is the infinite state space and A denotes the infinite action space. Each state o, E S encodes the previous actions {00, a............ ). where an action a, (v()) /d.tt//tt max) E A includes discrete number indicating the selec- tion of the vertex and a continuous number åd, E [0 C IR indicating the normalized service time ratio at the vertex v;, where ōd,(s) /do0/d((t)
P the transition probability func- tion, C(a,a, a) = [c](a, a), Cren (a, aT is the set of corresponding constraint functions and d(T, El=i Prin d denotes the cumulative reward of the given trajectory and the corre-
4

---

Published as a conference paper at ICLR 2026
sponding service time d, where denotes the number of constraint functions defined for each vertex.
Pott is the unit profit of vertex w(t), and dr60 is the service time.
The objective of CMDP is to learn a policy zo : - P(A) that maximizes the overall reward:
max
(T( ( [R( d
We
(1)
S.L. E Il. II. [ as) 3 0, S,
where J, is the expected return, and IT denotes the set of feasible policies satisfying all VP constraints. At each step i, the action is sampled from the policy Ty. We denote this sampling process compactly as (T, d) ~ Te, where both the path and service allocation are jointly generated by the policy. The overall policy Te is trained by REINFORCE (Williams 1992) using the following loss function:
1 Σ (R(T, b) log( M
==
where b 1/4 EE R(T, dlg) denotes the average reward of the trajectories among M batch samples.
To address the inherent interdependency between discrete routing decisions and continuous service- time allocation, we propose a two-stage DeCoST framework to decompose and coordinate the path selection and service time allocation. As shown in Figure in the first stage, DeCoST employs parallel decoder that integrates a routing decoder and an STD to provide path generation strategy and an initial estimation of service times, which jointly generate the discrete continuous action pair a, used during path construction. In the second stage, based on the fixed discrete path trajectory, the service time allocation problem simplified into an I.P problem, which is efficiently solved by STO. Given the initial service times d in the first stage and the optimal service time d' in the second stage, pTAR loss of a and d' are calculated to encourage STD to broadly explore policies, thereby enabling an early and reliable estimation of problem structure and improving the first-stage service-time prediction. The following sections introduce the specific design of the two-stage optimization process and the service time supervision mechanism.
discrete-continuuss
4.1 TWO-STAGE OPTIMIZATION
Determine the feasible trajectory. In the first stage, the policy vo uses a parallel decoder structure with a route decoder and an STD. The route decoder selects the next node to visit, while the STD simultaneously predicts the corresponding service time. Together, they generate a feasible trajectory 7 along with the corresponding service times d.
Two techniques are integrated into the generation process to improve the quality of the constructed solutions and ensure their feasibility: spatial encoding for structural awareness and feasibility masking for time window constraints. These enhancements enable the model to capture graph connectivity better while avoiding infeasible decisions during trajectory construction.
Spatial encoding (Ying et al. 202T) is applied to the solver to incorporate edge features. Therefore. the solver not only encodes node features, but also encodes edge features (node distances) as an attention bias, thereby improving the model's understanding of the graph structures and enabling the model to pay more attention to node combinations with lower costs and denser connections.
In addition, similar to Bi et al. (024), feasibility masking is applied to guarantee the feasibility of the generated trajectory: the mask dynamically excludes candidate vertices that would violate constraints in one of the following two cases: i) When adding the time limit mar, is impossible. ii) When the start time of the next vertex exceeds its time window. By incorporating feasibility masking, the model is guided to construct only feasible trajectories in the first stage, which significantly reduces the search space.
vertex and returning vo within
The feasible trajectory is subsequently fixed in the second stage, allowing the decoupling of the discrete routing variables and the continuous service times.
Service time optimization. Given the fixed trajectory, in the second stage, OPTWVP is decomposed into decoupled continuous I.P problem that maximizes the total collected rewards. The second
5

---

Published as a conference paper at ICLR 2026
Algorithm 1 Service time optimization algorithm
Input: Trajectory т, distance matrix t, time windows (s s*)), max service time dmax. limited time max,.
Output: Optimal service time allocation d", optimal total reward r*
1: Initialize: trajectory length I, service duration f- O, start time s t- 0 (1 [s initialization
2: do 0, 0,
3: for io = 0 to 2 do
4: 8i+1
max + 1,+1, 1 // start time update 5: sorted f From high to low, sorted indices of nodes in T.
6: for all i sorted do
7: d; = min max, min ++++
ンj= رi Dj=1 (++))))
8: for - + 1 to
do
9:
8) f m- + d--1 + tj. 57 // start time update
10: d' + d. t s, R + p'd
stage service time optimization problem, expressed in matrix form, is given follows:
p' d.
max
s.d
s.t.
s <s
(3)
0 s d < dmaxs
(I - U's +
where p = P1-1) d = [4.....4-11]
dmax = di max............................. d1-1 max], s [so...... 81-1 s = [sp ....... $T-1 IT. s* = [sp ...,, s t= [ta...., E R' respec- tively denote profit, service time, maximum service time, start time, start, end of time window and travel time in the selected trajectory т. I and E / are the identity matrix and the upper shift matrix, and denotes the trajectory length.
1-11T
An STO algorithm introduced that performs parallel computation to obtain the optimal service-time allocation, shown in Algorithm[] The algorithm first constructs feasible solution, then iteratively selects the vertex with the highest reward and assigns a service time that satisfies both the end of time-window constraints and the maximum service-time limit. The start times of subsequent nodes are updated accordingly. The procedure terminates once the overall time budget max, is reached.
Theorem hereafter states the optimality of the solution computed by Algorithm
Theorem 4.1. The service time optimization algorithm shown in Algorithm 7 returns optimal solution (s*, d') ) to the service time scheduling problem specified in Equation
The proof of this theorem can be found in Appendix A
4.2 SUPERVISED LEARNING OF SERVICE TIME DECODER
Although the trajectory T and initial service time have been constructed through the constructive solver, and a of optimal service times have been further calculated, the quality of initial service time allocation has decisive influence on the quality of the final solution. This results from significant trade-off in how the total time budget allocated between travel and service. Improper service time allocation may lead to two extreme situations: (1) Low service time: The model prefers to access more vertices, but each node is underserved, resulting in a potential low reward; (2) High service time: Although the reward of a single vertex is increased, more optional nodes are sacrificed, which might reduce the overall reward.
This indicates that inappropriate travel-service time allocation critically damage the quality of the solution. To learn the trade-off between travel time and service time allocation and better guide the policy of the initial service time assignment, learnable metric, named the profit-weighter time allocation ratio (pTAR), is introduced. is defined by the sum of profit-weighted service times p,d, versus travel times & of the vertices in the trajectory
Σ p:d
pf AR(d)
4
SE

---

Published as a conference paper at ICLR 2026
The pTAR metric reflects the profit efficiency of a solution, measuring how much total reward is achieved per unit of travel cost. A higher p'TAR value indicates a strategy that focuses more on rewarding regions with lower travel expense, which correlates with the quality of the constructed trajectory. To prevent the model from overfitting to the I.-deeriedd conditional optimum, a repulsive supervisory loss is further defined as:
AR - -pT - pfT AR()))))
(5)
REINFORCE (Williams) 1992) trains the policy na, and the overall loss function is designed as summation of REINFORCE loss and the supervisory loss of service time, expressed as:
Liotal B,L P2C
(6)
where B1, denotes the tuning parameter.
EXPERIMENTS
Implementation details. We conduct experiments on the OPTWVP benchmark, typical VRP with continuous time constraints. The methods are tested on the datasets with different time window sizes (TW 100 and TW- 500) and node numbers (n = 50, n 100, and л - 500). The training set has 10000 instances for each dataset, and the test set has 10000 instances for n = 50 TW = 100, 100 TW- 100, and 100 instances for the others. The network is trained for 800 epochs. with an early stop strategy of stopping when there is no improvement for 100 epochs. We implement the proposed approach in Python using the PyTTorcc library. All runtime experiments are performed on a laptop with NVIDIA GeForce RTX 4070, Intel (R) Core(TM) i7 CPU 2.20GHz to ensure consistency, while all score experiments are performed on both the laptop and a server with NVIDIA GeForce RTX 5090 GPU, AMD Ryzen 9 9950X 16-Core Processor to confirm robustness across platforms. Please refer to Appendix D
for more details on the implementation. The code is publicly available at https: qi thub. c SwwnGaw DeeeiaaaaDDeeSSIT DeCoST
Baselines The proposed approach is compared with three types of baselines: 1) Commercial optimization tool: Gurobi (Gurobi Optimization, LLC, 2024). which implements the branch and cut (B&C) algorithm to obtain the exact solution. 2) Meta-heuristic algorithms: Preedy-Profit ratio search (Greedy-PRS) a two-stage greedy heuristic that first determines a route by selecting nodes based on the highest unit profit and then optimizes service times using PuLP (Mitchell et al. 2011) without altering the route; Incremental local search (ILS) (Marzal & Sebastia 2024), a metaheuristic search algorithm that implements fast first solution and local search. 3) Learning- boarenng-bbaed solvers: Since there are no current NCO methods to solve OPTWVP, we implemented greedy methods and our two-stage approach deal with service time in POMO (Kwon et al.. 2020) and GFACS (Kim et al., 2025).
Evaluation metrics. Three metrics are adopted to evaluate the performance of the methods: 1) Score: the average total collected rewards of the solutions within the test sets. 2) Gap: Gap = (R" - R)/R* x 100% denotes the average optimality gap between the optimal reward R" w.r.t. the strong baseline Gurobi (Gurobi Optimization, LLC, 2024) and the reward R obtained within the test sets. Gurobi is set to run until the global optimum proven, ensuring that the computed Re corresponds to the exact optimal solution. 3) Runtime: The average runtime denotes the average inference time required to find a solution for the instance within the test sets. For the ILS method, the reported runtime corresponds to the time to reach the reported score within the search time limit, which is set to 10 seconds.
5.1 PERFORMANCE ON SOLVING OPS WITH TIME CONSTRAINTS
To comprehensively evaluate the performance of the DeCoST framework on the extended VP problem, we compare it against several representative baselines, with results summarized Table The results show that DeCoST consistently achieves strong performance in all settings. It outperforms other heuristic and NCO methods in terms of solution quality (Score and Gap), while maintaining high computational efficiency. Adding the STO module significantly improves the NCO methods. For example, GFACS with STO reduces the gap from 13.4% to 3.38% in the setting n = 100, TW 100. The increased runtime (up to 6760ms) is mainly due to the non-autoregressive structure
7

---

Published as a conference paper at ICLR 2026
Table 1: Performance comparison OP under different problem sizes and time window settings. Bold values denote the best performance in each setting, and underlined values denote the second-best. Category C refers NCO methods, and H refers heuristic baselines. The default unit for runtime is milliseconds (ms).
50, TW
100
100, TW
100
Cat.
Method
Score 1
Gap
Runtime
Score
Gap 4
Runtime
B&C
15.2
0.00%
200
26.1
0.00%
1023
Greedy-PRS
12.9
15.7%
44
21.9
16.2%
48
H
ILS
14.5
4.34%
2109
24.9
4,2%
7122
GFACS (Greedy)
11.1
25.7%
94.2
22.6
13.4%
98.2
GFACS
12.3
18.6%
4310
25.2
3.38%
6760
C
POMO
11.3
25.3%
46.6
11.5
55.7%
$2.3
DeCoST (Ours)
15.1
1.06 %
94.0
25.6
1.97%
158
Cat.
Method
71
50, TW
500
100, TW
500 Runtime +
Score f
Gap 4
Runtime +
Score
Gap 4
B&C
51.9
0.00%
1346s
>24h
GreSdy-PRS
46.1
11.4%
46.1
79,7
51
ILS
47.8
7.82%
1262
85.0
8441
GFACS (Greedy)
35.21
31.7%
89.8
60.5
GFACS
47.4
8.57%
6950
84.4
8750
C
POMO
31.3
39.6%
40.7
54,6
60.6
DeCoST (Ours)
51.4
0.83% %
60.4
88.1
100
Table 2: Performance OPTWVP with large-scale configuration (n 500, TW 100). Bold
values indicate the best result.
Method
Score 1
Gap +
Runtime (ms) $
B&C
82.3
0.00%
68400
Greedy-PRS
69.6
15.6%
60
ILS
78.2
4.98%
8803
GFACS (Greedy)
67.4 .7.4
18.1%
112
GFACS
73.1
11.3%
9420
POMO
58.6
28.8%
747
DeCoST (Ours)
79.6
3,31 %
1329
of GFACS, which limits the batch parallelism of STO and forces more frequent optimization of single instances. Although runtime rises, the substantial increase solution quality demonstrates that precise optimization of service time is crucial for achieving better solution. To ensure fair comparison, the STO module is only integrated into NCO frameworks, which lack native mechanisms for service time allocation. We do not apply STO heuristic baselines like ILS Greedy-PRS. as they already incorporate built-in optimization strategies. Compared to strong meta-heuristic baselines like ILS, DeCoST yields better comparable solution quality and improves inference efficiency by factor of 20 to 45. We also include supplementary experiments on comparison with ILS with search time limit 10s Appendix B.I
DeCoST also demonstrates strong performance and scalability in solving large-scale OP instances. For instance, with 500, as shown in Table 2 DeCoST maintains high solution quality while requiring only 1329ms average siinificannnlllly faster than ILS, which takes 8803ms. Although slight degradation in solution quality expected as the problem size increases-an common trend in combinatorial optimization, DeCoST consistently outperforms all competing baselines.
Figure reveals the distribution of the optimality gap of different methods under different settings (Refer to Appendix B.2 for more details). It can be observed that DeCoST shows the smallest optimality gap in all settings, with a low box height and fewer outliers, indicating that the method always maintains high solution quality and consistency multiple instances and has significant stability.
Finally, also include extension experiments Team OPTWVP, sensitivity analysis with respect to cost function parameters, performance evaluation on initial service times, efficiency study of pTAR loss in Appendix B.3 B.4
B.5
and B.6 respectively.
8

---

Published as a conference paper at ICLR 2026
n:- 56, 100
m 56, TW7 500
16
100, TW 1.00
100, TW 500 56
24
26
18
Figure 3: Boxplot of the optimality gap under different problem sizes and time window settings.
Table 3: Ablation study on DeCoST (n 50). Bold numbers denote the best in each block (TW).
Method Setting
STO
SL
Score
Gap
Runtime (ms)
TW 100
Baseline
x
X
11.3
25.3%
46.6
Baseline SE
23.0%
Baseline SE STO
x
14.9
2.28%
77.5
DeCo8T (ours)
15.1
1.06%
94.0
TW 500
Baseline Baseline SE Baseline SF STO DeCoST (ours)
39.6%
40.7
x
35.5
31.2%
39.9
x
50.9
1.88%
55.6
51.4
0.83%
5.2 PERFORMANCE ON DECOST WITH MODULE ABLATIONS
Table shows the ablation results of the three components in the DeCoST framework: the spatial encoder (SE) that incorporates node-edge features, the STO module, and the supervised loss (SL) guided by our proposed pTAR metrie. Experiments are conducted shown in the results, the baseline model (without any of the three modules) performs the worst, with Gap values reaching 25.3% and 39.6%. Introducing the SE module yields moderate performance gains without noticeable runtime overhead, indicating the positive impact geometric structure encoding on routing decisions. However, the most substantial improvement comes from the STO module, which significantly reduces the Gap to 2.28% and 1.88% under the two settings, with only about 30ms of additional runtime. When further augmented with the SL module, the Gap decreases to 1.06% and 0.83% in the TW = 500 setting, demonstrating that supervised guidance from pTTAR can further refine the allocation of service time and improve the quality of the solution. In summary, STO plays decisive role in improving performance, while SE and SL provide complementary enhancements. The synergy among the three components enables DeCoST to deliver near-optimal solution quality with minimal inference time, validating the effectiveness and coherence of the overall design.
two time window settings. As
5.3 PERFORMANCE ON SOLOMON 100
We also evaluated DeCoST with ILS on the data set Solomon 10d widely used standard dataset the vehicle routing problem. with the same configuration of (Marzal & Sebastia 2024). The Solomon100 dataset consists of 1ol-node TOPTW VP instances. Due to the limited number of available samples, we select 29 instances for training and instances for testing, with a training schedule of 1000 epochs. The training and validation batch sizes are set to 2 and 1, respectively. The performance is summarized in Table DeCoST consistently outperforms ILS on this real-world dataset under both 10 and 20 s time limits. Notably, DeCoST achieves high-quality solutions approximately 34.5 times faster inference speed compared to IL..
Table 4: Performance comparison on OPTWVP on Solomon 100.
Method
Score
Gap
B&C
ILS (T=10<)
9846.3
-7.8%
ILS (T=20s)
10616.9
-0.59%
DeCoST (T=0.29s)
10680.3
CONCLUSION AND FUTURE WORK
This paper proposes a two-stage DeCoST framework to explicitly decouple discrete and continuous decision variables for the OPTWVP: the first stage fixes the routing trajectory and the second stage
http::///www..n....oooo/o//////a benchmankk

---

Published as a conference paper at ICLR 2026
optimizes the service times through STO. A mathematical proof demonstrates the global optimality of the second-stage solution. Furthermore, a repulsive supervisory metric, pTAR, incorporates optimal service times into the first-stage trajectory decision to learn a global ongghhoizzon structure estimation, thereby improving the overall quality and efficiency of the solution. Experiments on OPTWVP instances demonstrate that the proposed method outperforms both state-of-the-ar NCO methods and the latest meta-heuristic algorithms in terms of solution quality and computational efficiency. Although our method demonstrates strong accuracy both AR and NAR solvers, limitation arises when integrating with NAR approaches: the lack of batch processing limits STO's parallelism, thereby impacting overall efficiency. Future work will focus on improving computational efficiency in such settings and extending the framework to more general vehicle routing scenarios.
ACKNOWLEDGMENTS
Co-funded by the European Union under the EU HE Magician Grant Agreement 101120731. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Commission. Neither the European Union nor the granting authority can be held responsible for them.
ETHICS STATEMENT
This work complies with the ICLR Code of Ethics. We did not involve human subjects or personal data. All datasets are publicly available and used under their original licenses. For more details about the datasets. please refer to Appendix E Our study does not target sensitive attributes and poses no foreseeable risks beyond the usual limitations of machine learning research. We have no conflicts of interest or external sponsorship to declare. For transparency and reproducibility, we provide an anonymized code repository with all configuration files.
REPRODUCIBILITY STATEMENT
All datasets used are publicly accessible, enabling full reproduction of our results. We report all training and evaluation details and hyperparameters in the paper. We also provide code repository https: /ttpthub..tttt////// comm/Swndao//DeCool
REFERENCES
Léo Baty, Kai Jungel, Patrick S. Klein, Axel Parmentier, and Maximilian Schiffer. Combinatorial optimization-ennicheed machine learning solve the dynamic vehicle routing problem with time windows. Transportation Science, 5884):708-725, 2024.
Federico Berto, Chuanbo Hua, Junyoung Park, Laurin Luttmann, Yining Ma, Fanchen Bu, Jiarui Wang, Haoran Ye, Minsu Kim, Sanghyeok Choi, Nayeli Gast Zepeda. André Hottung, Jianan Zhou, Jieyi Bi, Yu Hu, Fei Liu, Hyeonah Kim, Jiwoo Son, Haeyeon Kim, Davide Angioni, Wouter Kool, Zhiguang Cao, Qingfu Zhang, Joungho Kim, Jie Zhang, Kijung Shin, Cathy Wu, Sungsoo Ahn, Guojie Song, Changhyun Kwon, Kevin Tiemey, Lin Xie, and Jinkyoo Park. RI4co: An extensive reinforcement learning for combinatorial optimization benchmark. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2, KDD '25 pp. 5278-5289, New York, NY, USA, 2025a. Association for Computing Machinery. ISBN 9798400714544 145422
Federico Berto, Chuanbo Hua, Nayeli Gast Zepeda, André Hottung, Niels Wouda, Leon Lan, Junyoung Park, Kevin Tierney, and Jinkyoo Park. Routefinder: Towards foundation models for vehicle routing problems. Transactions Machine Learming Research, 2025b. ISSN 2835-8856. URL httpthtppss/ppppeeeeee
net /ttp///r////// forum? 0 1d=gzGloa0FFF
Jieyi Bi, Yining Ma. Jiahai Wang, Zhiguang Cao, Jinbiao Chen, Yuan Sun, and Yeow Meng Chee. Learning generalizable models for vehicle routing problems via knowledge distillation. In Al- ice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https: http::::/pppeevveeeee net ffo.umidrdd
BOVNpURgKMM.
10

---

Published as a conference paper at ICLR 2026
Jieyi Bi, Yining Ma, Jianan Zhou, Wen Song, Zhiguang Cao, Yaoxin Wu, and Jie Zhang. Learning to handle complex constraints for vehicle routing problems. In The eighth Annual Confer- ence Neural Information Processing Systems, 2024. URL httpttts//pppeeeeeaiiiieeee forum?
d= do-ut
95ZuR jP.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, Cambridge, 2004.
David Canca, Eva Barrena, and Gilbert Laporte. Arrival and service time dependencies in the single- and multi-visit selective traveling salesman problem. Computers Operations Research, 166: 106632, 2024. ISSN 0305-0548.
Felix Chalumeau, Shikha Surana, Clément Bonnet, Nathan Grinsztajn, Arnu Pretorius, Alexandre Laterre, and Thomas D Barrett. Combinatorial optimization with policy adaptation using latent space search. In sevethh Conference Neural Information Processing Systems, 2023. URL
wwtp:/wwwwwww.e........ee feet/foorm?id VpMBaqt 9H1
Jingxiao Chen, Ziqin Gong, Minghuan Liu, Jun Wang, Yong Yu, and Weinan Zhang. Looking ahead to avoid being late: Solving hard-constrained traveling salesman problem. ArXiv, abs/2403.05318, 2024.
Jinho Choo, Yeong-Dae Kwon, Jihoon Kim, Jeongwoo Jae, André Hottung, Kevin Tiemey, and Youngjune Gwon. Simulation-guie beam search for neural combinatorial optimization. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances Neural Information Processing Systems, 2022. URL https:///////.... pettps://openevee /wpporpppeeviiiooeeee wwweeview.... ew net wttpe/iwwwweeeeotreeeeeeeee forummrrrm i== EYASIRpys5
Tong Ding, Lei Liu, Zhongmin Yan, and Lizhen Cui. Enhancing sustainable data collection with unmanned aerial vehicles: A deep reinforcement learning approach. IEEE Internet of Things Journal, 12(5):4657-4666, 2025.
Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Mare Andreoli. BQ-NCO: Bisimu- lation quotienting for efficient neural combinatorial optimization. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https:tp////// /ttpss://opeteeeeee..eeeee ntt/ forum?
id Bd=BRRlkee kTDvvm
Lanah Evers, Kristiaan Gloric, Suzanne van der Ster, Ana Isabel Barros, and Herman Monsuur. A two-stage approach the orienteering problem with stochastic weights. Computers & Operations Research, 43:248-288 2600, 2014. ISSN 0305-0548.
Aymen Gannouni, Vladimir Samsonov, Mohamed Behery. Tobias Meisen, and Gerhard Lakemeyer. Neural combinatorial optimization for production scheduling with sequence-dependen setup waste. In 2020 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pp. 2640-26477 2020.
Runze Guo, Feng Xue, Anlong Ming, and Nicu Sebe. An efficient learning- based solver comparable to metaheuristics for the capacitated are routing problem, 2024. URL htll:tt:::0 httpttps://axxi...om //tgg/.rig.o/////////// 0bs/2403.07023
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024. URL https: /www gurobi com
Qingyu Han, Linxin Yang, Qian Chen, Xiang Zhou, Dong Zhang, Akang Wang, Ruoyu Sun, and Xiaodong Luo. A GNN-guided predict-and-search framework for mixed-integer linear program- ming. In The Eleventh International Conference on Learning Representations, 2023, URL net forum
Nasimeh Heydaribeni, Xinrui Zhan, Ruisi Zhang, Tina Eliassi- and Farinaz Koushanfar. Dis- tributed constrained combinatorial optimization leveraging hypergraph neural networks. Nature Machine Intelligence, 6(6):664 2024.
André Hottung, Mridul Mahajan, and Kevin Tiemey. Polynet: Learning diverse solution strategies for neural combinatorial optimization. In The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025. OpenReview.net, 2025a.
11

---

Published as a conference paper at ICLR 2026
André Hottung, Paula Long-Chung, and Kevin Tiemey. Neural deconstruction search for vehicle routing problems. Trans. Mach. Learn. Res., 2025, 2025b.
Xinyi HU, Jasper C.H. Lee, Jimmy H.M. Lee, and Peter J. Stuckey. Multi-stage predict+optinize for (mixed integer) linear programs. In The ehihty- Annual Conference on Neural Information Processing Systems, 2024, URL tattps::/opennee
wttpriiwwweeeeeeeeeeeeeeeeeee mett/oorumiic pXF iH
Taoan Huang, Aaron Ferber, Yuandong Tian, Bistra Dilkina, and Benoit Steiner. Searching large neighborhoods for integer linear programs with contrastive learning. In Proceedings of the 40th International Conference on Machine Learning, ICML'23. JMLR.org. 2023.
Taoan Huang, Aaron M Ferber, Arman Zharmagambetov, Yuandong Tian, and Bistra Dilk- ina. Contrastive predict-and-searde for mixed integer linear programs, 2024. URL https
jUAOOL jUAOth
YUAN JIANG, Zhiguang Cao, Yaoxin Wu, Wen Song, and Jie Zhang. Ensemble-based deep reinforcement learning for vehicle routing problems under distribution shift. In A. Oh, T. Naumann, A. Globerson, Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 53112-53125. Curran Associates, Inc., 2023.
M. Khodadadian, A. Divsalar, C. Verbeeck, A. Gunawan, and P. Vansteenwegen. Time dependent orienteering problem with time windows and service time dependent profits. Computers & Operations Research, 143:105794, 2022. ISSN 0305-0548.
Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-NCO: Leveraging symmetricity for neu- ral combinatorial optimization. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL httpps://openreviee net htte:/ofoommmmd==/22200
Minsu Kim, Sanghyeok Choi, Hyeonah Kim, Jiwoo Son, Jinkyoo Park, and Yoshua Bengio. Ant colony sampling with GFlownets for combinatorial optimization. In The 28th International Conference on Artificial Intelligence and Statistics, 2025. URL
Forum? "oorum?dd=XYJsAg7TTX
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019.
Yufei Kuang, Jie Wang, Haoyang Liu, Fangzhou Zhu, Xijun Li, Jia Zeng, Jianye HAO, Bin Li, and Feng Wu. Rethinking branching on exact combinatorial optimization solver: The first deep symbolic discovery framework. In The Twelfth International Conference Learning Representations, 2024. URL httt:t://opeereiieee net wtt.://www..eeeoooddddd--d- jKhNBulMKKhBBuNM
Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: policy optimization with multiple optima for reinforcement learning. In Proceedings the 34th International Conference on Neural Information Processing Systems, NIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 978171382955 1329546..
Yeong- -ee Kwon, Jinho Choo, Iljoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. In A. Beygelzimer, Y. Dauphin, P. Liang, and Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL net
https: Nttpss//openreviie httpeewwwwweetttteeeeeeeeeee forum?id-4
ChZs8ki0
Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate for large-scale vehicle routing. In Proceedings of the 35th International Conference Neural Information Processing Systems, NIPS '21, Red Hook, NY, USA, 2021. Curran Associates Inc. ISBN 9781713845393.
Yang Li, Jinpei Guo, Runzhong Wang, Hongyuan Zha, and Junchi Yan. Fast t2t: Optimization consistency speeds up diffusion- based training-to- to-testing solving for combinatorial optimization. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL htttps://opense net http://wwww...eeooooooo/o///////
12

---

Published as a conference paper at ICLR 2026
Yang Li, Jiale Ma, Wenzheng Pan, Runzhong Wang. Haoyu Geng, Nianzu Yang. and Junchi Yan. ML4TSPBench: Drawing methodological principles for TSP and beyond from streamlined de- sign space of learning and search. In The Thirteenth International Conference Learning Representations, 2025a. URL httpp:::/pppeeeeiiiiis
net forrmoormmmm///mo d= VKEOLL
Yixuan Li, Can Chen, Jiajun Li, Jiahui Duan, Xiongwei Han, Tao Zhong, Vincent Chau, Weiwei Wu, and Wanyuan Wang. Fast and interpretable mixed-inted linear program solving by learning model reduction. In Proceedings of the Thirty-Ninth AAAI Conference on Artificial Intelligence and Thirth-Sevetth Conference on Innovative Applications of Artificial Intelligence and Fifteenth Symposium on Educational Advances in Artificial Intelligence, AAAI25/AAII2SSAATT AAAI Press, 2025b. ISBN 978-1-57735-899 -77-8-897--8
Haoyang Liu, Jie Wang. Zijie Geng, Xijun Li, Yuxuan Zong, Fangzhou Zhu, Jianye HAO, and Feng Wu. Apollo-MILP: An alternating prediction-correction neural solving framework for mixed-integer linear programming. In The Thirteenth International Conference Learning Representations, 2025. URL Utt.htts::// /ttp:://///eeeeeeeee/ee net/ fow.mrirrddiioemoe d0mm:m11m=mFm0mmmm POtt
Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. In Thirty- Conference on Neural
Information Processing Systems, 2023. URL https::/ htttts://openreveww.rto RBI 4oAbdpm
forum?id
Yining Ma, Zhiguang Cao, and Yeow Meng Chee. Learning to search feasible and infeasible regions of routing problems with flexible neural k-opt. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https: fictps://openreviiet wwrpeereeiiee.nee/oooniiiiiiiiie dtw.oouummmiid-iuukkkk JukwH2yP
Eliseo Marzal and Laura Sebastia. Solving the tourist trip design problem with time windows and variable profit using incremental local search. Applied Soft Computing, 155:11 1 1399, 2024. ISSN 1568-4946.
Yimeng Min, Yiwei Bai, and Carla P Gomes.
Unsupervised learning for solving the travelling salesman problem. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL
wwtp:eewwwwwwweeeeeeeeeeeeeeeeee wwwpeeet//ttiiioeeeeeeeeeeoooeee Balld-AABccaaa 1ABc7aIW20
Stuart Mitchell, Michael O' Sullivan, and lain Dunning. Pulp: A linear programming toolkit for python. Technical report, The University of Auckland, Auckland, New Zealand, 2011.
Lakshadeep Naik, Sinan Kalkan, Sune L. Sørensen, Mikkel Kjærgaard, and Norbert Krüger Basenet: A learning- based mobile manipulator base pose sequence planning for pickup tasks. In 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 3666-3673, 2024.
Erfaneh Nikzad, Mahdi Bashiri, and Babak Abbasi. Home healthcare staff dimensioning problem for temporary caregivers: matheuristic solution approach. Computers & Operations Research, 152: 106126, 2023. ISSN 0305-0548.
Javier Panadero, Eva Barrena, Angel A. Juan and David Canca. The stochastic team orienteering problem with desidion- rewards. Mathematics, 10(16), 2022.
Max B. Paulus and Andreas Krause. Learning to dive in branch and bound. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL
nett/Eorun2ico-111PPhOo
Andrea Pirabán-Ramírez, William Javier Guerrero-Rueda, and Nacima Labadie. The multi-trip vehicle routing problem with increasing profits for the blood transportation: An iterated local search metaheuristic. Computers & Industrial Engineering, 170:108294, 2022. ISSN 0360-8352.
Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. DIMES: A differentiable meta solver for com- binatorial optimization problems. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL /ttp::///peeeeeeeeee net hwwp:/rrtttotmeee.e wwr.mrrrmmommmmmooooo.oooooorrmu farrumiidiii
Hangsong Su, Feng Xue, Runze Guo, and Anlong Ming. Balanced line coverage in large-scale urban scene, 2023. URL
wtt.://rrrraa////00/// 11119
13

---

Published as a conference paper at ICLR 2026
Zhiqing Sun and Yiming Yang. DIFUSCO: Graph-based diffusion solvers for combinatorial opti-
mization. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL
https: httppp/s///peneeeeee...o net/ (orss//uommm1mGGPP00000
Ching Pui Wan, Tung Li, and Jason Min Wang. Rlor: A flexible framework of deep reinforcement learning for operation research, 2023. URL TtLhtttt::/// arxiv. http//aaw.vv....o..aaa//////...t hwagg/ab/223000 2313.13117
Pengfu Wan, Shukang Wang, Gangyan Xu, Yuying Long, and Runqiu Hu. Hybrid heuristic- multi-uav route planning for time-dependent data collection. IEEE Internet of Things Journal, 11 24)42441444447, 2024.
Shengzhe Wang, Ziyan Xu, Chaoqun Wu, Lin Hua, and Dahu Zhu. Towards region-based robotic machining system from perspective of intelligent manufacturing: A technology framework with case study. Journal of Manufacturing Systems, 70:451-463, 2023. ISSN 0278-6125.
Zhenwei Wang, Ruibin Bai, and Tiehua Zhang. Towards munstraint-basee adaptive hypergraph learning for solving vehicle routing: An end-to-end solution. arXiv preprint arXiv:2503. 10421, 2025.
Ronald Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Mach. Learn., 8(3 ((3--):229-295) May 1992. ISSN 0885-6125.
Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. NeuroLKH: Combining deep learning model with lin-kernighan-helsge
heuristic for solving the traveling salesman problem. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL httts::/ wtw.rreewwww..eeeooouuueaaaaaaae forum?id VKVShLsAu2
net.
Haoran Ye, Jiarui Wang, Helan Liang, Zhiguang Cao, Yong Li, and Fanzhang Li. Glop: learning global partition and local construction for solving large-scale routing problems real-time. In Proceedings of the Thirty-Fighth AAAI Conference Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence, AAAI22//AAT 24/EAA//22// AAAI Press, 2024.
ISBN 978-1-57735-887-9.
Chengxuan Ying. Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform badly for graph representation? Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https: / http//peeevviieeeeeeeeeee https://ppenreriew..cc net/ fo furum? i d= CeWoooxX FDa
A. Beygelzimer,
Qinxiao Yu, Kan Fang, Ning Zhu, and Shoufeng Ma. A matheuristic approach to the orienteering problem with service time dependent profits. European Journal of Operational Research, 273(2): 488-503, 2019. ISSN 0377-2217.
Changwen Zhang, Wenli Ouyang. Hao Yuan, Liming Gong, Yong Sun, Ziao Guo, Zhichen Dong, and Junchi Yan. Towards imitation learning to branch for MIP: A hybrid reinforcement learning based sample augmentation approach. In The Twelfth International Conference on Learning Representations, 2024. URL https:: hattps://cpenreviiee net.eeww.eeeeeeeee wtt.:e/eooommmmdddddo0e0ae..
David W Zhang, Corrado Rainone, Markus Peschl, and Roberto Bondesan. Robust scheduling with GFlownets. In The Eleventh International Conference on Learning Representations, 2023a. URL
net/ forum 2id=:mdddd-BBBBB 6wK9h
Dinghuai Zhang, Hanjun Dai, Nikolay Malkin, Aaron Courville, Yoshua Bengio, and Ling Pan. Let the flows tell: solving graph combinatorial optimization problems with gflownets. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2023b. Curran Associates Inc.
Zhi Zheng, Changliang Zhou, Tong Xialiang, Mingxuan Yuan, and Zhenkun Wang. UDC: unified
neural divide-and-on and-conquer framework for large-scale combinatorial optimization problems. In The eight Annual Conference on Neural Information Processing Systems, 2024. URL httpss//cpperevv/ net wtt.:e/neeeeeoommmmemaaooooooooo
14

---

Published as a conference paper at ICLR 2026
Jianan Zhou, Zhiguang Cao. Yaoxin Wu, Wen Song, Yining Ma, Jie Zhang, and Chi Xu. Mvmoe multi-task vehicle routing solver with mfxture-of efxerersss.............. In Proceedings of the 41st International Conference Machine Learning, (4. JMLR.org. 2024.
15

---

Published as a conference paper at ICLR 2026
LLM USAGE DISCLOSURE
We LLM as writing aid for grammar checking and for polishing the Introduction. The L.LM did not generate technical content, experiments, or results. All claims, data, equations, and code were authored, verified, and the responsibility of the human authors. No confidential, proprietary, or identifying information was shared with the LLM.
A PROOF OF THEOREM 4.1
In this paper, we propose a service time optimization algorithm obtain an optimal solution for second-stage service time allocation. The details of the proof are given by:
Proof. Consider the Lagrangian of the problem in the matrix form:
3
T
7+
= p=1
+ D11
X2
Ag
T
A T
A
d
(7)
+T (I
U s + +++t
where s, d are the start, service time of the given trajectory 7 from Algorithm | shift matrix, and À (}1 A2, As da As] denotes the Lagrangian multipliers of the corresponding constraints.
U denotes the upper
Since problem (3) is constrained convex optimization problem, long there exists solution (s, d, X) such that satisfies the Karush-Kunn-Tucke (KKT) conditions, the solution (s, d), are the optimal solution of the primal and dual problem, respectively [Boyd & Vandenberghe (2004).
The KKT conditions of problem can be expressed as:
8, S 8; S 8,
0 S S max
+ d, + 4 8 S O,
\TA 3;)
2 T 0
(8)
\a,(-dd
(d; di max) 0
Ao,1(5: + di + t, - 81+1)
-1, + 22,1 + Ao,1 A5
~ + A4,5 + >5.5 = P3
Consider an arbitrary solution from algorithm [ is a feasible solution s, d for the primal problem (3). The optimality of the solution can be guaranteed by finding a feasible solution À for the dual problem.
According to the line 9 of the algorithm, the selected nodes in the route can be separated into three categories: V- { dd, d; max s+ 22 r}. V {uyld, 5 1/ dits
EjH l+tj, 0i T). and V (ws d4 0, v. r).
For V, My is not constrained by the time windows of other vertices, according to the complementary slackness and gradient condition:
An,i + 22,5 + As,5 = A5,5-1,
\3,i 0,
A4,5 + A5,5 Pi
16

---

Published as a conference paper at ICLR 2026
For V, assume that the d, is constrained by the end of the i 2+1+ 1 th node's time window, i.e.
d + 1+1+1 8
dits Σ t+i
(10)
which indicates that the route from i satisfies:
8% + dg + 4 = 8k+1, k 1, 1, ,i+4, +
(11)
81+1+1 = 7+++11
which indicates that the th vertex to the i / vertex are constrained by the end time of i + ( + 1th vertex's time window. The corresponding gradient condition and complementary slackness from the d vertex to the i +++1 th vertex:
Àsk Ps + Ask Ask:
Ask d1k A2k + A = .,. ,
(12)
A1+tt4 = 0.
For E V, according to the gradient condition and complementary slackness:
Asi 0,
Ası = p: + Aza:
(13)
Ası Ani A2s Asi-1-
Vi E V, V, V, the feasibility of the corresponding Lagrange multiplier (A1r, A25, Asi Aas Ass) relies solely on the value of Àsi-1 and satisfies (9). (12), and (33), respectively. So, in the following, different sub-trajectories are constructed to evaluate the feasibility of different sub-trajectories.
Given that each node E V, V. V corresponds to a Lagrange multiplier tuple (Air, A2i, Azia Aais Ane
whose feasibility depends solely on the value of A, and satisfies conditions (9). (12). and (13).
respectively, the trajectory т can be categorized into four types of sub-trajectories. As the feasibility of each node can be recursively determined from the preceding node via As it follows that:
each sub-trajectory is locally feasible with respect to its starting value A then the entire trajectory T is globally feasible.
In the following sections, the feasibility of all possible sub-trajectories is validated by finding feasible solution that holds sequentially under the recursive propagation of Xs.
Case 1: {V/V} V Consider the case where a sub-trajectory [i, S (V/V) is followed by node +-+1e ++11 KKT conditions yields:
Asa- = + A3A Aaki
Ask- = A1L- - A2k + A5A-11 k: i,..,, ,..,,,,1,
A144411 + A2.11111 + Ap A5,iti
(14)
A3 = 0,
A45+141 + A5,5+141 Ps.
Vasi-1 E [0,44141], 3(A1e, Aee, ASk Ask, Ast), h E
1] is the feasible solution of sub-
trajectory from to +1+11
d1, = -222 >4.t 0,
A = Pi - PPk + X3,5s
A5,5 A5,A-11 K = i.... i
(15)
A1,4441 -22,14411 A3,
A5, = >s.itt
A4,44411 - P - A5,1-15
such that it satisfies the KKT condition.
17

---

Published as a conference paper at ICLR 2026
Case 2: (V/V) (V/V) Consider the where sub- sub-trajectory [ 4 (V/V) is
followed by another sub-trajectory [ + 4 + 1, +1 + 1 (V/V), KKT conditions yields:
Ask = Ps + ^3k >4a=
Ask = A1R A2a 1
-i. i,. i 4 + 12,
(16)
A1++++1 = O.
-ii--1 0, there exists feasible solution (AIR, A2ki ABE Aes Asx), &o [i, 1.ith, 4 + l22 + 11 of sub-trajectory from i to + 12 + 1, such that:
A1a d2k A4k O,
A3k = - Pk + A35.
(17)
Ask 1, k i. . 1 + 12.
which satisfies the KKT condition.
Case V V Consider the case where node i E V is followed by node + 1 E V. KKT
conditions yields:
A1,1 + 22 + As,5 A5,1-1.
A 0,
4 + As,i Pi.
(18)
-1,,+1 + 2 + Ao,411 A5,i0
A3,+41 0,
A4,441 + As,i+1 Pitl:
Visi-1 [0, min(pi, P.+1 11 H. there exists feasible solution (AIR A2er Ase, Ass, Aos), A [i, 1] of sub-trajectory from to + 1+ 1, such that:
\1,i λ2,; = A3,3 = 0,
A5,i A5,i-1:
A4,i Pi A5,i-1,
(19)
A1,+11 .2,i+11 A3,5+1 = 0,
A5,441 A5,i-1:
4,,+1 = Pi+1 >5,i-1,
which satisfies the KKT condition.
Case 4: V + (V/V) Consider the case where node E V followed by sub-trajectory
1+,,, 1.1,++1 1] C (V/V), KKT conditions yields:
-1,, λ2,2 As A5.i-1:
As,i = 0,
A As,i Pi-
(20)
A + A4,x + As. = Pk.
As,1 À1,x + λ2 A5, & E li 1,1+1+111 1}.
Vasi11 E pt). there exists a feasible solution (AIR A2Rs Aska Asko Ask), k E ( + 1 1] of sub-trajectory from i i such that:
A1. = \2,5 = >,s,s= =0
As,i >5,i-11
A4.; = Pi -A5,is
(21)
ÀI, -22 >4. 0,
ASA = Pi PPE + A3,5=
AS,A A5,A-1, h: [i,i+++1]
which satisfies the KKT condition.
To this end, given arbitrary trajectory and the solution (s. d) from algorithm 1 VÄsk min J. & e [0, 1. there exists a feasible such that (s, d, A) satisfies the KKT conditions, which demonstrates the optimality of the primal and dual problems.
18

---

Published as a conference paper at ICLR 2026
B SUPPLEMENTARY EXPERIMENTS
B.I RESULTS ON RUNNING THE ILS FOR LONGER THAN 10 SECONDS
To ensure a stronger comparison between ILS and DeCoST, we additionally evaluated ILS with extended time budgets of 20s, 50s, and 200s (partially), shown in the following table. The results demonstrate that, while ILS indeed finds slightly better solutions as time increases (10s -> 200s), the improvement remains marginal, and it still does not match the performance of our proposed method, which, in addition, exhibits significantly higher efficiency.
Table 5: Performance comparison OPTWVP under different problem sizes and time window settings. Bold values denote the best performance in each setting. Category C refers to NCO methods, and H refers heuristic baselines. The default unit for runtime is milliseconds (ms).
Cat.
Method
n
50, TW
100
n
100. TW 100
Score
f
Gap
Runtime
Score
Gap +
Runtime
B&C
15.2
0.00%
200
26.1
0.00%
1023
ILS s)
14.5
4.34%
2109
24.9
4.2%
7122
IL.S (20 s)
14.5
4.34%
2120
24.9
4.2%
7162
ILS (50 s)
14.5
4.34%
3620
25.0
4.1%
12438
ILS (200
c
DeCoST (Ours)
15.1
1.06 %
94.0
25.6
1.97%
158
50, TW
500
100, TW 500
Cat.
Method
Score f
Gap
Runtime
Score
Gap
Runtime
B&C
51.9
0.00%
1346s
>24h
ILS (10
47.8
7.82%
1262
85.0
8441
ILS (20 s)
47.8
7.82%
1270
83.5
8305
ILS (50 s)
47.8
7.82%
2474
83.7
12407
ILS (200
47.8
7.82%
8606
83.7
19045
C
DeCoST (Ours)
51.4
0.83% %
60.4
88.1
100
B.2 DISTRIBUTIONAL CHARACTERISTICS ROBUSTNESS OF PERFORMANCE ACROSS INSTANCES
The following table reports the characteristics of the gap distribution in four different datasets (n=50,tw=100; n=50,tw=500; 10000 n=500,tw=100),
Table 6: Distributional characteristics of gap performance
Method
mean
std
median
q25
q75
min
max
POMO
31.946
8.432
31.666
26.318
37.363
0.000
76.748
Greedy-PRS
15,904
7.302
15.343
10.740
20.395
0.000
61.360
GFACS
11.728
7.300
11.210
5.597
16.111
0.000
34.373
ILS
4.465
4.111
3.743
1.207
6.548
0.000
31,978
DeCoST
2.172
2.131
1.830
0.184
3.393
0.000
13.070
As shown in the table, method DeCoST not only achieves the lowest value (2.172), but also demonstrates the smallest standard deviation (2.131) among all methods, indicating its overall superior performance and stability. Compared to other baselines, DeCoST yields more stable and consistent results across different instances, as reflected by its smaller interquartile range (q25-q75) and narrower minimum- maximum span.
B.3 EXTENSION ON TEAM OPTWVP
For OPTWVP, the challenge lies in the complex coupling between discrete path selection and continuous service time allocation, which significantly expands the search space, making difficult quickly find high-quality solutions.
19

---

Published as a conference paper at ICLR 2026
Team OPTWVP shares the similar challenge the OPTWVP. As shown in Table 7 the additional dimension of considering multiple vehicles does not change the core challenge of the discrete- continuous coupling inherent in the problem. Therefore, method is naturally generalisable to the team problem extension.
Table Performance comparison on TOPTWVP under n 50, TW 100 settings. Bold values denote the best performance in each setting, and underlined values denote the second-best. Category C refers to NCO methods, and H refers heuristic baselines.
TW 100
Cat.
Method
Score 1 (%)
B&C
H
ILS
31.83
-11.27
POMO
35.87 36.99
DeCoST (Ours)
+3.12
Not applicable the runtime exceeds one hour per instance.
B.4 SENSITIVITY ANALYSIS
We conducted a comprehensive sensitivity analysis to evaluate the robustness of our method with respect the parameters of the cost function B1 and 32 (default is 1000, 1000). Both parameters systematically varied across the range [100, 500, 1000, 2000, 5000), and the resulting performance gaps are summarised in the table below. Across all combinations tested, the performance gap
Table 8: Sensitivity analysis of DeCoST with 50, TW 100
B1/B2
100
500
1000
2000
5000
100
0.95%
0.88%
0.83%
0.88%
0.92%
500
0.91%
0.96%
0.89%
0.83%
0.84%
1000
0.87%
0.92%
0.84%
0.96%
0.88%
2000
0.92%
0.81%
0.84%
0.97%
0.84%
5000
0.88%
0.93%
0.83%
0.92%
0.94%
remains within the narrow range of [0.81%, 0.97%]. The mean performance gap over the 25 tested combinations 0.89%, with a standard deviation of 0.05%, demonstrating that our method is stable and largely insensitive to moderate changes in the cost function parameters. This robustness supports the reliability of our approach under varying cost configurations.
B.5 PERFORMANCE EVALUATION OF THE INITIAL SERVICE TIME
To evaluate the impact of initial service time settings the quality of solution construction, experiments are conducted by varying the service time reserved in the first stage from 0% 100% of the maximum service times in increments of 10%. In the first stage, feasible trajectory is obtained with fixed ser- vice time ratio. In the second stage, service times are further optimized with the Gurobi solver. Experiments are conducted on different test sets to ensure sufficient diversity in pTARR values on different trajectories. The average reward of this decomposition strategy, in comparison to the optimal reward, is illustrated in Figure
0.5
0.4
03
02
Percentage
4 The results show that, on average, reserving approx- imately 70% of the maximum service time leads to near-optimal solutions, with an average optimality gap of 3.87% across the test sets. However, significant number of outliers still occur in this setting. Similar issues are observed at other service time ratio levels, indicating that any fixed pre-reserved service time ratio is not robust enough across diverse instances. This justifies the necessity of designing STD and STO in solving OPTWVP.
Figure 4: Analysis of initial service time ratio versus optimality gap.
20

---

Published as a conference paper at ICLR 2026
B.6 EFFICIENCY ANALYSIS OF PTAR LOSS
To investigate this, conducted supplementary experiments small- to medium- instances (n=50/100, tw=100) to see the efficiency of the introduction pTAR loss. We define pTAR efficiency pTAR efficiency the percent increase in performance gap reduction the percent increase in runtime". This metric quantifies the "gain per unit time cost" when introducing the pTTAR loss.
Algorithm/ / num of nodes
gap of n50
runtime of n50
gap of 100
runtime of 100
DeCoST without pTAR
2.28%
21.48
3.06%
45.71
DeCoST
1.06%
25.67
1.22%
52.55
Percent increase
53.5%
19.5%
60.1%
15.0%
pTAR efficiency
2.74
4.0
We observe that introducing the pTAR loss consistently improves performance, albeit with an additional runtime overhead of approximately 17%. Moreover, the pTTAR efficiency for n=100 is higher than the pTAR efficiency for n=50, suggesting that p'TAR becomes more cost-effective as instance size grows within the tested range.
C MATHEMATICAL FORMULATION OF OPTWVP
In this paper, we mainly consider an orienteering problem (OP) variants that have a strong coupling of discrete and continuous variables, namely the orienteering problem with time windows and variable profit (OPTWVP). The mathematical formulation of OPTWWP is expressed as:
Σ p;dy
max
n
s.t.
T1
j=2
Σ
THNia = 1
(22)
S 1,
Vk = ..... (IN) - 1)
IN-1
|N|
Σ
Ti
Σ
Ikj = yks = 2...., ([N] 1);
i=1
j=2
77 < < :
Vi .,... N
8; + d, + t, $ L(1 Kij),
Vi,j = 1,..., |N];
0 d, < d, max:
where Zaj. Vs are the binary indicators whether the edge ety and vertex es in the solution. 8t, dss T3 T denotes the start time, the service time, and time windows of the vertex v.. And T Ti. and i, denote the time window of vertex and the travel time, respectively.
is worth noting that OP, OPVP, OPTW can be considered as special case of OPTWVP Marzal & Sebastial (2024). As shown Table OPTWVP includes all constraints considered in the OPTW and OPVP.
Table 9: Comparison OP variants
OP Variants
Time Window Constraints
Time- Varying Profits
OP
X
X
OPTW OPVP
X
OPTWVP
21

---

Published as a conference paper at ICLR 2026
D NETWORK ARCHITECTURE OF DECOST
The proposed DeCoST adopts encoder-decoder architecture tailored for hybrid routing problems that involve both discrete and continuous decision variables. The model consists of a unified graph encoder and two parallel decoders: routing decoder for node selection and a service time decoder (STD) for predicting continuous service durations.
D.1 INPUT REPRESENTATION
Each problem instance is formulated as fully connected graph EV, where the vertex feature is defined as:
X; = (Ti, Vs. 8; of .P:)
i E V,
(23)
where (zy, yr) denotes the spatial coordinate, s; S are the start and end of the time window, and ps is the unit profit at node i. The edge feature is given by:
E= (Ei
(24)
where ei, represents the travel time or Euclidean distance between node i and node j.
D.2 ENCODER
The encoder transforms node and edge features into latent representations hiev E Rdd using stack of L Transformer layers. In contrast to node embeddings, we incorporate edge features (e.g.. pairwise node distances) as additive bias terms in the attention computation. This design choice is motivated by the fact that geometric relationships between nodes play a critical role in routing problems. However, conventional attention mechanisms cannot typically explicitly encode such structural information.
et al. (2020), which operates solely on
To address this, we adopt the spatial encoding strategy inspired by Graphormer Ying et al. (202I), and inject edge-aware bias into the attention scores. This allows the model to explicitly capture the cost and connectivity structure between nodes, thereby improving its ability to model path feasibility and graph-awar eecision-making.
Formally, we modify the attention score between node i and node j as:
(4x)²kk bi.j Vda
aij
(25)
where and ky denote the query and key vectors, de is the dimensionality of the key, and b is edge bias term derived from the edge feature Gi,j (e.g., the travel distance between i and j). We compute the edge bias for each attention head via a learnable projection:
W(hh) edge k(,j
(26)
where w-(h) odge E a learnable scalar weight for the h-th attention head. The final head attention then computed as:
Attny, (g:, Ky, U2) Σ Softmax (a!!) Ug.
(27)
j=1
where qis kj, by are the linear projections of node embeddings, and bi,j is the attention bias derived from Cij-
D.3 DECODERS
The decoder includes two parallel heads. The routing decoder computes the probability of selecting the next node as:
h h2
= Softmax
{ tanh
(28)
Vd
22

---

Published as a conference paper at ICLR 2026
where ha is the attention output computed from the embedding of the last visited node and the current context, and Ç is a temperature parameter controlling exploration. The STD shares the same structure but uses Sigmoid activation to produce normalized scalar 6, [0, 1/, representing the ratio of the maximum allowable service time allocated at node j. Both decoders share the same encoder output key-value memory and are conditioned
context vector derived from the partial solution 7t- This enables context-aware prediction of both discrete actions and continuous variables.
EXPERIMENT DETAILS
E.1 BASELINES
Gurobi Gurobi Optimization, LLC (002)): Gurobi is seneral-purpose optimization solver that implements the Branch and Cut (B&C) algorithm to obtain the exact optimal solution.
Greedy-Prov Preedy-Profii Ratio Search (Greedy-PRS): Greedy-PRS heuristic. In the first stage, the route is determined by selecting the node with the highest profit per time unit at each step. The profit per unit time is defined as the total profit obtained upon completing the node, divided by the travel time to the node plus the waiting and service time at the node. the second stage, service times are optimized using Pul.P Mitchell et al.) (201T), linear programming module that is able to solve linear programming problems, without altering the route.
a two-stage customized greedy
Incremental local search (ILS) Marzal & Sebastia (2024), a state-of-the-an metaheuris- tic search algorithm solving OPTWVP. It implements fast first solution and local search techniques by first generating an efficient initial feasible solution and then performing neighborhood search for optimization.
KoMo]woon et al. (2020): POMO is baseline end-to-end constructive solver that leverages the symmetry of combinatorial optimization problems to improve search efficiency, However, the original POMO framework cannot integrate edge features and handle continuous-time variables. Therefore, we extend the network to the graphformer Ying et al. (2021) and implements our proposed service time decoder (STD) and service time optimization (STO) algorithm.
GFACS et al. 2025): GFACS a non-autoregressive generative method. It first utilizes GFlowNet to extract feature information from graph edges and nodes, and then generates heatmaps to guide the Ant Colony System for solution search. We implemented the STD and greedy/STO approaches top of this framework.
E.2 HYPERPARAMETERS
Table 10: Hyperparameters used for POMO and DeCoST under different dataset configurations
Dataset Config
Train episodes
Test episodes
Epoch
Batch size
POMO size
50, TW- 100
10000
10000
800
128
50
n 50, TW 500
10000
100
800
128
50
100, TW 100
10000
1000
800
128
50
n 100, TW- 500
10000
100
800
128
50
500, TW 100
10000
100
800
64
50
Solomon
29
10
1000
250
We follow the original settings in GFACS Kim et al. (2025). For ILS Marzal & Sebastia (024)).
to balance solver efficiency and ensure fair comparison, we set the maximum search time TO seconds during comparative experiments. For the hyperparameters listed in Table [T are used for both the ablation studies and the comparative experiments between POMO and our proposed method, DeCoST. These settings are consistently applied across different dataset configurations to ensure fair and reliable comparison. The additional 31, 33 hyperparameter, which balances the contribution between the primary objective loss and the Pur loss, is specific to DeCoST and is set to 1000, 1000, respectively. During training, the loss is small, which leads to a decrease in the gradient signal, so we magnify the loss by 1000 times to improve the training efficiency and convergence speed.
23


Reviews:
[{"review_id": "Z9G0JNiPXZ", "reviewer": "Reviewer_MPHD", "summary": "This paper introduces DeCoST, a two-stage framework designed to solve hybrid combinatorial optimization problems that combine discrete routing and continuous time-dependent decisions. Specifically,  the discrete components refer to the routing decisions (i.e choosing which locations to visit and in what order) while the continuous components concern the time variables, such as how long to spend at each location and when to start service within the allowed time windows. The DeCoST algorithm first determines the discrete route and then optimizes the continuous service times through a linear program to maximize the overall reward. In the first stage, DeCoST employs a parallel decoder to generate a feasible route and an initial estimate of service times, enhanced by spatial encoding and feasibility masks that respect time-window constraints. A profit-weighted time allocation ratio (pTAR) is introduced in order to learn the trade-off between travel time and service time allocation for the initial service time assignment. In the second stage, given the fixed route, a linear programming (LP)-based Service Time Optimization (STO) algorithm computes globally optimal service times. \nExperiments show that DeCoST consistently outperforms both heuristic and neural combinatorial optimization (NCO) baselines. Overall, DeCoST offers a theoretically grounded, efficient, and generalizable approach to hybrid discrete-continuous optimization, bridging exact optimization and neural learning methods.", "questions": "Is it possible to provide any form of theoretical guarantee or performance bound for the first-stage routing policy?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The authors propose a novel well-designed two-stage framework that cleanly separates discrete and continuous decision-making for the orienteering problem with time windows and variable profits. It also combines rigorous theoretical guarantees via the LP formulation in the second stage with extensive experiments supporting the results.", "weaknesses": "One weakness of the paper is that, unlike the second stage, the first-stage routing policy has no theoretical guarantee of optimality. It relies on reinforcement learning, which may converge to only locally optimal routes, so the overall solution quality depends on the effectiveness of this learned policy without any formal performance bound.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ObljMchl49", "reviewer": "Reviewer_HfEA", "summary": "This paper addresses the Orienteering Problem with Time Windows and Variable Profits (OPTWVP), which involves both discrete routing and continuous service-time decisions. The authors propose a two-stage DEcoupled discrete–Continuous optimization with Service-time-guided Trajectory (DeCoST) framework. In Stage 1, a parallel decoding structure predicts a route and initial service-time allocation; in Stage 2, service times are refined via a linear programming formulation, with theoretical guarantees of global optimality. The method reportedly achieves better solution quality and faster inference than state-of-the-art constructive and metaheuristic solvers across benchmark instances.", "questions": "1. Is it necessary to tailor algorithm 1? A standard continuous optimization problem should also be solvable in polynomial time given a fixed visit sequence?\n 2. Can the authors provide stronger justification or empirical evidence for Gurobi’s failure to find feasible solutions?\n 3. Why is a comaprison to Gurobi skipped for the solomon benchmark?\n 4. What are the key differences between DeCoST and hybrid approaches in prior works (e.g., neural combinatorial optimization combined with LP or MILP refinement)?\n 5. Would the method scale similarly for larger instances or tighter time windows?", "limitations": "", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. Clear and structured exposition: The paper is well written, easy to follow, and methodologically consistent. The decomposition into discrete and continuous components is intuitively appealing and technically well-motivated.\n2. Solid engineering contribution: The combination of a neural constructive method with an LP-based continuous-time refinement is elegant and appears to yield computational gains.", "weaknesses": "1. Motivation for optimizing service times unclear: In standard formulations of the orienteering problem with time windows, service times are typically derived from route structure and scheduling constraints. It remains unclear why an explicit optimization of service times is required and how this impacts practical applicability. A full formal problem statement would clarify the modeling choices.\n\n2. Limited methodological novelty: While the decoupling approach is well-implemented, the paradigm of combining discrete RL-style route construction with an optimization-based refinement layer is well established in recent literature (e.g., in ride-hailing and hybrid combinatorial optimization works). The contribution appears primarily incremental rather than conceptually new.\n\n3. Missing related work: The paper overlooks several closely related lines of research, in particular the Neural Search and Decision Learning frameworks developed by Kevin Tierney and co-authors. Including and contrasting these would help position the contribution more accurately.\n\n 4. Questionable experimental evidence.\n • Table 1 raises concerns: it is surprising that Gurobi fails to find feasible solutions within 24 hours — this requires verification or clarification.\n • Figure 3 lacks subcaptions, and key plots are underexplained.\n • The absence of comparisons on standard Solomon benchmarks limits interpretability of the numerical improvements.\n • It is unclear whether the reported gains (up to 6.6×) persist across varying problem sizes and constraint tightness.\n\n 5. Marginal theoretical contribution: Theorem 1 and Algorithm 1 formalize a well-known fact — that continuous variables over a fixed route can be optimized efficiently via LP. The inclusion adds little beyond formal completeness and could be shortened.\n\n 6. Overstated generality: While the authors claim compatibility with various solvers and broad applicability, evidence for transferability beyond OPTWVP is not provided.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8zhsQ6G4cE", "reviewer": "Reviewer_wvRc", "summary": "This paper addresses the Orienteering Problem with Time Windows and Variable Profits (OPTWVP), a routing problem where the solution may serve any subset of nodes, subject to time-windows constraints on when each node can be served and a constraint on the duration of route, maximizing the variable profit collected from serving the nodes. The paper proposes a computational approach that consists of two stages: first, a learned policy constructs an initial solution (route and initial service times); second, a polynomial-time algorithm finds optimal service times (given the route). The policy is learned using REINFORCE with baseline, and it is based on a graph-transformer architecture. The polynomial-time algorithm for improving the solution is proven to be optimal. The proposed approach is evaluated on benchmark problem instances, demonstrating that it outperforms baselines.", "questions": "* Can you elaborate on the significance of the polynomial-time algorithm for finding service time considering that an LP can also solve this?\n* What other routing problems could this algorithm be applied to? Or other contributions of the paper readily applicable to other routing problems?", "limitations": "", "rating": 2, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* The polynomial-time algorithm for finding service times for a given route is a nice contribution, and it is proven to be optimal.\n* The combination of the RL policy with the polynomial-time algorithm is beneficial (while there exist approaches that use traditional optimization methods to improve solutions provided by NCO for similar problems, there is novelty in the specific combination, which decouples the routing from the scheduling).\n* The numerical results are promising.", "weaknesses": "* The key contribution of the paper seems to be polynomial-time algorithm for finding service time. While this is an interesting contribution, ICLR might not be the best venue for publishing it since it is not a learning-based approach. A broader AI conference might be a better fit.\n* The significance of this contribution is limited by the fact that the problem can also be solved by a straightforward LP, which also takes polynomial time. So this contribution really only seems important to communities that deeply care about this optimization problem.\n* The novelty in the combination of the RL policy with the polynomial-time algorithm seems to be OPTWVP-specific (generally, the idea of combining NCO with traditional optimization is not novel, but specific combination based on fixing the route is), which might be of limited interest to ICLR.\n* The discussion on lines 72 to 76 seems misleading. The references argue that transformers are ill-suited for continuous time series. However, this paper considers a discrete set of variables (scheduled times) that may have continuous values, which is very different, and which should not be an issue for transformers. The paper does not make it clear what the supposed issue with \"hybrid decision variables\" is. In the end, the proposed RL-based approach is a fairly straightforward one (graph transformer with discrete and continuous action heads); so there does not seems to be a \"hybrid decision\" challenge.\n\nThe presentation of the paper needs to be revised to improve its readability. The following is a non-exhaustive list of major and minor issues:\n* The paper should provide at least an informal definition of OPTWVP in the introduction for readers who are not familiar with the problem. There is currently no definition or explanation.\n* References should be \\citep instead of \\cite when the names of the authors are not used as subject or object.\n* Figure 1(a) and its description are not particularly clear, e.g., it is not obvious how the problem is mapped to OPTWVP. Perhaps present a more straightforward, vehicle-routing example.\n* The features and architectures of the learned policy are not described in the main text in adequate detail. Without reading the appendix, it is not clear how the Routing Decoder and STD work together. There is limited space in the main text, but these seem like important details.\n* Notation is inconsistent. On line 199, $P$ and $C$ are introduced, but they are later typeset in calligraphic font $\\mathcal{P}$ and $\\mathcal{C}$. On line 204, subscript $5n$ is never explained (why 5? what is $n$?).\n* The constraint on line 213 does not seem to make sense. What does the expectation of inequality mean? Later, it seems that the constraints are strict, so what is the point of the expectation?\n* Also, most of the notation introduced in lines 199 to 214 is never used later, so what is the point of introducing them?\n* On line 224, $G$ and $M$ are never introduced or explained. Typo for $\\mathcal{G}$? Batch size $M$?\n* Equation (1) would be simpler if it used the notation $R(\\tau_i | G)$, which is introduced anyway.\n* Lines 226 to 228 discuss coupling again. The importance of this is unclear; this \"coupling\" is just a mixed continuous-discrete action space.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AST55CJ0jV", "reviewer": "Reviewer_u59i", "summary": "The paper develops a two-stage algorithm for solving the OPTWVP, where the first stage determines the order nodes are visited and the second stage determines how much time to spend at each node.  The first stage is solved heuristically using learned policy and the second stage is solved exactly using a linear programming model. Paper develops solid experimental evidence that the approach works well in practice.", "questions": "1.\tSince the second stage is a linear program, what is the advantage of using Algorithm 1 over an off-the-shelf linear programming solver, e.g. Gurobi?\n2.\tCan you provide more details on the OPTWVP benchmarks? Are these standard benchmarks akin to the Solomon ones mentioned later in the paper? If so, can you provide a reference for them? Or are they generated in some fashion?  If so, what parameters are varied and how?\n3.\tHow does the model behave when presented with a completely new benchmark class, e.g. one that is not part of the training data.  In other words, if the model was only trained on n = 50 and n = 100, how do the results on n = 500 change?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tSolid experimental evidence that the approach is faster than state of the art methods, including global optimization and local optimization.\n2.\tRelatively clear exposition of the main ideas in the core paper, backed up by details in the supplemental material", "weaknesses": "1.\tThe discussion on the benchmark problems is limited, which it makes it unclear how narrow the results are.  In other words, what is different about each problem in the training/testing data set (price, travel time, etc.). If the benchmarks all share very similar structure, the results become less compelling, but are very compelling if the problem data has a lot of variance with the static space of a <TW, n> class. \n2.\tThe practical motivation could be explicit and direct for how problems of interest map into the OPTWVP model.  It may not be readily obvious to portions of the ICLR community not versed in the orienteering/vehicle routing community\n\nMinor comment (not a weakness) - marzal/sebastia reference appears twice in the reference list.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)