dashboard changes - routing in router.py

1 files changed, 294 insertions, 0 deletions

diff --git a/dashboard_website/router.py b/dashboard_website/router.py
new file mode 100644
index 0000000..3929cca
--- /dev/null
+++ b/dashboard_website/router.py
@@ -0,0 +1,294 @@
+import folium
+import numpy as np
+import pandas as pd
+import requests
+from sklearn.cluster import KMeans
+
+host = "http://acetyl.net:5000" # queries acetyl.net:5000, the OSRM engine
+
+# external facing functions
+
+# gets single leg route between bike and clue
+# should be HD and GeoJSON
+def getRouteFullJSON(bike, clue):
+    url = f"{host}/route/v1/bike/{bike['longitude']},{bike['latitude']};{clue['longitude']},{clue['latitude']}?steps=true&overview=full&geometries=geojson"
+    r = response.get(url)
+    return r.json()
+
+def getRouteHDPolyline(bike, clue):
+    url = f"{host}/route/v1/bike/{bike['longitude']},{bike['latitude']};{clue['longitude']},{clue['latitude']}?overview=full&geometries=geojson"
+    r = response.get(url)
+    p = r.json()['trips'][0]['geometry']['coordinates']
+    return p
+
+def getRouteFastPolyline(bike, clue):
+    url = f"{host}/route/v1/bike/{bike['longitude']},{bike['latitude']};{clue['longitude']},{clue['latitude']}?geometries=geojson"
+    r = response.get(url)
+    p = r.json()['trips'][0]['geometry']['coordinates']
+    return p
+
+def getZSP(bike, home, clue_cluster):
+    pass
+
+# determines clusters based on current bikes and clues
+def getClusters(bikes, clues, endpoint):
+    pass
+
+# utility functions (internal)
+def cluster_and_optimize(df, centroids, end, time_diff=0.25, max_time=24, n=2):
+    """
+    Takes a dataframe of gps coordinates, a list of centroids, and an end point and returns a dataframe with a cluster
+    :param df: a dataframe of gps coordinates
+    :param centroids: a list of centroids
+    :param end: the end point of the trip
+    :param time_diff: the maximum time difference between the longest trip and the average trip
+    :param max_time: the maximum time of the trip
+    :param n: the number of routes to create
+    :return: a dataframe with a cluster column
+    """
+    # Create a new column with normalized gps coordinates and centroids
+    df['normalized_gps'], norm_centroids = __normalize_gps(df['gps'].values.tolist(), centroids)
+
+    # Cluster the coordinates
+    kmeans = KMeans(n_clusters=len(norm_centroids), init=norm_centroids)
+    kmeans.fit(df['normalized_gps'].values.tolist())
+
+    df['cluster'] = kmeans.labels_
+
+    routes = []
+    starts = []
+    for i in range(len(centroids)):
+        routes.append(df[df['cluster'] == i]['gps'].values.tolist())
+        starts.append(list_to_string([centroids[i]]))
+
+    routes = __minimize_route_time_diff(routes, starts, end, time_diff, n)
+
+    # Remove waypoints from the longest route until the trip time is less than the max time
+    for i in range(len(routes)):
+        routes[i] = __remove_longest_waypoints(routes[i], starts[i], end, max_time)
+        df.loc[df['gps'].astype(str).isin(map(str, routes[i])), 'cluster'] = i
+
+    return df, routes
+
+
+def list_to_string(list_of_lists):
+    """
+    Takes a list of lists and returns a string of the list of lists
+    :param list_of_lists: a list of lists
+    :return: a string of the list of lists
+    """
+    string = ''
+    for i in list_of_lists:
+        string += str(i[1]) + ',' + str(i[0]) + ';'
+
+    return string
+
+
+def create_json_df(coordinate_string, start, end):
+    """
+    Takes a string of coordinates and returns a dataframe of the coordinates in order of the waypoint index
+    :param coordinate_string: a string of coordinates
+    :param start: the start point of the trip
+    :param end: the end point of the trip
+    :return: a dataframe of the coordinates in order of the waypoint index
+    """
+    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
+    df = pd.DataFrame(coordinates['waypoints'])
+
+    # Separate the location column into lon and lat columns
+    df['lat'] = df['location'].apply(lambda x: x[0])
+    df['lon'] = df['location'].apply(lambda x: x[1])
+
+    df['waypoint_index'] = df['waypoint_index'].astype(int)
+
+    # Map out the waypoints in order of the waypoint index
+    df = df.sort_values(by=['waypoint_index'])
+
+    return df
+
+
+def get_trip_time(coordinate_string, num_waypoints, start, end, time_per_waypoint=90):
+    """
+    Takes a string of coordinates and returns the trip time in hours
+    :param coordinate_string: a string of coordinates
+    :param num_waypoints: the number of waypoints
+    :param start: the start point of the trip
+    :param end: the end point of the trip
+    :param time_per_waypoint: the time per waypoint in seconds
+    :return: the trip time in hours
+    """
+    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'])
+    waypoint_time_seconds = num_waypoints * time_per_waypoint
+
+    total_time_hours = (travel_time_seconds + waypoint_time_seconds) / 3600
+
+    return total_time_hours
+
+
+def __minimize_route_time_diff(routes, starts, end, time_diff, n):
+    """
+    Takes a list of lists of coordinates, a list of start points, an end point, a time difference, and a number of routes
+    :param routes: the list of lists of coordinates
+    :param starts: the list of start points
+    :param end: the end point
+    :param time_diff: the time difference
+    :param n: the number of routes
+    :return: a list of lists of coordinates
+    """
+    times = []
+
+    for i, route in enumerate(routes):
+        times.append(get_trip_time(list_to_string(route), len(route), starts[i], end))
+
+    # Find the average trip time
+    average_time = np.mean(times)
+
+    # Sort the trip times
+    sorted_indices = np.argsort(times)
+
+    # Find the difference between the longest trip time and the average trip time
+    time_difference = times[sorted_indices[-1]] - average_time
+
+    # If the difference is greater than the time difference, move a coordinate from the longest route to the shortest route
+    if time_difference > time_diff:
+        # Move a coordinate from the longest route to the shortest route
+        closest_coordinate = __find_closest_coordinate(routes[sorted_indices[-1]],
+                                                       __mean_center(routes[sorted_indices[0]]))
+        routes[sorted_indices[0]].append(closest_coordinate)
+        routes[sorted_indices[-1]].remove(closest_coordinate)
+
+        # Recursively minimize the time difference between the routes
+        return __minimize_route_time_diff(routes, starts, end, time_diff, n)
+
+    # If the difference of the longest trip time from average is less than the time difference, return the routes
+    return routes
+
+
+def __remove_longest_waypoints(route_coordinates, start, end, max_time):
+    """
+    Takes a list of coordinates, a start point, an end point, and a maximum time and returns a list of coordinates
+    :param route_coordinates: the list of coordinates
+    :param start: the start point
+    :param end: the end point
+    :param max_time: the maximum time
+    :return: a list of coordinates
+    """
+    # Find the trip time for the route
+    route_time = get_trip_time(list_to_string(route_coordinates), len(route_coordinates), start, end)
+
+    # If the trip time is greater than the max time, remove the waypoint with the longest distance from the mean
+    if route_time > max_time:
+        route_mean = __mean_center(route_coordinates)
+        furthest_coordinate = __find_farthest_coordinate(route_coordinates, route_mean)
+        route_coordinates.remove(furthest_coordinate)
+
+        return __remove_longest_waypoints(route_coordinates, start, end, max_time)
+
+    return route_coordinates
+
+
+def __normalize_gps(coordinates, centroids):
+    """
+    Takes a list of coordinates and a list of centroids and returns a list of normalized coordinates and a list of
+    normalized centroids
+    :param coordinates: the list of coordinates
+    :param centroids: the list of centroids
+    :return: the list of normalized coordinates and the list of normalized centroids
+    """
+
+    # Create a list of latitudes and longitudes
+    latitudes = [i[0] for i in coordinates]
+    longitudes = [i[1] for i in coordinates]
+
+    # Find the minimum and maximum latitudes and longitudes
+    min_lat = min(latitudes)
+    max_lat = max(latitudes)
+    min_lon = min(longitudes)
+    max_lon = max(longitudes)
+
+    # Normalize the coordinates and centroids using min-max normalization
+    normalized_coordinates = []
+    normalized_centroids = []
+
+    for i in coordinates:
+        normalized_coordinates.append(
+            [__min_max_normalize(i[0], min_lat, max_lat), __min_max_normalize(i[1], min_lon, max_lon)])
+    for i in centroids:
+        normalized_centroids.append(
+            [__min_max_normalize(i[0], min_lat, max_lat), __min_max_normalize(i[1], min_lon, max_lon)])
+
+    return normalized_coordinates, normalized_centroids
+
+
+def __min_max_normalize(value, min_value, max_value):
+    """
+    Takes a value, a minimum value, and a maximum value and returns the normalized value
+    :param value: the value
+    :param min_value: the minimum value
+    :param max_value: the maximum value
+    :return: the normalized value
+    """
+    return (value - min_value) / (max_value - min_value)
+
+
+def __find_closest_coordinate(coordinates, centroid):
+    """
+    Takes a list of coordinates and a centroid and returns the coordinate in the list that is closest to the centroid
+    :param coordinates: the list of coordinates
+    :param centroid: the centroid
+    :return: the coordinate in the list that is closest to the centroid
+    """
+    closest_coordinate = coordinates[0]
+    closest_coordinate_distance = __distance(closest_coordinate, centroid)
+
+    for coordinate in coordinates:
+        if __distance(coordinate, centroid) < closest_coordinate_distance:
+            closest_coordinate = coordinate
+            closest_coordinate_distance = __distance(coordinate, centroid)
+
+    return closest_coordinate
+
+
+def __find_farthest_coordinate(coordinates, centroid):
+    """
+    Takes a list of coordinates and a centroid and returns the coordinate in the list that is farthest from the centroid
+    :param coordinates: the list of coordinates
+    :param centroid: the centroid
+    :return: the coordinate in the list that is farthest from the centroid
+    """
+    farthest_coordinate = coordinates[0]
+    farthest_coordinate_distance = __distance(farthest_coordinate, centroid)
+
+    for coordinate in coordinates:
+        if __distance(coordinate, centroid) > farthest_coordinate_distance:
+            farthest_coordinate = coordinate
+            farthest_coordinate_distance = __distance(coordinate, centroid)
+
+    return farthest_coordinate
+
+
+def __mean_center(coordinates):
+    """
+    Takes a list of coordinates and returns the mean center of the coordinates
+    :param coordinates: the list of coordinates
+    :return: the mean center of the coordinates
+    """
+    return [sum([i[0] for i in coordinates]) / len(coordinates), sum([i[1] for i in coordinates]) / len(coordinates)]
+
+
+def __distance(coordinate1, coordinate2):
+    """
+    Takes two coordinates and returns the distance between them
+    :param coordinate1: the first coordinate
+    :param coordinate2: the second coordinate
+    :return: the distance between the two coordinates
+    """
+    return ((coordinate1[0] - coordinate2[0]) ** 2 + (coordinate1[1] - coordinate2[1]) ** 2) ** 0.5
\ No newline at end of file