Real-time freight locomotive rescheduling and uncovered train detection during disruption

This paper discusses rescheduling of freight train locomotives when dealing with a disrupted situation in the daily operations in Japan. Within the current framework of dispatching processes, passenger railway operators modify the entire timetables and an adjusted freight train timetable is distributed to a freight train operator. For this timetable, we solve the locomotive rescheduling problem by changing the assignment of the locomotives to all the trains and considering their periodic inspections. We then solve the uncovered train detection problem that selects unassigned trains according to their value if the rescheduling phase fails.     

SAPI: Statistical Analysis of Propagation of Incidents. A new approach for rescheduling trains after disruptions

In this paper, we present a new approach to solve the railway rescheduling problem. This problem deals with the reparation of a disturbed railway timetable after incidents in such a way to minimize the difference between the original plan and the new provisional plan. We use a mixed integer linear programming (MIP) formulation that models this problem correctly. However, the large number of variables and constraints denies the possibility to solve this problem efficiently using a standard MIP solver. A new approach called SAPI (Statistical Analysis of Propagation of Incidents) has been developed to tackle the problem. The key point of SAPI is to estimate the probability that an event, one step of the itinerary of a train, is affected by a set of incidents. Using these probabilities, the search space is reduced, obtaining very good solutions in a short time. The method has been tested with two different networks located in France and Chile. The numerical results show that our procedure is viable in practice.     

Adjusting a railway timetable in case of partial or complete blockades

Unexpected events, such as accidents or track damages, can have a significant impact on the railway system so that trains need to be canceled and delayed. In case of a disruption it is important that dispatchers quickly present a good solution in order to minimize the nuisance for the passengers. In this paper, we focus on adjusting the timetable of a passenger railway operator in case of major disruptions. Both a partial and a complete blockade of a railway line are considered. Given a disrupted infrastructure situation and a forecast of the characteristics of the disruption, our goal is to determine a disposition timetable, specifying which trains will still be operated during the disruption and determining the timetable of these trains. Without explicitly taking the rolling stock rescheduling problem into account, we develop our models such that the probability that feasible solutions to this problem exist, is high. The main objective is to maximize the service level offered to the passengers. We present integer programming formulations and test our models using instances from Netherlands Railways.     

Sensitivity analysis of a railway station track layout with respect to a given timetable

An important step in the process of designing a railway station track layout is the verification of the robustness of the layout with respect to the timetables it is based on. For this purpose we develop in this paper an algorithm to randomly perturb a given timetable such that the perturbation is feasible and has the same structure as the given timetable. Mathematically, in this paper we study the problem of, given a set of integer variables and a set of binary relations stating minimal and maximal differences between the variables, to generate solutions uniformly at random. The algorithm involves the simulation of a Markov chain whose state space is a particular subset of the set of feasible timetables and whose limiting and equilibrium distribution is the uniform distribution. Whereas this idea seems simple, some technical pitfalls need to be overcome to make it sound.     

Optimizing the Simplon railway corridor

This paper presents a case study of a railway timetable optimization for the very dense Simplon corridor, a major railway connection in the Alps between Switzerland and Italy. The key to deal with the complexity of this scenario is the use of a novel aggregation-disaggregation method. Starting from a detailed microscopic representation as it is used in railway simulation, the data is transformed by an automatic procedure into a less detailed macroscopic representation, that is sufficient for the purpose of capacity planning and amenable to state-of-the-art integer programming optimization methods. This macroscopic railway network is saturated with trains. Finally, the optimized timetable is re-transformed to the microscopic level in such a way that it can be operated without any conflicts among the train paths. Using this micro-macro aggregation-disaggregation approach in combination with integer programming methods, it becomes for the first time possible to generate a profit maximal and conflict free timetable for the complete Simplon corridor over an entire day by a simultaneous optimization of all trains requests. In addition, this also allows us to undertake a sensitivity analysis of various problem parameters.     

Adaptive selection of heuristics for improving exam timetables

