diff options
Diffstat (limited to 'dashboard_website/router.py')
| -rw-r--r-- | dashboard_website/router.py | 140 |
1 files changed, 107 insertions, 33 deletions
diff --git a/dashboard_website/router.py b/dashboard_website/router.py index 70af4c6..385cbae 100644 --- a/dashboard_website/router.py +++ b/dashboard_website/router.py @@ -101,33 +101,37 @@ def cluster_and_optimize( # 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) + if (bike.status != "DISABLED") and (bike.target_clue != None): + #routes[i].append(bike.target_clue) + print("Already assigned clue at: ", bike.target_clue) + already_assigned_clues.append(bike.target_clue) + for clue in clues: + if clue.assigned_team != 0 and ((clue.assigned_team-1) in active_indices) and (clue not in already_assigned_clues): + routes[clue.assigned_team - 1].append(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) + routes, times = __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)): - resp = __remove_longest_waypoints(routes[i], bikes[i], end, max(bikes[i].timeTilDeadline()/3600, max_max_time)) - if resp == -1: - return -1, [], [], [] - routes[i] = resp + #for i in range(len(routes)): + # resp = __remove_longest_waypoints(routes[i], bikes[i], end, max(max_max_time, bikes[i].timeTilDeadline()/3600), minimal) + # if resp == -1: + # return -1, [], [], [] + # routes[i] = resp + clue_pool = [] + routes = __balance_waypoints(routes, bikes, end, times, clue_pool, max_max_time, minimal) + if routes == -1: + return -1, [], [], [] # Get the json of the routes route_waypoints = [] @@ -151,8 +155,10 @@ def cluster_and_optimize( for i, route in enumerate(routes): route2 = ["" for x in route] 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]): + for j, k in enumerate(route_waypoints[i][1:-1]): route2[k["waypoint_index"] - 1] = route[j] + if (minimal and (bikes[i].target_clue != None)): + route2.insert(0, bikes[i].target_clue) routes[i] = route2 return status, routes, geometries, times @@ -184,7 +190,7 @@ def __get_json(coordinate_string, start, end): + start + coordinate_string + end - + "?roundtrip=false&source=first&destination=last&geometries=geojson&overview=full" + + "?roundtrip=false&source=first&destination=last&geometries=geojson&overview=full&exclude=ferry" ) coordinates = coordinates.json() @@ -208,7 +214,7 @@ def __get_trip_time( + start + coordinate_string + end - + "?roundtrip=false&source=first&destination=last" + + "?roundtrip=false&source=first&destination=last&exclude=ferry" ) coordinates = coordinates.json() @@ -266,9 +272,9 @@ def __minimize_route_time_diff( if time_difference > time_diff: # Move a coordinate from the longest route to the shortest route for _ in range(max(1,int(time_difference/0.12))): # roughly estimate how many points must be moved to equalize - closest_coordinate = __find_closest_coordinate( + closest_coordinate = __find_closest_coordinates( routes[active_indices[sorted_indices[-1]]], __mean_center(routes[sorted_indices[0]]) - ) + )[0] routes[active_indices[sorted_indices[0]]].append(closest_coordinate) routes[active_indices[sorted_indices[-1]]].remove(closest_coordinate) @@ -276,11 +282,67 @@ def __minimize_route_time_diff( 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 + return routes, times + +def __balance_waypoints( + routes: [Clue], bikes: [Bike], end: Point, times, clue_pool: [Clue], max_time, minimal +): + """ + 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 + """ + + 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 = [ max(bike.timeTilDeadline()/3600, max_time) for bike in bikes ] + time_balances = [ (max_times[i] - times[i]) for i in range(len(times))] + + balanced = True + for balance in time_balances: + if balance < 0: + balanced = False + break + if balanced: + return routes + # shorten too-long routes + for i, time_balance in enumerate(time_balances): + print(i, time_balance) + if time_balance < 0: # route too long + route_mean = __mean_center(routes[active_indices[i]]) + farthest_coordinates = __find_farthest_coordinates(routes[active_indices[i]], route_mean, max(1,min(int(-1*time_balance/0.12),int(len(routes[active_indices[i]])*0.75)))) + for farthest_coordinate in farthest_coordinates: + routes[active_indices[i]].remove(farthest_coordinate) + clue_pool.append(farthest_coordinate) + # lengthen routes with spare room + for i, time_balance in enumerate(time_balances): + if time_balance > 0.15: # route too short + route_mean = __mean_center(routes[active_indices[i]]) + closest_coordinates = __find_closest_coordinates(clue_pool, route_mean, 1) + for closest_coordinate in closest_coordinates: + routes[active_indices[i]].append(closest_coordinate) + clue_pool.remove(closest_coordinate) + + for i, route in enumerate(routes): + if bikes[i].status == "DISABLED": continue + if db.should_cancel_routing(): return -1 + times[active_indices[i]] = __get_trip_time( + __clues_to_string(route), + len(route), + __clues_to_string([starts[i]]), + __clues_to_string([end])[:-1], + ) * bikes[i].time_modifier + + return __balance_waypoints(routes, bikes, end, times, clue_pool, max_time, minimal) + def __remove_longest_waypoints( - route_coordinates: [Clue], start: Bike, end: Point, max_time, start_already_set=False + route_coordinates: [Clue], start: Bike, end: Point, max_time, minimal, 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 @@ -297,7 +359,7 @@ def __remove_longest_waypoints( print(max_time) - if start.status != "DISABLED" and start.target_clue != None: # already assigned a clue + if minimal and (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( @@ -315,11 +377,13 @@ def __remove_longest_waypoints( for farthest_coordinate in farthest_coordinates: route_coordinates.remove(farthest_coordinate) - return __remove_longest_waypoints(route_coordinates, start, end, max_time, start_already_set=True) + return __remove_longest_waypoints(route_coordinates, start, end, max_time, minimal, start_already_set=True) return route_coordinates + + def __normalize_points(clues: [Clue], bikes: [Bike]): """ Takes a list of coordinates and a list of centroids and returns a list of normalized coordinates and a list of @@ -372,23 +436,34 @@ def __min_max_normalize(value, min_value, max_value): return (value - min_value) / (max_value - min_value) -def __find_closest_coordinate(clues: [Clue], centroid: Point): +def __find_closest_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 closest to the centroid :param clues: the list of coordinates :param centroid: the centroid :return: the clue in the list that is closest to the centroid """ + # Convert the clues to a list of points - closest_coordinate = clues[0] - closest_coordinate_distance = __distance(closest_coordinate, centroid) + closest_coordinates = [] + for _ in range(min(n, len(clues))): + closest_coordinate = clues[0] + # remove only unrequired clues + i = 1 + while closest_coordinate in closest_coordinates: + closest_coordinate = clues[i] + i += 1 - for clue in clues: - if __distance(clue, centroid) < closest_coordinate_distance: - closest_coordinate = clue - closest_coordinate_distance = __distance(clue, centroid) + closest_coordinate_distance = __distance(closest_coordinate, centroid) - return closest_coordinate + for clue in clues: + if __distance(clue, centroid) < closest_coordinate_distance and (clue not in closest_coordinates): + closest_coordinate = clue + closest_coordinate_distance = __distance(clue, centroid) + + closest_coordinates.append(closest_coordinate) + + return closest_coordinates def __find_farthest_coordinates(clues: [Clue], centroid: Point, n:int=1): @@ -400,8 +475,7 @@ def __find_farthest_coordinates(clues: [Clue], centroid: Point, n:int=1): """ farthest_coordinates = [] - - for _ in range(n): + for _ in range(min(len(clues),n)): farthest_coordinate = clues[0] # remove only unrequired clues i = 1 |