Feature | Zhibin Chen and Yafeng Yin | August 15, 2017

Web Exclusive: In the zone

A way to adapt to and promote the deployment of autonomous vehicle technology

Mcity at University of Michigan

Autonomous vehicles (AVs) are expected to offer extraordinary improvements to both the safety and efficiency of existing roadways and mobility systems. Although in all likelihood it will be several years before a wide-scale adoption of AV technology reaches all aspects of our transportation system, recent developments suggest that new advancements could scale that timeframe down—perhaps significantly. Since 2009, when Google started testing self-driving technology in California, Google’s AVs have driven more than 3 million miles (as of May of this year). The company’s fully self-driving car, named “Firefly,” started the world's first fully driverless ride on public roads in 2015. Due to the gradual maturity of Google’s AV technology, the National Highway Traffic Safety Administration (NHTSA) agreed to consider the Google self-driving computer system as the ‘‘driver” of the vehicle in 2016. More recently, in September 2016, Uber launched a fleet of 14 AVs to pick up passengers in the city of Pittsburgh. In the same month, nuTonomy, a software company, launched the world’s first self-driving taxi in Singapore. Many car manufacturers, such as Volvo, BMW and Audi, are currently designing and testing prototype AVs. In the U.S., 18 states—Alabama, Arkansas, California, Colorado, Florida, Georgia, Louisiana, Michigan, New York, Nevada, North Dakota, Pennsylvania, South Carolina, Tennessee, Texas, Utah, Virginia and Vermont—as well as the District of Columbia have legalized AVs for testing on public roads.

 

Infrastructure adaptation planning for AVs

While thus far the development of AV technology appears to be primarily driven by the private sector, it is critical for government agencies to change various policies and practices to adapt to and further promote the deployment of the technology. Among them, infrastructure adaptation planning for AVs can be considered an important means.

 

Before manual driving can be completely phased out, the traffic stream on a road network will still be heterogeneous, with both conventional vehicles (CVs) and AVs, and will inevitably exist for a long time. To facilitate the formulation of AV platoons to improve throughput and hopefully improve the performance of the whole network, government agencies can initially identify critical locations to implement various AV mobility applications. For example, a “bottleneck manager” can be implemented at a recurrent freeway bottleneck. When approaching, AVs send requests via vehicle-to-infrastructure wireless communications to the “bottleneck manager,” which will prioritize the requests and optimize their trajectories to ensure timely passage while preventing the bottleneck from being activated. To leverage the growing adoption of AVs, government agencies may later dedicate certain traffic lanes, highway segments or even areas of networks exclusively to AVs to facilitate the formulation of vehicle platoons to further improve throughput. Subsequently implemented are innovative control strategies that aim to achieve system optimum in those areas. The dedicated AV areas will expand gradually as the level of the market penetration of AVs increases, and will eventually support a fully connected and automated mobility in the whole system. Similar ideas have been suggested in the literature. For example, as current managed lanes are equipped with advanced communication and data transfer systems, researchers have suggested converting some of them into dedicated lanes for AVs to reduce congestion and improve the safety of passengers. Further, the presence of AV areas is pointed out to be able to promote the AV adoption and maximize benefits brought by AVs as rapidly as possible.

 

Figure 1. An example of an AV zone.

 

AV zone design

This article deals with a particular issue in the above infrastructure adaptation planning process and aims to present a mathematical framework for the optimal design of AV zones in a general road network. With only AVs being allowed to enter, an AV zone consists of a set of links, i.e. roads, which are tailored to AVs (see Figure 1). Note that in order not to compromise CVs’ accessibility to various locations, the nodes within the zone in particular, the AV zone can be designed to consist of only urban expressways or arterial roads, excluding minor streets. Within the zone, it is assumed that AVs cannot choose their routes. Instead, they report their exits and are then guided by a central controller to achieve the system optimum flow distribution, which minimizes the total travel delay in the zone. Below we elucidate the operational concept for the AV zone:

  • Only AVs are allowed to use the links within the zone;
  • When entering the zone, AVs must report their exits of the zone to the control center, which routes AVs to traverse the zone; and
  • Based on AVs’ entrances and exits, the control center routes AVs to minimize the total travel delay in the zone.

 

Without the presence of CVs, AV zones will enable full utilization of the AV technology within the zones to hopefully improve the performance of the whole network. For example, due to the vehicle automation and the formulation of AV platoons, the per-lane capacity of links within AV zones can be much larger than those of regular links with mixed traffic stream of CVs and AVs. Accordingly, these zones can help reduce travel delays for AVs and further nurture the AV market. Nevertheless, the existence of AV zones likely increases travel delays for some CVs, as they cannot access the roads in AV zones. Therefore, government agencies will need to make a tradeoff between these pros and cons in designing AV zones. The optimal design will depend on the market penetration of AVs, network topology and link characteristics, and more importantly, the route choices of both CVs and AVs in the network.

 

