Congestion-aware system optimal route choice for shared autonomous vehicles

We study the shared autonomous vehicle (SAV) routing problem while considering congestion. SAVs essentially provide a dial-a-ride service to travelers, but the large number of vehicles involved (tens of thousands of SAVs to replace personal vehicles) results in SAV routing causing significant congestion. We combine the dial-a-ride service constraints with the linear program for system optimal dynamic traffic assignment, resulting in a congestion-aware formulation of the SAV routing problem. Traffic flow is modeled through the link transmission model, an approximate solution to the kinematic wave theory of traffic flow. SAVs interact with travelers at origins and destinations. Due to the large number of vehicles involved, we use a continuous approximation of flow to formulate a linear program. Optimal solutions demonstrate that peak hour demand is likely to have greater waiting and in-vehicle travel times than off-peak demand due to congestion. SAV travel times were only slightly greater than system optimal personal vehicle route choice. In addition, solutions can determine the optimal fleet size to minimize congestion or maximize service.     

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.     

A dynamic evacuation model for pedestrian–vehicle mixed-flow networks

In urban emergency evacuation, a potentially large number of evacuees may depend either on transit or other modes, or need to walk a long distance, to access their passenger cars. In the process of approaching the designated pick-up points or parking areas for evacuation, the massive number of pedestrians may cause tremendous burden to vehicles in the roadway network. Responsible agencies often need to contend with congestion incurred by massive vehicles emanating from parking garages, evacuation buses generated from bus stops, and the conflicts between evacuees and vehicles at intersections. Hence, an effective plan for such evacuation needs to concurrently address both the multi-modal traffic route assignment and the optimization of network signal controls for mixed traffic flows. This paper presents an integrated model to produce the optimal distribution of vehicle and pedestrian flows, and the responsive network signal plan for massive mixed pedestrian–vehicle flows within the evacuation zone. The proposed model features its effectiveness in accounting for multiple types of evacuation vehicles, the interdependent relations between pedestrian and vehicle flows via some conversion locations, and the inevitable conflicts between intersection turning vehicle and pedestrian flows. An illustrating example concerning an evacuation around the M&T stadium area has been presented, and the results indicate the promising properties of our proposed model, especially on reflecting the complex interactions between vehicle and pedestrian flows and the favorable use of high-occupancy vehicles for evacuation operations.     

Coordinated online in-vehicle routing balancing user optimality and system optimality through information perturbation

The inconsistence between system optimality and user optimality represents one of the key difficulties on network traffic congestion control. The advanced connected vehicle systems, enabling smart vehicles to possess/exchange real-time information and conduct portable computation, provide new opportunities to address this challenge. Motivated by this view, this study proposes a coordinated online in-vehicle routing mechanism with intentional information provision perturbation (CRM-IP), which seeks to shape individual vehicles online routing decisions so that user optimality and system optimality are balanced, by exploiting bounded rationality of the users. The proposed CRM-IP is modeled as a pure strategy atomic routing game, and implemented by a sequentially updating distributed algorithm. The mathematical analysis is conducted to quantify the absolute gain of system optimality corresponding to the loss of user optimality resulting from a given level of the information perturbation in the worst case so that the efficiency of the information perturbation can be evaluated. Furthermore, numerical experiments conducted based on City of Sioux Falls network investigate the average effects of the CRM-IP on system optimality and user optimality under various network traffic conditions, comparing to the CRM developed by Du et al. (in press). The results indicate that the improvement of system optimality and the reduction of individual vehicles’ travel time from the CRM is more significant when the network traffic is under an mild congestion state, such as under the levels of service (LOS’s) C, D, and E, rather than under extremely sparse or congested states, such as under LOS’s A and B, or F. Moreover, higher level of information perturbation benefits system optimality more, but the marginal effect decreases after the perturbation reaching certain level, such as $\lambda =0.1$ in this case study. In addition, a portion of vehicles may sacrifice user optimality due to the information perturbation, but the extent of the sacrifice is not significant, even though it increases with the information perturbation level. Hence, a small information perturbation is recommended to achieve an efficient network traffic control through the CRM-IP. Overall, this study proposes the CRM-IP as an efficient routing mechanism, which has a great potential to guide the routing decisions of individual vehicles so that their collective behavior improve network performance in both system optimality and user optimality.     

