An Integrated Framework Integrating Monte Carlo Tree Search and Supervised Learning for Train Timetabling Problem

• URL: http://arxiv.org/abs/2311.00971v1
• Date: Thu, 2 Nov 2023 03:39:14 GMT
• Title: An Integrated Framework Integrating Monte Carlo Tree Search and Supervised Learning for Train Timetabling Problem
• Authors: Feiyu Yang
• Abstract summary: The single-track railway train timetabling problem (TTP) is an important and complex problem. This article proposes an integrated Monte Carlo Tree Search (MCTS) computing framework that combines methods, unsupervised learning methods, and supervised learning methods for solving TTP in discrete action spaces.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The single-track railway train timetabling problem (TTP) is an important and complex problem. This article proposes an integrated Monte Carlo Tree Search (MCTS) computing framework that combines heuristic methods, unsupervised learning methods, and supervised learning methods for solving TTP in discrete action spaces. This article first describes the mathematical model and simulation system dynamics of TTP, analyzes the characteristics of the solution from the perspective of MCTS, and proposes some heuristic methods to improve MCTS. This article considers these methods as planners in the proposed framework. Secondly, this article utilizes deep convolutional neural networks to approximate the value of nodes and further applies them to the MCTS search process, referred to as learners. The experiment shows that the proposed heuristic MCTS method is beneficial for solving TTP; The algorithm framework that integrates planners and learners can improve the data efficiency of solving TTP; The proposed method provides a new paradigm for solving TTP.

Related papers

• Test-Time Training on Graphs with Large Language Models (LLMs) [68.375487369596]
  Test-Time Training (TTT) has been proposed as a promising approach to train Graph Neural Networks (GNNs) Inspired by the great annotation ability of Large Language Models (LLMs) on Text-Attributed Graphs (TAGs), we propose to enhance the test-time training on graphs with LLMs as annotators. A two-stage training strategy is designed to tailor the test-time model with the limited and noisy labels.
  arXiv  Detail & Related papers  (2024-04-21T08:20:02Z)
• Robust Analysis of Multi-Task Learning Efficiency: New Benchmarks on Light-Weighed Backbones and Effective Measurement of Multi-Task Learning Challenges by Feature Disentanglement [69.51496713076253]
  In this paper, we focus on the aforementioned efficiency aspects of existing MTL methods. We first carry out large-scale experiments of the methods with smaller backbones and on a the MetaGraspNet dataset as a new test ground. We also propose Feature Disentanglement measure as a novel and efficient identifier of the challenges in MTL.
  arXiv  Detail & Related papers  (2024-02-05T22:15:55Z)
• Reinforcement Learning for Scalable Train Timetable Rescheduling with Graph Representation [28.5828807787632]
  Train timetable rescheduling (TTR) aims to promptly restore the original operation of trains after disturbances or disruptions. This study proposes a reinforcement learning-based approach to TTR, which makes the following contributions compared to existing work.
  arXiv  Detail & Related papers  (2024-01-13T02:14:35Z)
• MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion Control in Real Networks [63.24965775030673]
  We propose a novel Reinforcement Learning (RL) approach to design generic Congestion Control (CC) algorithms. Our solution, MARLIN, uses the Soft Actor-Critic algorithm to maximize both entropy and return. We trained MARLIN on a real network with varying background traffic patterns to overcome the sim-to-real mismatch.
  arXiv  Detail & Related papers  (2023-02-02T18:27:20Z)
• Task Weighting in Meta-learning with Trajectory Optimisation [37.32107678838193]
  We introduce a new principled and fully-automated task-weighting algorithm for meta-learning methods. By considering the weights of tasks within the same mini-batch as an action, we cast the task-weighting meta-learning problem to a trajectory optimisation. We empirically demonstrate that the proposed approach out-performs common hand-engineering weighting methods in two few-shot learning benchmarks.
  arXiv  Detail & Related papers  (2023-01-04T01:36:09Z)
• A Survey on the Integration of Machine Learning with Sampling-based Motion Planning [9.264471872135623]
  This survey reviews machine learning efforts to improve the computational efficiency and applicability of Sampling-Based Motion Planners (SBMPs) It first discusses how learning has been used to enhance key components of SBMPs, such as node sampling, collision detection, distance or nearest neighbor, local planning, and termination conditions. It also discusses how machine learning has been used to provide data-driven models of robots, which can then be used by a SBMP.
  arXiv  Detail & Related papers  (2022-11-15T18:13:49Z)
• A Unified Perspective on Value Backup and Exploration in Monte-Carlo Tree Search [41.11958980731047]
  We propose two methods for improving the convergence rate and exploration based on a newly introduced backup operator and entropy regularization. We show that this theoretical formulation unifies different approaches, including our newly introduced ones, under the same mathematical framework. In practice, our unified perspective offers a flexible way to balance between exploration and exploitation by tuning the single $alpha$ parameter according to the problem at hand.
  arXiv  Detail & Related papers  (2022-02-11T15:30:08Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  We develop a two-stage framework, in which reinforcement learning (RL) and traditional operations research (OR) algorithms are combined together. The scheduling problem is solved in two stages, including a finite Markov decision process (MDP) and a mixed-integer programming process, respectively. Results show that the proposed algorithms could stably and efficiently obtain satisfactory scheduling schemes for agile Earth observation satellite scheduling problems.
  arXiv  Detail & Related papers  (2021-03-10T03:16:12Z)
• Deep Unfolding Network for Image Super-Resolution [159.50726840791697]
  This paper proposes an end-to-end trainable unfolding network which leverages both learning-based methods and model-based methods. The proposed network inherits the flexibility of model-based methods to super-resolve blurry, noisy images for different scale factors via a single model.
  arXiv  Detail & Related papers  (2020-03-23T17:55:42Z)
• Decentralized MCTS via Learned Teammate Models [89.24858306636816]
  We present a trainable online decentralized planning algorithm based on decentralized Monte Carlo Tree Search. We show that deep learning and convolutional neural networks can be employed to produce accurate policy approximators.
  arXiv  Detail & Related papers  (2020-03-19T13:10:20Z)

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.