Does anyone know how to do the matlab coding of this?

A local delivery service in Western Mass has hired you to improve their profit margins. Specifically, based on a list of deliveries for each day, you job is to plan a route that minimizes the distance traveled, thereby saving on fuel costs. Every route starts at the warehouse, runs through various delivery destinations, and returns to the warehouse. You do not double back or revisit a destination on any given route. Your task is to write a code that takes the locations for each days deliveries and determines the optimal route

Lets start with an example. Suppose you wish to cover just five destinations in the area. Constructing a route requires keeping the end points fixed the warehouse (destination #1) and creating permutations of the other labels 2-5:

1->2->3->4->5->1

1->2->4->3->5->1

1->5->4->2->3->1

In all, since there are 4 labels 2, 3, 4, 5 to be permuted, the total number of trips is 4*3*2*1=4!=24. Of course, if we naively permute the labels, each trip is also counted in reverse 1->2->3->4->5->1

is the same as 1->5->4->2->3->1 and so the actual number of unique trips is 24/2=12.

You have probably guessed by now that as we increase the number of stops, your problem gets out of hand very quickly. For example, with 5 stops, you had 4!/2=12 unique trips. In general, with N stops, you will have (N-1)!/2 unique trips. So, if you double the number of stops from 5 to 10, you will have 9!/2= 181,440 trips; if you increase this to 20 stops, you have 19!/2= 60,822,550,204,416,000 unique trips!! Brute force counting is clearly not the way to go for real-life problems. Yet, for this toy problem, we will adopt the brute force approach and see how far we can get.

Your code will consist of two parts, one script and one local function (at minimum). You can create as many subfunctions as you wish; just be sure to put them all below (or within) the local function. I have provided an m-file script to get you started. In this file, you can see that I have defined a matrix called coord that has the x and y coordinates of N destinations. Some sample values are provided for N=5. The first row of coord is the location of destination #1, the second row is destination #2, and so on. A route that went in order would be [1 2 3 4 5 1]. Your job is to write a function that has coord as an input, and two outputs [minDist, optRoute]. minDist is the minimum distance of all possible routes (i.e., the optimal route distance) which is a scalar; optRoute is the corresponding optimal route (e.g., [1 4 3 5 2 1]), which is a vector. Your function should be general and run for any number of destinations defined by the coord matrix.

Your function should do the following: 1. Using the destination coordinates, which are the input to the function, create a distance matrix, an NxN matrix in which each element is the distance between two destinations. So for example, the (1,2) element is the distance between destinations 1 and 2, the (3,5) element is the distance between destinations 3 and 5, etc. The diagonal of this matrix is zero (distance from a destination to itself is 0), and it is a symmetric matrix (distance from destination 2 to 4 is the same as 4 to 2). Use for loop(s) to create this matrix. Remember, it should work for any input coordinates. For the example coordinates in the script file, the distance matrix is pasted below:

0 10.0000 22.3607 22.3607 44.7214

10.0000 0 14.1421 20.0000 50.0000

22.3607 14.1421 0 14.1421 64.0312

22.3607 20.0000 14.1421 0 67.0820

44.7214 50.0000 64.0312 67.0820 0

Next, create a matrix containing all possible routes, with each row being a particular route, e.g., 1 2 4 3 5 1. Remember that every route must start at 1 and end at 1, and no destination may be revisited in a given route. Before doing this section, remind yourself how many routes are possible (described above). This step can be completed relatively easily using the perms command. For our working example, the permutation matrix is given below. perms simply returns all permutations, so a route basically appears twiceforward and in reverse; dont worry about this for now. Heres the permutation matrix for 5 destinations:

1 5 4 3 2 1

1 5 4 2 3 1

1 5 3 4 2 1

1 5 3 2 4 1

1 5 2 3 4 1

1 5 2 4 3 1

1 4 5 3 2 1

1 4 5 2 3 1

1 4 3 5 2 1

1 4 3 2 5 1

1 4 2 3 5 1

1 4 2 5 3 1

1 3 4 5 2 1

1 3 4 2 5 1

1 3 5 4 2 1

1 3 5 2 4 1

1 3 2 5 4 1

1 3 2 4 5 1

1 2 4 3 5 1

1 2 4 5 3 1

1 2 3 4 5 1

1 2 3 5 4 1

1 2 5 3 4 1

1 2 5 4 3 1

3. Using the distance matrix and the permutation matrix, use for loop(s) to calculate the length of each route.

4. Report the minimum distance and the optimal route; use informative text. For our example, the shortest route is 145.37 miles and is either [1 5 2 3 4 1] or [1 4 3 2 5 1] (route in reverse).

5. Return necessary outputs to the script

Having received the necessary information from the function your script should:

6. Plot the (x, y) coordinates of the destinations using any legible symbols of your choice and connect the destinations to show the optimal route. Label axes/use legible fonts/add titles/

7. Once you are done, test out your function to see if you can reproduce my data. Then, comment out my coordinates and uncomment the next section to generate an arbitrary number of random destinations. Try this out for different values of N you are allowed to hard-code this value.

8. In a comment at the bottom of your script, discuss how the computation time varies versus N. Is there an upper limit to the value of N that is realistic for your code and computer (start small and work your way up)?