<jupyter_start><jupyter_text>Route Optimization for Boston Tot Sprays Problem Description"The Parks department wants to be able to regularly visit each tot spray to check if it is clean and fully functional. Please provide an algorithm that would optimize the total travel time between all the tot sprays. It does not have to be the shortest route, but rather an algorithm that would produce an ordered list of the various locations for the driver to visit that would cut down the time compared to them guessing the best route themselves." First ApproachesThe task of visiting each Boston tot spray in minimum time is an application of the infamous "Traveling Salesman Problem".  The Parks department needs to visit each tot spray once, in succession, until all locations have been hit.  The route optimization here presented is not an exact solution to the problem, but rather an iterative approach that can be used to improve a given route.  Alternative algorithms and the thought process behind my selection can be found toward the end of this notebook. TerminologyEach tot spray is a *node*, the path linking each node an *edge*, and each route used to visit all of them a *tour*.  Each node is connected to every other node by an edge, which carries a *weight* given by the distance between the nodes.  The goal is to choose the optimal sequence of edges to make up the shortest tour. The 2-Opt AlgorithmThe fundamental idea behind an iterative approach to optimization is to make a small change and see if the result improves.  For our purposes this means that we start with a randomly chosen route, alter the route slightly, and determine if we get a shorter tour length.  If so, we remember the better tour, do another route alteration, rinse and repeat.The 2-opt algorithm chooses an edge and reverses its direction.  (This is the same as choosing two nodes and swapping them).  If the reversal improves the tour length, it's kept, if not, the original tour is kept.  This process is repeated by looping over pairs of nodes until all pairs have been considered.A => B => C => D becomes A => C => B => D, if ABCD > ACBD A => C => B => D becomes A => C => D => B, if ACBD > ACDB And so on.The concept of 2-opt is to "untangle" crossing routes over time.  With many iterations the route becomes smoother and smoother, optimizing the tour length.***Let's introduce the code: Code PreparationImport libraries and dataset.  I used random sampling on a smaller number of nodes for troubleshooting.  I add an entry to the dataframe to include City Hall.<jupyter_code>import pandas as pd
import numpy as np
from random import shuffle, sample, randint

#for random sampling
n = 49 #number of records in file
s = 20 #desired sample size
skip = sorted(sample(range(1,n+1),n-s))

#input path to the csv file here:
ts_df = pd.read_csv("/Users/mnksmith/Documents/Job Applications/Tot_Sprays.csv")#, skiprows=skip)

#add City Hall
home_lat, home_lon = 42.360644, -71.058014
ts_df.loc[-1] = [home_lon, home_lat, 0, 0, 'Central Boston', 'City Hall', '1 City Hall Square', 'TRUE', '10', '1 City Hall Square, Boston, MA 02201', 'Address', 0, 0, 0, 'None']  # adding a row
ts_df.index = ts_df.index + 1  # shifting index
ts_df.sort_index(inplace=True)<jupyter_output><empty_output><jupyter_text>What does a row of data look like?<jupyter_code>ts_df.head(3)<jupyter_output><empty_output><jupyter_text>We're just interested in the lat/lon coordinates stored in columns X and Y.Next let's create a function to calculate the distance between two nodes and a function to give the total length of the entire tour.  The distance is calculated by taking the coordinates of each node and applying the haversine formula .<jupyter_code>def distance(node1, node2, earth_radius=6371):
    lat1, lon1, lat2, lon2 = ts_df.Y[node1], ts_df.X[node1], ts_df.Y[node2], ts_df.X[node2]
    lat1, lon1, lat2, lon2 = np.radians([lat1, lon1, lat2, lon2])

    a = np.sin((lat2-lat1)/2.0)**2 + \
        np.cos(lat1) * np.cos(lat2) * np.sin((lon2-lon1)/2.0)**2

    return earth_radius * 2 * np.arcsin(np.sqrt(a))

