diff options
Diffstat (limited to 'dashboard_website/router.py')
| -rw-r--r-- | dashboard_website/router.py | 161 |
1 files changed, 103 insertions, 58 deletions
diff --git a/dashboard_website/router.py b/dashboard_website/router.py index e0e0720..4840c8d 100644 --- a/dashboard_website/router.py +++ b/dashboard_website/router.py @@ -5,10 +5,11 @@ import requests from sklearn.cluster import KMeans from datastructs import * +import db host = "http://acetyl.net:5000" # queries acetyl.net:5000, the OSRM engine -endtime = datetime.datetime(2023, 11, 18, hour=18, minute=45) # 11/18/2023 6:35pm +endtime = datetime.datetime(2024, 11, 16, hour=18, minute=45) # 11/18/2023 6:35pm # external facing functions @@ -42,38 +43,36 @@ def getRouteFastPolyline(bike, clue): return p -def getZSP(bike, home, clue_cluster): - pass - - # determines clusters based on current bikes and clues -def getClusters(bikes, clues, endpoint): +def getClusters(bikes, clues, endpoint, minimal=True): + status = 0 clusters = [[] for bike in bikes] route_geos = [[] for bike in bikes] times = {} - active_indices = [i for i in range(len(bikes)) if bikes[i].status == "ACTIVE"] - active_bikes = [bike for bike in bikes if bike.status == "ACTIVE"] + active_indices = [i for i in range(len(bikes)) if bikes[i].status != "DISABLED"] + active_bikes = [bike for bike in bikes if bike.status != "DISABLED"] if len(active_bikes) == 0: - return clusters, route_geos, times - active_clues = [clue for clue in clues if clue.status == "UNVISITED"] + return status, clusters, route_geos, times + active_clues = [ clue for clue in clues if (clue.status != "VISITED" and clue.status != "DISABLED") ] # select only active bikes # select only unvisited clues - clusters_t, route_geos_t, times_t = cluster_and_optimize( - active_clues, active_bikes, endpoint + status_c, clusters_t, route_geos_t, times_t = cluster_and_optimize( + active_clues, bikes, endpoint, minimal ) - for i in range(len(active_indices)): - route_geos[active_indices[i]] = route_geos_t[i] - clusters[active_indices[i]] = clusters_t[i] - bikes[active_indices[i]].setCluster(clusters_t[i]) - times[bikes[active_indices[i]].name] = times_t[i] + if status_c != 0: # routing canceled + return -1, [], [], [] + for i in range(len(bikes)): + route_geos[i] = route_geos_t[i] + clusters[i] = clusters_t[i] + times[i] = times_t[i] # return list of clue clusters corresponding to bikes - return clusters, route_geos, times + return status, clusters, route_geos, times # utility functions (internal) def cluster_and_optimize( - clues: [Clue], bikes: [Bike], end: Point, time_diff=0.25, max_time=24, n=2 + clues: [Clue], bikes: [Bike], end: Point, minimal : bool, time_diff=0.25, max_time=24 ): """ Takes a dataframe of gps coordinates, a list of centroids, and an end point and returns a dataframe with a cluster @@ -85,25 +84,43 @@ def cluster_and_optimize( :param n: the number of routes to create :return: a list of lists of clues (ordered by position on route), and a list of json route geojsons """ + status = 0 # OVERRIDE MAX TIME max_time = datetime.datetime.now() - endtime max_time = max_time.seconds / 3600 - routes = [ - clues - ] # one bike = one set of routes. only need to remove the faraway waypoints - if len(bikes) > 1: - # Create a new column with normalized gps coordinates and centroids - normalized_points, norm_centroids = __normalize_points(clues, bikes) - # Cluster the coordinates - kmeans = KMeans(n_clusters=len(norm_centroids), init=norm_centroids) - kmeans.fit(normalized_points) - - # Split the clues into clusters based on the cluster labels - routes = [[] for i in range(len(norm_centroids))] - for i, label in enumerate(kmeans.labels_): - routes[label].append(clues[i]) - - routes = __minimize_route_time_diff(routes, bikes, end, time_diff, n) + + # Create a new column with normalized gps coordinates and centroids + active_indices = [i for i in range(len(bikes)) if bikes[i].status != "DISABLED"] + active_bikes = [bike for bike in bikes if bike.status != "DISABLED"] + + normalized_points, norm_centroids = __normalize_points(clues, active_bikes) + # Cluster the coordinates + kmeans = KMeans(n_clusters=len(norm_centroids), init=norm_centroids) + kmeans.fit(normalized_points) + + # assign pre-determined clues to bikes + already_assigned_clues = [] + routes = [[] for i in bikes] + for clue in clues: + if clue.assigned_team != 0 and ((clue.assigned_team-1) in active_indices): + routes[clue.assigned_team - 1].append(clue) + already_assigned_clues.append(clue) + + # if we are not doing a hard reset, keep the current target clues + if minimal: + for i, bike in enumerate(bikes): + if (bike.status != "DISABLED") and (bike.target_clue != None) and (bike.target_clue not in routes[i]): + routes[i].append(bike.target_clue) + already_assigned_clues.append(clue) + + # Split the remaining clues into clusters based on the cluster labels + for i, label in enumerate(kmeans.labels_): + if clues[i].assigned_team == 0 and (clues[i] not in already_assigned_clues): + routes[active_indices[label]].append(clues[i]) + + routes = __minimize_route_time_diff(routes, bikes, end, minimal, time_diff) + if routes == -1: + return -1, [], [], [] # Remove waypoints from the longest route until the trip time is less than the max time for i in range(len(routes)): @@ -116,7 +133,7 @@ def cluster_and_optimize( for i, route in enumerate(routes): route_json = __get_json( __clues_to_string(route), - __clues_to_string([bikes[i]]), + __clues_to_string([bikes[i].target_clue if (minimal and (bikes[i].target_clue != None)) else bikes[i]]), __clues_to_string([end])[:-1], ) geometries.append(route_json["trips"][0]["geometry"]["coordinates"]) @@ -126,13 +143,15 @@ def cluster_and_optimize( times.append(eta_str) # Use the waypoint_index to reorder each route + for i, route in enumerate(routes): route2 = ["" for x in route] - for j, k in enumerate(route_waypoints[i][1:-1]): + start_index = 0 if (minimal and (bikes[i].target_clue != None)) else 1 # if starting route with first clue, first index of trip must be included + for j, k in enumerate(route_waypoints[i][start_index:-1]): route2[k["waypoint_index"] - 1] = route[j] routes[i] = route2 - return routes, geometries, times + return status, routes, geometries, times def __clues_to_string(points: [Clue]): @@ -199,7 +218,7 @@ def __get_trip_time( def __minimize_route_time_diff( - routes: [Clue], starts: [Point], end: Point, time_diff, n + routes: [Clue], bikes: [Bike], end: Point, minimal: bool, time_diff ): """ Takes a list of lists of coordinates, a list of start points, an end point, a time difference, and a number of routes @@ -210,17 +229,25 @@ def __minimize_route_time_diff( :param n: the number of routes :return: a list of lists of coordinates """ - times = [] + + if db.should_cancel_routing(): return -1 + + active_indices = [i for i in range(len(bikes)) if bikes[i].status != "DISABLED"] + starts = [ bike.target_clue if (minimal and (bike.target_clue != None)) else bike for bike in bikes ] # all bikes regardless of enabled + max_times = [ bike.timeTilDeadline()/3600 for bike in bikes if bike.status != "DISABLED"] + times = [ ] for i, route in enumerate(routes): + if bikes[i].status == "DISABLED": continue times.append( __get_trip_time( __clues_to_string(route), len(route), __clues_to_string([starts[i]]), __clues_to_string([end])[:-1], - ) + ) * bikes[i].time_modifier ) + if db.should_cancel_routing(): return -1 # Find the average trip time average_time = np.mean(times) @@ -237,18 +264,18 @@ def __minimize_route_time_diff( 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) + routes[active_indices[sorted_indices[0]]].append(closest_coordinate) + routes[active_indices[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) + return __minimize_route_time_diff(routes, bikes, end, minimal, time_diff) # 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: [Clue], start: Bike, end: Point, max_time + route_coordinates: [Clue], start: Bike, end: Point, max_time, start_already_set=False ): """ Takes a list of coordinates, a start point, an end point, and a maximum time and returns a list of coordinates @@ -258,6 +285,11 @@ def __remove_longest_waypoints( :param max_time: the maximum time :return: a list of coordinates """ + if len(route_coordinates) < 1: + return [] + + if start.status != "DISABLED" and start.target_clue != None: # already assigned a clue + start = start.target_clue # Find the trip time for the route route_time = __get_trip_time( __clues_to_string(route_coordinates), @@ -269,10 +301,11 @@ def __remove_longest_waypoints( # 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) + farthest_coordinates = __find_farthest_coordinates(route_coordinates, route_mean) + for farthest_coordinate in farthest_coordinates: + route_coordinates.remove(farthest_coordinate) - return __remove_longest_waypoints(route_coordinates, start, end, max_time) + return __remove_longest_waypoints(route_coordinates, start, end, max_time, start_already_set=True) return route_coordinates @@ -348,22 +381,34 @@ def __find_closest_coordinate(clues: [Clue], centroid: Point): return closest_coordinate -def __find_farthest_coordinate(clues: [Clue], centroid: Point): +def __find_farthest_coordinates(clues: [Clue], centroid: Point, n:int=1): """ Takes a list of coordinates and a centroid and returns the clue in the list that is farthest from the centroid :param clues: the list of coordinates :param centroid: the centroid :return: the clue in the list that is farthest from the centroid """ - farthest_coordinate = clues[0] - farthest_coordinate_distance = __distance(farthest_coordinate, centroid) - - for clue in clues: - if __distance(clue, centroid) > farthest_coordinate_distance: - farthest_coordinate = clue - farthest_coordinate_distance = __distance(clue, centroid) - - return farthest_coordinate + + farthest_coordinates = [] + + for _ in range(n): + farthest_coordinate = clues[0] + # remove only unrequired clues + i = 1 + while farthest_coordinate.required or (farthest_coordinate in farthest_coordinates): + farthest_coordinate = clues[i] + i += 1 + + farthest_coordinate_distance = __distance(farthest_coordinate, centroid) + + for clue in clues: + if __distance(clue, centroid) > farthest_coordinate_distance and (not clue.required) and (clue not in farthest_coordinates): + farthest_coordinate = clue + farthest_coordinate_distance = __distance(clue, centroid) + + farthest_coordinates.append(farthest_coordinate) + + return farthest_coordinates def __mean_center(clues: [Clue]): |