Refer to ZestySalesman.ipynb for the latest route

1 files changed, 55 insertions, 54 deletions

diff --git a/utils.py b/utils.py
index 7f6a408..e0cc295 100644
--- a/utils.py
+++ b/utils.py
@@ -5,7 +5,7 @@ from sklearn.cluster import KMeans
 
 
 # Given a dataframe of coordinates and centroids, cluster the coordinates, minimize the time difference, and return the routes
-def cluster_and_minimize(df, centroids, norm_centroids, time_diff):
+def cluster_and_minimize(df, centroids, norm_centroids, end, time_diff):
     # Cluster the coordinates
     kmeans = KMeans(n_clusters=len(norm_centroids), init=norm_centroids)
 
@@ -16,8 +16,8 @@ def cluster_and_minimize(df, centroids, norm_centroids, time_diff):
     df['cluster'] = kmeans.labels_
 
     # Create centroid strings
-    centroid_1 = list_to_string([centroids[0]]) + ';'
-    centroid_2 = list_to_string([centroids[1]]) + ';'
+    centroid_1 = list_to_string([centroids[0]])
+    centroid_2 = list_to_string([centroids[1]])
 
     # Return the list of locations in each cluster
     route_1 = df[df['cluster'] == 0]
@@ -29,14 +29,14 @@ def cluster_and_minimize(df, centroids, norm_centroids, time_diff):
     route_2_str = list_to_string(route_2['gps'].values.tolist())
 
     # Get the trip time for each route
-    trip_hrs_1 = get_trip_time(centroid_1 + route_1_str, route_1_stops)
-    trip_hrs_2 = get_trip_time(centroid_2 + route_2_str, route_2_stops)
+    trip_hrs_1 = get_trip_time(route_1_str, route_1_stops, centroid_1, end)
+    trip_hrs_2 = get_trip_time(route_2_str, route_2_stops, centroid_2, end)
 
     # if the absolute value of the difference in trip times is greater than the time difference, minimize the time difference
     if abs(trip_hrs_1 - trip_hrs_2) > time_diff:
         route_1_coordinates, route_2_coordinates = minimize_route_time_diff(route_1['gps'].values.tolist(),
                                                                             route_2['gps'].values.tolist(),
-                                                                            centroid_1, centroid_2, time_diff)
+                                                                            centroid_1, centroid_2, end, time_diff)
     else:
         route_1_coordinates = route_1['gps'].values.tolist()
         route_2_coordinates = route_2['gps'].values.tolist()
@@ -48,6 +48,49 @@ def cluster_and_minimize(df, centroids, norm_centroids, time_diff):
     return df, route_1_coordinates, route_2_coordinates
 
 
