A graphical approach to identify sensor locations for link flow inference

Information of link flows in a traffic network becomes increasingly critical in contemporary transportation practice and researches. The network sensor installation is carried out to supply such information. In this paper, we present a graphical approach to determine the smallest subset of links in a traffic network for counting sensor installation, so as to infer the flows on all remaining links. The elegant assumption-free character of the problem introduced by Hu, Peeta and Chu is still kept in this approach. This study points out the topological tree feature of solutions that makes it possible for traffic management agencies to easily and flexibly select links for sensor installation in practice. Addressing from the same graphical perspective, we provide solutions to four other important problems about sensor locations. The preceding two problems are, in traffic networks that already have sensors installed on some links, to identify the subset of links on which link flows can be inferred from sensor measurements and to determine the smallest subset of links on which counting sensors also need to be installed so as to infer link flows on all remaining non-equipped links. The third is to identify the optimal locations for a given number of sensors so as to infer flows on as many links as possible by gradually enlarging the number of links included in circuits. The last one is to determine the smallest subset of links on which to install sensors, in such a way that it becomes possible at the same time to satisfy prior requirements and infer the flows on all remaining links, through building a minimum spanning tree. These methods can be applied to all kinds of long-term planning and link-based applications in traffic networks.     

Designing personal rapid transit (PRT) networks

This paper presents a heuristic method for designing a PRT network. Because the PRT system operating characteristics and performance measures differ widely from those of conventional transit technologies, an algorithm for the PRT network design problem (NDP) is derived by using concepts from some current NDP algorithms. We minimize the sum of passenger travel time cost, construction cost, vehicle cost and operational costs, subject to an available budget of guideway, a maximum number of vehicles and given link capacities. Starting with a well-connected initial network, the algorithm eliminates and adds links iteratively as it searches for a near-optimal solution. If this solution satisfies the budget constraint, it is considered to be acceptable. Otherwise, additional links are deleted until a feasible near-optimal solution is obtained. The link elimination phase of the algorithm only considers half of the links at a time which greatly decreases computing time. None of the links in an acceptable solution will be overloaded.     

Consistent link flow estimation from counts

Partly because of counting errors and partly because counts may be carried out on different days, traffic counts on links of a network are unlikely to satisfy the flow conservation constraint “flow IN = flow out” at every node of the network. Van Zuylen and Willumsen (1980) have described a method of eliminating inconsistencies in traffic counts when a single count is available for each link in the network. In this paper, the method is extended to the case when more than one count is available on some links of the network. In addition, an algorithm is described for application of the method.     

Guaranteed prediction and estimation of the state of a road network

The paper presents an algorithm for the prediction and estimation of the state of a road network comprising freeways and arterials, described by a Cell Transmission Model (CTM). CTM divides the network into a collection of links. Each link is characterized by its fundamental diagram, which relates link speed to link density. The state of the network is the vector of link densities. The state is observed through measurements of speed and flow on some links. Demand is specified by the volume of vehicles entering the network at some links, and by split ratios according to which vehicles are routed through the network. There is model uncertainty: the parameters of the fundamental diagram are uncertain. There is uncertainty in the demand around the nominal forecast. Lastly, the measurements are uncertain. The uncertainty in each model parameter, demand, and measurement is specified by an interval. Given measurements over a time interval [0, t] and a horizon τ ? 0, the algorithm computes a set of states with the guarantee that the actual state at time (t + τ) will lie in this set, consistent with the given measurements. In standard terminology the algorithm is a state prediction or an estimate accordingly as τ > 0 or =0. The flow exiting a link may be controlled by an open- or closed-loop controller such as a signal or ramp meter. An open-loop controller does not change the algorithm, indeed it may make the system more predictable by tightening density bounds downstream of the controller. In the feedback case, the value of the control depends on the estimated state bounds, and the algorithm is extended to compute the range of possible closed-loop control values. The algorithm is used in a proposed design of a decision support system for the I-80 integrated corridor.     

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.     

Identification of vehicle sensor locations for link-based network traffic applications

