I find global flight path maps mesmerizing. In a single image these maps present the vastness of our interconnected civilization on a global scale. These maps are by no means rare. However, they can be a fun programing exercise to generate.
Where to get flight data?
OpenFlights.org has assembled several databases relate to air travel. Their database on air routes and airports provided the necessary information to determine flight paths. The database contains nearly 60,000 routes from 3200 airports.
Flight paths were colored based on the departure continent. To correlate the departure airport, with a depature continent, an ISO-3166 database was utilized.
The aforementioned datasets were assembled as MATLAB Tables for use by the plotting script.
The shapefile for the world map was obtained from ArcGIS.
How to calculate the flight path.
The great-circle is the shortest distance between any two points traveling along the surface of a sphere. The great-circle is defined as a circle centered on the centroid of the sphere and orientated such that the perimeter of the circle passes through the two locations. The arc defined by the great-circle provides the shortest travel route often used for long-distance air travel.
Algebraic formulas for calculating the great circle distance as well as latitude and longitude values of intermediate points along the arc can be found here: https://www.movable-type.co.uk/scripts/latlong.html
A MATLAB function for calculating the great circle distance as well as intermediate points along the route is included at the bottom of this article.
The result
The map below shows the results of this exercise.
Solving the Traveling Salesman Problem Using the Google Maps API
The full source code for this problem will not be posted since my intent is not to write work that can easily be used in its entirety as a course project. If you are a course instructor and would like to use this as a demonstration, feel free to contact me with your request through your university email account.
Determining the distance between cities
Introduction
Using the Google Maps API, the driving distance, driving time, and GPS locations of each city can be determined. To do this, the Google Maps Distance Matrix and the Geocoding APIs was utilized. To request information from these APIs, one simply needs to generate a URL that contains a list of the information desired in a format specified by the API. When the URL is entered into a browser, the resulting webpage contains the desired information. A thorough description of how to use this API can be determined using the previous links.
An API key is not necessary to use the APIs; however, without a key, your IP address will be limited to 1000 requests per day (multiple users under the same IP will contribute to this limit). With an key, the limit is expanded to 2500 per key.
Now, consider the case where you have a 10 city traveling salesman problem. One could simply create a list of origin and destination cities which would result in a 10×10 matrix. The API could easily handle this request as long as the URL did not exceed the 2000 character limit. However, this is inefficient since the diagonals of this matrix are zeros and the matrix is symmetrical. I.e., the distance from A to B is the same as from B to A (obviously). Therefore, effective programming can be used here to minimize the number of API calls.
Reading the API data with MATLAB
The webread function within MATLAB makes it easy to grab and parse the data returned by the API. This function can grab handle several return formats. For this example, we will use JSON format which the function will automatically recognize and the output variable will be a structure containing the desired data.
To see the JSON file which MATLAB will parse, click here.
To better understand the format of the structure variable DistanceData run the previous code and study the format of the variable in the MATLAB workspace. Then try adding an additional origin city and see how the structure format changes.
For a six city problem, the following distance matrix and city center data was obtained using the API:
Driving Distance Between Cities (miles)
Madison
Duluth
Cleveland
Chicago
Houston
Denver
Madison
0
329.38
496.62
147.4
1135.1
962.42
Duluth
329.38
0
818.13
468.91
1327.3
1065.8
Cleveland
496.62
818.13
0
343.25
1296.8
1332.6
Chicago
147.4
468.91
343.25
0
1083.3
1003.7
Houston
1135.1
1327.3
1296.8
1083.3
0
1033.6
Denver
962.42
1065.8
1332.6
1003.7
1033.6
0
Travel Time Between Cities (Hours)
Madison
Duluth
Cleveland
Chicago
Houston
Denver
Madison
0
5.0294
7.6058
2.4889
17.289
13.858
Duluth
5.0294
0
12.236
7.1186
19.634
15.061
Cleveland
7.6058
12.236
0
5.3042
19.444
19.132
Chicago
2.4889
7.1186
5.3042
0
16.234
14.271
Houston
17.289
19.634
19.444
16.234
0
15.287
Denver
13.858
15.061
19.132
14.271
15.287
0
The background map was obtained through the use of the plot_google_map function written by Zohar Bar-Yehuda. Background image copyright Google Maps.
