An agent-based support system for railway station dispatching

For those railway stations without being automated, railway traffic dispatching still depends on dispatchers, especially under disturbed circumstances. In this study, an agent-based support system, named D-Agent, is developed to assist human dispatchers to make decisions in station operation. To this end, the common knowledge and possible difficulties concerning a station dispatcher in his/her routine work are firstly studied, and the D-Agent is proposed with the purpose of working out practicable solutions to these challenging tasks as a dispatcher does. Then the general model of the D-Agent is established, containing five basic modules: local database, knowledge base, skill base, reasoning mechanism and communication interfaces. The internal skills of the D-Agent are designed to execute various tasks in different scenarios. Besides, a skill extension of the D-Agent with mathematical formulations is particularly discussed in this paper, to find feasible and optimal traffic control solutions in disturbance situations such as train delays and route conflicts. The D-Agent is designed to learn from its own experimental history in applying different skills, and evaluate the skills by preference weights of alternative solutions in a particular task. This procedure allows the agent to have potential for continuous improvement. To verify the applicability of the proposed support system, a D-Agent for a terminal station of subway is simulated. The numerical example of train delays and route conflicts shows that the D-Agent can generally perform as a station dispatcher in fulfilling the specific tasks, estimate the traffic state in different operation strategies and support the decision-making of favored solutions. Significantly, it indicates that the mathematical methods can also been employed by an intelligent agent.     

A Train Dispatching Model Under a Stochastic Environment: Stable Train Routing Constraints and Reformulation

After major capacity breakdown(s) on a railway network, train dispatchers need to generate appropriate dispatching plans to recover the impacted train schedule from perturbations and minimize the expected total train delay time under stochastic scenarios. In this paper, we propose a cumulative flow variables-based integer programming model for dispatching trains under a stochastic environment on a general railway network. Stable Train Routing (STR) constraints are introduced to ensure that trains traverse on the same route across different capacity breakdown scenarios, which are further reformulated to equivalent linear inequality constraints. Track occupancy and safety headways are modelled as side constraints which are dualized through a proposed Lagrangian relaxation solution framework. The original complex train dispatching problem is then decomposed to a set of single-train and single-scenario optimization subproblems. For each subproblem, a standard label correcting algorithm is embedded for finding the time dependent least cost path on a space-time network. The resulting dual solutions can be transformed to feasible solutions through priority rules. Numerical experiments are conducted to demonstrate the efficiency and effectiveness of the proposed solution approach.     

Automated platforming & routing of trains in all Belgian railway stations

Automatically generating train to platform assignments has been an active research area for some time, but systems implementing this research are still not readily available to practitioners. However, now, our train platforming model has been implemented as the tool Leopard inside Infrabel, the Belgian railway infrastructure manager. In practice, initial macroscopic timetables are often not yet feasible inside stations on the microscopic level. This means that a platforming tool must be able to handle cases where not all trains can be platformed or routed. Our model provides a platforming and routing plan for as many trains as possible and puts the remaining trains on a fictive platform. Contrary to the manually made platforming plans, the optimised platforming plans have no platform conflicts nor routing conflicts. Our model assigns as much trains as possible, given the timetable and the available infrastructure. Our tool can solve the platforming problems for all 530 stations in Belgium together in about 10 min. This means (i) it saves many man months of planning time compared to the still common manual practice to platforming and (ii) it achieves higher quality results leading to significantly less in-station train delays in practice.     

Rapid,robust, distributed evaluation and control of train scheduling on a single line track

The technology for controlling the distance between two trains is shifting from traditional fixed red, yellow and green signals on the infrastructure track circuits towards more and more dynamic systems, which are based on moving blocks, where the distance is computed according to real-time positioning, and the control of the distance is computed on-line. This is the case, for example, in the European Rail Traffic Management System (ERTMS), which proposes three different levels, from 1 to 3. This paper addresses the time-honoured problem of scheduling trains on a single track, in the light of recent results in robust team decision theory. The control model can be used in two modes: as a decision support tool for train dispatchers to evaluate the distance between trains in the current schedule, and as a planning tool to evaluate the effects of timetable changes. The main contribution of the paper is the application of a recent result in robust team decision theory to control noncritical train distances in moving blocks, such as in ERTMS Level 3. The case study is related to real data from an ERTMS simulation and controller software tool.     

