Boosting Column Generation with Graph Neural Networks for Joint Rider Trip Planning and Crew Shift Scheduling

• URL: http://arxiv.org/abs/2401.03692v4
• Date: Sat, 12 Apr 2025 21:15:15 GMT
• Title: Boosting Column Generation with Graph Neural Networks for Joint Rider Trip Planning and Crew Shift Scheduling
• Abstract summary: This paper introduces the Joint Rider Trip Planning and Crew Shift Scheduling Problem (JRTPCSSP) and a novel solution method, called Attention and Gated GNN-Informed Column Generation (AGGNNI-CG)<n>AGGNNI-CG hybridizes column generation and machine learning to obtain near-optimal solutions to the JRTPCSSP with real-life constraints of the application.<n>AGGNNI-CG has been applied to a challenging, real-world dataset from the Paratransit system of Chatham County in Georgia.
• Score: 17.483751895564676
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Optimizing service schedules is pivotal to the reliable, efficient, and inclusive on-demand mobility. This pressing challenge is further exacerbated by the increasing needs of an aging population, the oversubscription of existing services, and the lack of effective solution methods. This study addresses the intricacies of service scheduling, by jointly optimizing rider trip planning and crew scheduling for a complex dynamic mobility service. The resulting optimization problems are extremely challenging computationally for state-of-the-art methods. To address this fundamental gap, this paper introduces the Joint Rider Trip Planning and Crew Shift Scheduling Problem (JRTPCSSP) and a novel solution method, called Attention and Gated GNN-Informed Column Generation (AGGNNI-CG), that hybridizes column generation and machine learning to obtain near-optimal solutions to the JRTPCSSP with real-life constraints of the application. The key idea of the machine-learning component is to dramatically reduce the number of paths to explore in the pricing problem, accelerating the most time-consuming component of the column generation. The machine learning component is a graph neural network with an attention mechanism and a gated architecture, which is particularly suited to cater for the different input sizes coming from daily operations. AGGNNI-CG has been applied to a challenging, real-world dataset from the Paratransit system of Chatham County in Georgia. It produces substantial improvements compared to the baseline column generation approach, which typically cannot produce high-quality feasible solutions in reasonable time on large-scale complex instances. AGGNNI-CG also produces significant improvements in service quality compared to the existing system.

Related papers

• Navigating the Clutter: Waypoint-Based Bi-Level Planning for Multi-Robot Systems [54.887871365121775]
  Multi-robot control in cluttered environments is a challenging problem that involves complex physical constraints.<n>We propose a hybrid multi-robot control framework that jointly optimize task and motion planning.<n>Our approach consistently improves task success over motion-agnostic and VLA-based baselines.
  arXiv  Detail & Related papers  (2026-04-22T22:58:47Z)
• Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Scheduling [39.98859285173431]
  The flexible job-shop scheduling problem (FJSP) has attracted significant attention due to its complex and strong alignment with real-world production scenarios.<n>Current deep reinforcement learning (DRL)-based approaches to FJSP predominantly employ constructive methods.<n>This paper proposes a Memory-enhanced Improvement Search framework with heterogeneous graph representation--MIStar.
  arXiv  Detail & Related papers  (2026-03-03T10:43:01Z)
• Graph-Coarsening Approach for the Capacitated Vehicle Routing Problem with Time Windows [0.0]
  This paper introduces a multilevel graph coarsening and refinement framework that aggregates customers into meta-nodes.<n>The proposed method reduces computation while preserving or improving solution quality, particularly with respect to capacity and time window constraints.<n>The paper also explores the integration of quantum-inspired optimization techniques, highlighting their potential to further accelerate large-scale vehicle routing tasks.
  arXiv  Detail & Related papers  (2025-10-25T15:13:41Z)
