Browsed by
Tag: Google Maps

Solving the Traveling Salesman Problem Using the Google Maps API

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.

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)

 MadisonDuluthClevelandChicagoHoustonDenver
Madison0329.38496.62147.41135.1962.42
Duluth329.380818.13468.911327.31065.8
Cleveland496.62818.130343.251296.81332.6
Chicago147.4468.91343.2501083.31003.7
Houston1135.11327.31296.81083.301033.6
Denver962.421065.81332.61003.71033.60

Travel Time Between Cities (Hours)

 MadisonDuluthClevelandChicagoHoustonDenver
Madison05.02947.60582.488917.28913.858
Duluth5.0294012.2367.118619.63415.061
Cleveland7.605812.23605.304219.44419.132
Chicago2.48897.11865.3042016.23414.271
Houston17.28919.63419.44416.234015.287
Denver13.85815.06119.13214.27115.2870
The background map was obtained through the use of the plot_google_map function written by Zohar Bar-Yehuda. Background image copyright Google Maps.
The background map was obtained through the use of the plot_google_map function written by Zohar Bar-Yehuda. Background image copyright Google Maps.