Optimal design of AV zones possesses a structure of the leader-follower or Stackelberg game, in which government agencies serve as the leader while CVs and AVs are the followers. Without AV zones, AVs and CVs will act selfish and choose their travel path based on a “user-optimum” routing principle, under which every individual aims to minimize their own trip times. The network equilibrium model based on such a behavior has been widely studied by transportation researchers. However, the presence of AV zones will inevitably change the routing behavior of CVs and AVs. For example, with the presence of AV zones, when making their route choices, CVs need to avoid the zone, and travel decisions of AVs become more complicated. Recall that, once entering the AV zone, AVs will be fully controlled by the control center to take the routes that can achieve the minimum travel delay in the zone. That is, the “system-optimum” instead of user-optimum routing principle will be adopted in the AV zone. As a result, for the paths that consist of both links outside of and within the AV zone, AVs follow the user-optimum routing principle in the former and the system-optimum routing principle in the latter. As AVs using the same entrance and exit of the AV zone may experience different travel times due to system-optimum routing, we assume that AVs perceive their travel delay to be the minimum travel delay between their corresponding entrances and exits of the AV zone. In light of this, given the design of an AV zone, AVs will have to decide whether to access the zone, and where to enter and exit, so as to minimize their perceived trip delay.

 

Accordingly, to capture such a phenomenon, an innovative user equilibrium model named as “mixed routing equilibrium model” is firstly developed to describe the flow distribution of AVs and CVs across the network with AV zones. The basic idea is to construct a dummy network to replace the original AV network, in which each dummy link represents the set of paths connecting an entrance and an exit of the AV zone; accordingly, the travel cost of each dummy link is in fact the travel cost of the associated entrance and exit pair. As a result, formulating the mixed routing equilibrium model across the original network is equivalent to establishing a traditional network equilibrium model on the revised network, which is much easier to model and has been investigated by a large body of literatures.  

 

With the established mixed routing equilibrium model, a mixed-integer bi-level programming model can be easily developed to optimize the design plan of AV zones. The simulated annealing algorithm is then adopted to solve the model efficiently.

 

Major finding

To explore the impact of AV zones on the network performance, numerical examples based on both medium and large networks are conducted. Below concludes some major findings:

 

Our proposed modeling framework is able to delineate the route choice behavior and the resultant travel cost saving for each individual vehicle, as well as the travel cost within and outside the AV zone, with the presence of AV zones. All of these outputs can be taken as performance measures for designing AV zones.   

 

The total travel delay in the AV zone as well as the whole road network can be reduced substantially by the optimal deployment of AV zones. Particularly, the total travel delay has been reduced by 57.5% and 21.4% in the AV-zone area and the whole network, respectively.

 

The existence of the AV zone can lead to travel cost saving of not only AVs, but also CVs. In particular, the travel cost saving of the latter can range from 12% to 26%.

 

An example of an AV zone sign.

 

Future practice

The mixed routing equilibrium model discussed above may become more relevant with the deployment of various advanced traffic control and management strategies leveraging connected and automated vehicle technologies. The modeling framework proposed in this article can be applied to various scenarios where vehicles adopt different routing principles at different subnetworks, as long as the routing strategies within the subnetworks are well defined. For example, in practice, the control center may have different routing strategies for different subnetworks, such as minimizing vehicle-miles traveled or traffic emissions.

 

Admittedly, there are potential liability and other issues with specifying routes for individual vehicles. For example, according to the system-optimum routing principle in the AV zone, some AVs may be forced to take longer routes to traverse the AV zone, for the purpose of minimizing the system delay instead of the individual delay. Also, AVs using the same entrance and exit of the AV zone may experience different travel times. The former will undermine individuals’ incentive to use the AV zone, while the latter will bring equality issues. Possible solutions to deal with these practical issues include but are not limited to: 1) designing incentive programs to incentivize AVs to use AV zones; 2) applying game-theory algorithm, e.g. the Shapley value, to fairly distribute the benefit brought by the AV zones, i.e. the travel cost saving (in monetary), to AVs; 3) the control center could simply apply “selfish routing,” i.e. allowing AVs to choose their routes in a user-optimum manner within the AV subnetwork. Doing so can still benefit the whole system, as the vehicle automation and the formulation of AV platoons can be guaranteed in the AV zones. 

 

---------------

Chen is a postdoctoral research fellow at the University of Michigan. Yin is a professor at the University of Michigan.

 

Lead image source: Mcity

Overlay Init