Information on link flows in a vehicular traffic network is critical for developing long-term planning and/or short-term operational management strategies. In the literature, most studies to develop such strategies typically assume the availability of measured link traffic information on all network links, either through manual survey or advanced traffic sensor technologies. In practical applications, the assumption of installed sensors on all links is generally unrealistic due to budgetary constraints. It motivates the need to estimate flows on all links of a traffic network based on the measurement of link flows on a subset of links with suitably equipped sensors. This study, addressed from a budgetary planning perspective, seeks to identify the smallest subset of links in a network on which to locate sensors that enables the accurate estimation of traffic flows on all links of the network under steady-state conditions. Here, steady-state implies that the path flows are static. A “basis link” method is proposed to determine the locations of vehicle sensors, by using the link-path incidence matrix to express the network structure and then identifying its “basis” in a matrix algebra context. The theoretical background and mathematical properties of the proposed method are elaborated. The approach is useful for deploying long-term planning and link-based applications in traffic networks.     

Network design: selection and design of links and facility location

In this paper we introduce new network design problems. A network of potential links is given. Each link can be either constructed or not at a given cost. Also, each constructed link can be constructed either as a one-way or two-way link. The objective is to minimize the total construction and transportation costs. Two different transportation costs are considered: (i) traffic is generated between any pair of nodes and the transportation cost is the total cost for the users and (ii) demand for service is generated at each node and a facility is to be located on a node to satisfy the demand. The transportation cost in this case is the total cost for a round trip from the facility to each node and back. We will consider two options in regard to the links between nodes. They can either be two-way only, or mixed, with both two-way and one-way (in either direction) allowed. When these options are combined with the two objective functions, four basic problems are created. These problems are solved by a descent algorithm, simulated annealing, tabu search, and a genetic algorithm. Extensive computational results are presented.     

Application of multiple criteria decision making for network improvement

In this paper we propose application of multiple criteria decision making to problems of a metropolitan network improvement plan. Initially, a bilevel multiple objective network design model is considered in two objectives which are minimal government budget and minimal total travel time of road users. We seek feasible improvement alternatives among those bottleneck links in an existing road network structure and travel demand. We present an effective heuristic algorithm to obtain noninferior solutions; then ELECTRE III multiple criteria decision making and group decision making are used to evaluate and to select a compromise solution among those noninferior solutions. From the design phase in multiple criteria decision making, multiple objective mathematical programming is used to formulate a continuous network design model. However, from the phase of evaluation, multiple criteria decision making to solve the discrete network design problem. The network of metropolitan Taipei is taken as an example to illustrate the operation of this model.     

Inferring origin–destination trip matrices from aggregate volumes on groups of links: a case study using volumes inferred from mobile phone data

The origin–destination matrix is an important source of information describing transport demand in a region. Most commonly used methods for matrix estimation use link volumes collected on a subset of links in order to update an existing matrix. Traditional volume data collection methods have significant shortcomings because of the high costs involved and the fact that detectors only provide status information at specified locations in the network. Better matrix estimates can be obtained when information is available about the overall distribution of traffic through time and space. Other existing technologies are not used in matrix estimation methods because they collect volume data aggregated on groups of links, rather than on single links. That is the case of mobile systems. Mobile phones sometimes cannot provide location accuracy for estimating flows on single links but do so on groups of links; in contrast, data can be acquired over a wider coverage without additional costs. This paper presents a methodology adapted to the concept of volume aggregated on groups of links in order to use any available volume data source in traditional matrix estimation methodologies. To calculate volume data, we have used a model that has had promising results in transforming phone call data into traffic movement data. The proposed methodology using vehicle volumes obtained by such a model is applied over a large real network as a case study. The experimental results reveal the efficiency and consistency of the solution proposed, making the alternative attractive for practical applications. Copyright © 2011 John Wiley & Sons, Ltd.     

Shortest route algorithm with movement prohibitions

This paper presents an algorithm with movement prohibitions which eliminates some problems encountered in network representation used for traffic assignment models, and further allows the representation of the network to be simplified. The paper first presents an appraisal of some proposed methods and reviews the basic concept of existing shortest-route algorithms. The problem of obtaining shortest routes in networks with movement prohibitions is formulated and an algorithm presented. The computational procedure is illustrated by means of a numerical example. The computational efficiency of the algorithm is tested and the test results show that the algorithm is very efficient.     

Network sensor health problem

