Using Nearest-Neighbor Algorithm to Optimize the Route - 1375 Words

Using Nearest-Neighbor Algorithm to Optimize the Route (Coursework Sample) Content: USING NEAREST-NEIGHBOR ALGORITHM TO OPTIMIZE THE ROUTEName of the Student:Name of the Institution:Discussion:What are your favourite problem solving strategies, what works for you and what doesnt work? How do you approach the problem quantitative or qualitative? What is your weakest problem solving area?Re: DiscussionBy DanielOperation research improves the business efficiency. An observation I have made in this chapter is that Nearest Neighbour algorithm and sorted edge algorithm are almost similar technique the only difference is that Sorted edges algorithm first sort the edges and then a start point is chosen based on the least weighted edge whereas in the Nearest-neighbour algorithm one can start in any vertex and the other steps are similar. More understanding will be coming as I study the course.Re: DiscussionBy JosephWow, what an observation Daniel, since mathematical science aims at improving the business efficiency by always optimizing the cost that why all t he techniques leans on greedy algorithm and thats where similarities comes from, always minimizing the cost.My favourite problem solving strategies is first understanding the problem which I am facing in depth. Then I do research on various people who were faced with the same problem and how they solved their problem. There are many platforms given to use on which people can post their problem and people can respond to them. My favourite platform is , you can find most of the problem handled, this definitely works for me. What doesnt work for me is trying to memorize or cramming what people did to solve their problem instead I work on my creativity and work it out on my own based on the knowledge acquired from the research made. I approach quantitative and qualitative problem differently. I work on qualitative problem easily because they dont involve a lot of calculation whereas quantitative problem is my best I deal with them step by step, thus making my analysis easier.My weakest problem solving area is in transforming a map into a graph so that I can apply various techniques involved in calculating the optimal route between different points in the graph. The problem which I was recently faced with was when I was trying to determine a route between different point using a nearest-neighbour technique without traversing any vertex twice especially when five vertices are involved. I have not yet realized a way of solving it.Re: DiscussionBy DanielThank you, Joseph, for the information. It is good to know how you deal with the problems you encounter. About the problem, you encountered when you were using nearest-neighbour technique. If you encounter any route that doesnt follow the algorithm given, you can easily make an assumption that the route involved is not optimal since it will involve more weighted edges than necessary. Therefore, you should consider the other routes.Re: DiscussionBy BrianThank you, Daniel and Joseph, for posting. I have also been taking this course. What is the difference between Minimum-Cost Hamiltonian circuit and minimum cost spanning tree? I find them similarRe: DiscussionBy DanielHi Brian,Its good to know, you are benefiting through this discussion board. Both Minimum-cost Hamiltonian circuit and Minimum cost spanning tree aims at finding the optimal route i.e. determining the minimum value. The Difference between them is that Minimum spanning tree deals with sorted edges and then Kruskals algorithm is applied whereas Minimum Hamiltonian circuit generates all the Hamiltonian tours and then after adding up the edges. A tour with minimum distance is chosen.Re: DiscussionBy BrianThank you for posting Daniel, now I have more insight about the difference between the two. If I may ask another Why does travelling salesman problem considered to be Hamiltonian circuit?Re: DiscussionBy DanielThank you for the question, travelling salesman problem involves finding the trip of minimum cost that a salesman can visit the c ities in sales territory once and only once, starting and ending the trip in the same city. This is what makes it a Hamiltonian circuit. You can find more information on1. The graph below shows 5 major cities in Texas i.e. Dallas, Austin, Houston, Galveston and Beaumont and their distances.left28765500CONNECTION DISTANCE Dallas-Austin 283.4 km Dallas-Beaumont 394.5 km Dallas- Houston 362 km Austin-Galveston 308.1 km Beaumont-Houston 125.5 km Beaumont-Galveston 110.3 Houston-Galveston 77.3 Austin-Beaumont 349.5 A table showing distance between the citiesfig 1.12. Using Nearest-Neighbor technique to determine the optimal route and cost spent(a) Using Dallas as the starting point (Tour 1)CONNECTION DISTANCE Dallas-Austin 283.4 km Dallas-Beaumont 394.5 km Dallas- Houston 362 km Austin-Galveston 308.1 km Beaumont-Houston 125.5 km Beaumont-Galveston 110.3 km Houston-Galveston 77.3 km Austin-Beaumont 349.5 km Fig 1.2The red squiggly line shows the route from Dallas Houston Galveston Aus tin- BeaumontThe total distance Covered283.4+301.1+77.3+125.5+394.5 = 1181.8kmCONNECTION DISTANCE Dallas-Austin 283.4 km Dallas-Beaumont 394.5 km Dallas- Houston 362 km Austin-Galveston 308.1 km Beaumont-Houston 125.5 km Beaumont-Galveston 110.3 km Houston-Galveston 77.3 km Austin-Beaumont 349.5 km (b) Using Austin as the Starting point (Tour 2)Fig1.3The blue squiggly line shows the route from Austin- Dallas- Houston-Galveston- Beaumont- Austin.The total distance covered: 283.4+362+77.3+110.3+349.5 = 1182.5kmCONNECTION DISTANCE Dallas-Austin 283.4 km Dallas-Beaumont 394.5 km Dallas- Houston 362 km Austin-Galveston 308.1 km Beaumont-Houston 125.5 km Beaumont-Galveston 110.3 km Houston-Galveston 77.3 km Austin-Beaumont 349.5 km (c) Using Houston as the starting point (Tour 3)Fig 1.4The purple squiggly line shows the route from Houston- Galveston- Beaumont- Austin- Dallas-HoustonThe total distance covered = 77.3+110.3+349.5+283.4+362 = 1182.5km(d)Using Galveston as the starting point ( Tour 4)CONNECTION DISTANCE Dallas-Austin 283.4 km Dallas-Beaumont 394.5 km Dallas- Houston 362 km Austin-Galveston 308.1 km Beaumont-Houston 125.5 km Beaumont-Galveston 110.3 km Houston-Galveston 77.3 km Austin-Beaumont 349.5 km Starting from Galveston is impossible to use the nearest-neighbor technique without breaking the algorithm since you can only visit Beaumont more than 2 times for you to reach Galveston and close the circuit.Fig 1.5Total Distance covered: 77.3+125.5+349.5+283.4+394.5+110.3 = 1340.5kmCONNECTION DISTANCE Dallas-Austin 283.4 km Dallas-Beaumont 394.5 km Dallas- Houston 362 km Austin-Galveston 308.1 km