Sensitivity analysis on stochastic equilibrium transportation networks using genetic algorithm

This study deals with the sensitivity analysis of an equilibrium transportation networks using genetic algorithm approach and uses the bi‐level iterative sensitivity algorithm. Therefore, integrated Genetic Algorithm‐TRANSYT and Path Flow Estimator (GATPFE) is developed for signalized road networks for various level of perceived travel time in order to test the sensitivity of perceived travel time error in an urban stochastic road networks. Level of information provided to drivers correspondingly affects the signal timing parameters and hence the Stochastic User Equilibrium (SUE) link flows. When the information on road system is increased, the road users try to avoid conflicting links. Therefore, the stochastic equilibrium assignment concept tends to be user equilibrium. The GATPFE is used to solve the bi‐level problem, where the Area Traffic Control (ATC) is the upper‐level and the SUE assignment is the lower‐level. The GATPFE is tested for six‐junction network taken from literature. The results show that the integrated GATPFE can be applied to carry out sensitivity analysis at the equilibrium network design problems for various level of information and it simultaneously optimize the signal timings (i.e. network common cycle time, signal stage and offsets between junctions).     

Vehicular event sharing with a mobile peer-to-peer architecture

In vehicular ad hoc networks (VANETs), different types of information can be useful to drivers. Such networks are highly dynamic due to both the movements of the vehicles and the short range of the wireless communications. Thus, the information exchanges between vehicles about relevant information can only rely on short interactions. Therefore, an efficient mechanism to manage and disseminate the relevant information is required. Specifically, we present in this paper a system for data sharing in vehicular networks, which we call Vehicular Event Sharing with a mobile Peer-to-peer Architecture (VESPA). In this system, a new technique based on the concept of Encounter Probability is proposed for vehicles to share information using vehicle-to-vehicle communications. The objective is to facilitate the dissemination of information between vehicles when they meet each other, taking into account the relevance of the data to the drivers. Besides, the relevance must also be considered to inform a driver about the interesting events. Moreover, our proposal takes into account any type of event (e.g., available parking spaces, obstacles in the road, information relative to the coordination of vehicles in emergency situations, etc.) in the network. An experimental evaluation and the implemented prototype show the interest of the system.     

System optimal dynamic traffic assignment: Properties and solution procedures in the case of a many-to-one network

Thanks to its high dimensionality and a usually non-convex constraint set, system optimal dynamic traffic assignment remains one of the most challenging problems in transportation research. This paper identifies two fundamental properties of the problem and uses them to design an efficient solution procedure. We first show that the non-convexity of the problem can be circumvented by first solving a relaxed problem and then applying a traffic holding elimination procedure to obtain the solution(s) of the original problem. To efficiently solve the relaxed problem, we explore the relationship between the relaxed problems based on different traffic flow models (PQ, SQ, CTM) and a minimal cost flow (MCF) problem for a special space-expansion network. It is shown that all the four problem formulations produce the same minimal system cost and share one common solution which does not involve inside queues in the network. Efficient solution algorithms such as the network simplex method can be applied to solve the MCF problem and identify such an optimal traffic pattern. Numerical examples are also presented to demonstrate the efficiency of the proposed solution procedure.     

A dynamic behavioural traffic assignment model with strategic agents

Foresee traffic conditions and demand is a major issue nowadays that is very often approached using simulation tools. The aim of this work is to propose an innovative strategy to tackle such problem, relying on the presentation and analysis of a behavioural dynamic traffic assignment.The proposal relies on the assumption that travellers take routing policies rather than paths, leading us to introduce the possibility for each simulated agent to apply, in real time, a strategy allowing him to possibly re-route his path depending on the perceived local traffic conditions, jam and/or time already spent in his journey.The re-routing process allows the agents to directly react to any change in the road network. For the sake of simplicity, the agents’ strategy is modelled with a simple neural network whose parameters are determined during a preliminary training stage. The inputs of such neural network read the local information about the route network and the output gives the action to undertake: stay on the same path or modify it. As the agents use only local information, the overall network topology does not really matter, thus the strategy is able to cope with large and not previously explored networks.Numerical experiments are performed on various scenarios containing different proportions of trained strategic agents, agents with random strategies and non strategic agents, to test the robustness and adaptability to new environments and varying network conditions. The methodology is also compared against existing approaches and real world data. The outcome of the experiments suggest that this work-in-progress already produces encouraging results in terms of accuracy and computational efficiency. This indicates that the proposed approach has the potential to provide better tools to investigate and forecast drivers’ choice behaviours. Eventually these tools can improve the delivery and efficiency of traffic information to the drivers.     

Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state–space–time network representations

