TLDR: This paper introduces a unified optimization framework for planning and replanning metro crew in multi-line systems, accounting for diverse workforce qualifications and preferences. It proposes a Hierarchical Time-Space Network (HTSN) model and develops efficient algorithms (Two-Stage Column Generation for planning, Fast Path Adjustment Heuristic for replanning). Experiments with real data from Shanghai and Beijing Metro demonstrate significant improvements in operational cost reduction and task completion, especially for urgent tasks during disruptions, by enabling cross-line crew coordination.
Metro systems are the backbone of urban transportation, offering efficient and high-capacity travel. However, managing the workforce for these complex networks, especially across multiple lines, presents significant challenges. Labor costs are a major expense, and ensuring smooth, cost-effective operations requires highly optimized crew planning.
Historically, research in metro crew planning has largely focused on individual lines, often simplifying crew characteristics by assuming everyone has the same skills. This approach overlooks the complexities of modern multi-line networks where crew members might need to switch lines, and their qualifications and personal preferences vary greatly. Furthermore, existing studies often treat initial planning and real-time replanning during disruptions as separate problems, leading to inefficiencies when rapid adjustments are needed.
A Unified Approach to Crew Management
A new research paper by Qihang Chen, titled Unified Crew Planning and Replanning Optimization in Multi-Line Metro Systems Considering Workforce Heterogeneity, introduces a groundbreaking unified optimization framework to address these challenges. This framework is designed for multi-line metro crew planning and replanning, specifically accounting for the diverse skills and preferences of the workforce.
The core of this framework is a novel Hierarchical Time-Space Network (HTSN) model. This model effectively represents all possible actions a crew member can take, from signing in to performing tasks, taking breaks, and even transferring between different lines. The HTSN is structured in four tiers: line blocks (representing actions on a specific line within a duty), duty layers (multi-line search space for a duty frame), daily subnetworks (entire daily planning space), and the overall hierarchical network (spanning the entire planning horizon).
Handling Diverse Workforces and Cross-Line Operations
A key innovation is how the framework handles workforce heterogeneity. Crew members have varying qualifications, meaning they are certified to operate on specific metro lines. This is modeled as a ‘hard constraint,’ ensuring that duties are only assigned to qualified personnel. Additionally, individual preferences, such as preferred sign-in/sign-out depots, are incorporated as ‘soft constraints’ by assigning penalties if preferences are violated, allowing for more considerate crew allocation.
The framework also emphasizes the importance of cross-line operations. This means crew members qualified on multiple lines can switch between them. This flexibility is crucial for global optimization, allowing for better resource allocation. The paper distinguishes between interday cross-line shifting (switching lines between different days) and intraday cross-line deadheading (transferring to another line within the same day to address urgent needs). These cross-line capabilities are vital for efficient disruption recovery, as available crew from one line can quickly be redeployed to a disrupted line.
Solving Complex Planning and Replanning Problems
The planning and replanning problems are formulated as integer programming problems. To solve the initial crew planning problem, a Two-Stage Column Generation (TSCG) method is proposed. This method efficiently handles the vast number of potential duty lists by breaking the problem into smaller, manageable parts. For real-time crew replanning during disruptions, where speed is critical, a Fast Path Adjustment Heuristic (FPAH) method is designed. This heuristic quickly adjusts crew schedules based on the HTSN restricted subnetwork, ensuring continuity with ongoing tasks and locations.
Also Read:
- DISPLIB: A Unified Approach to Train Dispatching Optimization
- Optimizing Disaster Logistics: A New Approach to Vehicle Routing with Multi-Functional Nodes and Cascaded Time Minimization
Real-World Validation and Impact
The effectiveness of the proposed methods was tested using real-world timetable data from the Shanghai Metro and Beijing Metro, two of the world’s largest metro systems. The results demonstrated that the TSCG and FPAH methods significantly outperform traditional heuristic benchmarks. For crew planning, TSCG achieved notable reductions in operational costs and improvements in task coverage. In replanning scenarios, particularly during simulated passenger surges, FPAH showed substantial gains in overall task coverage and, crucially, in the completion rate of urgent tasks. The studies also highlighted that incorporating cross-line operations dramatically improves the completion rates of urgent tasks, underscoring the value of multi-line coordination.
This research provides valuable insights into enhancing the operational efficiency and resilience of public transportation in smart cities. By enabling global optimization and cross-line coordination, the framework offers a robust solution for managing complex metro systems and responding effectively to disruptions. Future work aims to incorporate more diverse crew attributes and explore advanced cross-line strategies like express train scheduling to further optimize metro operations.
