A Reinforcement Learning Approach to the Orienteering Problem with Time Windows

• URL: http://arxiv.org/abs/2011.03647v2
• Date: Tue, 29 Jun 2021 18:37:29 GMT
• Title: A Reinforcement Learning Approach to the Orienteering Problem with Time Windows
• Authors: Ricardo Gama and Hugo L. Fernandes
• Abstract summary: The Orienteering Problem with Time Windows (OPTW) is an optimization problem where the goal is to maximize the total score collected from different visited locations. This study explores the use of Pointer Network models trained using reinforcement learning to solve the OPTW problem.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Orienteering Problem with Time Windows (OPTW) is a combinatorial optimization problem where the goal is to maximize the total score collected from different visited locations. The application of neural network models to combinatorial optimization has recently shown promising results in dealing with similar problems, like the Travelling Salesman Problem. A neural network allows learning solutions using reinforcement learning or supervised learning, depending on the available data. After the learning stage, it can be generalized and quickly fine-tuned to further improve performance and personalization. The advantages are evident since, for real-world applications, solution quality, personalization, and execution times are all important factors that should be taken into account. This study explores the use of Pointer Network models trained using reinforcement learning to solve the OPTW problem. We propose a modified architecture that leverages Pointer Networks to better address problems related with dynamic time-dependent constraints. Among its various applications, the OPTW can be used to model the Tourist Trip Design Problem (TTDP). We train the Pointer Network with the TTDP problem in mind, by sampling variables that can change across tourists visiting a particular instance-region: starting position, starting time, available time, and the scores given to each point of interest. Once a model-region is trained, it can infer a solution for a particular tourist using beam search. We based the assessment of our approach on several existing benchmark OPTW instances. We show that it generalizes across different tourists that visit each region and that it generally outperforms the most commonly used heuristic, while computing the solution in realistic times.

Related papers

• Federated Gradient Matching Pursuit [17.695717854068715]
  Traditional machine learning techniques require centralizing all training data on one server or data hub. In particular, federated learning (FL) provides such a solution to learn a shared model while keeping training data at local clients. We propose a novel algorithmic framework, federated gradient matching pursuit (FedGradMP), to solve the sparsity constrained minimization problem in the FL setting.
  arXiv  Detail & Related papers  (2023-02-20T16:26:29Z)
• Revisit the Algorithm Selection Problem for TSP with Spatial Information Enhanced Graph Neural Networks [4.084365114504618]
  This paper revisits the algorithm selection problem for Euclidean Traveling Salesman Problem (TSP) We propose a novel Graph Neural Network (GNN), called GINES. GINES takes the coordinates of cities and distances between cities as input. It is better than the traditional handcrafted feature-based approach on one dataset.
  arXiv  Detail & Related papers  (2023-02-08T13:14:20Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems. We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately. Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
  arXiv  Detail & Related papers  (2022-10-31T09:46:26Z)
• Travel the Same Path: A Novel TSP Solving Strategy [0.0]
  We consider the imitation learning framework, which helps a deterministic algorithm making good choices whenever it needs to. We demonstrate a strong generalization ability of a graph neural network trained under the imitation learning framework.
  arXiv  Detail & Related papers  (2022-10-12T03:56:37Z)
• Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networks [75.33431791218302]
  We study the training problem of deep neural networks and introduce an analytic approach to unveil hidden convexity in the optimization landscape. We consider a deep parallel ReLU network architecture, which also includes standard deep networks and ResNets as its special cases.
  arXiv  Detail & Related papers  (2021-10-18T18:00:36Z)
• On the Difficulty of Generalizing Reinforcement Learning Framework for Combinatorial Optimization [6.935838847004389]
  Combinatorial optimization problems (COPs) on the graph with real-life applications are canonical challenges in Computer Science. The underlying principle of this approach is to deploy a graph neural network (GNN) for encoding both the local information of the nodes and the graph-structured data. We use the security-aware phone clone allocation in the cloud as a classical quadratic assignment problem (QAP) to investigate whether or not deep RL-based model is generally applicable to solve other classes of such hard problems.
  arXiv  Detail & Related papers  (2021-08-08T19:12:04Z)
• Generalization Guarantees for Neural Architecture Search with Train-Validation Split [48.265305046655996]
  This paper explores the statistical aspects of such problems with train-validation splits. We show that refined properties of the validation loss such as risk and hyper-gradients are indicative of those of the true test loss. We also highlight rigorous connections between NAS, multiple kernel learning, and low-rank matrix learning.
  arXiv  Detail & Related papers  (2021-04-29T06:11:00Z)
• Learning to Sparsify Travelling Salesman Problem Instances [0.5985204759362747]
  We use a pruning machine learning as a pre-processing step followed by an exact Programming approach to sparsify the travelling salesman problem. Our learning approach requires very little training data and is amenable to mathematical analysis.
  arXiv  Detail & Related papers  (2021-04-19T14:35:14Z)
• Exploiting Shared Representations for Personalized Federated Learning [54.65133770989836]
  We propose a novel federated learning framework and algorithm for learning a shared data representation across clients and unique local heads for each client. Our algorithm harnesses the distributed computational power across clients to perform many local-updates with respect to the low-dimensional local parameters for every update of the representation. This result is of interest beyond federated learning to a broad class of problems in which we aim to learn a shared low-dimensional representation among data distributions.
  arXiv  Detail & Related papers  (2021-02-14T05:36:25Z)
• A Flexible Framework for Designing Trainable Priors with Adaptive Smoothing and Game Encoding [57.1077544780653]
  We introduce a general framework for designing and training neural network layers whose forward passes can be interpreted as solving non-smooth convex optimization problems. We focus on convex games, solved by local agents represented by the nodes of a graph and interacting through regularization functions. This approach is appealing for solving imaging problems, as it allows the use of classical image priors within deep models that are trainable end to end.
  arXiv  Detail & Related papers  (2020-06-26T08:34:54Z)
• Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks [91.65637773358347]
  We propose a general graph neural network framework designed specifically for multivariate time series data. Our approach automatically extracts the uni-directed relations among variables through a graph learning module. Our proposed model outperforms the state-of-the-art baseline methods on 3 of 4 benchmark datasets.
  arXiv  Detail & Related papers  (2020-05-24T04:02:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.