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.

url=https://maps.googleapis.com/maps/api/distancematrix/json?origins=Madison+WI&destinations=Milwaukee+WI|Chicago+IL&units=imperial
DistanceData = webread(url);

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