Design and development of a hybrid ant colony-variable neighbourhood search algorithm for a multi-depot green vehicle routing problem

The traditional distribution planning problem in a supply chain has often been studied mainly with a focus on economic benefits. The growing concern about the effects of anthropogenic pollutions has forced researchers and supply chain practitioners to address the socio-environmental concerns. This research study focuses on incorporating the environmental impact on route design problem. In this work, the aim is to integrate both the objectives, namely economic cost and emission cost reduction for a capacitated multi-depot green vehicle routing problem. The proposed models are a significant contribution to the field of research in green vehicle routing problem at the operational level. The formulated integer linear programming model is solved for a set of small scale instances using LINGO solver. A computationally efficient Ant Colony Optimization (ACO) based meta-heuristic is developed for solving both small scale and large scale problem instances in reasonable amount of time. For solving large scale instances, the performance of the proposed ACO based meta-heuristic is improved by integrating it with a variable neighbourhood search.     

Joint optimization of freight facility location and pavement infrastructure rehabilitation under network traffic equilibrium

Establishment of industry facilities often induces heavy vehicle traffic that exacerbates congestion and pavement deterioration in the neighboring highway network. While planning facility locations and land use developments, it is important to take into account the routing of freight vehicles, the impact on public traffic, as well as the planning of pavement rehabilitation. This paper presents an integrated facility location model that simultaneously considers traffic routing under congestion and pavement rehabilitation under deterioration. The objective is to minimize the total cost due to facility investment, transportation cost including traffic delay, and pavement life-cycle costs. Building upon analytical results on optimal pavement rehabilitation, the problem is formulated into a bi-level mixed-integer non-linear program (MINLP), with facility location, freight shipment routing and pavement rehabilitation decisions in the upper level and traffic equilibrium in the lower level. This problem is then reformulated into an equivalent single-level MINLP based on Karush–Kuhn–Tucker (KKT) conditions and approximation by piece-wise linear functions. Numerical experiments on hypothetical and empirical network examples are conducted to show performance of the proposed algorithm and to draw managerial insights.     

Evaluating the assumption of independent turning probabilities

Several urban traffic models make the convenient assumption that turning probabilities are independent, meaning that the probability of turning right (or left or going straight through) at the downstream intersection is the same for all travelers on that roadway, regardless of their origin or destination. In reality most travelers make turns according to planned routes from origins to destinations. The research reported here identifies and quantifies the deviations that result from this assumption of independent turning probabilities.An analysis of this type requires a set of reasonably realistic “original” route flows, which were obtained by a static user-equilibrium traffic assignment and an entropy maximization condition for most likely route flows. These flows are compared with those route flows resulting from the Assumption of Independent Turning Probabilities (ITP). A small subnetwork of 3 km by 5 km in Tucson, Arizona, was chosen as a case study. An overall “typical ratio” of 2.2 between original route flows and ITP route flows was obtained. Aggregating route flows to origin–destination flows led to an overall “typical ratio” of 1.7. Such deviations are particularly high for routes that go back-and-forth, reaching a ratio of more than 3 in certain time periods. Substantial deviations for origins and destinations that are on the same border of the subnetwork are also observed in the analyses. In addition, under the ITP assumption, morning rush hour traffic peaking is the same in all directions, while in the original flows some directions do not exhibit a peak in the morning rush hour period. Overall, the conclusion of the paper is that the assumption of independent turning probabilities leads to substantial deviations both at the route level and at the origin–destination level, even for such a small network of the case study. These deviations are particularly detrimental when a network is being modeled and studied for route-based measures of effectiveness such as the number and types of routes passing a point – for monitoring specified vehicles and/or managing detouring strategies.     

The impacts of connected vehicle technology on network-wide traffic operation and fuel consumption under various incident scenarios

ABSTRACT