Analyses of cognitive processes in train traffic control

The study of complex information processing and problem-solving situations in practice is discussed, in particular the methods of analysing the cognitive aspects in train dispatcher's work. Some parallels are drawn with related work in processing industries. A prerequisite for the approach to the issue was that the results would have to yield very concrete starting-points for the design of technical aids. The research started from the assumption that it would be extremely difficult to derive design indications from apparently observable actions of the train dispatchers. This led to the choice of a combination of a preliminary simulation study followed by analysis of cognitive processes in the train dispatcher's behaviour in every day practice. It turned out to be helpful for the analysis to draw parallels between the cognitive processes in the behaviour of the train dispatchers and the way of working/thinking shown by test subjects in complex problem-solving experiments.     

A Fuzzy Petri Nets approach for railway traffic control in case of abnormality: Evidence from Taiwan railway system

Railway traffic control by dispatchers in case of abnormality is critical to assure the service quality of a railway system’s operation. However, this unique professional knowledge often lies in the dispatcher’s mind. Therefore, this study aims to transform a train dispatcher’s expertise into a useful knowledge rule. The fuzzy Petri Net approach is adopted to formulate the decision rules of train dispatchers in case of abnormality as the basis for future development of a dispatching decision support system. The dispatching decision rules, factors, and possible options when perturbation happens are collected via expert interviews and literature reviews. This study discusses the abnormal scenarios, including centralized traffic control system failure, automatic train protection failure, and locomotive failure. A case study of a line section of Taiwan’s railway network is implemented and the empirical result could be used as a reference in railway dispatching in case of abnormality.     

Dispatching and coordination in multi-area railway traffic management

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.     

Triangle-based routing for mobile ad hoc networks

Routing protocols for Mobile ad hoc networks (MANETs) have been studied extensively in the past decade. Routing protocols for MANETs can be broadly classified as reactive (on-demand), proactive, hybrid and position-based. Reactive routing protocols are attractive because a route between a source and a destination is established only when it is needed. Such protocols, unlike proactive protocols, do not have high overhead for route maintenance and are especially suitable for networks in which not all nodes communicate frequently. One problem with existing reactive routing protocols is the propagation of redundant route request messages during route discovery. In this paper, we present a low-overhead reactive routing protocol which reduces propagation of redundant route request messages. We also compare its performance with the well-known reactive routing protocol AODV.     

高速铁路运行控制与动态调度一体化的现状与展望

高速铁路运行控制系统是高速铁路的大脑和神经系统, 对列车的安全和高效运行至关重要. 随着我国高铁里程数和客运量的快速增加, 现有的控制手段和调度方法在快速、有效解决列车运行过程中出现的突发事件(比如电力故障、突发地震、山体滑坡、异物侵限等)方面尚有一定差距. 目前列车运行控制与调度采用分层架构, 突发情况下主要依赖调度员和司机的人工经验进行应急处置, 列车晚点时间较长, 旅客满意度不高. 因此, 如何针对高速列车运行过程中可能出现的突发事件, 提升其应急处置能力, 成为保障高铁安全高效运营的一大难题. 本文围绕高铁运行控制与动态调度一体化这一前沿研究热点, 对现有运行控制和动态调度的发展现状进行梳理, 在此基础上给出一体化的基本架构, 明确其基本内涵, 最后提出了未来的主要研究方向.     

An optimal fault-tolerant routing algorithm for weighted bidirectional double-loop networks

Double-loop networks are widely used in computer networks. In this paper, we present an optimal message routing algorithm and an optimal fault-tolerant message routing algorithm for weighted bidirectional double-loop networks. The algorithms presented are novel, and they do not use routing tables. After a precalculation of O(log N) steps to determine network parameters, the algorithms can route messages using constant time at each node along the route. The algorithm presented can route messages in the presence of up to three faulty nodes or links. The fault-tolerant routing algorithm guarantees an optimal route in the presence of one node failure.     