• CollaPipe: Adaptive Segment-Optimized Pipeline Parallelism for Collaborative LLM Training in Heterogeneous Edge Networks [57.95170323315603]
  We introduce CollaPipe, a distributed learning framework that integrates collaborative pipeline parallelism with federated aggregation to support self-evolving networks.<n>In CollaPipe, the encoder part is adaptively partitioned into variable-sized segments and deployed across mobile devices for pipeline-parallel training, while the decoder is deployed on edge servers to handle generative tasks.<n>To enhance training efficiency, we formulate a joint optimization problem that adaptively allocates model segments, micro-batches, bandwidth, and transmission power.
  arXiv  Detail & Related papers  (2025-09-24T07:54:01Z)
• Accelerating Privacy-Preserving Federated Learning in Large-Scale LEO Satellite Systems [57.692181589325116]
  Large-scale low-Earth-orbit (LEO) satellite systems are increasingly valued for their ability to enable rapid and wide-area data exchange.<n>Due to privacy concerns and regulatory constraints, raw data collected at remote clients cannot be centrally aggregated.<n>Federated learning offers a privacy-preserving alternative by training local models on distributed devices and exchanging only model parameters.<n>We propose a discrete temporal graph-based on-demand scheduling framework that dynamically allocates communication resources to accelerate federated learning.
  arXiv  Detail & Related papers  (2025-09-05T03:33:42Z)
• Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [55.78505925402658]
  Vehicle Routing Problems (VRP) are an extension of the Traveling Salesperson Problem and are a fundamental NP-hard challenge in Evolutionary optimization. We introduce a novel optimization framework that uses a reinforcement learning agent - trained on prior instances - to quickly generate initial solutions, which are then further optimized by genetic algorithms. For example, EARLI handles vehicle routing with 500 locations within 1s, 10x faster than current solvers for the same solution quality, enabling applications like real-time and interactive routing.
  arXiv  Detail & Related papers  (2025-04-08T15:21:01Z)
• RGL: A Graph-Centric, Modular Framework for Efficient Retrieval-Augmented Generation on Graphs [58.10503898336799]
  We introduce the RAG-on-Graphs Library (RGL), a modular framework that seamlessly integrates the complete RAG pipeline. RGL addresses key challenges by supporting a variety of graph formats and integrating optimized implementations for essential components. Our evaluations demonstrate that RGL not only accelerates the prototyping process but also enhances the performance and applicability of graph-based RAG systems.
  arXiv  Detail & Related papers  (2025-03-25T03:21:48Z)
• FusionLLM: A Decentralized LLM Training System on Geo-distributed GPUs with Adaptive Compression [55.992528247880685]
  Decentralized training faces significant challenges regarding system design and efficiency. We present FusionLLM, a decentralized training system designed and implemented for training large deep neural networks (DNNs) We show that our system and method can achieve 1.45 - 9.39x speedup compared to baseline methods while ensuring convergence.
  arXiv  Detail & Related papers  (2024-10-16T16:13:19Z)
• Heterogeneity-Aware Resource Allocation and Topology Design for Hierarchical Federated Edge Learning [9.900317349372383]
  Federated Learning (FL) provides a privacy-preserving framework for training machine learning models on mobile edge devices. Traditional FL algorithms, e.g., FedAvg, impose a heavy communication workload on these devices. We propose a two-tier HFEL system, where edge devices are connected to edge servers and edge servers are interconnected through peer-to-peer (P2P) edge backhauls. Our goal is to enhance the training efficiency of the HFEL system through strategic resource allocation and topology design.
  arXiv  Detail & Related papers  (2024-09-29T01:48:04Z)
• A Graph-based Adversarial Imitation Learning Framework for Reliable & Realtime Fleet Scheduling in Urban Air Mobility [5.19664437943693]
  This paper presents a comprehensive optimization formulation of the fleet scheduling problem. It also identifies the need for alternate solution approaches. The new imitative approach achieves better mean performance and remarkable improvement in the case of unseen worst-case scenarios.
  arXiv  Detail & Related papers  (2024-07-16T18:51:24Z)