+def minimize_route_time_diff(route_1_coordinates, route_2_coordinates, route_1_start, route_2_start, end,
+                             time_diff):
+    """
+    Takes two routes and a time difference and returns a route that is the same length as the shorter route but has a time difference that is less than the time difference
+    """
+    # Find the difference in time between the two routes
+    route_1_time = get_trip_time(list_to_string(route_1_coordinates),
+                                 len(route_1_coordinates), route_1_start, end)
+    route_2_time = get_trip_time(list_to_string(route_2_coordinates),
+                                 len(route_2_coordinates), route_2_start, end)
+    route_time_diff = abs(route_1_time - route_2_time)
+
+    # If the difference in time is greater than the time difference, move the closest coordinate from the longer route to the shorter route
+    if route_time_diff > time_diff:
+        # Find which route is longer
+        if len(route_1_coordinates) > len(route_2_coordinates):
+            longer_route = route_1_coordinates
+            shorter_route = route_2_coordinates
+
+            # Move the closest coordinate from the longer route to the shorter route
+            closest_coordinate = move_coordinate(longer_route, shorter_route)
+            longer_route.remove(closest_coordinate)
+            shorter_route.append(closest_coordinate)
+
+            # Recursively call the function
+            return minimize_route_time_diff(longer_route, shorter_route, route_1_start, route_2_start, end, time_diff)
+
+        else:
+            longer_route = route_2_coordinates
+            shorter_route = route_1_coordinates
+
+            # Move the closest coordinate from the longer route to the shorter route
+            closest_coordinate = move_coordinate(longer_route, shorter_route)
+            longer_route.remove(closest_coordinate)
+            shorter_route.append(closest_coordinate)
+
+            # Recursively call the function
+            return minimize_route_time_diff(shorter_route, longer_route, route_1_start, route_2_start, end, time_diff)
+
+    # If the difference in time is less than the time difference, return the routes
+    return route_1_coordinates, route_2_coordinates
+
+
 def list_to_string(list_of_lists):
     """
     Takes a list of lists of coordinates and returns a string of the coordinates
@@ -56,12 +99,12 @@ def list_to_string(list_of_lists):
     for i in list_of_lists:
         string += str(i[1]) + ',' + str(i[0]) + ';'
 
-    string = string[:-1]
     return string
 
 
-def create_json_df(coordinate_string):
-    coordinates = requests.get('http://acetyl.net:5000/trip/v1/bike/' + coordinate_string)
+def create_json_df(coordinate_string, start, end):
+    coordinates = requests.get(
+        'http://acetyl.net:5000/trip/v1/bike/' + start + coordinate_string + end + '?roundtrip=false&source=first&destination=last')
     coordinates = coordinates.json()
 
     # Create a dataframe from the JSON
@@ -79,11 +122,12 @@ def create_json_df(coordinate_string):
     return df
 
 
-def get_trip_time(coordinate_string, num_waypoints):
+def get_trip_time(coordinate_string, num_waypoints, start, end):
     """
     Takes a list of lists of coordinates and returns the time of the trip in hours
     """
-    coordinates = requests.get('http://acetyl.net:5000/trip/v1/bike/' + coordinate_string)
+    coordinates = requests.get(
+        'http://acetyl.net:5000/trip/v1/bike/' + start + coordinate_string + end + '?roundtrip=false&source=first&destination=last')
     coordinates = coordinates.json()
 
     travel_time_seconds = int(coordinates['trips'][0]['duration'])
@@ -130,49 +174,6 @@ def __min_max_normalize__(value, min_value, max_value):
     return (value - min_value) / (max_value - min_value)
 
 
-def minimize_route_time_diff(route_1_coordinates, route_2_coordinates, route_1_start, route_2_start,
-                             time_diff):
-    """
-    Takes two routes and a time difference and returns a route that is the same length as the shorter route but has a time difference that is less than the time difference
-    """
-    # Find the difference in time between the two routes
-    route_1_time = get_trip_time(route_1_start + list_to_string(route_1_coordinates),
-                                 len(route_1_coordinates))
-    route_2_time = get_trip_time(route_2_start + list_to_string(route_2_coordinates),
-                                 len(route_2_coordinates))
-    route_time_diff = abs(route_1_time - route_2_time)
-
-    # If the difference in time is greater than the time difference, move the closest coordinate from the longer route to the shorter route
-    if route_time_diff > time_diff:
-        # Find which route is longer
-        if len(route_1_coordinates) > len(route_2_coordinates):
-            longer_route = route_1_coordinates
-            shorter_route = route_2_coordinates
-
-            # Move the closest coordinate from the longer route to the shorter route
-            closest_coordinate = move_coordinate(longer_route, shorter_route)
-            longer_route.remove(closest_coordinate)
-            shorter_route.append(closest_coordinate)
-
-            # Recursively call the function
-            return minimize_route_time_diff(longer_route, shorter_route, route_1_start, route_2_start, time_diff)
-
-        else:
-            longer_route = route_2_coordinates
-            shorter_route = route_1_coordinates
-
-            # Move the closest coordinate from the longer route to the shorter route
-            closest_coordinate = move_coordinate(longer_route, shorter_route)
-            longer_route.remove(closest_coordinate)
-            shorter_route.append(closest_coordinate)
-
-            # Recursively call the function
-            return minimize_route_time_diff(shorter_route, longer_route, route_1_start, route_2_start, time_diff)
-
-    # If the difference in time is less than the time difference, return the routes
-    return route_1_coordinates, route_2_coordinates
-
-
 # Given two clusters and their respective lists of coordinates, move one coordinate from the larger centroid to the smaller centroid
 def move_coordinate(larger_centroid_coordinates, smaller_centroid_coordinates):
     # Calculate the centroid of the smaller cluster