Search

In large-cities, urban rail networks usually involve more than two connected lines and passengers mostly transfer several times to reach their destinations. Thus, the coordination of train timetables in different lines has become a key issue in recent years for improving the transfer convenience of passengers. In this paper, we first propose a synchronization quality index (SQI) to qualitatively evaluate the transfer convenience of passengers, and we develop a bi-objective optimization approach for the coordination of train timetables, where the objectives are to optimize both SQI and average waiting time of passengers. We also construct a mixed integer nonlinear programming formulation by considering the time-dependent properties of passenger demand and their transfers among multiple transit lines. Further, we adopt a local search, a simulated annealing algorithm and a genetic algorithm to solve the proposed model. A real-world instance based on the passenger demand data in Beijing Metro Network is conducted to verify the effectiveness of our approach. By comparing with the current (uncoordinated) timetable in Beijing Metro, our solution can improve the value of SQI by 31.28% and reduce the passenger waiting time by 3.49 %.

In this paper, we study the optimization of coordinated train timetable in an urban rail network under the consideration of time-dependent passenger demands. This problem arises in large urban rail networks with multiple lines that the passengers may transfer among different lines to arrive at their destinations. We propose an exact formulation to generate the optimal train timetables of all the involved lines in a rail transit network synchronously, and our objective is to minimize the maximal level of crowdedness of stations. In particular, we introduce several sets of passenger flow variables that enable to model this complex problem as a mixed-integer linear programming (MILP) that is possible to be solved to the optimal solution. By considering the number of boarding and alighting passengers as passenger flow variables, we explicitly incorporates the number of in-vehicle passengers in the modelling framework to capture the train carrying capacity constraints. The formulated models first extend the passenger-oriented train timetabling models in existing literature from a single transit line to a whole connected network. Case studies are conducted to verify the effectiveness of the proposed model.

This work tackles the problem of controlling operations at an automated container terminal. In the context of large supply chains, there is a growing trend for increasing productivity and economic efficiency. New models and algorithms are provided for scheduling and routing equipment that is moving containers in a quay area, loading/unloading ships, transporting them via Automated Guided Vehicles (AGVs) to Automated Stacking Cranes (ASCs), organizing them in stacks. In contrast with the majority of the approaches in the related literature, this work tackles two dynamics of the system, a discrete dynamic, characteristic of the maximization of operations efficiency, by assigning the best AGV and operation time to a set of containers, and a continuous dynamic of the AGV that moves in a geographically limited area. As an assumption, AGVs can follow free range trajectories that minimize the error of the target time and increase the responsiveness of the system. A novel solution framework is proposed and some computational result are reported to show the feasibility of the proposed approach.

This work addresses a tactical railway traffic scheduling problem focused on the optimization of train sequencing and routing decisions and timing decisions related to short-term maintenance works in a railway network subject to disturbed process times. This is modeled as a mixed-integer linear programming formulation in which the traffic flow and track maintenance variables, constraints and objectives are integrated under a stochastic environment. The resulting bi-objective optimization problem is to minimize the deviation from a scheduled plan and to maximize the number of aggregated maintenance works under stochastic disturbances. The two objectives require to schedule competitive train operations versus maintenance works on the same infrastructure elements. Computational experiments are performed on a realistic railway network. We measure the quality of the integrated solutions in terms of their robustness to stochastic perturbations of the train travel times and of the maintenance works. Pareto optimal methods are compared for the bi-objective problem. We also evaluate the impact of introducing routing stability constraints in order to force the trains to keep the same route among the different stochastic disturbed scenarios. The experiments show that forcing the routing stability reduces the routing flexibility and the ability to optimize the two performance indicators when dealing with stochastic disturbances.

