A column generation-based approach for integrated vehicle and crew scheduling on a single metro line with the fully automatic operation system by partial supervision
Document Type
Journal Article
Publication Date
2021
Subject Area
mode - subway/metro, place - urban, operations - scheduling, operations - performance, planning - methods, organisation - workforce planning, economics - operating costs
Keywords
Urban metro lines, Fully automatic operation, Vehicle and crew scheduling, Column generation
Abstract
With the rapid development of fully automated urban metro lines, unattended train operation has become a reality, leading to significant gains in efficiency in comparison with traditional operation. To make better use of this technology and reduce operational costs, this study proposes a novel approach for collaboratively optimizing both vehicle and crew scheduling on metro lines. This approach is based on the assumption that unattended train movement without passengers is permitted, while the in-service train requires supervision by the crew. By considering the characteristics of urban metro lines, a mathematical model that considers both the meal activity and employee deadheading for the integrated vehicle and crew scheduling problem is first formulated. The model consists of a master problem for minimizing the total cost and subproblems for generating duties. The subproblem is constructed using a connection-based network and modeled as a special resource-constrained shortest path problem. To solve the model efficiently, a two-phase pricing procedure, which combines a piece generation phase and a duty generation phase, is developed to price out duties with negative reduced costs. Finally, numerical experiments based on actual conditions are conducted. The results indicate that our proposed model provides a significantly tight linear relaxation with negligible, typically zero, optimality gaps. Moreover, in comparison with the traditional integrated formulation, our proposed model and algorithm achieve improved performance in terms of solution quality and computing time.
Rights
Permission to publish the abstract has been given by Elsevier, copyright remains with them.
Recommended Citation
Pan, H., Liu, Z., Yang, L., Liang, Z., Wu, Q., & Li, S. (2021). A column generation-based approach for integrated vehicle and crew scheduling on a single metro line with the fully automatic operation system by partial supervision. Transportation Research Part E: Logistics and Transportation Review, Vol. 152, 102406.
Comments
Transportation Research Part E Home Page:
http://www.sciencedirect.com/science/journal/13665545