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

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 e_ij has associated with it a cost c_ij
and a capacity b_ij. A commodity k=(1,…..,a) is
associated with each unique pair of source-destination nodes (s_k,t_k)
such that s_k is the source while t_k is the
destination for the commodity k. Also, let
be
the set of nodes with facilities. Let f_ij^k be
the flow on the edge e_ij 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.

REFERENCES

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.