Incidents are a major source of traffic congestion and can lead to long and unpredictable delays, deteriorating traffic operations and adverse environmental impacts. The emergence of connected vehicles and communication technologies has enabled travelers to use real-time traffic information. The ability to exchange traffic information among vehicles has tremendous potential impacts on network performance especially in the case of non-recurrent congestion. To this end, this paper utilizes a microscopic simulation model of traffic in El Paso, Texas to investigate the impacts of incidents on traffic operation and fuel consumption at different market penetration rates (MPR) of connected vehicles. Several scenarios are implemented and tested to determine the impacts of incidents on network performance in an urban area. The scenarios are defined by changing the duration of incidents and the number of lanes closed. This study also shows how communication technology affects network performance in response to congestion. The results of the study demonstrate the potential effectiveness of connected vehicle technology in improving network performance. For an incident with a duration of 900?s and MPR of 80%, total fuel consumption and total travel time decreased by approximately 20%; 26% was observed in network-wide travel time and fuel consumption at 100% MPR.     

An integrated modelling approach for the bicriterion vehicle routing and scheduling problem with environmental considerations

The consideration of pollution in routing decisions gives rise to a new routing framework where measures of the environmental implications are traded off with business performance measures. To address this type of routing decisions, we formulate and solve a bi-objective time, load and path-dependent vehicle routing problem with time windows (BTL-VRPTW). The proposed formulation incorporates a travel time model representing realistically time varying traffic conditions. A key feature of the problem under consideration is the need to address simultaneously routing and path finding decisions. To cope with the computational burden arising from this property of the problem we propose a network reduction approach. Computational tests on the effect of the network reduction approach on determining non-dominated solutions are reported. A generic solution framework is proposed to address the BTL-VRPTW. The proposed framework combines any technique that creates capacity-feasible routes with a routing and scheduling method that aims to convert the identified routes to problem solutions. We show that transforming a set of routes to BTL-VRPTW solutions is equivalent to solving a bi-objective time dependent shortest path problem on a specially structured graph. We propose a backward label setting technique to solve the emerging problem that takes advantage of the special structure of the graph. The proposed generic solution framework is implemented by integrating the routing and scheduling method into an Ant Colony System algorithm. The accuracy of the proposed algorithm was assessed on the basis of its capability to determine minimum travel time and fuel consumption solutions. Although the computational results are encouraging, there is ample room for future research in algorithmic advances on addressing the proposed problem.     

Transit stop inspection and maintenance scheduling: A GPU accelerated metaheuristics approach

Bus stops are integral elements of a transit system and as such, their efficient inspection and maintenance is required, for proper and attractive transit operations. Nevertheless, spatial dispersion and the extensive number of bus stops, even for mid-size transit systems, complicates scheduling of inspection and maintenance tasks. In this context, the problem of scheduling transit stop inspection and maintenance activities (TSIMP) by a two-stage optimization approach, is formulated and discussed. In particular, the first stage involves districting of the bus stop locations into areas of responsibility for different inspection and maintenance crews (IMCs), while in the second stage, determination of the sequence of bus stops to be visited by an IMC is modelled as a vehicle routing problem. Given the complexity of proposed optimization models, advanced versions of different metaheuristic algorithms (Harmony Search and Ant Colony Optimization) are exploited and assessed as possible options for solving these models. Furthermore, two variants of ACO are implemented herein; one implemented into a CPU parallel computing environment along with an accelerated one by means of general-purpose graphics processing unit (GPGPU) computing. The model and algorithms are applied to the Athens (Greece) bus system, whose extensive number of transit stops (over 7500) offers a real-world test bed for assessing the potential of the proposed modelling approach and solution algorithms. As it was shown for the test example examined, both algorithms managed to achieve optimized solutions for the problem at hand while there were fund robust with respect to their algorithmic parameters. Furthermore, the use of graphics processing units (GPU) managed to reduce of computational time required.     

Estimation of origin-destination matrices from link traffic counts on congested networks