This paper presents a hyper-heuristic approach which hybridises low-level heuristic moves to improve timetables. Exams which cause a soft-constraint violation in the timetable are ordered and rescheduled to produce a better timetable. It is observed that both the order in which exams are rescheduled and the heuristic moves used to reschedule the exams and improve the timetable affect the quality of the solution produced. After testing different combinations in a hybrid hyper-heuristic approach, the Kempe chain move heuristic and time-slot swapping heuristic proved to be the best heuristic moves to use in a hybridisation. Similarly, it was shown that ordering the exams using Saturation Degree and breaking any ties using Largest Weighted Degree produce the best results. Based on these observations, a methodology is developed to adaptively hybridise the Kempe chain move and timeslot swapping heuristics in two stages. In the first stage, random heuristic sequences are generated and automatically analysed. The heuristics repeated in the best sequences are fixed while the rest are kept empty. In the second stage, sequences are generated by randomly assigning heuristics to the empty positions in an attempt to find the best heuristic sequence. Finally, the generated sequences are applied to the problem. The approach is tested on the Toronto benchmark and the exam timetabling track of the second International Timetabling Competition, to evaluate its generality. The hyper-heuristic with low-level improvement heuristics approach was found to generalise well over the two different datasets and performed comparably to the state of the art approaches.     

Improving the robustness in railway station areas

In order to improve the robustness of a railway system in station areas, this paper introduces an iterative approach to successively optimize the train routing through station areas and to enhance this solution by applying some changes to the timetable in a tabu search environment. We present our vision on robustness and describe how this vision can be used in practice. By introducing the spread of the trains in the objective function for the route choice and timetabling module, we improve the robustness of a railway system. Using a discrete event simulation model, the performance of our algorithms is evaluated based on a case study for the Brussels’ area. The computational results indicate an average improvement in robustness of 6.2% together with a decrease in delay propagation of about 25%. Furthermore, the effect of some measures like changing the train offer to further increase the robustness is evaluated and compared.     

A robust descent type algorithm for geophysical inversion through adaptive regularization

A robust descent type algorithm through adaptive regularization is designed to solve a geophysical inverse problem. The scheme uses a regularized descent direction which is obtained through minimization of smoothed functional in every iterative step. The step length factor is chosen using Armijo's rule. Numerical experiment conducted to invert synthetic and field geophysical data demonstrates a high order of robustness in retrieving the model parameters.     

Reliability and heterogeneity of railway services

Reliability is one of the key factors in transportation, both for passengers and for cargo. This paper examines reliability in public railway systems. Reliability of railway services is a complex matter, since there are many causes for disruptions and at least as many causes for delays to spread around in space and time.One way to increase the reliability is to reduce the propagation of delays due to the interdependencies between trains. In this paper we attempt to decrease these interdependencies by reducing the running time differences per track section and by thus creating more homogeneous timetables. We also introduce two heuristic measures, that can be used to evaluate the homogeneity of a timetable.Because of the complexity of railway systems, we use network wide simulation for the analysis of the alternative timetables. We report on both theoretical and practical cases. Besides a comparison of different timetables, also general timetabling principles are deduced.     

Developing railway timetables which guarantee a better service

In order to improve passenger service, a waiting cost function, weighting different types of waiting times and late arrivals, is designed and minimised. The approach is applied to a small part of the Belgian railway network. In the first phase of the approach, ideal buffer times are calculated to safeguard connections when the arriving train is late. These buffer times are based on the delay distributions of the arriving trains and on the weighting of different types of waiting times. In a second phase, standard linear programming is used to construct an improved timetable with well-scheduled connections and, whenever possible, with ideal buffer times. Simulation compares different timetables and optimises the LP timetable. For the case of the Belgian railway network, the final result is a timetable with well-scheduled connections and a waiting cost that is 40% lower than the current timetable. Since only LP modelling is applied, the proposed technique is very promising for developing better timetables—even for very extensive railway networks.     

关键链断裂情况下的缓冲设置方法比较研究

