Fleet-Optimizer.py

# -*- coding: utf-8 -*-
"""NextEra-DRP.ipynb

Automatically generated by Colab.

Original file is located at
    https://colab.research.google.com/drive/17o_zZZvKcvSH7MU0m90RSkDsXPsT35uW
"""

# NextEra Energy Drone Optimization Challenge

# Welcome to the NextEra Energy Drone Optimization Challenge at UCF!

pip install ortools shapely

# importing all the libraries:
import numpy as np
from ortools.constraint_solver import pywrapcp, routing_enums_pb2
from shapely import wkt
import matplotlib.pyplot as plt
import geopandas as gpd

# uploading all files to google colab:
from google.colab import files
uploaded = files.upload()

# loading all the files:
assets = np.load("asset_indexes.npy")
distance_matrix = np.load("distance_matrix.npy")
photos = np.load("photo_indexes.npy")
points_lat_long = np.load("points_lat_long.npy")
predecessors = np.load("predecessors.npy")
waypoint_data = np.load("waypoint_indexes.npy")
with open("polygon_lon_lat.wkt") as f:
    polygon = wkt.loads(f.read())

# starting the processing of DRP:
def create_data_model(distance_matrix):
  data = {}
  scaled_matrix = np.round(distance_matrix).astype(int)
  data["distance_matrix"] = scaled_matrix
  data["num_of_drones"] = 1
  data["scaling_factor"] = 1.0
  data["depot"] = 0  # default

  return data

# creating a routing model using ortools:
def solve_DRP(data, max_distance_allowed):
  manager = pywrapcp.RoutingIndexManager(
      len(data["distance_matrix"]),
      data["num_of_drones"],
      data["depot"]
  )

  routing = pywrapcp.RoutingModel(manager)

  def distance_callback(from_index, to_index):
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return data["distance_matrix"][from_node][to_node]

  transit_callback_index = routing.RegisterTransitCallback(distance_callback)
  routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

  scaling_factor = data["scaling_factor"]
  scaled_max_distance = int(max_distance_allowed / scaling_factor)

  routing.AddDimension(
      transit_callback_index,
      0,                      # no slack
      scaled_max_distance,    # scaled maximum route distance
      True,                   # start cumul to zero
      "Distance",
  )

  distance_dimension = routing.GetDimensionOrDie("Distance")

  # Skip penalty
  skip_penalty = 20000
  for node in range(1, len(data["distance_matrix"])):  # exclude depot
    routing.AddDisjunction([manager.NodeToIndex(node)], skip_penalty)

  search_parameters = pywrapcp.DefaultRoutingSearchParameters()
  search_parameters.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
  search_parameters.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
  search_parameters.time_limit.seconds = 20

  solution = routing.SolveWithParameters(search_parameters)

  if not solution:
    print("No solution anymore")
    return

  # extract route information:
  route = []
  route_distance = 0
  index = routing.Start(0)

  while not routing.IsEnd(index):
    route.append(manager.IndexToNode(index))
    prev_index = index
    index = solution.Value(routing.NextVar(index))
    route_distance += routing.GetArcCostForVehicle(prev_index, index, 0)
  route.append(manager.IndexToNode(index))

  # unscaled route distance
  unscaled_route_distance = route_distance * scaling_factor
  visited_nodes = len(route) - 2  # excluding depot start & end
  cost_factor = unscaled_route_distance / max(1, visited_nodes)

  print(f"Visited Nodes: {visited_nodes}")
  print(f"Route: {route}")

  return route, unscaled_route_distance

# function to modify distance_matrix:
def modify_dist_matrix(dist_matrix, route):
  if not route:
    return dist_matrix
  if not isinstance(dist_matrix, np.ndarray):
    dist_matrix = np.array(dist_matrix)
  LARGE = 10_000_000
  for node in route:
    if node != 0:
      dist_matrix[:, node] = LARGE
      dist_matrix[node, :] = LARGE
  return dist_matrix

