Learning to Solve Orienteering Problem with Time Windows and Variable Profits

Songqun Gao; Zanxi Ruan; Patrick Floor; Marco Roveri; Luigi Palopoli; Daniele Fontanelli

cs.LGMar 6, 2026

Learning to Solve Orienteering Problem with Time Windows and Variable Profits

Authors: Songqun Gao, Zanxi Ruan, Patrick Floor, Marco Roveri, Luigi Palopoli, Daniele Fontanelli

Organizations: Department of Industrial Engineering, Università di Trento, Trento, Italy · Interdepartmental Robotics Labs (IDRA), Trento, Italy · Department of Engineering for Innovation Medicine, Università di Verona, Verona, Italy · Pipple, Eindhoven, Netherlands ·

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.

Figures & tables

Figure 1: (a) Application of OPTWVP in industrial scenarios. A manipulator and a human are collaborating on a defect removal task on the assembly line. The robot has limited time to operate. It 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 discrete-continuous decisions and capturing continuous-variable representations.

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 1 .

Cat.	Method	$n=50$ , TW $=100$			$n=100$ , TW $=100$
Cat.	Method	Score $\uparrow$	Gap $\downarrow$	Runtime $\downarrow$	Score $\uparrow$	Gap $\downarrow$	Runtime $\downarrow$
–	B&C	15.2	0.00%	200	26.1	0.00%	1023
H	Greedy-PRS	12.9	15.7%	44	21.9	16.2%	48
H	ILS	14.5	4.34%	2109	24.9	4.2%	7122
C	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

Table 1: Performance comparison on OPTWVP 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 to NCO methods, and H refers to heuristic baselines. The default unit for runtime is milliseconds (ms).

Method	Score $\uparrow$	Gap $\downarrow$	Runtime (ms) $\downarrow$
B&C	82.3	0.00%	68400
Greedy-PRS	69.6	15.6%	60
ILS	78.2	4.98%	8803
GFACS (Greedy)	67.4	18.1%	112
GFACS	73.1	11.3%	9420
POMO	58.6	28.8%	747

Table 2: Performance on OPTWVP with large-scale configuration (

n=500

, TW

=100

). Bold values indicate the best result.

Figure 3: Boxplot of the optimality gap under different problem sizes and time window settings.

Method / Setting	SE	STO	SL	Score $\uparrow$	Gap $\downarrow$	Runtime (ms) $\downarrow$
TW = 100
Baseline	✗	✗	✗	11.3	25.3%	46.6
Baseline + SE	✓	✗	✗	11.6	23.0%	46.7
Baseline + SE + STO	✓	✓	✗	14.9	2.28%	77.5
DeCoST (ours)	✓	✓	✓	15.1	1.06%	94.0
TW = 500

Table 3: Ablation study on DeCoST (

n=50

). Bold numbers denote the best in each block (TW).

Method	Score $\uparrow$	Gap $\downarrow$
B&C	-	-
ILS (T=10s)	9846.3	-7.8%
ILS (T=20s)	10616.9	-0.59%
DeCoST (T=0.29s)	10680.3	–

Table 4: Performance comparison on OPTWVP on Solomon 100.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Cat.	Method	$n=50$ , TW $=100$			$n=100$ , TW $=100$
Cat.	Method	Score $\uparrow$	Gap $\downarrow$	Runtime $\downarrow$	Score $\uparrow$	Gap $\downarrow$	Runtime $\downarrow$
–	B&C	15.2	0.00%	200	26.1	0.00%	1023
H	ILS ( $10$ s)	14.5	4.34%	2109	24.9	4.2%	7122
	ILS ( $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$ s)	-	-	-	-	-	-

Appendix

Table 5: Performance comparison on 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 to heuristic baselines. The default unit for runtime is milliseconds (ms).

Method	mean	std	median	q25	q75	max
POMO	31.946	8.432	31.666	26.318	37.363	76.748
Greedy-PRS	15.904	7.302	15.343	10.740	20.395	61.360
GFACS	11.728	7.300	11.210	5.597	16.111	34.373
ILS	4.465	4.111	3.743	1.207	6.548	31.978
DeCoST	2.172	2.131	1.830	0.184	3.393	13.070

Appendix

Table 6: Distributional characteristics of gap performance