In metro systems, a tactical train schedule with the rolling stock circulation plan aims to determine the movements of all physical trains. To utilize the regenerative energy as much as possible, this paper proposes an integrated model to simultaneously generate the optimal train schedule and rolling stock circulation plan, in which the brake-traction overlapping time at stations is maximized. In particular, our model rigorously considers the train turn-around constraints, train circulation constraints, and dynamic passenger demands to tackle the train loading capacity constraints. To eliminate the effect of non-linear constraints, we reformulate the original model into its equivalent linear model that can be efficiently solved by linear programming solvers. Finally, the numerical experiments based on Beijing Yizhuang Metro Line are implemented to demonstrate the effectiveness of our proposed model.

ITSC 2018, 21st International Conference on Intelligent Transportation Systems, Maui - Hawaï, ETATS-UNIS, 04-/11/2018 - 07/11/2018; The real-time railway traffic management problem (rtRTMP) aims to solve time-overlapping conflicting track requests due to traffic disturbances. The size of the problem and the time required to solve it are affected by the number of routing alternatives available to each train. The real-time train routing selection problem (rtTRSP) chooses a feasible routing subset for each train to use as input for the rtRTMP. Recently, a computational analysis has been performed via Ant Colony Optimization and the RECIFE-MILP solver. This paper generalizes such analysis by considering a different rtRTMP model, objective function and solution approach. We adopt the AGLIBRARY solver, which is based an alternative graph model of the problem and minimizes the maximum consecutive delay. The aim is to develop real-time disturbance response strategies and to quantify the advantages of the selection of a subset of routings when using different solvers. We analyze how changes in the rtRTMP model are reflected in the rtTRSP and which modifications are required. The computational analysis is performed on two French infrastructures: the line around the city of Rouen and the Lille terminal station area. The analysis shows that solving the rtTRSP helps both solvers significantly, even if they are based on different models, objectives and algorithms.

This paper focuses on the development of metaheuristic algorithms for the real-time traffic management problem of scheduling and routing trains in complex and busy railway networks. This key optimization problem can be formulated as a mixed integer linear program. However, since the problem is strongly NP-hard, heuristic algorithms are typically adopted in practice to compute good quality solutions in a short computation time. This paper presents a number of algorithmic improvements implemented in the AGLIBRARY optimization solver in order to improve the possibility of finding good quality solutions quickly. The optimization solver manages trains at the microscopic level of block sections and at a precision of seconds. The solver outcome is a detailed conflict-free train schedule, being able to avoid deadlock situations and to minimize train delays. The proposed algorithmic framework starts from a good initial solution for the train scheduling problem with fixed routes, obtained via a truncated branch-and-bound algorithm. Variable neighbourhood search or tabu search algorithms are then applied to improve the solution by re-routing some trains. The neighbourhood of a solution is characterized by the set of candidate trains to be re-routed and the available routes. Computational experiments are performed on railway networks from different countries and various sources of disturbance. The new algorithms often outperform a state-of-the-art tabu search algorithm and a commercial solver in terms of reduced computation times and/or train delays. © 2016 Elsevier Ltd. This paper focuses on the development of metaheuristic algorithms for the real-time traffic management problem of scheduling and routing trains in complex and busy railway networks. This key optimization problem can be formulated as a mixed integer linear program. However, since the problem is strongly NP-hard, heuristic algorithms are typically adopted in practice to compute good quality solutions in a short computation time. This paper presents a number of algorithmic improvements implemented in the AGLIBRARY optimization solver in order to improve the possibility of finding good quality solutions quickly. The optimization solver manages trains at the microscopic level of block sections and at a precision of seconds. The solver outcome is a detailed conflict-free train schedule, being able to avoid deadlock situations and to minimize train delays. The proposed algorithmic framework starts from a good initial solution for the train scheduling problem with fixed routes, obtained via a truncated branch-and-bound algorithm. Variable neighbourhood search or tabu search algorithms are then applied to improve the solution by re-routing some trains. The neighbourhood of a solution is characterized by the set of candidate trains to be re-routed and the available routes. Computational experiments are performed on railway networks from different countries and various sources of disturbance. The new algorithms often outperform a state-of-the-art tabu search algorithm and a commercial solver in terms of reduced computation times and/or train delays.

