The minimum path pair (MPP) query problem is to find the optimal meeting point of two minimum paths for two users in a network, where each user's minimum path has its own departure and destination ...nodes. However, the MPP query problem on a time-varying network that generally exists in the world remains open. In this study, we investigate the time-varying minimum path pair (TMPP) query problem, where the arcs of the network are time dependent. We first model the TMPP and then propose a time impulse neural network (TINN) to solve the TMPP. In the design of the TINN, the entire network topology is considered as the architecture of the neural network, and each node is viewed as a neuron. The core of an impulse-based neuron consists of six parts: input, impulse receiver, time window selector, neuron storage, impulse sender, and output. Unlike the traditional neural network, the whole neural network does not require a training process but is implemented through an impulse mechanism. The TINN consists of two stages; the first stage is to find the two minimum paths of two users, while the second stage is to calculate the distance between these two minimum paths. The underlying idea of the TINN is to find the minimum path using an impulse mechanism. The minimum path relies on the earliest time impulse stemming from the depart node that arrives at the destination node. With this mechanism, both the minimum path of the network and the distance between two paths can be addressed. Furthermore, theoretical analysis demonstrates the correctness and provides the complexity of the TINN. Experiments of the TINN are carried out based on the well-known New York City Map. A comparative study illustrates the effectiveness of the TINN.
Taxi service systems in big cities are immensely complex due to the interaction and self-organization between taxi drivers and passengers. An inefficient taxi service system leads to more empty trips ...for drivers and longer waiting time for passengers and introduces unnecessary congestion on the road network. In this paper, we investigate the efficiency level of the taxi service system using real-world large-scale taxi trip data. By assuming a hypothetical system-wide recommendation system, two approaches are proposed to find the theoretical optimal strategies that minimize the cost of empty trips and the number of taxis required to satisfy all the observed trips. The optimization problems are transformed into equivalent graph problems and solved using polynomial time algorithms. The taxi trip data in New York City are used to quantitatively examine the gap between the current system performance and the theoretically optimal system. The numerical results indicate that, if system-wide information between taxi drivers and passengers was shared, it is possible to reduce 60%-90% of the total empty trip cost depending on different objectives, and one-third of all taxis required to serve all observed trips. The existence of destructive competition among taxi drivers is also uncovered in the actual taxi service system. The huge performance gap suggests an urgent need for a system reconsideration in designing taxi recommendation systems.
The active distribution network has been fully developed because it can achieve efficient energy utilization through the effective control of distributed generation, electrical energy storage, and ...active loads. However, the research on the reliability of active distribution network operation still stays in the medium and long-term calculation, without considering the influence of dynamic equipment characteristics and active distribution network operation characteristics on reliability. In order to improve the comprehensiveness and calculation speed of the reliability calculation of an active distribution network, this paper proposes a fast calculation method for the reliability of the active distribution network based on dynamic equipment failure rates. Firstly, based on fuzzy-theory and data-driven methods, the cloud model and the Proportional Hazard Model are used to model the dynamic failure rates of exposed and enclosed types of equipment, respectively. This considers the impacts of the dynamic failure characteristics of the equipment on the reliability calculation and improves the comprehensiveness of the calculation. Then, the improved K-means algorithm is used to achieve a faster and more suitable scenario reduction and increase the computation rate. Finally, considering the island operation and contact line transfer under the active distribution network, simplifying the network by improving the minimum path method, the reliability calculation method of the active distribution network combining source–load uncertainty, switch fault information, and load transfer probability is further proposed. The cases show that the dynamic fault rate model is closer to an engineering reality and has generality. The improved K-means algorithm is faster and more accurate than the traditional algorithm. The final proposed fast reliability calculation method reduces the time by 72.76 times compared to the traditional method. It fully reflects the operational characteristics of the active distribution network and provides a reference for the optimal dispatch of the active distribution network.
For daily airport operations, the insufficient number and the improper scheduling of ground support vehicles are the main causes of flight delays. In this paper, a novel network model is proposed to ...complement the optimal scheduling of ferry vehicles for the flight ground support service. In the process of model construction, we first innovatively construct a ferry vehicle capacity network by having the introduced virtual flights and the ferry vehicle depot as nodes, in which the directed edges indicate that the two nodes associated may be consecutively served by the same ferry vehicle. Based on the capacity network, a mixed integer programming model is constructed to minimize the number of ferry vehicles needed. In addition, this paper shows that the mixed integer programming is equivalent to a linear programming when the service start time of each flight is fixed, which makes the solving process more efficient, and the linear programming model can be applied to solve the minimum node-disjoint path cover of directed acyclic graphs. The efficiency and accuracy of the method are validated by the actual flight data obtained from Beijing Capital International Airport. This study will provide a methodological reference for the optimal scheduling of airport ferry vehicles.
The School Bus Routing Problem (SBRP) is widely discussed in the operations research literature and can be solved by several exact methods and heuristics. This problem seeks to designate the most ...efficient routes for a fleet of school buses, minimizing the total distance covered and considering variables such as bus stop locations, number of passengers, and the assigned destination for each of them. This study aims at solving a real case SBRP of a small-sized county located in the state of Paraná. The proposed method is based on the Capacitated Vehicle Routing Problem (CVRP) and Travelling Salesman Problem (TSP) combined with a heuristic correction that guarantees sequence constraints, in which the student has to be collected before visiting their destination school. It was possible to obtain two routes of 30.76 km and 17.42 km respectively and both with the total vehicles’ capacity of 24 students, which corresponds to the reduction of about 10% in the daily distance covered by two buses.
Network reliability is famous for its problem solving ability in several real-life applications. However, due to its NP-hard nature (Ball in IEEE Trans Reliab 35(3):230–238, 1986), researchers are ...devoted to the improvement of computational efficiency in various approaches. Although flow in networks depicts its combination properties, only few of them are useful in the calculation of network reliability. In some point of views, we call it mining in flow data. This paper presents techniques of how to efficiently do the flow data mining tasks. A skill based on backtrack and maximal flow is illustrated with examples and benchmarks. The results show that the proposed approach is valuable in the calculation of network reliability.
Abstract
Subway stations and trains are densely populated public places. Once fire breaks out, it will cause casualties and seriously threaten people’s life and property safety. In order to explore ...the deep causes of subway fire and prevent subway fire accidents, this paper makes statistics on the causes of subway fire in various countries in recent years and classifies them. On this basis, the Bayesian network for subway fire causes is constructed, the probability of subway fire occurrence and the posterior probability of each basic event are calculated by using the prior probability of each basic event, and the corresponding safety management measures are proposed. The results show that the method can find out the probability of each basic event in subway fire by quantitative calculation, and the method is scientific and effective, which can provide reference for subway safety management.
PDF