Optimization of on-demand transportation systems and ride-sharing services involves solving a class of complex vehicle routing problems with pickup and delivery with time windows (VRPPDTW). This paper first proposes a new time-discretized multi-commodity network flow model for the VRPPDTW based on the integration of vehicles’ carrying states within space–time transportation networks, so as to allow a joint optimization of passenger-to-vehicle assignment and turn-by-turn routing in congested transportation networks. Our three-dimensional state–space–time network construct is able to comprehensively enumerate possible transportation states at any given time along vehicle space–time paths, and further allows a forward dynamic programming solution algorithm to solve the single vehicle VRPPDTW problem. By utilizing a Lagrangian relaxation approach, the primal multi-vehicle routing problem is decomposed to a sequence of single vehicle routing sub-problems, with Lagrangian multipliers for individual passengers’ requests being updated by sub-gradient-based algorithms. We further discuss a number of search space reduction strategies and test our algorithms, implemented through a specialized program in C++, on medium-scale and large-scale transportation networks, namely the Chicago sketch and Phoenix regional networks.     

ARTEMIS: French-German project for railway movements command and control

The development of railway transportation, especially through the gradual implementation of high-speed European network, is inciting railway companies to design railway movements command and control systems to enhance technical performance in terms of throughput and control of disturbances while simultaneously minimizing operational costs. The new command-control systems must be modular, adaptable and evolutive structures from both functional and geographical viewpoints if they are to satisfy all operational needs. Concurrent research into performance enhancement and cost reduction prescribes a system in which the majority of the “real time” components are aboards the locomotives. This is particularly true for those components used by the train to indicate its own position on the network as well as those enabling it to converse with operational control centers. The initial task is to design a global architecture of the command-control system that satisfies modularity and availability criteria followed by the development of numerous technical components including radar self-location systems and cellular radio transmission networks. The French (SNCF) and German (DB) national railways have implemented a vast program of co-operation aimed at providing valid, proven answers to these problems so as to allow their trains to travel freely on either network.     

Macroscopic relations of urban traffic variables: Bifurcations, multivaluedness and instability

Recent experimental work has shown that the average flow and average density within certain urban networks are related by a unique, reproducible curve known as the Macroscopic Fundamental Diagram (MFD). For networks consisting of a single route this MFD can be predicted analytically; but when the networks consist of multiple overlapping routes experience shows that the flows observed in congestion for a given density are less than those one would predict if the routes were homogeneously congested and did not overlap. These types of networks also tend to jam at densities that are only a fraction of their routes’ average jam density.This paper provides an explanation for these phenomena. It shows that, even for perfectly homogeneous networks with spatially uniform travel patterns, symmetric equilibrium patterns with equal flows and densities across all links are unstable if the average network density is sufficiently high. Instead, the stable equilibrium patterns are asymmetric. For this reason the networks jam at lower densities and exhibit lower flows than one would predict if traffic was evenly distributed.Analysis of small idealized networks that can be treated as simple dynamical systems shows that these networks undergo a bifurcation at a network-specific critical density such that for lower densities the MFDs have predictably high flows and are univalued, and for higher densities the order breaks down. Microsimulations show that this bifurcation also manifests itself in large symmetric networks. In this case though, the bifurcation is more pernicious: once the network density exceeds the critical value, the stable state is one of complete gridlock with zero flow. It is therefore important to ensure in real-world applications that a network’s density never be allowed to approach this critical value.Fortunately, analysis shows that the bifurcation’s critical density increases considerably if some of the drivers choose their routes adaptively in response to traffic conditions. So far, for networks with adaptive drivers, bifurcations have only been observed in simulations, but not (yet) in real life. This could be because real drivers are more adaptive than simulated drivers and/or because the observed real networks were not sufficiently congested.     

Counting the different efficient paths for transportation networks and its applications

This paper deals with an interesting problem about how to efficiently compute the number of different efficient paths between an origin‐destination pair for a transportation network because these efficient paths are the possible paths used by drivers to some extent. Based on a novel triangle operation derived, it first presents a polynomial‐time combinatorial algorithm that can obtain the number of different simple paths between any two nodes for an acyclic network as well as the total travel cost of these paths. This paper proceeds to develop a combinatorial algorithm with polynomial‐time complexity for both counting the different efficient paths between an origin‐destination pair and calculating the total travel cost of these paths. As for applications, this paper shows that the preceding two algorithms can yield the lower and upper bounds for the number of different simple paths between an origin‐destination pair, while it has already be recognized that a polynomial‐time algorithm getting such a number does not exist for a general network. Furthermore, the latter algorithm can be applied for developing a heuristic method for the traffic counting location problem arising from the origin‐destination matrix estimation problems.     