This paper deals with the development of decision support systems for traffic management of large and busy railway networks in case of severe disturbances. Railway operators typically structure the control of complicated networks into the coordinated control of several local dispatching areas. A dispatcher takes rescheduling decisions on the trains running on its local area while a coordinator addresses global issues that may arise between areas. While several advanced train dispatching models and algorithms have been proposed to support the dispatchers' task, the coordination problem did not receive much attention in the literature on train scheduling. This paper presents new heuristic algorithms for both local dispatching and coordination and compares centralized and distributed procedures to support the task of dispatchers and coordinators. We adopt dispatching procedures driven by optimization algorithms and based on local or global information and decisions. Computational experiments on a Dutch railway network, actually controlled by ten dispatchers, assess the performance of the centralized and distributed procedures. Various traffic disturbances, including entrance delays and blocked tracks, are analyzed on various time horizons of traffic prediction. Results show that the new heuristics clearly improve the global performance of the network with respect to the state of the art.

This paper reports on the practical applicability of published techniques for real-time train scheduling. The final goal is the development of an advanced decision support system for supporting dispatchers’ work and for guiding them toward near-optimal real-time re-timing, re-ordering and re-routing decisions. The paper focuses on the optimization system AGLIBRARY that manages trains at the microscopic level of block sections and block signals and at a precision of seconds. The system outcome is a detailed conflict-free train schedule, being able to avoid deadlocks and to minimize train delays. Experiments on a British railway nearby London demonstrate that AGLIBRARY can quickly compute near-optimal solutions.

Delay management determines which connections should be maintained in case of a delayed feeder train. Recent delay management models incorporate the limited capacity of the railway infrastructure. These models introduce headway constraints to make sure that safety regulations are satisfied. Unfortunately, these headway constraints cannot capture the full details of the railway infrastructure, especially within the stations. We therefore propose an iterative optimization approach that iteratively solves a macroscopic delay management model on the one hand, and a microscopic train scheduling model on the other hand. The macroscopic model determines which connections to maintain and proposes a disposition timetable. This disposition timetable is then validated microscopically for a bottleneck station of the network, proposing a feasible schedule of railway operations. This schedule reduces delay propagation and thereby minimizes passenger delays. We evaluate our iterative optimization framework using real-world instances around Utrecht in the Netherlands.

This work addresses the real-time optimization of take-off and landing operations at a busy terminal control area in case of traffic congestion. Terminal areas are becoming the bottleneck of the entire air traffic control system, in particular in the major European airports, where there is a limited possibility to build new infrastructure. The real-time problem of effectively managing aircraft operations is particularly challenging, since it is necessary to incorporate the safety regulations into the optimization model and to consider numerous performance indicators that are important to compute good quality solutions. However, in practice there is no well-recognized objective function and traffic controllers often use simple scheduling rules. In this paper, mixed integer linear programming formulations are proposed to investigate the trade-off between various performance indicators of practical interest, while taking into account the safety constraints with a high modeling precision. Experiments are performed for the two major Italian airports, Milano Malpensa and Roma Fiumicino, by simulating various sets of random landing and take-off aircraft disturbances. Practical-size instances are solved to (near)optimality via a commercial solver. The optimized solutions are also compared with a commonly used scheduling rule. A comprehensive computational analysis makes possible the selection of those solutions that are able to find a good compromise among the various indicators and, consequently, the investigation of the most representative formulation. © 2016 Elsevier Ltd.

This paper deals with the re-engineering and design optimization of a warehouse for package storage operations occurring daily at a leading courier express company in Italy. The objective of our study is to quantify the return on investment and error reduction that can be achieved by the application of advanced tracking technologies in the package management process. This study considers the use of RFID tags to facilitate identifying items in a package delivery service facility. In a first phase, we analyze the current process and show the speed-up of the operators with barcode readers compared to the operations handbook. In a second phase, we introduce radio frequency identification (RFID) technologies in the warehouse and perform practical experiments in order to detect configurations with error-free item scanning. An optimal configuration of the warehouse and of the RFID-based package management process is obtained by a non-linear optimization model that minimizes the overall technology and management costs. The probability of item errors is modeled by a maximum likelihood estimation procedure that determines the scanning area of each antenna with minimal scanning error. The new process with RFID technology reduces the costs of daily operations in the studied warehouse up to 25% and the workload of the operators up to 4 h. © 2011 Springer Science+Business Media, LLC.

