A Lagrangian Relaxation Approach Based on a Time-Space-State Network for Railway Crew Scheduling

Y. Wang (Ying), Z. Shang (Zheming), Dennis Huisman (), Andrea D'Ariano and J.C. Zhang (Jinchuan)

No EI2018-45, Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute

Abstract: The crew scheduling problem is an important and difficult problem in railway crew management. In this paper, we focus on the railway crew scheduling problem with time window constraints caused by meal break rules. To solve this optimization problem, a solution method is proposed based on a time-space-state network and Lagrangian relaxation. In this method, the "hard constraints" corresponding to the crew rules are described as the state of vertices in the time-space-state network. Based on the network, this problem is modeled as a network flow model, referred to as an initial model. To break the symmetry and improve the strength of the formulation, five valid inequalities are added. To solve the problem, we relax the coupling constraints by Lagrangian relaxation. The resulting subproblems are shortest path problems in the time-space-state networks. We propose a Lagrangian heuristic to find a feasible solution. Finally, the solution method is tested on real-world instances from an intercity rail line and a regional railway network in China. We discuss the effects of additional valid inequalities and the effects of different length of meal time windows.

Keywords: Scheduling; Meal time window; Time-space-state network; Lagrangian relaxation (search for similar items in EconPapers)
Pages: 24
Date: 2018-09-01
New Economics Papers: this item is included in nep-tre
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://repub.eur.nl/pub/114114/EI2018-45.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ems:eureir:114114

Access Statistics for this paper

More papers in Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute Contact information at EDIRC.
Bibliographic data for series maintained by RePub ( this e-mail address is bad, please contact ).