This paper considers a nurse rostering problem from a ward at a Danish hospital. The problem is highly constrained and comprises a large set of different constraints. A branch-and-price method for solving the problem ...
详细信息
This paper considers a nurse rostering problem from a ward at a Danish hospital. The problem is highly constrained and comprises a large set of different constraints. A branch-and-price method for solving the problem exactly is proposed. The master problem is to assign schedules to the nurses, and its linear relaxation is solved by means of columngeneration. The pricing sub-problem is to generate feasible schedules for the nurses and-as a couple of different constraints including several special Danish regulations have to be observed-is solved by constraintprogramming. A number of specific algorithms for handling these constraints are proposed. The method is very flexible regarding the rules a schedule should comply with, which is a key concern when creating solution methods for nurse rostering problems. Computational tests show that optimal solutions can be found for instances with a two weeks planning period in a reasonable amount of computing time.
The Airline Crew Assignment Problem (ACA) consists of assigning lines of work to a set of crew members such that a set of activities is partitioned and the costs for that assignment are minimized. Especially for Europ...
详细信息
The Airline Crew Assignment Problem (ACA) consists of assigning lines of work to a set of crew members such that a set of activities is partitioned and the costs for that assignment are minimized. Especially for European airline companies, complex constraints defining the feasibility of a line of work have to be respected. We developed two different algorithms to tackle the large scale optimization problem of Airline Crew Assignment. The first is an application of the constraintprogramming (CP) basedcolumngeneration Framework. The second approach performs a CP based heuristic tree search. We present how both algorithms can be coupled to overcome their inherent weaknesses by integrating methods from constraintprogramming and Operations Research. Numerical results show the superiority of the hybrid algorithm in comparison to CP based tree search and columngeneration alone.
暂无评论