The Experts below are selected from a list of 12189 Experts worldwide ranked by ideXlab platform
Leo Kroon - One of the best experts on this subject based on the ideXlab platform.
-
Rolling Stock rescheduling in passenger railway transportation using dead heading trips and adjusted passenger demand
2017Co-Authors: Joris Wagenaar, Leo Kroon, Ioannis FragkosAbstract:In this paper we introduce dead-heading trips and adjusted passenger demand in the Rolling Stock Rescheduling Problem (RSRP). Unfortunately, disruptions disturb passenger railway transportation on a daily basis. Such a disruption causes infeasibilities in the timetable, Rolling Stock circulation, and crew schedule. We propose a Mixed-Integer Linear Programming model to tackle the RSRP. This formulation includes the possibility of using dead-heading trips (moving empty trains) during, and after, a disruption. Furthermore, passenger flows are included to handle the adjusted passenger demand after the occurrence of a disruption. Many Rolling Stock rescheduling models are unable to cope with changing passenger demand. In this paper we include passenger demand on a more accurate level in the RSRP. We have tested the model on different cases from Netherlands Railways. The results show that dead-heading trips are useful to reduce the number of cancelled trips and that adjusted passenger demand has a large influence on the rescheduled circulation.
-
passenger oriented railway disruption management by adapting timetables and Rolling Stock schedules
2017Co-Authors: Lucas P Veelenturf, Leo Kroon, Gábor MarótiAbstract:In passenger railway operations, unforeseen events require railway operators to adjust their timetable and their resource schedules. The passengers will also adapt their routes to their destinations. When determining the new timetable and Rolling Stock schedule, the railway operator has to take passenger behavior into account. The operator should increase the capacity of trains for which the operator expects more demand than on a regular day. Furthermore, the operator could increase the frequency of the trains that serve stations with an additional demand. This paper describes a real-time disruption management approach which integrates the rescheduling of the Rolling Stock and the timetable by taking the changed passenger demand into account. The timetable decisions are limited to additional stops of trains at stations at which they normally would not call. Several variants of the approach are suggested, with the difference in how to determine which additional stops should be executed. Real-time rescheduling requires fast solutions. Therefore a heuristic approach is used. We demonstrate the performance of the several variants of our algorithm on realistic instances of Netherlands Railways, the major railway operator in the Netherlands.
-
maintenance appointments in railway Rolling Stock rescheduling
2017Co-Authors: Joris Wagenaar, Leo Kroon, Marie SchmidtAbstract:This paper addresses the railway Rolling Stock rescheduling problem, while taking maintenance appointments into account. After a disruption, the Rolling Stock of the disrupted passenger trains has to be rescheduled to restore a feasible Rolling Stock circulation. Usually, a number of train units have a scheduled maintenance appointment during the day: these appointments must be taken into account while rescheduling the Rolling Stock. In this paper we propose three mixed-integer programming models for this purpose. All models are extensions of the composition model from the literature, which does not distinguish individual train units. The extra unit type model adds an additional Rolling Stock type for each train unit that requires maintenance. The shadow-account model keeps track of a shadow account for each train unit that requires maintenance. The job-composition model creates a path for each train unit such that the train units that require maintenance are on time for their maintenance appointments. Al...
-
a comparison of two exact methods for passenger railway Rolling Stock re scheduling
2016Co-Authors: Jorgen Thorlund Haahr, Lucas P Veelenturf, Joris Wagenaar, Leo KroonAbstract:The assignment of Rolling Stock units to timetable services in passenger railways is an important optimization problem that has been addressed by many papers in different forms. Solution approaches have been proposed for different planning phases: strategic, tactical, operational, and real-time planning. In this paper we compare two approaches within the operational and real-time planning phase. The first exact approach is based on a known Mixed Integer Linear Program (MILP) which is solved using CPLEX. The second approach is a new method that is an extension of a recently introduced MILP, which is solved using a column and row generation approach. In this paper, we benchmark the performance of the methods on networks of two countries (Denmark and The Netherlands). We use the approaches to make daily schedules and we test their real time applicability by performing tests with different disruption scenarios. The computational experiments demonstrate that both models can be used on both networks and are able to find optimal Rolling Stock circulations in the different planning phases. Furthermore, the results show that both approaches are sufficiently fast to be used in a real-time setting.
-
maintenance appointments in railway Rolling Stock rescheduling
2016Co-Authors: Joris Wagenaar, Leo Kroon, Marie SchmidtAbstract:This paper addresses the Rolling Stock Rescheduling Problem (RSRP), while taking maintenance appointments into account. After a disruption, the Rolling Stock of the disrupted passenger trains has to be rescheduled in order to restore a feasible Rolling Stock circulation. Usually, a number of train units have a scheduled maintenance appointment during the day: these appointments must be taken into account while rescheduling the Rolling Stock. In this paper we propose three Mixed Integer Programming (MIP) models for this purpose. All models are extensions of the Composition model from literature, which does not distinguish individual train units. The Extra Unit Type model adds an additional Rolling Stock type for each train unit that requires maintenance. The Shadow- Account model keeps track of a shadow account for each train unit that requires maintenance. The Job-Composition model creates a path for each train unit such that the train units that require maintenance are on time for their maintenance appointments. All models are tested on instances of Netherlands Railways (NS). The results show that especially the Shadow-Account model and the Job-Composition model are effectively able to take maintenance appointments into account during real-time rescheduling. It depends on the characteristics of an instance whether the Shadow-Account model or the Job-Composition model performs best.
Gábor Maróti - One of the best experts on this subject based on the ideXlab platform.
-
a variable neighborhood search heuristic for Rolling Stock rescheduling
2021Co-Authors: Rowan Hoogervorst, Gábor Maróti, Twan Dollevoet, Dennis HuismanAbstract:We present a Variable Neighborhood Search heuristic for the Rolling Stock rescheduling problem. Rolling Stock rescheduling is needed when a disruption leads to cancellations in the timetable. In Rolling Stock rescheduling, one must then assign duties, i.e., sequences of trips, to the available train units in such a way that both passenger comfort and operational performance are taken into account. For our heuristic, we introduce three neighborhoods, which focus on swapping duties between train units, on improving the individual duties and on changing the shunting that occurs between trips, respectively. These neighborhoods are used for both a Variable Neighborhood Descent local search procedure and for perturbing the current solution in order to escape from local optima. Moreover, we show that the heuristic can be extended to the setting of flexible Rolling Stock turnings at ending stations by introducing a fourth neighborhood. We apply our heuristic to instances of Netherlands Railways (NS). The results show that the heuristic is able to find high-quality solutions within one minute of solving time. This allows Rolling Stock dispatchers to use our heuristic in real-time rescheduling.
-
a variable neighborhood search heuristic for Rolling Stock rescheduling
2019Co-Authors: Rowan Hoogervorst, Gábor Maróti, Twan Dollevoet, Dennis HuismanAbstract:textabstractWe present a Variable Neighborhood Search heuristic for the Rolling Stock rescheduling problem. Rolling Stock rescheduling is needed when a disruption leads to cancellations in the timetable. In Rolling Stock rescheduling, we then assign duties, i.e., sequences of trips, to the available train units in such a way that both passenger comfort and operational performance are taken into account. For our heuristic, we introduce three neighborhoods that can be used for Rolling Stock rescheduling, which respectively focus on swapping duties between train units, on improving the individual duties and on changing the shunting that occurs between trips. These neighborhoods are used for both a Variable Neighborhood Descent local search procedure and for perturbing the current solution in order to escape from local optima. We apply our heuristic to instances of Netherlands Railways (NS). The results show that the heuristic is able to find high-quality solutions in a reasonable amount of time. This allows Rolling Stock dispatchers to use our heuristic in real-time rescheduling.
-
passenger oriented railway disruption management by adapting timetables and Rolling Stock schedules
2017Co-Authors: Lucas P Veelenturf, Leo Kroon, Gábor MarótiAbstract:In passenger railway operations, unforeseen events require railway operators to adjust their timetable and their resource schedules. The passengers will also adapt their routes to their destinations. When determining the new timetable and Rolling Stock schedule, the railway operator has to take passenger behavior into account. The operator should increase the capacity of trains for which the operator expects more demand than on a regular day. Furthermore, the operator could increase the frequency of the trains that serve stations with an additional demand. This paper describes a real-time disruption management approach which integrates the rescheduling of the Rolling Stock and the timetable by taking the changed passenger demand into account. The timetable decisions are limited to additional stops of trains at stations at which they normally would not call. Several variants of the approach are suggested, with the difference in how to determine which additional stops should be executed. Real-time rescheduling requires fast solutions. Therefore a heuristic approach is used. We demonstrate the performance of the several variants of our algorithm on realistic instances of Netherlands Railways, the major railway operator in the Netherlands.
-
rescheduling of railway Rolling Stock with dynamic passenger flows
2015Co-Authors: Leo Kroon, Gábor Maróti, Lars Kjaer NielsenAbstract:In this paper we describe a real-time Rolling Stock rescheduling model for disruption management of passenger railways. Large-scale disruptions, e.g., due to malfunctioning infrastructure or Rolling Stock, usually result in the cancellation of train services. As a consequence, the passenger flows change, because passengers will look for alternative routes to get to their destinations. Our model takes these dynamic passenger flows into account. This is in contrast with most traditional Rolling Stock rescheduling models that consider the passenger flows either as static or as given input. Furthermore, we describe an iterative heuristic for solving the Rolling Stock rescheduling model with dynamic passenger flows. The model and the heuristic were tested on realistic problem instances of Netherlands Railways, the major operator of passenger trains in the Netherlands. The computational results show that the average delay of the passengers can be reduced significantly by taking into account the dynamic behavior of the passenger flows on the detour routes, and that the computation times of the iterative heuristic are appropriate for an application in real-time disruption management.
-
a Rolling horizon approach for disruption management of railway Rolling Stock
2012Co-Authors: Lars Kjaer Nielsen, Leo Kroon, Gábor MarótiAbstract:This paper deals with real-time disruption management of Rolling Stock in passenger railway transportation. We describe a generic framework for dealing with disruptions of railway Rolling Stock schedules. The framework is presented as an online combinatorial decision problem, where the uncertainty of a disruption is modeled by a sequence of information updates. To decompose the problem and to reduce the computation time, we propose a Rolling horizon approach: Rolling Stock decisions are only considered if they are within a certain time horizon from the time of rescheduling. The schedules are then revised as time progresses and new information becomes available. We extend an existing model for Rolling Stock scheduling to the specific requirements of the real-time situation, and we apply it in the Rolling horizon framework. We perform computational tests on instances constructed from real-life cases of Netherlands Railways (NS), the main operator of passenger trains in the Netherlands. We explore the consequences of different settings of the approach for the trade-off between solution quality and computation time.
Joris Wagenaar - One of the best experts on this subject based on the ideXlab platform.
-
Rolling Stock rescheduling in passenger railway transportation using dead heading trips and adjusted passenger demand
2017Co-Authors: Joris Wagenaar, Leo Kroon, Ioannis FragkosAbstract:In this paper we introduce dead-heading trips and adjusted passenger demand in the Rolling Stock Rescheduling Problem (RSRP). Unfortunately, disruptions disturb passenger railway transportation on a daily basis. Such a disruption causes infeasibilities in the timetable, Rolling Stock circulation, and crew schedule. We propose a Mixed-Integer Linear Programming model to tackle the RSRP. This formulation includes the possibility of using dead-heading trips (moving empty trains) during, and after, a disruption. Furthermore, passenger flows are included to handle the adjusted passenger demand after the occurrence of a disruption. Many Rolling Stock rescheduling models are unable to cope with changing passenger demand. In this paper we include passenger demand on a more accurate level in the RSRP. We have tested the model on different cases from Netherlands Railways. The results show that dead-heading trips are useful to reduce the number of cancelled trips and that adjusted passenger demand has a large influence on the rescheduled circulation.
-
maintenance appointments in railway Rolling Stock rescheduling
2017Co-Authors: Joris Wagenaar, Leo Kroon, Marie SchmidtAbstract:This paper addresses the railway Rolling Stock rescheduling problem, while taking maintenance appointments into account. After a disruption, the Rolling Stock of the disrupted passenger trains has to be rescheduled to restore a feasible Rolling Stock circulation. Usually, a number of train units have a scheduled maintenance appointment during the day: these appointments must be taken into account while rescheduling the Rolling Stock. In this paper we propose three mixed-integer programming models for this purpose. All models are extensions of the composition model from the literature, which does not distinguish individual train units. The extra unit type model adds an additional Rolling Stock type for each train unit that requires maintenance. The shadow-account model keeps track of a shadow account for each train unit that requires maintenance. The job-composition model creates a path for each train unit such that the train units that require maintenance are on time for their maintenance appointments. Al...
-
a comparison of two exact methods for passenger railway Rolling Stock re scheduling
2016Co-Authors: Jorgen Thorlund Haahr, Lucas P Veelenturf, Joris Wagenaar, Leo KroonAbstract:The assignment of Rolling Stock units to timetable services in passenger railways is an important optimization problem that has been addressed by many papers in different forms. Solution approaches have been proposed for different planning phases: strategic, tactical, operational, and real-time planning. In this paper we compare two approaches within the operational and real-time planning phase. The first exact approach is based on a known Mixed Integer Linear Program (MILP) which is solved using CPLEX. The second approach is a new method that is an extension of a recently introduced MILP, which is solved using a column and row generation approach. In this paper, we benchmark the performance of the methods on networks of two countries (Denmark and The Netherlands). We use the approaches to make daily schedules and we test their real time applicability by performing tests with different disruption scenarios. The computational experiments demonstrate that both models can be used on both networks and are able to find optimal Rolling Stock circulations in the different planning phases. Furthermore, the results show that both approaches are sufficiently fast to be used in a real-time setting.
-
maintenance appointments in railway Rolling Stock rescheduling
2016Co-Authors: Joris Wagenaar, Leo Kroon, Marie SchmidtAbstract:This paper addresses the Rolling Stock Rescheduling Problem (RSRP), while taking maintenance appointments into account. After a disruption, the Rolling Stock of the disrupted passenger trains has to be rescheduled in order to restore a feasible Rolling Stock circulation. Usually, a number of train units have a scheduled maintenance appointment during the day: these appointments must be taken into account while rescheduling the Rolling Stock. In this paper we propose three Mixed Integer Programming (MIP) models for this purpose. All models are extensions of the Composition model from literature, which does not distinguish individual train units. The Extra Unit Type model adds an additional Rolling Stock type for each train unit that requires maintenance. The Shadow- Account model keeps track of a shadow account for each train unit that requires maintenance. The Job-Composition model creates a path for each train unit such that the train units that require maintenance are on time for their maintenance appointments. All models are tested on instances of Netherlands Railways (NS). The results show that especially the Shadow-Account model and the Job-Composition model are effectively able to take maintenance appointments into account during real-time rescheduling. It depends on the characteristics of an instance whether the Shadow-Account model or the Job-Composition model performs best.
-
a comparison of two exact methods for passenger railway Rolling Stock re scheduling
2015Co-Authors: Jorgen Thorlund Haahr, Lucas P Veelenturf, Joris Wagenaar, Leo KroonAbstract:The assignment of Rolling Stock units to timetable services in passenger railways is an important optimization problem that has been addressed by many papers in different forms. Solution approaches have been proposed for different planning phases: strategic, tactical, and also operational planning. In this paper we compare two approaches within two operational planning phases (i.e. the daily and the real time planning). The first exact approach is based on a Mixed Integer Linear Program (MILP) which is solved using CPLEX. The second approach is an extension of a recently introduced column generation approach. In this paper, we benchmark the performance of the methods on networks of two countries (Denmark and The Netherlands). We use the approaches to make daily schedules and we test their real time applicability by performing tests with different disruption scenarios. The computational experiments demonstrate that both models can be used on both networks and are able to find optimal Rolling Stock circulations in the different planning phases. Furthermore, the results show that both approaches are sufficiently fast to be used in a real-time setting.
Dennis Huisman - One of the best experts on this subject based on the ideXlab platform.
-
a variable neighborhood search heuristic for Rolling Stock rescheduling
2021Co-Authors: Rowan Hoogervorst, Gábor Maróti, Twan Dollevoet, Dennis HuismanAbstract:We present a Variable Neighborhood Search heuristic for the Rolling Stock rescheduling problem. Rolling Stock rescheduling is needed when a disruption leads to cancellations in the timetable. In Rolling Stock rescheduling, one must then assign duties, i.e., sequences of trips, to the available train units in such a way that both passenger comfort and operational performance are taken into account. For our heuristic, we introduce three neighborhoods, which focus on swapping duties between train units, on improving the individual duties and on changing the shunting that occurs between trips, respectively. These neighborhoods are used for both a Variable Neighborhood Descent local search procedure and for perturbing the current solution in order to escape from local optima. Moreover, we show that the heuristic can be extended to the setting of flexible Rolling Stock turnings at ending stations by introducing a fourth neighborhood. We apply our heuristic to instances of Netherlands Railways (NS). The results show that the heuristic is able to find high-quality solutions within one minute of solving time. This allows Rolling Stock dispatchers to use our heuristic in real-time rescheduling.
-
a variable neighborhood search heuristic for Rolling Stock rescheduling
2019Co-Authors: Rowan Hoogervorst, Gábor Maróti, Twan Dollevoet, Dennis HuismanAbstract:textabstractWe present a Variable Neighborhood Search heuristic for the Rolling Stock rescheduling problem. Rolling Stock rescheduling is needed when a disruption leads to cancellations in the timetable. In Rolling Stock rescheduling, we then assign duties, i.e., sequences of trips, to the available train units in such a way that both passenger comfort and operational performance are taken into account. For our heuristic, we introduce three neighborhoods that can be used for Rolling Stock rescheduling, which respectively focus on swapping duties between train units, on improving the individual duties and on changing the shunting that occurs between trips. These neighborhoods are used for both a Variable Neighborhood Descent local search procedure and for perturbing the current solution in order to escape from local optima. We apply our heuristic to instances of Netherlands Railways (NS). The results show that the heuristic is able to find high-quality solutions in a reasonable amount of time. This allows Rolling Stock dispatchers to use our heuristic in real-time rescheduling.
-
rescheduling in passenger railways the Rolling Stock rebalancing problem
2010Co-Authors: Gabriella Budai, Dennis Huisman, Gábor Maróti, Rommert Dekker, Leo KroonAbstract:textabstractThis paper addresses the Rolling Stock Rebalancing Problem (RSRP) which arises within a passenger railway operator when the Rolling Stock has to be rescheduled due to changing circumstances. RSRP is relevant both in the short-term planning stage and in the real-time operations. RSRP has as input a timetable and a Rolling Stock circulation where the allocation of the Rolling Stock among the stations at the start or at the end of a certain planning period does not match with the allocation before or after that planning period. The problem is then to modify the input Rolling Stock circulation in such a way that the number of remaining off-balances is minimal. If all off-balances have been solved, then the obtained Rolling Stock circulation can be implemented in practice. For practical usage of solution approaches for RSRP, it is important to solve the problem quickly. Since we prove that RSRP is NP-hard, we focus on heuristic solution approaches: we describe two heuristics and compare them with each other on (variants of) real-life instances of NS, the main Dutch passenger railway operator. Finally, to get further insight in the quality of the proposed heuristics, we also compare their outcomes with optimal solutions obtained by solving an existing Rolling Stock circulation model.
-
Rescheduling in passenger railways: The Rolling Stock rebalancing problem
2010Co-Authors: Gabriella Budai, Dennis Huisman, Gábor Maróti, Rommert Dekker, Leo KroonAbstract:This paper addresses the Rolling Stock Rebalancing Problem (RSRP) which arises within a passenger railway operator when the Rolling Stock has to be rescheduled due to changing circumstances. RSRP is relevant both in the short-term planning stage and in the real-time operations. RSRP has as input a timetable and a Rolling Stock circulation where the allocation of the Rolling Stock among the stations at the start or at the end of a certain planning period does not match with the allocation before or after that planning period. The problem is then to modify the input Rolling Stock circulation in such a way that the number of remaining off-balances is minimal. If all off-balances have been solved, then the obtained Rolling Stock circulation can be implemented in practice. For practical usage of solution approaches for RSRP, it is important to solve the problem quickly. Since we prove that RSRP is NP-hard, we focus on heuristic solution approaches: we describe two heuristics and compare them with each other on (variants of) real-life instances of NS, the main Dutch passenger railway operator. Finally, to get further insight in the quality of the proposed heuristics, we also compare their outcomes with optimal solutions obtained by solving an existing Rolling Stock circulation model.
Alexander Schrijver - One of the best experts on this subject based on the ideXlab platform.
-
efficient circulation of railway Rolling Stock
2006Co-Authors: Arianna Alfieri, Leo Kroon, Rutger Groot, Alexander SchrijverAbstract:Railway Rolling Stock is one of the most significant cost components for operators of passenger trains. The efficient circulation of Rolling Stock is therefore one of the main objectives pursued in practice. This paper focuses on the determination of appropriate numbers of train units of different types together with their efficient circulation on a single line. To utilize the train units on this line in an efficient way, they are coupled to or uncoupled from the trains in certain stations according to the passengers' seat demand in peak and off-peak hours. Because coupling and uncoupling train units must respect specific rules related to the shunting possibilities in the stations, it is important to take into account the order of the train units in the trains. This aspect strongly increases the complexity of the Rolling Stock circulation problem. This paper presents a solution approach based on an integer multicommodity flow model with several additional constraints related to the shunting processes at the stations. The approach is applied to a real-life case study based on the timetable of NS Reizigers, the main Dutch operator of passenger trains.
-
a Rolling Stock circulation model for combining and splitting of passenger trains
2004Co-Authors: Pieterjan Fioole, Gábor Maróti, Leo Kroon, Alexander SchrijverAbstract:This paper addresses the railway Rolling Stock circulation problem. Given the departure and arrival times as well as the expected numbers of passengers, we have to assign the Rolling Stock to the timetable services. We consider several objective criteria that are related to operational costs, service quality and reliability of the railway system. Our model is an extension of an existing Rolling Stock model for routing train units along a number of connected train lines. The extended model can also handle underway combining and splitting of trains. We illustrate our model by computational experiments based on instances of NS Reizigers, the main Dutch operator of passenger trains
-
efficient circulation of railway Rolling Stock
2002Co-Authors: Arianna Alfieri, Leo Kroon, Rutger Groot, Alexander SchrijverAbstract:textabstractRailway Rolling Stock (locomotives, carriages, and train units) is one of the most significant cost sources for operatorsof passenger trains, both public and private. Rolling Stock costsare due to material acquisition, power supply, and material maintenance. The efficient circulation of Rolling Stock material is therefore one of the objectives pursued. In this paper we focus on the circulation of train units on a single line. In order to utilize the train units on this line in an efficient way, they are added to or removed from the trains in certain stations, according to the passengers' seat demand. Since adding and removing train units has to respect specific rules, it is important to know the exact order of the train units in the trains. This aspect strongly increases the complexity of the Rolling Stock circulation problem. In this paper we present aninteger programming approach to solve this problem. We also apply this approach to a real life case study based on the 2001-2002 timetable of NS Reizigers, the major Dutch operator of passenger trains.