Many existing studies on the sensor health problem determine an individual sensor’s health status based on the statistical characteristics of collected data by the sensor. In this research, we study the sensor health problem at the network level, which is referred to as the network sensor health problem. First, based on the conservation principle of daily flows in a network, we separate all links into base links and non-base links, such that the flows on the latter can be calculated from those on the former. In reality, the network flow conservation principle can be violated due to the existence of unhealthy sensors. Then we define the least inconsistent base set of links as those that minimize the sum of squares of the differences between observed and calculated flows on non-base links. But such least inconsistent base sets may not be unique in a general road network. Finally we define the health index of an individual sensor as the frequency that it appears in all of the least inconsistent base sets. Intuitively, a lower health index suggests that the corresponding sensor is more likely to be unhealthy. We present the brute force method to find all least inconsistent base sets and calculate the health indices. We also propose a greedy search algorithm to calculate the approximate health indices more efficiently. We solve the network sensor health problem for a real-world example with 16 nodes and 30 links, among which 18 links are monitored with loop detectors. Using daily traffic count data from the Caltrans Performance Measurement System (PeMS) database, we use both the brute-force and greedy search methods to calculate the health indices for all the sensors. We find that all the four sensors flagged as unhealthy (high value) by PeMS have the lowest health indices. This confirms that a sensor with a lower health index is more likely to be unhealthy. Therefore, we can use such health indices to determine the relative reliability of different sensors’ data and prioritize the maintenance of sensors.     

Formulating and solving the network design problem by decomposition

The optimal transportation network design problem is formulated as a convex nonlinear programming problem and a solution method based on standard traffic assignment algorithms is presented. The technique can deal with network improvements which introduce new links, which increase the capacity of existing links, or which decrease the free-flow (uncongested) travel time on existing links (with or without simultaneously increasing link capacity). Preliminary computational experience with the method demonstrates that it is capable of solving very large problems with reasonable amounts of computer time.     

Heuristic ranking and selection procedures for network design problems

Two heuristic approaches to solving discrete non-linear network design problems and other subset selection problems are described and tested. These heuristics operate similarly to other add, delete and interchange heuristics that have been applied to network design problems. However, the selection criterion adopted here is the ratio of objective function change per unit of resource cost, which other authors have described as an effective gradient measure for zero-one integer programming problems. Optimal branch-and-bound algorithms previously developed and tested are reviewed, and those results serve as benchmarks with which to compare these heuristics described in this paper. The first heuristic ranks and deletes alternative network modifications from an entire set of candidate projects, such as new links or link improvements, until the subset of remaining projects fits within the constraint space. This method was found to achieve optimal or near-optimal solutions to each of the test cases, even when the number of candidate projects deleted in each iteration was increased from one to many. The quality of those results led us to investigate a constrained random sampling procedure in which candidate projects are ranked with regard to randomly generated networks, and a solution is then chosen on the basis of these rankings. This second approach was found to achieve solutions that were almost as good as those obtained with the rank and delete heuristic.     

Critical Review of Time-Dependent Shortest Path Algorithms: A Multimodal Trip Planner Perspective

Abstract

A multimodal trip planner that produces optimal journeys involving both public transport and private vehicle legs has to solve a number of shortest path problems, both on the road network and the public transport network. The algorithms that are used to solve these shortest path problems have been researched since the late 1950s. However, in order to provide accurate journey plans that can be trusted by the user, the variability of travel times caused by traffic congestion must be taken into consideration. This requires the use of more sophisticated time-dependent shortest path algorithms, which have only been researched in depth over the last two decades, from the mid-1990s. This paper will review and compare nine algorithms that have been proposed in the literature, discussing the advantages and disadvantages of each algorithm on the basis of five important criteria that must be considered when choosing one or more of them to implement in a multimodal trip planner.     

Integrated modeling of urban hierarchy and transportation network planning

A major problem addressed during the preparation of spatial development plans relates to the accessibility to facilities where services of general interest such as education, health care, public safety, and justice are offered to the population. In this context, planners typically aim at redefining the level of hierarchy to assign to the urban centers of the region under study (with a class of facilities associated with each level of hierarchy) and redesigning the region’s transportation network. Traditionally, these two subjects – urban hierarchy and transportation network planning – have been addressed separately in the scientific literature. This paper presents an optimization model that simultaneously determines which urban centers and which network links should be promoted to a new level of hierarchy so as to maximize accessibility to all classes of facilities. The possible usefulness of the model for solving real-world problems of integrated urban hierarchy and transportation network planning is illustrated through an application to the Centro Region of Portugal.     