Evaluating traffic effects of a route guidance system by dynamic simulation

This paper will present how to evaluate the global traffic effect of a telematic route guidance system by using a developed simulation tool, DYNEMO. A mesoscopic model, that gathers the merits of both macroscopic and microscopic traffic models, has been applied in this tool for dynamic traffic simulation. The communication between vehicles and the telematic infrastructure inside a road network is simulated by decision points that able to give last traffic messages, as vehicles pass by them. The evaluation will be made from the traffic aspect, safety aspect and consumption as well as emission. We will illustrate the approach by using the city road network of Braunschweig in Germany as an example of implementing a kind of route guidance system like EURO-SCOUT.     

多路路由算法及其在QoS路由中的应用

提出一个分布式服务质量路由算法,以求在不影响已存在连接的服务质量的前提下,寻找满足服务质量要求的可行路,该算法根据网络运营状况不同,改变寻路范围,当网络资源很充裕,寻路花费可忽略,可行路的存在性是首要问题时,寻路范围可以是整个网络,使得只要存在可行路,就一定能找到;当网络资源匮乏,寻路信息应尽可能少时,寻路范围将减少,直至每点只向一个邻点发送寻路信息,但其接通率不少于最短路算法。     

Optimizing Train Network Routing Using Deterministic Search

In this paper, we use walk search strategy to solve the optimization problem of train routing on railway network. The proposed approach is a local search algorithm which explores the railway network by walker’s navigating through the network. Using some selection rules, walker can dynamically determine the optimal route of trains. In order to analyze and evaluate the proposed approach, we present two computational studies in which the search algorithm is tested on a part of railway network. The results demonstrate that the proposed approach is an effective tool for optimizing the train routing problem on railway network. Moreover, it can be executed with shorter computation time.     

Development of an expert system for optimizing natural gas pipeline operations

This paper presents an expert system as a decision support tool to optimize natural gas pipeline operations. A natural gas pipeline control system is a controlling system that involves many complicated operating processes. Since a dispatcher (who operates the system) might not be able to handle all of his or her tasks consistently, an expert system has been developed for optimizing the operations by providing consistent, fast and reliable decision support to the dispatcher. Consequently, inconsistency in the dispatcher's performance can be minimized. To build an expert system, the knowledge from an experienced dispatcher, who is familiar with the process in this controlling system is acquired and that knowledge has been implemented as rules in the knowledge base of the expert system. When this expert system has been validated by gas pipeline experts, it can help inexperienced dispatchers to operate the processes more effectively. The expert system is implemented on the real-time expert system shell G2 (trademark of Gensym Corp. of USA). The system also consists of a user interface that helps dispatchers visualize system conditions.     

MPS-CAN analyzer: Integrated implementation of response-time analyses for Controller Area Network

We present a new response-time analyzer for Controller Area Network (CAN) that integrates and implements a number of response-time analyses which address various transmission modes and practical limitations in the CAN controllers. The existing tools for the response-time analysis of CAN support only periodic and sporadic messages. They do not analyze mixed messages which are partly periodic and partly sporadic. These messages are implemented by several higher-level protocols based on CAN that are used in the automotive industry. The new analyzer supports periodic, sporadic as well as mixed messages. It can analyze the systems where periodic and mixed messages are scheduled with offsets. It also supports the analysis of all types of messages while taking into account several queueing policies and buffer limitations in the CAN controllers such as abortable or non-abortable transmit buffers. Moreover, the tool supports the analysis of mixed, periodic and sporadic messages in the heterogeneous systems where Electronic Control Units (ECUs) implement different types of queueing policies and have different types of buffer limitations in the CAN controllers. We conduct a case study of a heterogeneous application from the automotive domain to show the usability of the tool. Moreover, we perform a detailed evaluation of the implemented analyses.     

一种无线Mesh网络中可证明安全的HMIPv6路由优化方案