Conventional methods for estimating origin-destination (O-D) trip matrices from link traffic counts assume that route choice proportions are given constants. In a network with realistic congestion levels, this assumption does not hold. This paper shows how existing methods such as the generalized least squares technique can be integrated with an equilibrium traffic assignment in the form of a convex bilevel optimization problem. The presence of measurement errors and time variations in the observed link flows are explicitly considered. The feasibility of the model is always guaranteed without a requirement for estimating consistent link flows from counts. A solution algorithm is provided and numerical simulation experiments are implemented in investigating the model's properties. Some related problems concerning O-D matrix estimation are also discussed.     

Surrogate‐based optimization of cordon toll levels in congested traffic networks

The benefit, in terms of social surplus, from introducing congestion charging schemes in urban networks is depending on the design of the charging scheme. The literature on optimal design of congestion pricing schemes is to a large extent based on static traffic assignment, which is known for its deficiency in correctly predict travel times in networks with severe congestion. Dynamic traffic assignment can better predict travel times in a road network, but are more computational expensive. Thus, previously developed methods for the static case cannot be applied straightforward. Surrogate‐based optimization is commonly used for optimization problems with expensive‐to‐evaluate objective functions. In this paper, we evaluate the performance of a surrogate‐based optimization method, when the number of pricing schemes, which we can afford to evaluate (because of the computational time), are limited to between 20 and 40. A static traffic assignment model of Stockholm is used for evaluating a large number of different configurations of the surrogate‐based optimization method. Final evaluation is performed with the dynamic traffic assignment tool VisumDUE, coupled with the demand model Regent, for a Stockholm network including 1240 demand zones and 17 000 links. Our results show that the surrogate‐based optimization method can indeed be used for designing a congestion charging scheme, which return a high social surplus. Copyright © 2016 John Wiley & Sons, Ltd.     

An optimization method for sustainable traffic control in urban areas

The optimization of traffic signalization in urban areas is formulated as a problem of finding the cycle length, the green times and the offset of traffic signals that minimize an objective function of performance indices. Typical approaches to this optimization problem include the maximization of traffic throughput or the minimization of vehicles’ delays, number of stops, fuel consumption, etc. Dynamic Traffic Assignment (DTA) models are widely used for online and offline applications for efficient deployment of traffic control strategies and the evaluation of traffic management schemes and policies. We propose an optimization method for combining dynamic traffic assignment and network control by minimizing the risk of potential loss induced to travelers by exceeding their budgeted travel time as a result of deployed traffic signal settings, using the Conditional Value-at-Risk model. The proposed methodology can be easily implemented by researchers or practitioners to evaluate their alternative strategies and aid them to choose the alternative with less potential risk. The traffic signal optimization procedure is implemented in TRANSYT-7F and the dynamic propagation and route choice of vehicles is simulated with a mesoscopic dynamic traffic assignment tool (DTALite) with fixed temporal demand and network characteristics. The proposed approach is applied to a reference test network used by many researchers for verification purposes. Numerical experiments provide evidence of the advantages of this optimization method with respect to conventional optimization techniques. The overall benefit to the performance of the network is evaluated with a Conditional Value-at-Risk Analysis where the optimal solution is the one presenting the least risk for ‘guaranteed’ total travel times.     

A network wide simulation strategy of alternative fuel vehicles

This paper presents an integrated simulator “CUIntegration” to evaluate routing strategies based on energy and/or traffic measures of effectiveness for any Alternative Fuel Vehicles (AFVs). The CUIntegration can integrate vehicle models of conventional vehicles as well as AFVs developed with MATLAB-Simulink, and a roadway network model developed with traffic microscopic simulation software VISSIM. The architecture of this simulator is discussed in this paper along with a case study in which the simulator was utilized for evaluating a routing strategy for Plug-in Hybrid Electric Vehicles (PHEVs) and Electric Vehicles (EVs). The authors developed a route optimization algorithm to guide an AFV based on that AFV driver’s choice, which included; finding a route with minimum (1) travel time, (2) energy consumption or (3) a combination of both. The Application Programming Interface (API) was developed using Visual Basic to simulate the vehicle models/algorithms developed in MATLAB and direct vehicles in a roadway network model developed in VISSIM accordingly. The case study included a section of Interstate 83 in Baltimore, Maryland, which was modeled, calibrated and validated. The authors considered a worst-case scenario with an incident on the main route blocking all lanes for 30 min. The PHEVs and EVs were represented by integrating the MATLAB-Simulink vehicle models with the traffic simulator. The CUIntegration successfully combined vehicle models with a roadway traffic network model to support a routing strategy for PHEVs and EVs. Simulation experiments with CUIntegration revealed that routing of PHEVs resulted in cost savings of about 29% when optimized for the energy consumption, and for the same optimization objective, routing of EVs resulted in about 64% savings.     