Deregulating direct flights across the Taiwan Strait: The transformation of Eastern Asian air transport market and network

Over the past decades Hong Kong has been successfully playing a role as a gateway to China. Since 1988, it has also been the most important hub between Taiwan and China. Over 5 million passengers travelled between Taipei and Hong Kong in 1997, making the link the busiest in the world's international air links and contributing one-sixth of the passengers to Hong Kong airport, which before 1997 had the most international passengers in Asia. In the foreseeable future Taiwan will possibly start some direct services to China; the air link between Hong Kong and Taipei will then compete with many links across Taiwan Strait. These changes may cause the transformation of the market and network structure in eastern Asia. Niches of specific airlines and airports will disappear. This paper examines the issues of possible changes in eastern Asian air transport market: the current market environment, the problems for direct flights across Taiwan Strait, the possible links between Taiwan and China, the future role of Hong Kong, and the market structure in the future.     

Implementation of cordon pricing on urban network with practical approach

The road pricing is regarded as a transport policy to realize the efficient use of urban network. The network analysis with variable demand has been often applied to describe the network level of congestion pricing on the urban network. In the study, the cordon pricing system is analyzed to implement in the urban area with practical approach. It is assumed that the congestion tolls are collected in crossing the cordon lines on the network. Therefore, the scale of cordon zones and the values of congestion tolls would be determined simultaneously to produce the maximum social net benefit. The combinatorial optimization with unit price is formulated. The genetic algorithm (GA) is applied as a practical method to provide the solutions for the combinatorial optimization problem. As the pattern of cordon pricing is determined, the performance of system is estimated to confirm the applicability. It is concluded that the cordon pricing can be applied with the practical approach.     

Effects of queue spillover in networks considering simultaneous departure time and route choices

This paper explores the effects of queue spillover in transportation networks, in the context of dynamic traffic assignment. A model of spatial queue is defined to characterize dynamic traffic flow and queuing formation in network links. Network users simultaneously choose departure time and travel route to minimize the travel cost including journey time and unpunctuality penalty. Using some necessary conditions of the dynamic user equilibrium, dynamic network flows are obtained exactly on some networks with typical structure. Various effects of queue spillover are discussed based on the results of these networks, and some new paradoxes of link capacity expansion have been found as a result of such effects. Analytical and exact results in these typical networks show that ignoring queuing length may generate biased solutions, and the link storage capacity is a very important factor concerning the performance of networks.     

Train design and routing optimization for evaluating criticality of freight railroad infrastructures

Freight transportation by railroads is an integral part of the U.S. economy. Identifying critical rail infrastructures can help stakeholders prioritize protection initiatives or add necessary redundancy to maximize rail network resiliency. The criticality of an infrastructure element, link or yard, is based on the increased cost (delay) incurred when that element is disrupted. An event of disruption can cause heavy congestion so that the capacity at links and yards should be considered when freight is re-routed. This paper proposes an optimization model for making-up and routing of trains in a disruptive situation to minimize the system-wide total cost, including classification time at yards and travel time along links. Train design optimization seeks to determine the optimal number of trains, their routes, and associated blocks, subject to various capacity and operational constraints at rail links and yards. An iterative heuristic algorithm is proposed to attack the computational burden for real-world networks. The solution algorithm considers the impact of volume on travel time in a congested or near-congested network. The proposed heuristics provide quality solutions with high speed, demonstrated by numerical experiments for small instances. A case study is conducted for the network of a major U.S. Class-I railroad based on publicly available data. The paper provides maps showing the criticality of infrastructure in the study area from the viewpoint of strategic planning.     

A Trip Reconstruction Tool for GPS-based Personal Travel Surveys

ABSTRACT

This article reports on the development of a trip reconstruction software tool for use in GPS-based personal travel surveys. Specifically, the tool enables the automatic processing of GPS traces of individual survey respondents in order to identify the road links traveled and modes used by each respondent for individual trips. Identifying the links is based on a conventional GIS-based map-matching algorithm and identifying the modes is a rule-based algorithm using attributes of four modes (walk, bicycle, bus and passenger-car). The tool was evaluated using GPS travel data collected for the study and a multi-modal transportation network model of downtown Toronto. The results show that the tool correctly detected about 79% of all links traveled and 92% of all trip modes.