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.     

Request redirection algorithms for distributed Web systems

Replication of information among multiple servers is necessary to support high request rates to popular Web sites. We consider systems that maintain one interface to users, even it they consist of multiple nodes with visible IP addresses that are distributed among different networks. In these systems, first-level dispatching is achieved through the Domain Name System (DNS) during the address lookup phase. Distributed Web systems can use a request redirection mechanism as second-level dispatching because the DNS routing scheme has limited control on offered load. Redirection is always executed by the servers, but there are many alternatives that are worth investigating. We explore the combination of DNS dispatching with redirection schemes that use centralized or distributed control on the basis of global or local state information. In fully distributed schemes, DNS dispatching is carried out by simple algorithms because load sharing is taken by some redirection mechanisms that each server activates autonomously. On the other hand, in fully centralized schemes, redirection is used as a tool to enforce decisions taken by the same centralized entity that provides the first-level dispatching. We also investigate hybrid strategies. We conclude that distributed algorithms are preferable over their centralized counterpart because they provide stable performance, take content-aware dispatching decisions, limit the percentage of redirected requests, and their implementation is much simpler than that required by centralized schemes.     

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.     

Non-Discriminatory Automatic Registration of Knock-On Train Delays

Incidents and waiting for train connections are registered by dispatchers as sources of train delays, but route and headway conflicts are not always clearly recognized. Moreover, traffic management and route setting are the primary task of dispatchers and signallers, whilst monitoring and incident registration is not allowed to take up too much of their time. This paper describes a tool that automatically and without discrimination identifies route conflicts and the train numbers involved. It is based on standard train describer and infrastructure messages recorded on the Dutch railway network. The logic of these messages is captured in a coloured Petri net (CPN) model on which a prototype tool for route conflict identification and estimation of knock-on delay has been developed.     

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.     

TAP: Traffic-aware topology control in on-demand ad hoc networks

Energy efficiency is crucial to achieve satisfactory network lifetime in ad hoc networks. In order to reduce the energy consumption significantly, a node needs to turn off its transceiver. Many existing energy-saving algorithms are based on constructing a simplified routing backbone for global connectivity. In this paper some problems involved with node sleep in on-demand ad hoc networks are addressed firstly. Then we propose a distributed, cross-layer Traffic-Aware Participation (TAP) algorithm, where nodes make decisions on whether to sleep or not based on both the traffic pattern and local connectivity. Nodes get dynamic traffic characteristics as well as active neighbors within two hops via routing control and data packets periodically. We further present a lightweight algorithm to avoid network partition resulted from node sleeping. Simulation results show that, compared to current sleep-based topology control algorithms, TAP achieves better network service quality and lower delay while allowing comparable energy conservation.     

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.     

Distributed wireless power transfer in sensor networks with multiple Mobile Chargers

We investigate the problem of efficient wireless power transfer in wireless sensor networks. In our approach, special mobile entities (called the Mobile Chargers) traverse the network and wirelessly replenish the energy of sensor nodes. In contrast to most current approaches, we envision methods that are distributed and use limited network information. We propose four new protocols for efficient charging, addressing key issues which we identify, most notably (i) what are good coordination procedures for the Mobile Chargers and (ii) what are good trajectories for the Mobile Chargers. Two of our protocols (DC, DCLK) perform distributed, limited network knowledge coordination and charging, while two others (CC, CCGK) perform centralized, global network knowledge coordination and charging. As detailed simulations demonstrate, one of our distributed protocols outperforms a known state of the art method, while its performance gets quite close to the performance of the powerful centralized global knowledge method.     

A New Methodology for Modeling, Analysis, Synthesis, and Simulation of Time-Optimal Train Traffic in Large Networks

From a system-theoretic standpoint, a constrained state-space model for train traffic in a large railway network is developed. The novelty of the work is the transformation or rather reduction of the directed graph of the network to some parallel lists. Mathematization of this sophisticated problem is thus circumvented. All the aspects of a real network (such as that of the German rail) are completely captured by this model. Some degrees of freedom, as well as some robustness can be injected into the operation of the system. The problem of time-optimal train traffic in large networks is then defined and solved using the maximum principle. The solution is obtained by reducing the boundary value problem arising from the time-optimality criterion to an initial value problem for an ordinary differential equation. A taxonomy of all possible switching points of the control actions is presented. The proposed approach is expected to result in faster-than-real-time simulation of time-optimal traffic in large networks and, thus, facilitation of real-time control of the network by dispatchers. This expectation is quantitatively justified by analysis of simulation results of some small parts of the German rail network.     