• Sparser is Faster and Less is More: Efficient Sparse Attention for Long-Range Transformers [58.5711048151424]
  We introduce SPARSEK Attention, a novel sparse attention mechanism designed to overcome computational and memory obstacles. Our approach integrates a scoring network and a differentiable top-k mask operator, SPARSEK, to select a constant number of KV pairs for each query. Experimental results reveal that SPARSEK Attention outperforms previous sparse attention methods.
  arXiv  Detail & Related papers  (2024-06-24T15:55:59Z)
• Learning-enabled Flexible Job-shop Scheduling for Scalable Smart Manufacturing [11.509669981978874]
  In smart manufacturing systems, flexible job-shop scheduling with transportation constraints is essential to optimize solutions for maximizing productivity. Recent developments in deep reinforcement learning (DRL)-based methods for FJSPT have encountered a scale generalization challenge. We introduce a novel graph-based DRL method, named the Heterogeneous Graph Scheduler (HGS)
  arXiv  Detail & Related papers  (2024-02-14T06:49:23Z)
• Spatial-temporal-demand clustering for solving large-scale vehicle routing problems with time windows [0.0]
  We propose a decompose-route-improve (DRI) framework that groups customers using clustering. Its similarity metric incorporates customers' spatial, temporal, and demand data. We apply pruned local search (LS) between solved subproblems to improve the overall solution.
  arXiv  Detail & Related papers  (2024-01-20T06:06:01Z)
• TOP-Former: A Multi-Agent Transformer Approach for the Team Orienteering Problem [47.40841984849682]
  Route planning for a fleet of vehicles is an important task in applications such as package delivery, surveillance, or transportation. We introduce TOP-Former, a multi-agent route planning neural network designed to efficiently and accurately solve the Team Orienteering Problem.
  arXiv  Detail & Related papers  (2023-11-30T16:10:35Z)
• Enhancing Column Generation by Reinforcement Learning-Based Hyper-Heuristic for Vehicle Routing and Scheduling Problems [9.203492057735074]
  Column generation (CG) is a vital method to solve large-scale problems by dynamically generating variables. We propose a reinforcement learning-based hyper-heuristic framework, dubbed RLHH, to enhance the performance of CG.
  arXiv  Detail & Related papers  (2023-10-15T00:05:50Z)
• Dynamic Scheduling for Federated Edge Learning with Streaming Data [56.91063444859008]
  We consider a Federated Edge Learning (FEEL) system where training data are randomly generated over time at a set of distributed edge devices with long-term energy constraints. Due to limited communication resources and latency requirements, only a subset of devices is scheduled for participating in the local training process in every iteration.
  arXiv  Detail & Related papers  (2023-05-02T07:41:16Z)
• 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)
• Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration [72.15369769265398]
  Experimentally, ECORD achieves a new SOTA for RL algorithms on the Maximum Cut problem. Compared to the nearest competitor, ECORD reduces the optimality gap by up to 73%.
  arXiv  Detail & Related papers  (2022-05-27T17:13:10Z)
• Scalable Vehicle Re-Identification via Self-Supervision [66.2562538902156]
  Vehicle Re-Identification is one of the key elements in city-scale vehicle analytics systems. Many state-of-the-art solutions for vehicle re-id mostly focus on improving the accuracy on existing re-id benchmarks and often ignore computational complexity. We propose a simple yet effective hybrid solution empowered by self-supervised training which only uses a single network during inference time.
  arXiv  Detail & Related papers  (2022-05-16T12:14:42Z)
• Optimal Solving of Constrained Path-Planning Problems with Graph Convolutional Networks and Optimized Tree Search [12.457788665461312]
  We propose a hybrid solving planner that combines machine learning models and an optimal solver. We conduct experiments on realistic scenarios and show that GCN support enables substantial speedup and smoother scaling to harder problems.
  arXiv  Detail & Related papers  (2021-08-02T16:53:21Z)
• 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)

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.