(412f) Many-to-Many Routing of Vehicles in a City Network with Facility Interception Constraints

Villez, K., Purdue University
Pervaiz, Z., Purdue University

routing of vehicles in a city network with facility interception

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

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
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:


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
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

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.


J. & VENKATASUBRAMANIAN, V. 2011. An optimization framework for
cost effective design of refunding station infrastructure for
alternative fuel vehicles. Computers
and Chemical Engineering,


1966. Minimum-Cost Multicommodity Network Flows. Operations


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.

See more of this Session: Complex and Networked Systems

See more of this Group/Topical: Computing and Systems Technology Division