A Learning-Augmented Dynamic Programming Approach for Orienteering Problem with Time Windows

Guansheng Peng (Great Bay University) · Lining Xing (Jiangsu University of Technology) · Fuyan Ma (Chinese Academy of Military Science) · Aldy Gunawan (Singapore Management University) · Guopeng Song (National University of Defense Technology) · Pieter Vansteenwegen (KU Leuven)

combinatorial optimization deep learning models directed edges domain expertise dynamic programmingeffective relaxationsexact algorithmsgraph convolutional networkmachine learning techniquesnp-hard problems optimal solutionsorienteering problemperformance gains supervised training time windows

Recent years have witnessed a surge of interest in solving combinatorial optimization problems (COPs) using machine learning techniques. Motivated by this trend, we propose a learning-augmented exact approach for tackling an NP-hard COP, the Orienteering Problem with Time Windows, which aims to maximize the total score collected by visiting a subset of vertices in a graph within their time windows. Traditional exact algorithms rely heavily on domain expertise and meticulous design, making it hard to achieve further improvements. By leveraging deep learning models to learn effective relaxations of problem restrictions from data, our approach enables significant performance gains in an exact dynamic programming algorithm. We propose a novel graph convolutional network that predicts the directed edges defining the relaxation. The network is trained in a supervised manner, using optimal solutions as high-quality labels. Experimental results demonstrate that the proposed learning-augmented algorithm outperforms the state-of-the-art exact algorithm, achieving a 38% speedup on Solomon’s benchmark and more than a sevenfold improvement on the more challenging Cordeau’s benchmark.