Cooperative traffic control of a mixed network with two urban regions and a freeway

Currently most optimization methods for urban transport networks (i) are suited for networks with simplified dynamics that are far from real-sized networks or (ii) apply decentralized control, which is not appropriate for heterogeneously loaded networks or (iii) investigate good-quality solutions through micro-simulation models and scenario analysis, which make the problem intractable in real time. In principle, traffic management decisions for different sub-systems of a transport network (urban, freeway) are controlled by operational rules that are network specific and independent from one traffic authority to another. In this paper, the macroscopic traffic modeling and control of a large-scale mixed transportation network consisting of a freeway and an urban network is tackled. The urban network is partitioned into two regions, each one with a well-defined Macroscopic Fundamental Diagram (MFD), i.e. a unimodal and low-scatter relationship between region density and outflow. The freeway is regarded as one alternative commuting route which has one on-ramp and one off-ramp within each urban region. The urban and freeway flow dynamics are formulated with the tool of MFD and asymmetric cell transmission model, respectively. Perimeter controllers on the border of the urban regions operating to manipulate the perimeter interflow between the two regions, and controllers at the on-ramps for ramp metering are considered to control the flow distribution in the mixed network. The optimal traffic control problem is solved by a Model Predictive Control (MPC) approach in order to minimize total delay in the entire network. Several control policies with different levels of urban-freeway control coordination are introduced and tested to scrutinize the characteristics of the proposed controllers. Numerical results demonstrate how different levels of coordination improve the performance once compared with independent control for freeway and urban network. The approach presented in this paper can be extended to implement efficient real-world control strategies for large-scale mixed traffic networks.     

Approximate network loading and dual-time-scale dynamic user equilibrium

In this paper we present a dual-time-scale formulation of dynamic user equilibrium (DUE) with demand evolution. Our formulation belongs to the problem class that Pang and Stewart (2008) refer to as differential variational inequalities. It combines the within-day time scale for which route and departure time choices fluctuate in continuous time with the day-to-day time scale for which demand evolves in discrete time steps. Our formulation is consistent with the often told story that drivers adjust their travel demands at the end of every day based on their congestion experience during one or more previous days. We show that analysis of the within-day assignment model is tremendously simplified by expressing dynamic user equilibrium as a differential variational inequality. We also show there is a class of day-to-day demand growth models that allow the dual-time-scale formulation to be decomposed by time-stepping to yield a sequence of continuous time, single-day, dynamic user equilibrium problems. To solve the single-day DUE problems arising during time-stepping, it is necessary to repeatedly solve a dynamic network loading problem. We observe that the network loading phase of DUE computation generally constitutes a differential algebraic equation (DAE) system, and we show that the DAE system for network loading based on the link delay model (LDM) of Friesz et al. (1993) may be approximated by a system of ordinary differential equations (ODEs). That system of ODEs, as we demonstrate, may be efficiently solved using traditional numerical methods for such problems. To compute an actual dynamic user equilibrium, we introduce a continuous time fixed-point algorithm and prove its convergence for effective path delay operators that allow a limited type of nonmonotone path delay. We show that our DUE algorithm is compatible with network loading based on the LDM and the cell transmission model (CTM) due to Daganzo (1995). We provide a numerical example based on the much studied Sioux Falls network.     

Dynamic system-optimal traffic assignment using a state space model

We propose a new mathematical formulation for the problem of optimal traffic assignment in dynamic networks with multiple origins and destinations. This problem is motivated by route guidance issues that arise in an Intelligent Vehicle-Highway Systems (IVHS) environment. We assume that the network is subject to known time-varying demands for travel between its origins and destinations during a given time horizon. The objective is to assign the vehicles to links over time so as to minimize the total travel time experienced by all the vehicles using the network. We model the traffic network over the time horizon as a discrete-time dynamical system. The system state at each time instant is defined in a way that, without loss of optimality, avoids complete microscopic detail by grouping vehicles into platoons irrespective of origin node and time of entry to network. Moreover, the formulation contains no explicit path enumeration. The state transition function can model link travel times by either impedance functions, link outflow functions, or by a combination of both. Two versions (with different boundary conditions) of the problem of optimal traffic assignment are studied in the context of this model. These optimization problems are optimal control problems for nonlinear discrete-time dynamical systems, and thus they are amenable to algorithmic solutions based on dynamic programming. The computational challenges associated with the exact solution of these problems are discussed and some heuristics are proposed.     