Coordinated platooning with multiple speeds

In a platoon, vehicles travel one after another with small intervehicle distances; trailing vehicles in a platoon save fuel because they experience less aerodynamic drag. This work presents a coordinated platooning model with multiple speed options that integrates scheduling, routing, speed selection, and platoon formation/dissolution in a mixed-integer linear program that minimizes the total fuel consumed by a set of vehicles while traveling between their respective origins and destinations. The performance of this model is numerically tested on a grid network and the Chicago-area highway network. We find that the fuel-savings factor of a multivehicle system significantly depends on the time each vehicle is allowed to stay in the network; this time affects vehicles’ available speed choices, possible routes, and the amount of time for coordinating platoon formation. For problem instances with a large number of vehicles, we propose and test a heuristic decomposed approach that applies a clustering algorithm to partition the set of vehicles and then routes each group separately. When the set of vehicles is large and the available computational time is small, the decomposed approach finds significantly better solutions than does the full model.     

A model‐based demand‐balancing control for dynamically divided multiple urban subnetworks

Traffic control is an effective and efficient method for the problem of traffic congestion. It is necessary to design a high‐level controller to regulate the network traffic demands, because traffic congestion is not only caused by the improper management of the traffic network but also to a great extent caused by excessive network traffic demands. Therefore, we design a demand‐balance model predictive controller based on the macroscopic fundamental diagram‐based multi‐subnetwork model, which can optimize the network traffic mobility and the network traffic throughput by regulating the input traffic flows of the subnetworks. Because the transferring traffic flows among subnetworks are indirectly controlled and coordinated by the demand‐balance model predictive controller, the subnetwork division can variate dynamically according to real traffic states, and a global optimality can be achieved for the entire traffic network. The simulation results show the effectiveness of the proposed controller in improving the network traffic throughput. Copyright © 2016 John Wiley & Sons, Ltd.     

Solving the User Optimum Privately Owned Automated Vehicles Assignment Problem (UO-POAVAP): A model to explore the impacts of self-driving vehicles on urban mobility

Interest in vehicle automation has been growing in recent years, especially with the very visible Google car project. Although full automation is not yet a reality there has been significant research on the impacts of self-driving vehicles on traffic flows, mainly on interurban roads. However, little attention has been given to what could happen to urban mobility when all vehicles are automated. In this paper we propose a new method to study how replacing privately owned conventional vehicles with automated ones affects traffic delays and parking demand in a city. The model solves what we designate as the User Optimum Privately Owned Automated Vehicles Assignment Problem (UO-POAVAP), which dynamically assigns family trips in their automated vehicles in an urban road network from a user equilibrium perspective where, in equilibrium, households with similar trips should have similar transport costs. Automation allows a vehicle to travel without passengers to satisfy multiple household trips and, if needed, to park itself in any of the network nodes to benefit from lower parking charges. Nonetheless, the empty trips can also represent added congestion in the network. The model was applied to a case study based on the city of Delft, the Netherlands. Several experiments were done, comparing scenarios where parking policies and value of travel time (VTT) are changed. The model shows good equilibrium convergence with a small difference between the general costs of traveling for similar families. We were able to conclude that vehicle automation reduces generalized transport costs, satisfies more trips by car and is associated with increased traffic congestion because empty vehicles have to be relocated. It is possible for a city to charge for all street parking and create free central parking lots that will keep total transport costs the same, or reduce them. However, this will add to congestion as traffic competes to access those central nodes. In a scenario where a lower VTT is experienced by the travelers, because of the added comfort of vehicle automation, the car mode share increases. Nevertheless this may help to reduce traffic congestion because some vehicles will reroute to satisfy trips which previously were not cost efficient to be done by car. Placing the free parking in the outskirts is less attractive due to the extra kilometers but with a lower VTT the same private vehicle demand would be attended with the advantage of freeing space in the city center.     

