(579b) Optimal Rerouting of Traffic Flows for Resilient Management of Recharging Station Networks

One of the most important challenges to be met in
the transition towards an ecologically friendly society is the
implementation of better ways of transportation, which reduce the
amounts of energy used and which permit the switch to "greener"
sources of energy. One part of the solution is likely to be met by
means of electrical vehicles. Because electrical vehicles are limited
in range and their "refueling" (i.e. recharging) takes
time, a system in which batteries can be replaced quickly has been
proposed [1]. Still, for such a system to work, it is of critical
importance that electric vehicles can efficiently reach a service
station. We have studied this problem in the past by optimizing the
location of service stations for a given traffic flow in the form of
an Integer Linear Program (ILP). Originally, this was solved for a
failure-free setting [2]. More recently, we have extended this for
scenarios in which parts of the infrastructure (roads, road junctions
and service stations) can fail [3].

In our
vision, the previously adopted strategy to optimize the location of
service stations is only one necessary element. Next to this, one
should account for the fact that the route of electrical vehicles can
be modified. Indeed, the routes of electrical vehicles can be guided
and manipulated so to make sure that they can reach service stations
efficiently under varying conditions. We explore this option in this
work by evaluation of the following algorithm.

Consider
first that the set of service stations is fixed and the normal
traffic flow of conventional cars is known in the form of routes
(paths) over a city network. In such case, we reroute the cars in a
greedy fashion as follows:

• The paths which contain a service station remain the same

• The paths which do not contain a service station are modified as follows:

1. Select the most busy path (highest car flows)

2. For the selected path, find the shortest path from start location to destination which contain one of the service stations. Do this for all available service stations. To this end, we apply Dijkstra's algorithm to find (1) the shortest path between the start location and the selected service station and (2) the shortest path between the selected service station and the destination location.

3. If no paths could be found which include a service station, exclude the traffic flow associated with this path in subsequent steps and go to 7. Otherwise, continue to 4.

4. Following the above enumeration of shortest paths, sort the obtained paths from shortest to longest.

5. Now the flow in the original path is distributed over the paths starting with the shortest paths while not exceeding the capacity of any of the roads. If all computed paths are used to their maximum capacity, retain the excessive amount of cars on the original path.

6. If any of the roads in the city network become saturated, i.e., reach their maximum capacity, exclude these roads as available roads in the network for repeated optimization steps.

7. Stop the algorithm if any of the following conditions is met:

   1. All edges in the network are saturated

   2. All car flows have been excluded from optimization (step 3) or have been rerouted successfully (step 5).

We apply the above algorithm to the case study
used before, which is that of the city of Alexandria, VA. To compute
the normal flow of conventional cars, we use the model as implemented
in TRANSIMS.

REFERENCES

1. K. Galbraith, “Better Place unveils battery swap station,” http://green.blogs.nytimes.com/2009/05/13/better-place-unveils-battery-s... , 2009

2. A. Shukla, J. Pekny, and V. Venkatasubramanian, “An optimization framework for cost effective design of refueling station infrastructure for alternative fuel vehicles,” Computers & Chemical Engineering, In Press, Available online, 2011.

3. Kris Villez, Akshya Gupta, Venkat Venkatasubramanian, Craig Rieger. Resilient design of recharging station networks for electric transportation vehicles. Submitted to the 4th International Symposium on Resilient Control Systems (ISRCS2011).