Train Scheduling with Hybrid Answer Set Programming

• URL: http://arxiv.org/abs/2003.08598v1
• Date: Thu, 19 Mar 2020 06:50:04 GMT
• Title: Train Scheduling with Hybrid Answer Set Programming
• Authors: Dirk Abels, Julian Jordi, Max Ostrowski, Torsten Schaub, Ambra Toletti, and Philipp Wanko
• Abstract summary: We present a solution to real-world train scheduling problems, involving routing, scheduling, and optimization, based on Answer Set Programming (ASP) We exemplarily show how the hybrid ASP system clingo[DL] can be used to tackle demanding planning-and-scheduling problems.
• Score: 1.4823899140444556
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a solution to real-world train scheduling problems, involving routing, scheduling, and optimization, based on Answer Set Programming (ASP). To this end, we pursue a hybrid approach that extends ASP with difference constraints to account for a fine-grained timing. More precisely, we exemplarily show how the hybrid ASP system clingo[DL] can be used to tackle demanding planning-and-scheduling problems. In particular, we investigate how to boost performance by combining distinct ASP solving techniques, such as approximations and heuristics, with preprocessing and encoding techniques for tackling large-scale, real-world train scheduling instances. Under consideration in Theory and Practice of Logic Programming (TPLP)

Related papers

• Interactive and Expressive Code-Augmented Planning with Large Language Models [62.799579304821826]
  Large Language Models (LLMs) demonstrate strong abilities in common-sense reasoning and interactive decision-making. Recent techniques have sought to structure LLM outputs using control flow and other code-adjacent techniques to improve planning performance. We propose REPL-Plan, an LLM planning approach that is fully code-expressive and dynamic.
  arXiv  Detail & Related papers  (2024-11-21T04:23:17Z)
• Offline reinforcement learning for job-shop scheduling problems [1.3927943269211593]
  This paper introduces a novel offline RL method designed for optimization problems with complex constraints. Our approach encodes actions in edge attributes and balances expected rewards with the imitation of expert solutions. We demonstrate the effectiveness of this method on job-shop scheduling and flexible job-shop scheduling benchmarks.
  arXiv  Detail & Related papers  (2024-10-21T07:33:42Z)
• Differentiable Combinatorial Scheduling at Scale [18.09256072039255]
  We propose a differentiable scheduling framework, utilizing Gumbel-Softmax differentiable sampling technique. To encode inequality constraints for scheduling tasks, we introduce textitconstrained Gumbel Trick, which adeptly encodes arbitrary inequality constraints. Our method facilitates an efficient and scalable scheduling via gradient descent without the need for training data.
  arXiv  Detail & Related papers  (2024-06-06T02:09:39Z)
• Accelerating Exact Combinatorial Optimization via RL-based Initialization -- A Case Study in Scheduling [1.3053649021965603]
  This research aims to develop an innovative approach that employs machine learning (ML) for addressing optimization problems. We introduce a novel two-phase RL-to-ILP scheduling framework, which includes three steps: 1) solver as coarse-grain scheduler, 2) solution relaxation and 3) exact solving via ILP. Our framework demonstrates the same scheduling performance compared with using exact scheduling methods while achieving up to 128 $times$ speed improvements.
  arXiv  Detail & Related papers  (2023-08-19T15:52:43Z)
• 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)
• A Memetic Algorithm with Reinforcement Learning for Sociotechnical Production Scheduling [0.0]
  This article presents a memetic algorithm with applying deep reinforcement learning (DRL) to flexible job shop scheduling problems (DRC-FJSSP) From research projects in industry, we recognize the need to consider flexible machines, flexible human workers, worker capabilities, setup and processing operations, material arrival times, complex job paths with parallel tasks for bill of material manufacturing, sequence-dependent setup times and (partially) automated tasks in human-machine-collaboration.
  arXiv  Detail & Related papers  (2022-12-21T11:24:32Z)
• Answer-Set Programming for Lexicographical Makespan Optimisation in Parallel Machine Scheduling [18.286430978487388]
  We deal with a challenging scheduling problem on parallel machines with sequence-dependent setup times and release dates. We put the individual machine spans in non-ascending order and lexicographically minimise the resulting robustnesss. Our experimental results show that ASP is indeed a promising KRR paradigm for this problem and is competitive with state-of-the-art CP and MIP solvers.
  arXiv  Detail & Related papers  (2022-12-18T12:43:24Z)
• Better than the Best: Gradient-based Improper Reinforcement Learning for Network Scheduling [60.48359567964899]
  We consider the problem of scheduling in constrained queueing networks with a view to minimizing packet delay. We use a policy gradient based reinforcement learning algorithm that produces a scheduler that performs better than the available atomic policies.
  arXiv  Detail & Related papers  (2021-05-01T10:18:34Z)
• 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)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• Subset Sampling For Progressive Neural Network Learning [106.12874293597754]
  Progressive Neural Network Learning is a class of algorithms that incrementally construct the network's topology and optimize its parameters based on the training data. We propose to speed up this process by exploiting subsets of training data at each incremental training step. Experimental results in object, scene and face recognition problems demonstrate that the proposed approach speeds up the optimization procedure considerably.
  arXiv  Detail & Related papers  (2020-02-17T18:57:33Z)

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.