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

- Conference: AIChE Annual Meeting
- Year: 2012
- Proceeding: 2012 AIChE Annual Meeting
- Group: Computing and Systems Technology Division
- Session:
- Time:
Wednesday, October 31, 2012 - 10:10am-10:30am

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

subject to the following constraints:

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.

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