The Experts below are selected from a list of 3705 Experts worldwide ranked by ideXlab platform
Dennis Huisman - One of the best experts on this subject based on the ideXlab platform.
-
solution approaches for integrated vehicle and Crew Scheduling with electric buses
2021Co-Authors: Shyam Sundar Govinda Raja Perumal, Dennis Huisman, Twan Dollevoet, Richard Martin Lusby, Jesper Larsen, Morten RiisAbstract:Abstract The use of electric buses is expected to rise due to its environmental benefits. However, electric vehicles are less flexible than conventional diesel buses due to their limited driving range and longer recharging times. Therefore, Scheduling electric vehicles adds further operational difficulties. Additionally, various labor regulations challenge public transport companies to find a cost-efficient Crew schedule. Vehicle and Crew Scheduling problems essentially define the cost of operations. In practice, these two problems are often solved sequentially. In this paper, we introduce the integrated electric vehicle and Crew Scheduling problem (E-VCSP). Given a set of timetabled trips and recharging stations, the E-VCSP is concerned with finding vehicle and Crew schedules that cover the timetabled trips and satisfy operational constraints, such as limited driving range of electric vehicles and labor regulations for the Crew while minimizing total operational cost. An adaptive large neighborhood search that utilizes branch-and-price heuristics is proposed to tackle the E-VCSP. The proposed method is tested on real-life instances from public transport companies in Denmark and Sweden that contain up to 1109 timetabled trips. The heuristic approach provides evidence of improving efficiency of transport systems when the electric vehicle and Crew Scheduling aspects are considered simultaneously. By comparing to the traditional sequential approach, the heuristic finds improvements in the range of 1.17–4.37% on average. A sensitivity analysis of the electric bus technology is carried out to indicate its implications for the Crew schedule and the total operational cost. The analysis shows that the operational cost decreases with increasing driving range (120–250 km) of electric vehicles.
-
solution approaches for vehicle and Crew Scheduling with electric buses
2020Co-Authors: Shyam Sundar Govinda Raja Perumal, Dennis Huisman, Twan Dollevoet, Richard Martin Lusby, Jesper Larsen, Morten RiisAbstract:The use of electric buses is expected to rise due to its environmental benefits. However, electric vehicles are less exible than conventional diesel buses due to their limited driving range and longer recharging times. Therefore, Scheduling electric vehicles adds further operational dificulties. Additionally, various labor regulations challenge public transport companies to find a cost-effcient Crew schedule. Vehicle and Crew Scheduling problems essentially define the cost of operations. In practice, these two problems are often solved sequentially. In this paper, we introduce the integrated electric vehicle and Crew Scheduling problem (E-VCSP). Given a set of timetabled trips and recharging stations, the E-VCSP is concerned with finding vehicle and Crew schedules that cover the timetabled trips and satisfy operational constraints, such as limited driving range of electric vehicles and labor regulations for the Crew while minimizing total operational cost. An adaptive large neighborhood search that utilizes branch-and-price heuristics is proposed to tackle the E-VCSP. The proposed method is tested on real-life instances from public transport companies in Denmark and Sweden that contain up to 1,109 timetabled trips. The heuristic approach provides evidence of improving efficiency of transport systems when the electric vehicle and Crew Scheduling aspects are considered simultaneously. By comparing to the traditional sequential approach, the heuristic finds improvements in the range of 1.17-4.37% on average. A sensitivity analysis of the electric bus technology is carried out to indicate its implications for the Crew schedule and the total operational cost. The analysis shows that the operational cost decreases with increasing driving range (120 to 250 kilometers) of electric vehicles.
-
integrating timetabling and Crew Scheduling at a freight railway operator
2016Co-Authors: Lukas Bach, Twan Dollevoet, Dennis HuismanAbstract:We investigate to what degree we can integrate a train timetabling/engine Scheduling problem with a Crew Scheduling problem. In the timetabling/engine Scheduling problem, we determine for each demand a specific time within its time window when the demand should be serviced. Furthermore, we generate engine duties for the demands. In our solution approach for the overall problem, we first obtain an optimal solution for the timetabling/engine Scheduling problem. When solving the Crew Scheduling problem, we then exploit the fact that numerous optimal and near optimal solutions exist for the previous problem. We consider all these solutions that can be obtained from the optimal engine schedule by shifting the demands in time, while keeping the order of demands in the engine duties intact. In particular, in the Crew Scheduling stage it is allowed to retime the service of demands if the additional cost is outweighed by the Crew savings. This information is implemented in a mathematical model for the Crew Scheduling problem. The model is solved using a column generation scheme. We perform computational experiments based on a case at a freight railway operator, DB Schenker Rail Scandinavia, and show that significant cost savings can be achieved.
-
integrating timetabling and Crew Scheduling at a freight railway operator
2014Co-Authors: Lukas Bach, Twan Dollevoet, Dennis HuismanAbstract:__Abstract__ We investigate to what degree we can integrate a Train Timetabling / Engine Scheduling Problem with a Crew Scheduling Problem. In the Timetabling Problem we design a timetable for the desired lines by fixing the departure and arrival times. Also, we allocate time-slots in the network to secure a feasible timetable. Next, we assign engines in the Engine Scheduling Problem to the lines in accordance with the timetable. The overall integration is achieved by obtaining an optimal solution for the Timetabling / Engine Scheduling Problem. We exploit the fact that numerous optimal, and near optimal solutions exists. We consider all solutions that can be obtained from the optimal engine schedule by altering the timetable, while keeping the order of demands in the schedules intact. The Crew Scheduling model is allowed to re-time the service of demands if the additional cost is outweighed by the Crew savings. This information is implemented in a mathematical model for the Crew Scheduling Problem. The model is solved using a column generation scheme. Hereby it is possible for the Crew Scheduling algorithm to adjust the timetable and achieve a better overall solution. We perform computational experiments based on a case at a freight railway operator, DB Schenker Rail Scandinavia, and show that significant cost savings can be achieved.
-
solving large scale Crew Scheduling problems in practice
2010Co-Authors: Erwin Abbink, Dennis Huisman, Twan Dollevoet, Luis Albino, Jorge Roussado, Ricardo L SaldanhaAbstract:This paper deals with large-scale Crew Scheduling problems arising at the Dutch railway operator, Netherlands Railways (NS). NS operates about 30,000 trains a week. All these trains need a driver and a certain number of guards. Some labor rules restrict the duties of a certain Crew base over the complete week. Therefore splitting the problem in several subproblems per day leads to suboptimal solutions. In this paper, we present an algorithm, called LUCIA, which can solve such huge instances without splitting. This algorithm combines Lagrangian heuristics, column generation and fixing techniques. We compare the results with existing practice. The results show that the new method significantly improves the solution.
Francois Soumis - One of the best experts on this subject based on the ideXlab platform.
-
structured convolutional kernel networks for airline Crew Scheduling
2021Co-Authors: Yassine Yaakoubi, Francois Soumis, Simon LacostejulienAbstract:Motivated by the needs from an airline Crew Scheduling application, we introduce structured convolutional kernel networks (Struct-CKN), which combine CKNs from Mairal et al. (2014) in a structured prediction framework that supports constraints on the outputs. CKNs are a particular kind of convolutional neural networks that approximate a kernel feature map on training data, thus combining properties of deep learning with the non-parametric flexibility of kernel methods. Extending CKNs to structured outputs allows us to obtain useful initial solutions on a flight-connection dataset that can be further refined by an airline Crew Scheduling solver. More specifically, we use a flight-based network modeled as a general conditional random field capable of incorporating local constraints in the learning process. Our experiments demonstrate that this approach yields significant improvements for the large-scale Crew pairing problem (50,000 flights per month) over standard approaches, reducing the solution cost by 17% (a gain of millions of dollars) and the cost of global constraints by 97%.
-
Airline Crew Scheduling: models, algorithms, and data sets
2017Co-Authors: Atoosa Kasirzadeh, Mohammed Saddoune, Francois SoumisAbstract:The airline Crew Scheduling problem has received extensive attention, particularly in the last 60 years. This problem is frequently divided into Crew pairing and Crew assignment because of its large size and the complex safety agreements and contractual rules. Several solution methodologies have been developed, but many objectives and constraints are treated approximately and research is ongoing. In this paper, we present a comprehensive problem definition for the airline Crew Scheduling problem, and we review existing problem formulations and solution methodologies. In addition, we formulate the personalized cockpit Crew Scheduling problem as a set covering problem and we solve it using column generation. We present computational results for real data from a major US carrier, and we describe the data sets (available on the internet) in detail to establish a basis for future research.
-
integrated airline Crew Scheduling a bi dynamic constraint aggregation method using neighborhoods
2011Co-Authors: Mohammed Saddoune, Guy Desaulniers, Issmail Elhallaoui, Francois SoumisAbstract:The integrated Crew Scheduling (ICS) problem consists of determining, for a set of available Crew members, least-cost schedules that cover all flights and respect various safety and collective agreement rules. A schedule is a sequence of pairings interspersed by rest periods that may contain days off. A pairing is a sequence of flights, connections, and rests starting and ending at the same Crew base. Given its high complexity, the ICS problem has been traditionally tackled using a sequential two-stage approach, where a Crew pairing problem is solved in the first stage and a Crew assignment problem in the second stage. Recently, Saddoune et al. (2010b) developed a model and a column generation/dynamic constraint aggregation method for solving the ICS problem in one stage. Their computational results showed that the integrated approach can yield significant savings in total cost and number of schedules, but requires much higher computational times than the sequential approach. In this paper, we enhance this method to obtain lower computational times. In fact, we develop a bi-dynamic constraint aggregation method that exploits a neighborhood structure when generating columns (schedules) in the column generation method. On a set of seven instances derived from real-world flight schedules, this method allows to reduce the computational times by an average factor of 2.3, while improving the quality of the computed solutions.
-
an integrated aircraft routing Crew Scheduling and flight retiming model
2007Co-Authors: Anne Mercier, Francois SoumisAbstract:In the integrated aircraft routing, Crew Scheduling and flight retiming problem, a minimum-cost set of aircraft routes and Crew pairings must be constructed while choosing a departure time for each flight leg within a given time window. Linking constraints ensure that the same schedule is chosen for both the aircraft routes and the Crew pairings, and impose minimum connection times for Crews that depend on aircraft connections and departure times. We propose a compact formulation of the problem and a Benders decomposition method with a dynamic constraint generation procedure to solve it. Computational experiments performed on test instances provided by two major airlines show that allowing some flexibility on the departure times within an integrated model yields significant cost savings while ensuring the feasibility of the resulting aircraft routes and Crew pairings.
-
the operational flight and multi Crew Scheduling problem
2005Co-Authors: Mirela Stojkovic, Francois SoumisAbstract:This paper introduces a new kind of operational multi-Crew Scheduling problem which consists in simultaneously modifying, as necessary, the existing flight departure times and planned individual work days (duties) for the set of Crew members, while respecting predefined aircraft itineraries. The splitting of a planned Crew is allowed during a day of operations, where it is more important to cover a flight than to keep planned Crew members together. The objective is to cover a maximum number of flights from a day of operations while minimizing changes in both the flight schedule and the next-day planned duties for the considered Crew members. A new type of the same flight departure time constraints is introduced. They ensure that a flight which belongs to several personalized duties, where the number of duties is equal to the number of Crew members assigned to the flight, will have the same departure time in each of these duties. Two variants of the problem are considered. The first variant allows covering of flights by less than the planned number of Crew members, while the second one requires covering of flights by a complete Crew. The problem is mathematically formulated as an integer nonlinear multi-commodity network flow model with time windows and supplementary constraints. The optimal solution approach is based on Dantzig-Wolfe decomposition/column generation embedded into a branch-and-bound scheme. The resulting computational times on commercial-size problems are very good. Our new simultaneous approach produces solutions whose quality is far better than that of the traditional sequential approach where the flight schedule has been changed first and then input as a fixed data to the Crew Scheduling problem.
Jacques Desrosiers - One of the best experts on this subject based on the ideXlab platform.
-
accelerating strategies in column generation methods for vehicle routing and Crew Scheduling problems
2002Co-Authors: Guy Desaulniers, Jacques Desrosiers, Marius M SolomonAbstract:This paper focuses on accelerating strategies used in conjunction with column generation to solve vehicle routing and Crew Scheduling problems. We describe techniques directed at speeding up each of the five phases of the solution process: pre-processor, subproblem, master problem, branch-and-bound, and post-optimizer. In practical applications, these methods often were key elements for the viability of this optimization approach. The research cited here shows their use led to computational gains, and notably to solutions that could not have been obtained otherwise due to practical problem complexity and size. In particular, we present recent methods directed at the integer programming aspect of the approach that were instrumental in substantially reducing the integrality gap found in certain applications, thereby helping to efficiently produce excellent quality solutions.
-
Simultaneous Vehicle and Crew Scheduling in Urban Mass Transit Systems
2001Co-Authors: Knut Haase, Guy Desaulniers, Jacques DesrosiersAbstract:This paper presents an exact approach for solving the simultaneous vehicle and Crew Scheduling problem in urban mass transit systems. We consider the single depot case with a homogeneous fleet of vehicles. This approach relies on a set partitioning formulation for the driver Scheduling problem that incorporates side constraints for the bus itineraries. The proposed solution approach consists of a column generation process (only for the Crew schedules) integrated into a branch-and-bound scheme. The side constraints on buses guarantee that an optimal vehicle assignment can be derived afterwards in polynomial time. A computational study shows that this approach out-performs the previous methods found in the literature for a set of randomly generated instances. A heuristic version of the solution approach is also proposed and tested on larger instances.
-
benders decomposition for simultaneous aircraft routing and Crew Scheduling
2000Co-Authors: Jeanfrancois Cordeau, Francois Soumis, Goran Stojkovic, Jacques DesrosiersAbstract:Given a set of flight legs to be flown by a single type of aircraft, the simultaneous aircraft routing and Crew Scheduling problem consists of determining a minimum-cost set of aircraft routes and Crew pairings such that each flight leg is covered by one aircraft and one Crew, and side constraints are satisfied. While some side constraints such as maximum flight time and maintenance requirements involve only Crews or aircraft, linking constraints impose minimum connection times for Crews that depend on aircraft connections. To handle these linking constraints, a solution approach based on Benders decomposition is proposed. The solution process iterates between a master problem that solves the aircraft routing problem, and a subproblem that solves the Crew pairing problem. Because of their particular structure, both of these problems are solved by column generation. A heuristic branch-and-bound method is used to compute integer solutions. On a set of test instances based on data provided by an airline, the integrated approach produced significant cost savings in comparison with the sequential planning process commonly used in practice. The largest instance solved contains more than 500 flight legs over a 3-day period.
-
the operational airline Crew Scheduling problem
1998Co-Authors: Mirela Stojkovic, Francois Soumis, Jacques DesrosiersAbstract:This paper describes the operational airline Crew Scheduling problem and represents a first published attempt to solve it. The problem consists of modifying, as necessary, personalized planned monthly assignments of airline Crew members during day-to-day operations. It requires overing, at minimal cost, all flight segments from a given time period with available Crew while minimizing the disturbances of Crew members. To generate modified pairings for selected Crew members, both the classical Crew pairing problem and the problem of constructing personalized monthly assignments must be treated simultaneously. An optimization approach is proposed for the problem in which the flight schedule is fixed and represents input data. The problem is mathematically formulated as a Set Partitioning type problem, and a column generation method embedded in a branch-and-bound search tree has been implemented to solve it. Good results, from the point of view of both solution times and achieved objectives, have been obtained on generated test problems. Because the solution time is reasonable, several different scenarios of the same problem may be solved. A final decision can then be made by considering all scenarios and choosing the one whose solution is the best in the given situation.
Jesper Larsen - One of the best experts on this subject based on the ideXlab platform.
-
solution approaches for integrated vehicle and Crew Scheduling with electric buses
2021Co-Authors: Shyam Sundar Govinda Raja Perumal, Dennis Huisman, Twan Dollevoet, Richard Martin Lusby, Jesper Larsen, Morten RiisAbstract:Abstract The use of electric buses is expected to rise due to its environmental benefits. However, electric vehicles are less flexible than conventional diesel buses due to their limited driving range and longer recharging times. Therefore, Scheduling electric vehicles adds further operational difficulties. Additionally, various labor regulations challenge public transport companies to find a cost-efficient Crew schedule. Vehicle and Crew Scheduling problems essentially define the cost of operations. In practice, these two problems are often solved sequentially. In this paper, we introduce the integrated electric vehicle and Crew Scheduling problem (E-VCSP). Given a set of timetabled trips and recharging stations, the E-VCSP is concerned with finding vehicle and Crew schedules that cover the timetabled trips and satisfy operational constraints, such as limited driving range of electric vehicles and labor regulations for the Crew while minimizing total operational cost. An adaptive large neighborhood search that utilizes branch-and-price heuristics is proposed to tackle the E-VCSP. The proposed method is tested on real-life instances from public transport companies in Denmark and Sweden that contain up to 1109 timetabled trips. The heuristic approach provides evidence of improving efficiency of transport systems when the electric vehicle and Crew Scheduling aspects are considered simultaneously. By comparing to the traditional sequential approach, the heuristic finds improvements in the range of 1.17–4.37% on average. A sensitivity analysis of the electric bus technology is carried out to indicate its implications for the Crew schedule and the total operational cost. The analysis shows that the operational cost decreases with increasing driving range (120–250 km) of electric vehicles.
-
solution approaches for vehicle and Crew Scheduling with electric buses
2020Co-Authors: Shyam Sundar Govinda Raja Perumal, Dennis Huisman, Twan Dollevoet, Richard Martin Lusby, Jesper Larsen, Morten RiisAbstract:The use of electric buses is expected to rise due to its environmental benefits. However, electric vehicles are less exible than conventional diesel buses due to their limited driving range and longer recharging times. Therefore, Scheduling electric vehicles adds further operational dificulties. Additionally, various labor regulations challenge public transport companies to find a cost-effcient Crew schedule. Vehicle and Crew Scheduling problems essentially define the cost of operations. In practice, these two problems are often solved sequentially. In this paper, we introduce the integrated electric vehicle and Crew Scheduling problem (E-VCSP). Given a set of timetabled trips and recharging stations, the E-VCSP is concerned with finding vehicle and Crew schedules that cover the timetabled trips and satisfy operational constraints, such as limited driving range of electric vehicles and labor regulations for the Crew while minimizing total operational cost. An adaptive large neighborhood search that utilizes branch-and-price heuristics is proposed to tackle the E-VCSP. The proposed method is tested on real-life instances from public transport companies in Denmark and Sweden that contain up to 1,109 timetabled trips. The heuristic approach provides evidence of improving efficiency of transport systems when the electric vehicle and Crew Scheduling aspects are considered simultaneously. By comparing to the traditional sequential approach, the heuristic finds improvements in the range of 1.17-4.37% on average. A sensitivity analysis of the electric bus technology is carried out to indicate its implications for the Crew schedule and the total operational cost. The analysis shows that the operational cost decreases with increasing driving range (120 to 250 kilometers) of electric vehicles.
-
the home care Crew Scheduling problem preference based visit clustering and temporal dependencies
2012Co-Authors: Matias Sevel Rasmussen, Anders Hoeg Dohn, Tor Fog Justesen, Jesper LarsenAbstract:Abstract In the Home Care Crew Scheduling Problem a staff of home carers has to be assigned a number of visits to patients’ homes, such that the overall service level is maximised. The problem is a generalisation of the vehicle routing problem with time windows. Required travel time between visits and time windows of the visits must be respected. The challenge when assigning visits to home carers lies in the existence of soft preference constraints and in temporal dependencies between the start times of visits. We model the problem as a set partitioning problem with side constraints and develop an exact branch-and-price solution algorithm, as this method has previously given solid results for classical vehicle routing problems. Temporal dependencies are modelled as generalised precedence constraints and enforced through the branching. We introduce a novel visit clustering approach based on the soft preference constraints. The algorithm is tested both on real-life problem instances and on generated test instances inspired by realistic settings. The use of the specialised branching scheme on real-life problems is novel. The visit clustering decreases run times significantly, and only gives a loss of quality for few instances. Furthermore, the visit clustering allows us to find solutions to larger problem instances, which cannot be solved to optimality.
-
the home care Crew Scheduling problem
2008Co-Authors: Anders Hoeg Dohn, Matias Sevel Rasmussen, Tor Fog Justesen, Jesper LarsenAbstract:In the Home Care Crew Scheduling Problem (HCCSP) a staff of caretakers has to be assigned a number of tasks, such that the total number of assigned tasks is maximised. The tasks have different locations and positions in time, and travelling time and time windows must be respected. The challenge when assigning tasks to caretakers lies in the existence of several soft constraints and indeed also in timewise constraints connecting the tasks. Preferably all of these constraints are satisfied, however for different reasons, this is not always possible. We call a solution to the problem home care optimal, if it satisfies all soft constraints. The problem originates from the Scheduling of tasks in the home care sector and has many similarities with the well-studied Vehicle Routing Problem with Time Windows (VRPTW) and the Crew Scheduling Problem with Time Windows (CSPTW). Former approaches to solving the HCCSP involve the use of heuristic methods. In this thesis, we will show that by using an exact algorithm as the basis and then modifying this intelligently, it is possible to generate home care optimal solutions which are in general better than the solutions found by the use of heuristics. The thesis constitutes a proof-of-concept and only focuses on the efficiency of the algorithm to some extent. The developed exact algorithm is based on a branch-and-price approach using column generation. The algorithm is tested on real-life problem instances supplied by the Danish company Zealand Care and we obtain solutions that are near to home care optimal in most cases. The problem is decomposed into a master and a subproblem. We model a very general precedence constraint that captures all timewise constraints from real-life, and we handle precedence constraints in the branching, which we have not seen elsewhere in the literature. We devise an exact label setting algorithm for solving the Elementary Shortest Path Problem with Resource Constraints (ESPPRC) subproblem. Solving the subproblem constitutes a substantial impact on the overall running time of the branch-and-price algorithm. To counteract this, intelligent reductions of the ESPPRC networks are introduced. When reducing the ESPPRC networks, the number of unassigned tasks may increase, hence the branch-and-price algorithm is extended to handle tasks that are unassigned as a consequence of the reductions of the ESPPRC networks. The reductions in the ESPPRC networks and the changes to the branchand-price algorithm result in improvements of both the quality of the solutions, many of which are close to being home care optimal, and the overall efficiency of the algorithm.
Ulrich W Thonemann - One of the best experts on this subject based on the ideXlab platform.
-
a graph partitioning strategy for solving large scale Crew Scheduling problems
2015Co-Authors: Silke Jutte, Ulrich W ThonemannAbstract:Railway Crew Scheduling deals with generating driver duties for a given train timetable such that all work regulations are met and the resulting schedule has minimal cost. Typical problem instances in the freight railway industry require the generation of duties for thousands of drivers operating tens of thousands of trains per week. Due to short runtime requirements, common solution approaches decompose the optimization problem into smaller subproblems that are solved separately. Several studies have shown that the way of decomposing the problem significantly affects the solution quality. An overall best decomposition strategy for a freight railway Crew Scheduling problem, though, is not known. In this paper, we present general considerations on when to assign two scheduled train movements to separate subproblems (and when to rather assign them to the same subproblem) and deduct a graph partitioning based decomposition algorithm with several variations. Using a set of real-world problem instances from a major European railway freight carrier, we evaluate our strategy and benchmark the performance of the decomposition algorithm both against a common non-decomposition algorithm and a lower bound on the optimal solution schedule. The test runs show that our decomposition algorithm is capable of producing high-quality solution schedules while significantly cutting runtimes compared to the non-decomposition solution algorithm. We are following a "greenfield" approach, where no information on previous schedules is needed. Hence, our approach is applicable to any railway Crew Scheduling setting, including network enlargement, integration of new customers, etc.
-
divide and price a decomposition algorithm for solving large railway Crew Scheduling problems
2011Co-Authors: Silke Jutte, Ulrich W ThonemannAbstract:Abstract The railway Crew Scheduling problem consists of generating Crew duties to operate trains at minimal cost, while meeting all work regulations and operational requirements. Typically, a railway operation uses tens of thousands of train movements (trips) and requires thousands of Crew members to be assigned to these trips. Despite the large size of the problem, Crew schedules need to be generated in short time, because large parts of the train schedule are not finalized until few days before operation. We present a column generation based decomposition algorithm which achieves high-quality solutions at reasonable runtimes. Our divide-and-price algorithm decomposes the problem into overlapping regions which are optimized in parallel. A trip belonging to several regions is initially assigned to one region (“divide”). The corresponding dual information from optimization is then used as a bonus to offer the trip to other regions (“price”). Pricing and assignment of trips are dynamically updated in the course of the optimization. Tests of our algorithm on large-scale problem instances of a major European freight railway carrier yielded promising results.
-
optimizing railway Crew Scheduling at db schenker
2011Co-Authors: Silke Jutte, Marc Albers, Ulrich W Thonemann, Knut HaaseAbstract:Freight railway Crew Scheduling consists of generating Crew duties for operating trains on a schedule at minimal cost while meeting all work regulations and operational requirements. Typically, a freight railway operation uses thousands of trains and requires thousands of Crew members to operate them. Because of the problem's large size, even moderate percentage savings in Crew costs translate into large monetary savings. However, freight railway operations are complex, and a Crew-Scheduling problem is difficult to solve. We describe the development and implementation of Crew-Scheduling software at DB Schenker, the largest European railway freight carrier. The software is based on a column-generation solution technique. Computational results demonstrate that high-quality solutions can be obtained using reasonable run times, even for large problem instances. We implemented all of DB Schenker's major requirements to ensure that the software is operationally viable. Management also uses this software as a decision support tool for strategic planning.