Dynamic overload control for distributed call processors using the neural network method.

Overload control of call processors in telecom networks is used to protect the network of call processing computers from excessive load during traffic peaks, and involves techniques of predictive control with limited local information. Here we propose a neural network algorithm, in which a group of neural controllers are trained using examples generated by a globally optimal control method. Simulations show that the neural controllers have better performance than local control algorithms in both the throughput and the response to traffic upsurges. Compared with the centralized control algorithm, the neural control significantly decreases the computational time for making decisions and can be implemented in real time.     

Comparison of Stochastic Global Optimization Methods to Estimate Neural Network Weights

Training a neural network is a difficult optimization problem because of numerous local minima. Many global search algorithms have been used to train neural networks. However, local search algorithms are more efficient with computational resources, and therefore numerous random restarts with a local algorithm may be more effective than a global algorithm. This study uses Monte-Carlo simulations to determine the efficiency of a local search algorithm relative to nine stochastic global algorithms when using a neural network on function approximation problems. The computational requirements of the global algorithms are several times higher than the local algorithm and there is little gain in using the global algorithms to train neural networks. Since the global algorithms only marginally outperform the local algorithm in obtaining a lower local minimum and they require more computational resources, the results in this study indicate that with respect to the specific algorithms and function approximation problems studied, there is little evidence to show that a global algorithm should be used over a more traditional local optimization routine for training neural networks. Further, neural networks should not be estimated from a single set of starting values whether a global or local optimization method is used.     

An Advanced Real-Time Train Dispatching System for Minimizing the Propagation of Delays in a Dispatching Area Under Severe Disturbances

In highly utilized rail networks, as in the Netherlands, conflicts and subsequent train delays propagate considerably in time and space during operations. In order to realistically forecast and minimize delay propagation, there is a need to extend short-term traffic planning up to several hours. On the other hand, as the magnitude of the time horizon increases the problem becomes computationally intractable and hard to tackle. In this paper, we decompose a long time horizon into tractable intervals to be solved in cascade with the objective of improving punctuality. We use the ROMA dispatching system to pro-actively detect and globally solve conflicts on each time interval. The future evolution of railway traffic is predicted on the basis of the actual track occupation, the Dutch signaling system and dynamic train characteristics. Extensive computational tests are carried out on the railway dispatching area between Utrecht and Den Bosch.     

An autonomy-oriented computing approach to community mining in distributed and dynamic networks

A network community refers to a special type of network structure that contains a group of nodes connected based on certain relationships or similar properties. Our ability to mine communities hidden inside networks will readily enable us to effectively understand and exploit such networks. So far, various methods and algorithms have been developed to perform the task of community mining, where it is often required that the networks are processed in a centralized manner, and their structures will not dynamically change. However, in the real world, many applications involve distributed and dynamically evolving networks, in which resources and controls are not only decentralized but also updated frequently. It would be difficult for the existing methods to deal with these types of networks since their global topological representations are either not available or too hard to obtain due to their huge size, decentralization, and/or dynamic updates. The aim of our work is to address the problem of mining communities from a distributed and dynamic network. It differs from the previous ones in that here we introduce the notion of self-organizing agent networks, and provide an autonomy-oriented computing (AOC) approach to distributed and incremental mining of network communities. The AOC-based method utilizes reactive agents that can collectively detect and update community structures in a distributed and dynamically evolving network, based only on their local views and interactions. While providing detailed formulations, we present the results of our systematic validations using real-world benchmark networks as well as synthetic networks that include a distributed intelligent Portable Digital Assistant (iPDA) network example.     

Local algorithms for edge colorings in UDGs

In this paper, we consider two problems: the edge coloring and the strong edge coloring problems on unit disk graphs (UDGs). Both problems have important applications in wireless sensor networks as they can be used to model link scheduling problems in such networks. It is well known that both problems are NP-complete, and approximation algorithms for them have been extensively studied under the centralized model of computation. Centralized algorithms, however, are not suitable for ad hoc wireless sensor networks whose devices typically have limited resources, and lack the centralized coordination.We develop local distributed approximation algorithms for the edge coloring and the strong edge coloring problems on unit disk graphs. For the edge coloring problem, our local distributed algorithm has approximation ratio 2 and locality 50. For the strong edge coloring problem on UDGs, we present two local distributed algorithms with different tradeoffs between their approximation ratio and locality. The first algorithm has ratio 128 and locality 22, whereas the second algorithm has ratio 10 and locality 180.     