Cat.	Method	$n=50$ , TW $=100$
Cat.	Method	Score $\uparrow$	$\Delta$ (%) $\uparrow$
–	B&C	- a
H	ILS	31.83	-11.27
C	POMO	35.87	-
C	DeCoST (Ours)	36.99	+3.12

Appendix

Table 7: 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 to heuristic baselines.

$\beta_{1}/\beta_{2}$	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%

Appendix

Table 8: Sensitivity analysis of DeCoST with

n=50

, TW

=100

Figure 4: Analysis of initial service time ratio versus optimality gap.

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

Appendix

Table 13

OP Variants	Time Window Constraints	Time-Varying Profits
OP	✗	✗
OPTW	✓	✗
OPVP	✗	✓
OPTWVP	✓	✓

Appendix

Table 9: Comparison of OP variants

Dataset Config	Train episodes	Test episodes	Epoch	Batch size	POMO size
$n=50$ , TW $=100$	10000	10000	800	128	50
$n=50$ , TW $=500$	10000	100	800	128	50
$n=100$ , TW $=100$	10000	1000	800	128	50
$n=100$ , TW $=500$	10000	100	800	128	50
$n=500$ , TW $=100$	10000	100	800	64	50
Solomon	29	10	1000	2	250

Appendix

Table 10: Hyperparameters used for POMO and DeCoST under different dataset configurations

Learning to Optimize

Learning to Optimize uses data to adapt algorithms, solver decisions, and solution maps for faster or better optimization.

See all 128 papers

Trajectory-Safe Orienteering for Human-Robot Shared Environments
Sep 28, 2026Songqun Gao, Elena Basei, Marco Roveri +2Trajectory Generation Robot Safety
Department of Industrial Engineering, Universit`a di Trento, Trento, Italy. · Interdepartmental Robotics Labs (IDRA), University of Trento, Trento, Italy · Department of Information Engineering and Computer Science, Universit`a di Trento, Trento, Italy.
Orienteering Problem with Uncertain Time-Varying Rewards: Framework and Benchmark for Everyday Service Robotics
Aug 19, 2026Masafumi Endo, Kohei Honda, Yuu Jinnai +1Service Robotics Robotics
CyberAgent Inc. · Nagoya University
Smart routes: a system for development and comparison of algorithms for solving vehicle routing problems with realistic constraints
Aug 14, 2026Andrew Soroka, German Mikhelson, Alexander Mescheryakov +1Vehicle Routing Metaheuristic Optimization
Moscow State University, Faculty of Computational Mathematics and Cybernetics, Moscow · Space Research Institute of RAS, Moscow

Sep 28, 2026J/K move · Enter open · S save

Trajectory-Safe Orienteering for Human-Robot Shared Environments

Songqun Gao, Elena Basei, Marco Roveri, Luigi Palopoli+1

Department of Industrial Engineering, Universit`a di Trento, Trento, Italy. · Interdepartmental Robotics Labs (IDRA), University of Trento, Trento, Italy · Department of Information Engineering and Computer Science, Universit`a di Trento, Trento, Italy.

Trajectory Generation Robot Safety Human-Robot Collaboration Robot Task Planning Safe Motion Planning

Open paper AskPDF arXiv

Orienteering problem (OP) has wide real-world applications and also great potential in human-robot collaboration. However, existing approaches struggle to simultaneously ensure safe and feasible trajectories while achieving high-quality task execution in shared workspaces. To this end, this work studies the OP with time windows and variable profits (OPTWVP). A two-stage DEcoupled discrete-Continuous Optimization with Service-time-guided Trajectory (DeCoST) approach is proposed to effectively solve OPTWVP in shared spaces. Meanwhile, the safety-aware time windows of nodes and the discretized workspace are introduced to ensure collision-free trajectories between the end effector and the human. Preliminary results validate the effectiveness of DeCoST in generating collision-free trajectory plans while preserving the quality of orienteering tasks.

Abstract

Learning to Optimize

Explore similar work

Trajectory-Safe Orienteering for Human-Robot Shared Environments

Orienteering Problem with Uncertain Time-Varying Rewards: Framework and Benchmark for Everyday Service Robotics

Smart routes: a system for development and comparison of algorithms for solving vehicle routing problems with realistic constraints