workington in progress

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]):