def calc_length(tour):
    length = 0
    for i in range(len(tour)):
        length += distance(tour[i-1], tour[i])

    return length<jupyter_output><empty_output><jupyter_text>Now let's write the 2-opt algorithm.  A few things to note: - To make the tour start and finish at City Hall, I appended a final node to the tour and excluded the first and last nodes from consideration in the swapping process. - The nested for-loops consider edges for potential reversal and iterate. - This process may produce a different end route given different starting conditions, so the algorithm repeats `N_ITER` times, shuffling the inital tour order each time.<jupyter_code>def two_opt(ts_df):
    best_tour = []
    best_length = float('inf')
    N_ITER = 15
    

    for i in range(N_ITER):
        tour = list(range(len(ts_df.index)))
        shuffle(tour)
        tour.append(0)
        length = calc_length(tour)

        changed = True
        while changed:

            changed = False

            for a in range(0, len(ts_df.index)):

                for b in range(a+1, len(ts_df.index)-1):

                    new_tour = tour[:a] + tour[a:b][::-1] + tour[b:]
                    new_length = calc_length(new_tour)

                    if new_length < length:
                        length = new_length
                        tour = new_tour
                        changed = True

        if length < best_length:
            best_length = length
            best_tour = tour

    return best_tour, best_length<jupyter_output><empty_output><jupyter_text>ResultsThe two-opt function ouputs an ordered path and a tour length.<jupyter_code>path, length = two_opt(ts_df)
print('Path: ', path)
print('Length: %.2f km' % (length))<jupyter_output>Path:  [0, 8, 10, 9, 18, 11, 19, 7, 38, 40, 48, 39, 17, 16, 14, 44, 22, 47, 13, 15, 23, 24, 21, 20, 33, 49, 43, 1, 2, 4, 3, 31, 32, 34, 28, 35, 45, 46, 29, 25, 12, 26, 30, 36, 27, 37, 41, 42, 5, 6, 0]
Length: 59.63 km<jupyter_text>Converting the path indices to the park names and re-ordering the original dataframe to the new route:<jupyter_code>output_route = [0] * 51
output_df = ts_df.copy()
#output_df.append(pd.Series([np.nan]), ignore_index = True)
for i in range(len(path)-1):
    output_route[i] = ts_df['Park_Name'][path[i]]
    output_df.iloc[i] = ts_df.iloc[path[i]]
output_route[50] = ts_df['Park_Name'][path[50]]


print(output_route)
output_df.head(5)<jupyter_output>['City Hall', 'Puopolo Playground', 'Rutherford Union Playground', 'Doherty Playground', 'East Boston Memorial Park', 'Byrne Playground', 'Sumner/Lamson Street Playground', 'Christopher Columbus Park', 'Buckley Playground', 'Sweeney Playground', 'Medal of Honor Park', 'Dot Curran Play Area Moakley Park', 'Ryan Playground', 'Ronan Park', 'Ripley Playground', 'Erie/Ellington Street Playground', 'Harambee Park (Franklin Field)', 'Elmhurst Park', 'Rev. Loesch Park', 'Roberts Park', 'Thetford/Evans Park', 'Walker Playground', 'Er<NAME> Jr. Playground', 'McGann Playground\xa0', 'Malcolm X Park', 'Healy Playground', 'Hynes Playground', 'Hardiman Park', 'Hobart\xa0Park', 'Ringer Playground', 'Hooker/Sorento Playground', 'Jeep Jones Park', 'Lambert Avenue Playground', 'Marcella/Connolly Park', 'El Parquesito Dela Hermandad, Franklin Park', 'Father Roussin Park', 'Trotter Playground', 'Laviscount Park', 'Holborn Street Playground', "Children's Playground", 'Quincy/Stanley Playground', 'Denni[...]<jupyter_text>To check if the route produced by this algorithm makes sense, let's plot the route on top of a map of boston.  The gmplot package is necessary to run this section of the code (`pip install gmplot`).<jupyter_code>from gmplot import gmplot
from IPython.display import IFrame
from IPython.core.display import HTML 


gmap = gmplot.GoogleMapPlotter(42.35, -71.064361, 12)

ts_lats = np.empty(len(ts_df.index))
ts_lons = np.empty(len(ts_df.index))
for i in range(0,len(ts_df.index)):
    ts_lats[i], ts_lons[i] = ts_df.Y[i], ts_df.X[i]
gmap.scatter(ts_lats, ts_lons, c='red', size=200, marker=False)

for j in range(0,len(path)-1):
    path_lats, path_lons = zip(*[(ts_lats[path[j]],ts_lons[path[j]]), (ts_lats[path[j+1]],ts_lons[path[j+1]])])
    gmap.plot(path_lats, path_lons, 'darkblue', edge_width=5)

ch_lat, ch_lon = zip(*[(ts_df.Y[0], ts_df.X[0])])
gmap.scatter(ch_lat, ch_lon,'red')

gmap.draw("totspray_map3.html")

IFrame("totspray_map3.html", width=750, height=700)<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup