**Robo-Pizzeria Drone Delivery Route Optimization**Welcome to the Robo-Pizzeria educational module! Here, we will explore how to plan an optimal delivery route for drones used to deliver pizzas to various locations in a two-dimensional plane. **Key Features of the Business Model:**- **Direct Flight Capability**: Drones can fly directly to any location. The travel time is proportional to the distance between locations.- **Location Points**: Delivery locations are given as points in a 2-dimensional plane. The Robo-Pizzeria is located at the origin (0,0).**Problem Statement:**The task is to plan the route for the drone to deliver pizzas to \( n \) locations efficiently. The route should start from Robo-Pizzeria, visit all delivery locations, and return to the starting point while minimizing the total travel distance.Let's explore the steps and methodologies to solve this problem.**a) Converting Delivery Locations to a Complete Weighted Graph:**Consider four delivery locations represented by the following coordinates:\[\{ (1, 1), (-2, -1), (2, 1), (-3, 5) \}\]To convert these locations into a complete weighted graph with five nodes (including the Robo-Pizzeria at the origin), we need to state the adjacency matrix for the graph. Since the graph is undirected, only the upper triangle of the matrix is needed.**b) Graph Conversion Procedure:**To convert an arbitrary set of \( n \) delivery points (including the origin) into a complete weighted graph \( G = (V, E) \) with \( n + 1 \) nodes, the following steps can be used:1. Create a node for each delivery location and the origin.2. Compute the Euclidean distance between every pair of nodes.3. Construct the adjacency matrix with these distances as weights.**c) Minimum Cost Route Problem Formalization:**The problem of finding the minimum cost route for the drone can be formalized as a graph problem with both input and output criteria:- **Input**: A complete weighted graph \( G = (V, E) \) with \( n + 1 \) nodes.- **Output**: A Hamiltonian circuit (route that visits each node exactly once and returns to the starting point) with the minimum possible cost (total distance).**d) Brute Force Approach:**Bob has begun using a brute force algorithm to try all

a) We have n = 5 locations (including the Robo-Pizzeria) at coordinates {(0, 0), (1, 1), (-2, -1),…

You, Alice and Bob manage "Robo-Pizzeria" a company that uses drones to deliver pizza. Here are some important features of your business model: • Drones can fly directly to a location so the time it takes to travel to a location is proportional to the distance between the two locations. • Delivery locations are given as points in a 2-dimensional plane. The Robo-Pizzeria is located at the origin (0,0). The first problem you are trying to solve is planning the route for your drone to follow while delivering pizzas to n locations. The route must leave from the Robo-Pizzeria, visit all locations, and return while travelling the minimum total distance. a) Show how you can turn these 4 delivery locations into a complete weighted graph with 5 nodes (including the Robo-Pizzeria at the origin) by stating the adjacency matrix for the graph. {(1, 1), (-2,-1), (2, 1), (-3,5)} (Since the graph is undirected you only need to state the upper triangle of the matrix.) b) Now describe the procedure you followed so that you could convert an arbitrary set of n delivery points (and the origin) into a complete weighted graph G = {V, E) with n + 1 nodes. c) Formalize the problem of finding the minimum cost route for your drone as a graph problem with input and output criteria. d) Bob has begun carrying out a brute force algorithm trying all possible paths from the Robo-Pizzeria and back again for the example graph. Help him by listing all 24 possible routes and the cost of each route. (Hint: I used a spreadsheet to help with this step.) e) Alice notices that this problem is very similar to the well known Travelling Salesper- son Problem. This problem has no known solutions that take a reasonable amount of time. However, it does have some efficient approximation algorithms. Alice has found one that works as follows: • First, compute a minimum spanning tree of the input graph. • Visit nodes in order of the depth-first traversal of the tree (starting at any node). Perform this algorithm on your input graph (show your work). What order should you visit the locations and what is the total distance travelled by the drone? Did your algorithm find an optimal path?