A survey of distributed optimization

In distributed optimization of multi-agent systems, agents cooperate to minimize a global function which is a sum of local objective functions. Motivated by applications including power systems, sensor networks, smart buildings, and smart manufacturing, various distributed optimization algorithms have been developed. In these algorithms, each agent performs local computation based on its own information and information received from its neighboring agents through the underlying communication network, so that the optimization problem can be solved in a distributed manner. This survey paper aims to offer a detailed overview of existing distributed optimization algorithms and their applications in power systems. More specifically, we first review discrete-time and continuous-time distributed optimization algorithms for undirected graphs. We then discuss how to extend these algorithms in various directions to handle more realistic scenarios. Finally, we focus on the application of distributed optimization in the optimal coordination of distributed energy resources.     

A multi-agent approach for integrated emergency vehicle dispatching and covering problem

The most important decisions that should be made by emergency vehicle managers are related to the allocation and the covering problems. The allocation (or dispatching) problem consists of deciding which vehicle must be assigned to assist an emergency in the best times. The covering problem aims at keeping the region under surveillance well-covered by relocating available vehicles. As components are geographically distributed, decentralized solution approaches may present several advantages. This paper develops a decentralized distributed solution approach based on multi-agent systems (MAS) to manage the emergency vehicles. The proposed system integrates the dispatching of vehicles to calls with zone coverage issues. This integration means that allocation and covering decisions are considered jointly. The idea of MAS has been applied in many others real-world contexts, and has been proven to provide more flexibility, reliability, adaptability and reconfigurability. To our knowledge, there is no existing work that uses MAS for real-time emergency vehicle allocation problem while accounting for the coverage requirements for future demands. We propose a multi-agent architecture that fit the real emergency systems, and that aims at keeping good performance compared to the centralized solution. The objective is to coordinate agents to reach good quality solutions in a distributed way. For this purpose two approaches are examined. The first one is used to show the impact of distributing data and control on the solution quality, since the dispatching decisions are based only on local evaluations of the fitness. The second approach is based on implicit agents' coordination using a more refined and efficient auction mechanism. The performance of each approach is compared to the centralized solution obtained by solving the proposed model with ILOG CPLEX solver. The obtained results show the importance of the coordination method to keep a good quality of service while distributing data and decision making, and prove the performance of the second approach.     

传感器网络分布式数据流的频繁项集挖掘算法

研究无线传感器网络中数据流频繁项集挖掘问题。针对集中式的静态数据流频繁项集挖掘方法不能在传感器网络中直接使用这一特点,提出基于传感器网络的分布式数据流的频繁项集挖掘算法FIMVS。该算法基于FPtree快速挖掘出传感器节点上单一数据流的局部频繁项集,然后通过路由将其在无线传感器网络里逐层上传合并,在Sink节点上汇聚后,采用自顶向下的高效剪枝策略挖掘出全局频繁项集。实验结果表明,该算法能有效地大幅度减少候选项集,降低无线传感器网络中的通信量,并有较高的时间和空间效率。     

Optimization Techniques for Reactive Network Monitoring

We develop a framework for minimizing the communication overhead of monitoring global system parameters in IP networks and sensor networks. A global system predicate is defined as a conjunction of the local properties of different network elements. A typical example is to identify the time windows when the outbound traffic from each network element exceeds a predefined threshold. Our main idea is to optimize the scheduling of local event reporting across network elements for a given network traffic load and local event frequencies. The system architecture consists of N distributed network elements coordinated by a central monitoring station. Each network element monitors a set of local properties and the central station is responsible for identifying the status of global parameters registered in the system. We design an optimal algorithm, the Partition and Rank (PAR) scheme, when the local events are independent; whereas, when they are dependent, we show that the problem is NP-complete and develop two efficient heuristics: the PAR for dependent events (PAR-D) and Adaptive (Ada) algorithms, which adapt well to changing network conditions, and outperform the current state of the art techniques in terms of communication cost.