Transportation Net �for America Cities

--Hongli Xu, Sang Lu

Transportation net construct

• Find transportation centers (limited number) in America main cities by minimize the total distance for transportation.
• For each transportation center group, which means cities assign to the center, find the optimize route.
• Our objective is constructing most effective transportation net for America.
• All companies which need transportation packages, products or others will interested in our project.

Just like the graph show left：

The red points are the transportation center, while blue points are the cities we set transportation point, we need assign them to each center.

Then use black line to link them by optimize route.

Our data source

• Our data ‘uscities.xlsx’ is raw statistics for America cites (Totally 28339 cities)

​

• What we are proud of is, we construct the America transportation net by processing raw city data, getting main cities’ (according to population) distance matrix from longitude and latitude data, and using knowledge about ‘Traveling Salesman’ and ‘Service Center Location’ we learned in class to build linear program.

First step: Find the Transportation Center

• In this simple example, we have 6 cities and set 2 transportation centers, for our whole dataset, we have 40 cities and set 5 transportation centers.
• Our target is to minimize the total distance for transportation and find the assignment of each city.
• And we found there are two transportation group, one is only Anchorage, the other is combined with Atlanta, Austin, Baltimore, Boston and Chicago.

​

DVs, Constraints, Objectives and Assumptions

• Decision variables: Transportation center location, Cities assign to the center
• Constraints: (1) Build limit amounts of transportation center

(2) Each city needs to get assigned to a center

(3) Only can assign center to a city if a center exists there

(4) All DVs are binary variables

• Objective: Minimize the total distance of transportation after set centers
• Assumption: The selection of total cities and the number of transportation centers are determined by ourselves, each part can reset them by your own need.

How do we find transportation centers?

• We use python to import all cities’ data, and select top 40 population cities.
• Use Pyomo package to build model and find optimization result (use the information shown in last slides).
• Since we transfer the problem to linear program, so we will use ‘glpk’ method to get result.

​

Second step: Find optimize route for each group

• As we mentioned in last example, there are two transportation group, one is only Anchorage, the other is combined with Atlanta, Austin, Baltimore, Boston and Chicago.
• We will find best route for each group (the group which is individually Anchorage is no need).
• The optimize route for this group is Austin-Atlanta-Chicago-Boston-Baltimore-Austin.

​

DVs, Constraints, Objectives and Assumptions

• Decision variables: Route from X to Y
• Constraints: (1)Depart every city once

(2) Go through every city

(3) Get rid of silly solution (not depart and arrive at same city)

(4) All DVs are binary variables

(5) Subtour constraints (will no longer need under Google or tools)

• Objective: Minimize the total distance of transportation route
• Assumption: We assume this problem is a Traveling Salesperson Problem, which means only one vehicle route.

How do we find optimize route?

• We use python to import all cities’ data.
• Group them by the assignment plan we get in finding transportation center process (from first step).
• Use Google or tools to find optimize route for each group.

​

​

​

​

Tableau Visualization Output

The output

• Sample Excel: Which I express in previous slides, a simple example to help interpret our project
• Python Notebook: The code used to realize data processing and model optimizing (Also one PDF version)
• PDF: The final optimal result we get from python
• PNG: Visualization of our Transportation Net

Further extension

• Since time limitation (large data optimization cost a lot of time), we only choose top cities in America, in fact we have a larger cities dataset, so we can extend the program wider, for example, denser net or larger map.
• When the data become larger, we can transfer the optimal route from Traveling Salesperson Problem to Vehicle Routing Problem, which might be closer to real life (Each center has several routes to realize transportation target).

-Thanks for your watching-

The whole project are equally contributed to both group members.

​

Reference:

• https://stackoverflow.com/questions/19413259/efficient-way-to-calculate-distance-matrix-given-latitude-and-longitude-data-in
• https://developers.google.com/optimization/routing/vrp
• 730 Course Material