The treatment of uncertainty in the dynamic origin–destination estimation problem using a fuzzy approach

Regardless of existing types of transportation and traffic model and their applications, the essential input to these models is travel demand, which is usually described using origin–destination (OD) matrices. Due to the high cost and time required for the direct development of such matrices, they are sometimes estimated indirectly from traffic measurements recorded from the transportation network. Based on an assumed demand profile, OD estimation problems can be categorized into static or dynamic groups. Dynamic OD demand provides valuable information on the within-day fluctuation of traffic, which can be employed to analyse congestion dissipation. In addition, OD estimates are essential inputs to dynamic traffic assignment (DTA) models. This study presents a fuzzy approach to dynamic OD estimation problems. The problems are approached using a two-level model in which demand is estimated in the upper level and the lower level performs DTA via traffic simulation. Using fuzzy rules and the fuzzy C-Mean clustering approach, the proposed method treats uncertainty in historical OD demand and observed link counts. The approach employs expert knowledge to model fitted link counts and to set boundaries for the optimization problem by defining functions in the fuzzification process. The same operation is performed on the simulation outputs, and the entire process enables different types of optimization algorithm to be employed. The Box-complex method is utilized as an optimization algorithm in the implementation of the approach. Empirical case studies are performed on two networks to evaluate the validity and accuracy of the approach. The study results for a synthetic network and a real network demonstrate the robust performance of the proposed method even when using low-quality historical demand data.     

Generic model for resource allocation in transportation. Application to urban parking management

In this paper, we define the online localized resource allocation problem, especially relevant for modeling transportation applications. The problem modeling takes into account simultaneously the geographical location of consumers and resources together with their online nondeterministic appearance. We use urban parking management as an illustration of this problem. In fact, urban parking management is an online localized resource allocation problem, where the question is how to find an efficient allocation of parking spots to drivers, while they all have dynamic geographical positions and appear nondeterministically. We define this problem and propose a multiagent system to solve it. The objective of the system is to decrease, for private vehicles drivers, the parking spots search time. The drivers are organized in communities and share information about spots availability. We have defined two cooperative models and compared them: a fully cooperative model, where agents share all the available information, and a “coopetitive” model, where drivers do not share information about the spot that they have chosen. Results show the superiority of the first model.     

Reverse time-restricted shortest paths: Application to air traffic management

In this paper, we consider a particular class of network flow problems that seeks a shortest path, if it exists, between a source node s and a destination node d in a connected digraph, such that we arrive at node d at a specified time τ while leaving node s no earlier than a lower-bounding time LB, and where the availability of each network link is time-dependent in the sense that it can be traversed only during specified intervals of time. We refer to this problem as the reverse time-restricted shortest path problem (RTSP), and it arises, for example, in the context of generating flight plans within air traffic management approaches under severe convective weather conditions. We show that this problem is NP-hard in general, but is polynomially solvable under a special regularity condition. A pseudo-polynomial time dynamic programming algorithm is developed to solve Problem RTSP, along with an effective heap implementation strategy. Computational results using real flight generation test cases as well as random simulated problems are presented.     

Distributed optimization and coordination algorithms for dynamic speed optimization of connected and autonomous vehicles in urban street networks

Dynamic speed harmonization has shown great potential to smoothen the flow of traffic and reduce travel time in urban street networks. The existing methods, while providing great insights, are neither scalable nor real-time. This paper develops Distributed Optimization and Coordination Algorithms (DOCA) for dynamic speed optimization of connected and autonomous vehicles in urban street networks to address this gap. DOCA decomposes the nonlinear network-level speed optimization problem into several sub-network-level nonlinear problems thus, it significantly reduces the problem complexity and ensures scalability and real-time runtime constraints. DOCA creates effective coordination in decision making between each two sub-network-level nonlinear problems to push solutions towards optimality and guarantee attaining near-optimal solutions. DOCA is incorporated into a model predictive control approach to allow for additional consensus between sub-network-level problems and reduce the computational complexity further. We applied the proposed solution technique to a real-world network in downtown Springfield, Illinois and observed that it was scalable and real-time while finding solutions that were at most 2.7% different from the optimal solution of the problem. We found significant improvements in network operations and considerable reductions in speed variance as a result of dynamic speed harmonization.     

Effect of providing traffic information estimated by a stochastic network equilibrium model with stochastic demand