def visualize_mission_route(route, mission_number):
    poly_geom = polygon
    poly_x, poly_y = poly_geom.exterior.xy
    route_x = [points_lat_long[i, 0] for i in route]  # x = longitude
    route_y = [points_lat_long[i, 1] for i in route]  # y = latitude

    plt.figure(figsize=(8, 8))

    # Fly Zone
    plt.fill(poly_x, poly_y, color="lightblue", alpha=0.3, label="Fly Zone")
    plt.plot(poly_x, poly_y, color="blue", linewidth=1.0)

    # Route Path
    plt.plot(route_x, route_y, '-', color="red", linewidth=1.5, alpha=0.8, label=f"Mission {mission_number}")

    # Add direction arrows
    for i in range(len(route_x) - 1):
        plt.arrow(
            route_x[i], route_y[i],
            route_x[i + 1] - route_x[i],
            route_y[i + 1] - route_y[i],
            shape='full',
            lw=0,
            length_includes_head=True,
            head_width=0.0002,  # adjust based on coordinate scale
            color='red',
            alpha=0.7
        )

    # Mark start (green) and end (blue)
    plt.scatter(route_x[0], route_y[0], color='green', s=80, label='Start (0)', zorder=5)
    plt.scatter(route_x[-1], route_y[-1], color='blue', s=80, label='End (0)', zorder=5)

    # Mark intermediate waypoints
    plt.scatter(route_x[1:-1], route_y[1:-1], color='red', s=40, zorder=4)

    plt.title(f"Mission {mission_number} Route Visualization", fontsize=12, weight="bold")
    plt.xlabel("Longitude")
    plt.ylabel("Latitude")
    plt.legend()
    plt.grid(True, linestyle="--", alpha=0.5)
    plt.axis("equal")
    plt.tight_layout()
    plt.show()

# main function which iteratively runs:
def main():

  final_distance_travel = 0

  max_distance_allowed = 37725
  data = create_data_model(distance_matrix)

  total_number_of_nodes = len(data["distance_matrix"])
  nodes_left = total_number_of_nodes - 1
  missions = 0
  flag = False

  while nodes_left > 0:
    print(f"\n\nMission - {missions+1}")
    print(f"Nodes Left: {nodes_left}")
    route, path_cost = solve_DRP(data, max_distance_allowed)
    final_distance_travel += path_cost
    visualize_mission_route(route, missions+1)
    nodes_left -= (len(route) - 2)
    data["distance_matrix"] = modify_dist_matrix(data["distance_matrix"], route)
    missions += 1

  print(f"Total Number of Missions: {missions}")
  print(f"Total Number of Nodes Visited: {total_number_of_nodes - 1}")
  print(f"Total Number of Nodes Left to visit: {nodes_left}")
  print(f"Total distance travelled: {final_distance_travel}")

main()

# [
# mission_time - [10,  20,  30,  40,  50,  60,  70,  80,  90,  100,  110,  120]
# total_distance - [406605.0,  383160.0,  381606.0,  381823.0,  380770.0,  377158.0,  377131.0,  376523.0,  385868.0,  384845.0,  388482.0,  380787.0]
# number_of_missions - [12,  12,  11,  11,  11,  11,  11,  11,  11,  11,  11,  11]
# ]

# Data
mission_time = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120]
total_distance = [406605.0, 383160.0, 381606.0, 381823.0, 380770.0, 377158.0,
                  377131.0, 376523.0, 385868.0, 384845.0, 388482.0, 380787.0]
number_of_missions = [12, 12, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11]

# Create figure
fig, ax1 = plt.subplots(figsize=(9, 5))

# Plot total distance (left axis)
color = 'tab:red'
ax1.set_xlabel('Solver Time per Iteration (seconds)')
ax1.set_ylabel('Total Distance Covered', color=color)
ax1.plot(mission_time, total_distance, '-o', color=color, label='Total Distance')
ax1.tick_params(axis='y', labelcolor=color)

# Create second y-axis for missions
ax2 = ax1.twinx()
color = 'tab:blue'
ax2.set_ylabel('Number of Missions', color=color)
ax2.plot(mission_time, number_of_missions, '-s', color=color, label='Missions')
ax2.tick_params(axis='y', labelcolor=color)

# Styling
fig.suptitle('Effect of Solver Time on Route Optimization', fontsize=13, weight='bold')
fig.tight_layout()
plt.grid(True, linestyle='--', alpha=0.6)

# Add combined legend
lines, labels = ax1.get_legend_handles_labels()
lines2, labels2 = ax2.get_legend_handles_labels()
ax1.legend(lines + lines2, labels + labels2, loc='best')

plt.show()