282392 Many-to-Many Routing of Vehicles in a City Network with Facility Interception Constraints

Wednesday, October 31, 2012: 10:10 AM
327 (Convention Center )
Zeeshan Pervaiz1, Kris Villez1 and Venkat Venkatasubramanian2, (1)School of Chemical Engineering, Purdue University, West Lafayette, IN, (2)Chemical Engineering, Columbia University, New York, NY

Many-to-many routing of vehicles in a city network with facility interception constraints

Zeeshan A. Pervaiz, K. Villez, V. Venkatasubramanian

Providing infrastructures which enable a shift to a sustainable society is of special importance in the transportation sector. A particular problem concerns the optimal location of service stations for electric vehicles. In addition, optimal routing of vehicles to these stations is crucial given that current driving ranges are limited for many electrical vehicles. The many-to-many routing of vehicles to such service stations is solved by means of a Minimum Cost Multi Commodity Flow (MCMCF) problem formulation. Our results indicate that this is indeed possible for small to medium-scale settings.

The city of Alexandria, VA, is used as a case study to test our methodology. This case study is available in TRANSIMS and has been used in prior work (Shukla et al., 2011, Villez et al., 2011). Figure 2 shows the road network for this case study with five facility locations. TRANSIMS is an agent-based simulator developed by Los Alamos National Laboratory. This simulator allows to extract two essential inputs for our methodology which are (1) the topology of the traffic network including arcs (roads) and nodes (road junctions or terminal ends) and (2) the source-destination pairs and the average number of vehicles (flow) per day. The road network, excluding public transport infrastructures, has a total of 2573 nodes with 7214 edges. There are a total of 13892 unique source destination pairs (commodities), each of which have an associated commodity.

The third requirement is that one knows the location of the facilities. To this end, we use the optimized locations as found in Villez et al. (2011) for ten different scenarios, namely for the number of facilities ranging from one to ten.

Figure 2. Road map of Alexandria, VA, with 5 service stations (squares), adopted from Villez et al. (2011).

For the formulation of the problem, consider a directed Graph G=(V,E) with nodes V=(1,….,n) and directed arcs. Each arc eij has associated with it a cost cij and a capacity bij. A commodity k=(1,…..,a) is associated with each unique pair of source-destination nodes (sk,tk) such that sk is the source while tk is the destination for the commodity k. Also, let be the set of nodes with facilities. Let fijk be the flow on the edge eij for the commodity k. Then solving the MCMCF problem is equivalent to the minimization of the total cost:

Eq. 1.1

subject to the following constraints:

Eq. 1.2

Eq. 1.3

Eq. 1.4

Equations 1.2 represent the nodal balances in each node of the graph (junction of the road network). Equations 1.3 represent the capacity constraint in each edge of the graph (road in the network). Equations 1.1 to 1.3 represent the problem formulated in (Tomlin 1966). Equation 1.4 are new. These are added to ensure that all routes are constrained to go through at least one of the provided facilities.

The total load on the network as presented by all the commodities is 165263 units, while the loads presented by the selected pairs (commodities) are 6527, 13205, 27632 and 41728 units respectively. So the percentage load offered by the four sets of commodities is 1.7%, 3.43%, 7.18% and 10.85% respectively.

In Figure 4, the objective function values are plotted as function of the fraction of the load on the Alexandria city network represented by the selected source-destination pairs (commodities). As expected one can see that the objective function is increasing with the number of commodities. As can be seen, this increase is almost linear. More importantly, the result are largely the same for all considered sets of facility locations (1 to 10 locations). This indicates the benefit of additional facilities at this limited load fraction is very limited.

Figure 4. Objective function plotted as function of the fraction of total load (%) in the Alexandria city network. Ten lines are shown for each set facility locations with facility numbers ranging from 1 to 10.


SHUKLA, A., PEKNY, J. & VENKATASUBRAMANIAN, V. 2011. An optimization framework for cost effective design of refunding station infrastructure for alternative fuel vehicles. Computers and Chemical Engineering, 35, 1431-1438.

TOMLIN, J. A. 1966. Minimum-Cost Multicommodity Network Flows. Operations Research, 14, 45-51.

VILLEZ, K., GUPTA, A., VENKATASUBRAMANIAN, V. & RIEGER, C. Resilient design of recharging station networks for electric transportation vehicles. 4th International Symposium on Resilient Control Systems, ISRCS 2011, August 9, 2011 - August 11, 2011, 2011 Boise, ID, United states. IEEE Computer Society, 55-60.

Extended Abstract: File Not Uploaded
See more of this Session: Complex and Networked Systems
See more of this Group/Topical: Computing and Systems Technology Division