This is a summary of the author's PhD thesis supervised by Ingo A. Hansen and defended on 7 April 2008 at the Delft University of Technology. The thesis is written in English and is available from http://www. darenet. nl. This work deals with the development of an innovative decision support system for railway traffic control in order to cope with real-time timetable disturbances (i. e., multiple train delays and blocked tracks) more effectively. This dynamic traffic control system co-ordinates the speed of successive trains on open track (re-timing), solves expected route conflicts (re-ordering) and provides dynamic use of platform tracks in a station or alternative paths in a corridor between stations (local re-routing). We adopt blocking time theory for a microscopic modeling track occupation and signaling constraints and alternative graphs for optimal solving dynamic traffic control problems with the aim of increasing the punctuality by a more intelligent use of infrastructure capacity at a network scale. © 2010 Springer-Verlag.

Lecture Notes in Computer Science, 9335, ISSN:0302-9743, ISSN:1611-3349, Computational Logistics: 6th International Conference, ICCL 2015, Delft, The Netherlands, September 23-25, 2015: Proceedings, ISBN:978-3-319-24263-7, ISBN:978-3-319-24264-4

The aircraft scheduling problem ASP is the real-time problem of scheduling takeoff and landing operations at a congested airport in a given time horizon, taking into account the runways and the air segments in the terminal maneuvering area . The ASP can be viewed as a job shop scheduling problem with additional real-world constraints. Compared with the current literature based on job shop scheduling applied to solve the ASP, we enrich the existing models by including new formulations of relevant practical constraints. We introduce and analyze three alternative ASP formulations, in which the objective function is the minimization of delay propagation with respect to the off-line timetable. Scheduling rules, heuristic and exact methods are implemented and tested on instances from the Roma Fiumicino airport, in Italy. Computational experiments show that practical-size instances are solved to near-optimality by our branch and bound algorithm in a few seconds of computation. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 653, 212-227 2015

This work focuses on the stochastic evaluation of train schedules computed by a microscopic scheduler of railway operations based on deterministic information. The research question is to assess the degree of sensitivity of various rescheduling algorithms to variations in process times (running and dwell times). In fact, the objective of railway traffic management is to reduce delay propagation and to increase disturbance robustness of train schedules at a network scale. We present a quantitative study of traffic disturbances and their effects on the schedules computed by simple and advanced rescheduling algorithms. Computational results are based on a complex and densely occupied Dutch railway area; train delays are computed based on accepted statistical distributions, and dwell and running times of trains are subject to additional stochastic variations. From the results obtained on a real case study, an advanced branch and bound algorithm, on average, outperforms a First In First Out scheduling rule both in deterministic and stochastic traffic scenarios. However, the characteristic of the stochastic processes and the way a stochastic instance is handled turn out to have a serious impact on the scheduler performance. © 2013 Springer Science+Business Media New York.

This paper studies quantitative methods for evaluating the potential benefits of introducing new advanced tracking technologies in the pharmaceutical industry with special reference to radio frequency identification (RFID). RFID technology is an effective way for increasing the quality of the data that are used to generate production schedules, but there is a lack of scientific research to quantify the return on investment that can be achieved in practice. In this work, we distinguish two major sources of data unreliability: one is the inherent stochasticity of operations, which cannot be reduced by RFID, and the other one is the data estimation error, which can be significantly reduced by RFID. We focus on the marginal contribution of the latter quantity to the productivity of the packaging department of a pharmaceutical plant, propose a systematic method for assessing this impact and discuss its implementation in a practical test case. Our results confirm that advanced tracking technologies in combination with effective scheduling procedures show a significant potential for improving productivity. Extensions to other production environments and their issues associated with scheduling problems are also discussed.