HMIPv6技术能够实现无线Mesh网络的无缝切换,针对其绑定更新过程中执行路由优化存在的安全问题,提出了一种适用于无线Mesh网络的基于椭圆曲线公钥自认证体制的安全路由优化方案。该方案使用户在执行路由优化的过程中能够实现对绑定更新消息的认证与授权,且通过有效的会话密钥协商机制为绑定更新消息的传输提供了安全保障,具有可证明安全性。最后通过性能分析表明,该方案简化了标准路由优化方案的流程,提高了一般注册过程的效率。     

P2P网络环境下的一种高效搜索算法:Multilayer Light-Gossip

由于现有非结构化P2P网络路由协议均在应用层实现,缺乏缓存机制和对Internet底层通信子网路由资源的利用,存在可扩展性差和效率不高的问题·在基于层域结构的RLP2P网络环境下,将路由空间分为域间和域内两层,结合泛洪和生成树搜索方式的优点,提出并实现了一种Multilayer Light-Gossip分级搜索算法和域间基于正六边形的蜂窝路由探测策略,把网络中的搜索消息分为域间和域内扩散两类分级扩散,以一定的消息冗余保持网络的稳健性和搜索的有效性,使定位某种服务的工作量和查询范围从网络中的所有结点数降到域内的节点数·运用预测评估方法对级间路由消息进行预分组,使消息能够自适应地沿着一条在时间度量上距离尽量短的路径前进·实验结果表明,Multilayer Light-Gossip算法大幅提高搜索效率和减少冗余消息,在广域环境下具有良好的搜索性能和扩展性·     

基于位置信息的改进AODV路由算法

针对AODV协议路由开销较大的问题,提出一种基于位置信息的改进路由协议(GAODV).GAODV利用中间节点重新计算转发角度,保证转发角度内邻居节点数不小于预设门限值,同时还引入基于位置信息的计数器方案,使距离目的节点近的中间节点优先转发路由请求消息,有利于减少转发冗余路由请求信息和降低寻路失败概率.OPNET仿真实验结果表明,GAODV在数据分组投递率、路由开销、总丢包数、端到端时延和平均路由跳数等方面都优于已有算法.     

Design of a Railway Scheduling Model for Dense Services

We address the problem of generating detailed conflict-free railway schedules for given sets of train lines and frequencies. To solve this problem for large railway networks, we propose a network decomposition into condensation and compensation zones. Condensation zones contain main station areas, where capacity is limited and trains are required to travel with maximum speed. They are connected by compensation zones, where traffic is less dense and time reserves can be introduced for increasing stability. In this paper, we focus on the scheduling problem in condensation zones. To gain structure in the schedule we enforce a time discretisation which reduces the problem size considerably and also the cognitive load of the dispatchers. The problem is formulated as an independent set problem in a conflict graph, which is then solved using a fixed-point iteration heuristic. Results show that even large-scale problems with dense timetables and large topologies can be solved quickly.     

Location detection and disambiguation from twitter messages

A remarkable amount of Twitter messages are generated every second. Detecting the location entities mentioned in these messages is useful in text mining applications. Therefore, techniques for extracting the location entities from the Twitter textual content are needed. In this work, we approach this task in a similar manner to the Named Entity Recognition (NER) task, but we focus only on locations, while NER systems detect names of persons, organizations, locations, and sometimes more (e.g., dates, times). But, unlike NER systems, we address a deeper task: classifying the detected locations into names of cities, provinces/states, and countries in order to map them into physical locations. We approach the task in a novel way, consisting in two stages. In the first stage, we train Conditional Random Fields (CRF) models that are able to detect the locations mentioned in the messages. We train three classifiers: one for cities, one for provinces/states, and one for countries, with various sets of features. Since a dataset annotated with this kind of information was not available, we collected and annotated our own dataset to use for training and testing. In the second stage, we resolve the remaining ambiguities, namely, cases when there exists more than one place with the same name. We proposed a set of heuristics able to choose the correct physical location in these cases. Our two-stage model will allow a social media monitoring system to visualize the places mentioned in Twitter messages on a map of the world or to compute statistics about locations. This kind of information can be of interest to business or marketing applications.