Optimal route finder for multiple stops using the Google Maps API

To run: python3 hamiltonian.py <suburb>.csv [optional database, default=addresses/db.csv]

Generate virtual environment

• python3 -m venv env

Add API key to virtual environment

• vim env/bin/activate
• At the end of deactivate() function:
  • unset DISTANCE_MATRIX_API_KEY
• At the end of the file:
  • export DISTANCE_MATRIX_API_KEY="{insert API key}"
• Reference: https://stackoverflow.com/a/38645983

Activate virtual environment

• source env/bin/activate

python3 hamiltonian.py addresses/prospect.csv addresses/example_db.csv

addresses/db.csv - Database of all orders and addresses

• example here
• TAB separated values (TSV) file
• Columns: Name, zID, Email, Phone, Beige size, Rose size, Shirt size, Champion hoodie size, Address, Suburb

addresses/<suburb>.csv - List of addresses in route

• example here
• Limit of 10 addresses per CSV (limited by Distance Matrix API)
• Note: suburb in <suburb>.csv should match suburb field in db.csv

Drivers will depart from home and travel to each address within their surrounding suburb.

Optimal path will be the path with shortest travel time. This path must create a circuit with the driver's home as the start and end location, passing through every delivery address at least once.

Given a list of origins and destinations, the API will return an array of distances between from each origin to each destination.

* array of size `origins` x `destinations` 
* O(sizeof(`origins`) * sizeof(`destinations`)) 

For our application, we have a list of locations, and want to find the optimal route between them all. Therefore, origins = destinations

* Suppose we have `n` addresses
* Return array is size `n^2`
* Time complexity = `O(n^2)`

Input from CSV files.

We can either have one large CSV with all addresses, or manually separate by suburb.

Time complexity

• assuming 5 suburbs with equal destinations
• Total number of addresses = n

For 100 addresses,

Much more worth to separate by suburb with multiple smaller CSV's.

developers.google.com/maps/documentation/distance-matrix/usage-and-billing

Each query sent to the Distance Matrix API generates elements, where the number of origins times the number of destinations equals the number of elements.

• There is no limit on the maximum number of elements per day (EPD)
• Maximum of 25 origins or 25 destinations per request
• Maximum of 100 elements per server-side request
• Maximum of 100 elements per client-side request
• 1000 elements per second (EPS), calculated as the sum of client-side and server-side queries

Input: List of optimal path from start to end, List of addresses, Total trip time

Output: ETA, Number of stops, (Address,Name,Order contents,Mobile) for each destination, and URL with route inputted into Google Maps

Input: Path to file (e.g. addresses/blacktown.csv)

Output: String formatted for destinations parameter of Distance Matrix API (e.g. 123+Cherry+St.+Chazza+NSW+1234|456+Parrot+Land,+Wakeley+8421|54+Monkey+Road,+Wahoo,+NSW,+124|)

Called by get_addresses_str()

Input: List of addresses

Output: String formatted for destinations parameter of Distance Matrix API

Input: Response from Distance Matrix API

Output (To stdout): Matrix of paths between each node (with distance and duration)

Input: Response from Distance Matrix API

Output: 2D list of travel time between each node

Input: Response from Distance Matrix API

Output: 2D list of travel distance between each node

Queries the Distance Matrix API given string-formatted addresses.

Query chooses to avoid tolls

params = urllib.parse.urlencode(
    {
        "origins" : addresses,
        "destinations" : addresses,
        "key" : API_KEY,
        "avoid" : "tolls"
    }
)

Input: Address string formatted for destinations paramater of Distance Matrix API

Output: Response from Distance Matrix API