To estimate travel times through road networks, in this study, we assume a stochastic demand and formulate a stochastic network equilibrium model whose travel times, flows, and demands are stochastic. This model enables us to examine network reliability under stochastic circumstances and to evaluate the effect of providing traffic information on travel times. For traffic information, we focus on travel time information and propose methods to evaluate the effect of providing that information. To examine the feasibility and validity of the proposed model and methods, we apply them to a simple network and the real road network of Kanazawa, Japan. The results indicate that providing ambulance drivers in Kanazawa with travel time information leads to an average reduction in travel time of approximately three minutes.     

Integrated planning of static and dynamic charging infrastructure for electric vehicles

This paper investigates the optimal deployment of static and dynamic charging infrastructure considering the interdependency between transportation and power networks. Static infrastructure means plug-in charging stations, while the dynamic counterpart refers to electrified roads or charging lanes enabled by charging-while-driving technology. A network equilibrium model is first developed to capture the interactions among battery electric vehicles’ (BEVs) route choices, charging plans, and the prices of electricity. A mixed-integer bi-level program is then formulated to determine the deployment plan of charging infrastructure to minimize the total social cost of the coupled networks. Numerical examples are provided to demonstrate travel and charging plans of BEV drivers and the competitiveness of static and dynamic charging infrastructure. The numerical results on three networks suggest that (1) for individual BEV drivers, the choice between using charging lanes and charging stations is more sensitive to parameters including value of travel time, service fee markup, and battery size, but less sensitive to the charging rates and travel demand; (2) deploying more charging lanes is favorable for transportation networks with sparser topology while more charging stations can be more preferable for those denser networks.     

Ant Colony Routing algorithm for freeway networks

Dynamic traffic routing refers to the process of (re)directing vehicles at junctions in a traffic network according to the evolving traffic conditions. The traffic management center can determine desired routes for drivers in order to optimize the performance of the traffic network by dynamic traffic routing. However, a traffic network may have thousands of links and nodes, resulting in a large-scale and computationally complex non-linear, non-convex optimization problem. To solve this problem, Ant Colony Optimization (ACO) is chosen as the optimization method in this paper because of its powerful optimization heuristic for combinatorial optimization problems. ACO is implemented online to determine the control signal – i.e., the splitting rates at each node. However, using standard ACO for traffic routing is characterized by four main disadvantages: 1. traffic flows for different origins and destinations cannot be distinguished; 2. all ants may converge to one route, causing congestion; 3. constraints cannot be taken into account; and 4. neither can dynamic link costs. These problems are addressed by adopting a novel ACO algorithm with stench pheromone and with colored ants, called Ant Colony Routing (ACR). Using the stench pheromone, the ACR algorithm can distribute the vehicles over the traffic network with less or no traffic congestion, as well as reduce the number of vehicles near some sensitive zones, such as hospitals and schools. With colored ants, the traffic flows for multiple origins and destinations can be represented. The proposed approach is also implemented in a simulation-based case study in the Walcheren area, the Netherlands, illustrating the effectiveness of the approach.     

A decision support framework for handling schedule perturbation

Perturbations of flight schedules may occur everyday. Poor scheduling of flights may result in a substantial loss of profit and decreased levels of service for air carriers. This research aims at developing a framework to help carriers in handling schedule perturbations caused by the breakdown of aircraft. The framework is based on a basic schedule perturbation model constructed as a dynamic network from which several perturbed network models are developed for scheduling following incidents. These network models are formulated as pure network flow problems or network flow problems with side constraints. The former are solved using the network simplex method while the latter are solved using Lagrangian relaxation with subgradient methods. To show how to apply the framework in the real world, a case study focusing on the operations of a major Taiwan air carrier in East Asia is presented.     

Train scheduling simulation that minimises operational conflicts due to service constraints

This paper presents an attempt made to facilitate re‐scheduling of trains to minimize operational delays and accommodate uniform headways for off peak sub urban services subject to resource constraints such as locomotive availability, poor track conditions and stations without siding facilities. The paper describes the computer simulation model designed to optimize train schedules on single‐track rail lines. Using this simulation program it is possible to plan and optimize timetables for railway networks with train runs within short time periods for both single track and double track conditions. The paper describes the capabilities of presenting the results of the simulation runs. These include the time‐distance graph, the network with train movements, dialog boxes with information about selected trains. The programme is capable of changing the starting point, departure time, train destinations and adding or deleting a stop etc. from the user interface. Four objects of array variables are used in the simulation process to keep train and station data. Two object arrays are used for the train movements in up and down directions. The stations' data are stored in the other two object arrays. One of these arrays of stations contains all the stations of the line while the other one contains only the stations with siding facilities. A case study that covers a 61 km long single‐track line with 14 stations is presented to highlight the model capabilities.