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 · Department of Information Engineering and Computer Science, Università di Trento, Trento, Italy
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
Score ↑
Gap ↓
Runtime ↓
Score ↑
Gap ↓
Runtime ↓
–
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
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 ↑
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
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 ↑
Gap ↓
Runtime (ms) ↓
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 ↑
Gap ↓
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
Score ↑
Gap ↓
Runtime ↓
Score ↑
Gap ↓
Runtime ↓
–
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
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
Appendix
Table 6: Distributional characteristics of gap performance
Cat.
Method
n=50 , TW =100
Score ↑
Δ (%) ↑
–
B&C
- a
H
ILS
31.83
-11.27
C
POMO
35.87
-
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.
β1/β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
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.
Songqun Gao, Elena Basei, Marco Roveri +2
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.
We present the orienteering problem with uncertain time-varying rewards (OP-UTVR), a novel variant of the orienteering problem (OP). While most existing OP formulations assume rewards to be known in advance, practical applications involve uncertain and time-varying rewards, as with shifting customer demand for delivery agents. OP-UTVR relaxes this assumption by allowing agents to estimate reward dynamics from observations and forecast future rewards. This enables informed routing decisions despite stochastic reward changes and inevitable prediction errors. We address this problem using three planners that differ in planning horizon and online adaptivity, and derive theoretical bounds on their performance under reward stochasticity. We further introduce a mobile service robot benchmark for OP-UTVR, where a robot navigates among pedestrians in indoor environments. Experiments reveal trade-offs between planning horizon and adaptivity, and demonstrate the effectiveness of long-horizon planning with online adaptation.
The problem of route optimization with realistic constraints is becoming extremely relevant in the face of global urban population growth. While we are aware of approaches that theoretically provide an exact optimal solution, their application becomes challenging as the problem size increases because of exponential complexity. We investigate the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) and compare solutions obtaining by exact solver SCIP with heuristic algorithms such as LKH, 2-OPT, 3-OPT, the ORTools framework, and the deep learning model JAMPR. We demonstrate that for problem of size 50 deep learning and classical heuristic solutions became close to SCIP exact solution but requires less time. Additionally for problems with size 100, SCIP exact methods around 13 times slower that neural and classical heuristics with the same route cost and on around 50% worse for the first feasible solution on the same time. To conduct experiments, we developed the Smart Routes platform for solving route optimization problems, which includes exact, heuristic, and deep learning models, and facilitates convenient integration of custom algorithms and datasets.
Andrew Soroka, German Mikhelson, Alexander Mescheryakov +1
Moscow State University, Faculty of Computational Mathematics and Cybernetics, Moscow · Space Research Institute of RAS, Moscow