From 921a49433ccb34f2481f5f88de59f596976193cb Mon Sep 17 00:00:00 2001 From: itsGarrin Date: Mon, 6 Nov 2023 19:08:49 -0500 Subject: Refer to ZestySalesman.ipynb for the latest route --- utils.py | 109 ++++++++++++++++++++++++++++++++------------------------------- 1 file changed, 55 insertions(+), 54 deletions(-) (limited to 'utils.py') 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 -- cgit v1.2.3