应用关键链项目管理方法时,由于项目的复杂性,在确定关键链和非关键链后,进一步插入汇入缓冲时,常常会出现资源再次冲突,需要对计划进行重排,重排后又出现关键链断裂、汇入缓冲起不到保护作用等问题。针对这些问题,本文采用分散缓冲法制定项目调度计划,并用项目实例证明了方法的可行性和通用性,且设计仿真实验将分散缓冲计划与重排后的关键链调度计划进行比较,结果发现当项目活动时间的变化性较小时,应用分散缓冲法还可以获得较好的项目绩效。     

A probabilistic (max, +) approach for determining railway infrastructure capacity

We consider the problem of determining the capacity of a planned railway infrastructure layout under uncertainties. In order to address the long-term nature of the problem, in which the exact (future) demand of service is unknown, we develop a “timetable”-free approach to avoid the specification of a particular timetable. We consider a generic infra-element that allows a concise representation of many different combinations of infrastructure, safety systems and traffic regimes, such as mixed double and single track lines (e.g., a double track line including a single tunnel tube), and train operations on partly overlapping routes at station yards. We translate the capacity assessment problem for such a generic infra-element into an optimization problem and provide a solution procedure. We illustrate our approach with a capacity assessment for the newly built high-speed railway line in The Netherlands.     

双目标突发事件应急救援前摄性调度优化

本文以救援时间最短化与计划鲁棒性最大化为目标,研究突发事件应急救援前摄性调度优化问题。作者首先对所研究问题进行界定,其中计划鲁棒性定义为各活动开始时间可调整时差的总和,任务是在应急预算和救援期限的约束下,确定活动执行模式与开始时间以实现上述两个目标。随后,构建问题的0-1规划优化模型,鉴于其强NP-hard属性,设计禁忌搜索启发式算法。最后用一个算例对研究进行说明,得到如下结论:救援时间随应急预算的增加而缩短,随救援期限的放宽而延长;计划鲁棒性随应急预算的增加或救援期限的放宽而提高;当权重分配系数增大时,应急救援时间先保持不变而后缩短,计划鲁棒性则呈减小趋势。本文研究可为突发事件应急救援的组织与协调提供决策支持。     

单架飞机受干扰后飞机路径恢复多项式算法研究

飞机路径恢复是航班调整中保证航班能够运行的必要条件之一,而传统目标下的飞机路径优化问题是NP-hard的。本文针对单架飞机受到干扰后,基于最小最大目标的同机型飞机路径最优化问题,给出了一个新的多项式时间算法。首先基于航空公司调整航班的常用原则,提出把最大航班延误时间最小化作为问题的目标。然后根据问题的一些特点和目标形式,设计出解构造算法,得到飞机路径恢复问题的最优解,并分析出算法的复杂度为O(n²)。相对于一般的最小最大二分图匹配算法(复杂度为O(n³log(n))),该算法具有较小的时间复杂度。最后用实例验证了解构造算法的有效性。该研究结果将为航空公司减少航班延误提供理论和方法支持。     

可达到和可逼近总极小点的存在性和最优性

针对积分总极值，讨论并拓展了丰满集和丰满函数的概念，研究了拟上丰满和伪上丰满函数的总极值问题. 在总极值的变差积分最优性条件下，证明了拟上丰满函数的可达到极小点和伪上丰满函数的可逼近极小点的存在性.     

Robust algorithms for multiphase regression models

This paper proposes a robust procedure for solving multiphase regression problems that is efficient enough to deal with data contaminated by atypical observations due to measurement errors or those drawn from heavy-tailed distributions. Incorporating the expectation and maximization algorithm with the M-estimation technique, we simultaneously derive robust estimates of the change-points and regression parameters, yet as the proposed method is still not resistant to high leverage outliers we further suggest a modified version by first moderately trimming those outliers and then implementing the new procedure for the trimmed data. This study sets up two robust algorithms using the Huber loss function and Tukey's biweight function to respectively replace the least squares criterion in the normality-based expectation and maximization algorithm, illustrating the effectiveness and superiority of the proposed algorithms through extensive simulations and sensitivity analyses. Experimental results show the ability of the proposed method to withstand outliers and heavy-tailed distributions. Moreover, as resistance to high leverage outliers is particularly important due to their devastating effect on fitting a regression model to data, various real-world applications show the practicability of this approach.     