Modeling and optimization of multimodal urban networks with limited parking and dynamic pricing

Cruising-for-parking constraints mobility in urban networks. Car-users may have to cruise for on-street parking before reaching their destinations. The accessibility and the cost of parking significantly influence people's travel behavior (such as mode choice, or parking facility choice between on-street and garage). The cruising flow causes delays eventually to everyone, even users with destinations outside limited parking areas. It is therefore important to understand the impact of parking limitation on mobility, and to identify efficient parking policies for travel cost reduction. Most existing studies on parking fall short in reproducing the dynamic spatiotemporal features of traffic congestion in general, lack the treatment of dynamics of the cruising-for-parking phenomenon, or require detailed input data that are typically costly and difficult to collect. In this paper, we propose an aggregated and dynamic approach for modeling multimodal traffic with the treatment on parking, and utilize the approach to design dynamic parking pricing strategies. The proposed approach is based on the Macroscopic Fundamental Diagram (MFD), which can capture congestion dynamics at network-level for single-mode and bi-modal (car and bus) systems. A parsimonious parking model is integrated into the MFD-based multimodal modeling framework, where the dynamics of vehicular and passenger flows are considered with a change in the aggregated behavior (e.g. mode choice and parking facility choice) caused by cruising and congestion. Pricing strategies are developed with the objective of reducing congestion, as well as lowering the total travel cost of all users. A case study is carried out for a bi-modal city network with a congested downtown region. An elegant feedback dynamic parking pricing strategy can effectively reduce travel delay of cruising and the generic congestion. Remarkably, such strategy, which is applicable in real-time management with limited available data, is fairly as efficient as a dynamic pricing scheme obtained from system optimum conditions and a global optimization with full information about the future states of the system. Stackelberg equilibrium is also investigated in a competitive behavior between different parking facility operators. Policy indications on on-street storage capacity management and pricing are provided.     

A framework to evaluate policy options for supporting electric vehicles in urban freight transport

Electric vehicles (EVs) are considered as a feasible alternative to traditional vehicles. Few studies have addressed the impacts of policies supporting EVs in urban freight transport. To cast light on this topic, we established a framework combining an optimization model with economic analysis to determine the optimal behavior of an individual delivery service provider company and social impacts (e.g., externalities and welfare) in response to policies designed to support EVs, such as purchase subsidy, limited access (zone fee) to congestion/low-emission zones with exemptions for EVs, and vehicle taxes with exemptions for EVs. Numerical experiments showed that the zone fee can increase the company’s total logistics costs but improve the social welfare. It greatly reduced the external cost inside the congestion/low-emission zone with a high population, dense pollution, and heavy traffic. The vehicle taxes and subsidy were found to have the same influence on the company and society, although they have different effects with low tax/subsidy rates because their different effects on vehicle routing plans. Finally, we performed a sensitivity analysis. Local factors at the company and city levels (e.g., types of vehicle and transport network) are also important to designing efficient policies for urban logistics that support EVs.     

Congestion avoidance in city traffic

The number of vehicles on the road (worldwide) is constantly increasing, causing traffic jams and congestion especially in city traffic. Anticipatory vehicle routing techniques have thus far been applied to fairly small networked traffic scenarios and uniform traffic. We note here a number of limitations of these techniques and present a routing strategy on the assumption of a city map that has a large number of nodes and connectivity and where the vehicles possess highly varying speed capabilities. A scenario of operation with such characteristics has not previously been sufficiently studied in the literature. Frequent short‐term planning is preferred as compared with infrequent planning of the complete map. Experimental results show an efficiency boost when single‐lane overtaking is allowed, traffic signals are accounted for and every vehicle prefers to avoid high traffic density on a road by taking an alternative route. Comparisons with optimistic routing, pessimistic routing and time message channel routing are given. Copyright © 2014 John Wiley & Sons, Ltd.