Railway dispatchers reschedule trains in real-time in order to limit the propagation of disturbances and to regulate traffic in their respective dispatching areas by minimizing the deviation from the off-line timetable. However, the decisions taken in one area may influence the quality and even the feasibility of train schedules in the other areas. Regional control centers coordinate the dispatchers' work for multiple areas in order to regulate traffic at the global level and to avoid situations of global infeasibility. Differently from the dispatcher problem, the coordination activity of regional control centers is still underinvestigated, even if this activity is a key factor for effective traffic management. This paper studies the problem of coordinating several dispatchers with the objective of driving their behavior towards globally optimal solutions. With our model, a coordinator may impose constraints at the border of each dispatching area. Each dispatcher must then schedule trains in its area by producing a locally feasible solution compliant with the border constraints imposed by the coordinator. The problem faced by the coordinator is therefore a bilevel programming problem in which the variables controlled by the coordinator are the border constraints. We demonstrate that the coordinator problem can be solved to optimality with a branch and bound procedure. The coordination algorithm has been tested on a large real railway network in the Netherlands with busy traffic conditions. Our experimental results show that a proven optimal solution is frequently found for various network divisions within computation times compatible with real-time operations.

This chapter is the first thorough assessment of a full implementation of the concept of dynamic traffic management in combination with advanced optimization tools. In the last years, several studies on partial implementations of this concept have been carried out reporting promising results. The development of new strategies for railway traffic control experienced an increasing interest due to the expected growth of traffic demand and to the limited possibilities of enhancing the infrastructure, which increase the needs for efficient use of resources and the pressure on traffic controllers. Improving the efficiency requires advanced decision support tools that accurately monitor the current train positions and dynamics, and other operating conditions, predict the potential conflicts and reschedule trains in real-time such that consecutive delays are minimized. We carry on our study using an innovative computerized railway traffic management system, called ROMA (Railway traffic Optimization by Means of Alternative graphs). An extensive computational study is carried out, based on two complex and busy dispatching areas of the Dutch rail network. We study practical size instances and different types of disturbances, including train delays and blocked tracks. Our results show the high potential of ROMA as a support tool to improve punctuality through intelligent use of the rail infrastructure and efficient use of the available transport capacity.

Railway rescheduling is the task of restoring feasibility in case of disturbances and limiting the propagation of delays through a railway network. This task becomes more difficult when dealing with complex interlocking areas, since operational rules constrain the passage of trains through short track sections. This paper presents a detailed microscopic representation of the railway network that is able to tackle the complexity of a station area with multiple conflicting routes and high service frequency. Two alternative graph formulations are presented to model the incompatibility between routes: one based on track sections and another based on the aggregation of track sections into station routes. An extensive computational study gives useful information on the performance of the two formulations for different disturbance scenarios.

In order to face the expected growth of transport demand in the next years, several new traffic control policies have been proposed and analyzed both to generate timetables and to effectively manage the traffic in real-time. In this paper, a detailed optimization model is used to analyze one such policy, called green wave, which consists in letting trains wait at the stations to avoid speed profile modifications in open corridors. Such policy is expected to be especially effective when the corridors are the bottleneck of the network. However, there is a lack of quantitative studies on the real-time effects of using this policy. To this end, this work shows a comparison of the delays obtained when trains are allowed or not to change their speed profile in open corridors. An extensive computational study is described for two practical dispatching areas of the Dutch railway network.

The paper studies a train scheduling problem faced by railway infrastructure managers during real-time traffic control. When train operations are perturbed, a new conflict-free timetable of feasible arrival and departure times needs to be re-computed, such that the deviation from the original one is minimized. The problem can be viewed as a huge job shop scheduling problem with no-store constraints. We make use of a careful estimation of time separation among trains, and model the scheduling problem with an alternative graph formulation. We develop a branch and bound algorithm which includes implication rules enabling to speed up the computation. An experimental study, based on a bottleneck area of the Dutch rail network, shows that a truncated version of the algorithm provides proven optimal or near optimal solutions within short time limits.