Synchronization of two different uncertain chaotic systems with unknown parameters using a robust adaptive sliding mode controller

In this paper, a robust adaptive sliding mode controller (RASMC) is proposed to realize chaos synchronization between two different chaotic systems with uncertainties, external disturbances and fully unknown parameters. It is assumed that both master and slave chaotic systems are perturbed by uncertainties, external disturbances and unknown parameters. The bounds of the uncertainties and external disturbances are assumed to be unknown in advance. Suitable update laws are designed to tackle the uncertainties, external disturbances and unknown parameters. For constructing the RASMC a simple sliding surface is first designed. Then, the RASMC is derived to guarantee the occurrence of the sliding motion. The robustness and stability of the proposed RASMC is proved using Lyapunov stability theory. Finally, the introduced RASMC is applied to achieve chaos synchronization between three different pairs of the chaotic systems (Lorenz–Chen, Chen–Lorenz, and Liu–Lorenz) in the presence of the uncertainties, external disturbances and unknown parameters. Some numerical simulations are given to demonstrate the robustness and efficiency of the proposed RASMC.     

Robust Optimal Trajectory Planning for Robots by Stochastic Optimization

In the optimal control of industrial, field or service robots, the standard procedure is to determine first offline a reference trajectory and a feedforward control, based on some selected nominal values of the unknown stochastic model parameters, and to correct then the inevitable and increasing deviation of the state or performance of the robot from the prescribed state or performance of the system by online measurement and control actions. Due to the stochastic variations of the model parameters, increasing measurement and correction actions are needed during the process. By optimal stochastic trajectory planning (OSTP), based on stochastic optimization methods, the available a priori and sample information about the robot and its working environment is incorporated into the control process. Consequently, more robust reference trajectories and feedforward controls are obtained which cause much less online control actions. In order to maintain a high quality of the guiding functions, the reference trajectory and the feedforward control can be updated at some later time points such that additional information about the control process is available. After the presentation of the Adaptive Optimal Stochastic Trajectory Planning (AOSTP) procedure based on stochastic optimization methods, several numerical techniques for the computation of robust reference trajectories and feedforward controls under real-time conditions are presented. Additionally, numerical examples for a Manutec r3 industrial robot are discussed. The first one demonstrates real-time solutions of (OSTP) based on a sensitivity analysis of a before-hand calculated reference trajectory. The second shows the differences between reference trajectories based on deterministic methods and the stochastic methods introduced in this paper. Based on simulations of the robots behavior, the increased robustness of stochastic reference trajectories is demonstrated.     

An improved multi-staged algorithmic process for the solution of the examination timetabling problem

The efficient creation of examination timetables is a recurring and important problem for universities worldwide. Good timetables typically are characterized by balanced distances between consecutive exams for all students. In this contribution an approach for the examination timetabling problem as defined in the second International Timetabling Competition () is presented. The solution approach is managed on the top level by GRASP (Greedy Randomized Adaptive Search Procedure) and it involves several optimization algorithms, heuristics and metaheuristics. A construction phase is executed first producing a relatively high quality feasible solution and an improvement phase follows that further ameliorates the produced timetable. Each phase consists of stages that are consumed in a circular fashion. The procedure produces feasible solutions for each dataset provided under the runtime limit imposed by the rules of the ITC07 competition. Results are presented and analyzed.     

一种求解柔性资源约束前摄性项目调度问题的启发式算法

在不确定环境中,一个具有较高鲁棒性的进度计划可以保证项目的稳定实施。考虑到现实中资源可能具有多种技能,会对制定鲁棒性较高进度计划的过程产生影响,因此本文研究了柔性资源约束下前摄性项目调度优化问题。首先界定研究问题;然后从鲁棒性最大化的视角出发,构建了研究问题的优化模型,在对模型进行分析的基础上将其分解为经典鲁棒优化和资源技能分配两个子模型;随后设计了求解问题的基于削峰算法的启发式算法;最后用一个实际案例验证了算法有效性,并分析了关键参数对进度计划鲁棒性的影响,得到如下结论:项目进度计划鲁棒性随着项目工期的延长、资源可用量的增加或资源柔性的提高而增大。