.png){kind=icon}
返回
Two-level decomposition algorithm for crew rostering problems with fair working condition
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2014.02.010.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
A typical railway crew scheduling problem consists of two phases: a crew pairing problem to determine a set of crew duties and a crew rostering problem. The crew rostering problem aims to find a set of rosters that forms workforce assignment of crew duties and rest periods satisfying several working regulations. In this paper, we present a two-level decomposition approach to solve railway crew rostering problem with the objective of fair working condition. To reduce computational efforts, the original problem is decomposed into the upper-level master problem and the lower-level subproblem. The subproblem can be further decomposed into several subproblems for each roster. These problems are iteratively solved by incorporating cuts into the master problem. We show that the relaxed problem of the master problem can be formulated as a uniform parallel machine scheduling problem to minimize makespan, which is NP-hard. An efficient branch-and-bound algorithm is applied to solve the master problem. Effective valid cuts are developed to reduce feasible search space to tighten the duality gap. Using data provided by the railway company, we demonstrate the effectiveness of the proposed method compared with that of constraint programming techniques for large-scale problems through computational experiments. (C) 2014 Elsevier B.V. All rights reserved.
Keyword:
Railway scheduling
Crew rostering
Two-level decomposition algorithm
Cut generation
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
2.2W
被引数:
6.4W
机构
引用论文
.png){kind=icon}
分享收藏Integrated airline crew scheduling: A hi-dynamic constraint aggregation method using neighborhoods集成的航空公司机组调度: 使用邻域的高动态约束聚合方法
PREAI
分享收藏
查看更多内容