Using Nearest-Neighbor Algorithm to Optimize the Route (Coursework Sample)

USING NEAREST-NEIGHBOR ALGORITHM TO OPTIMIZE THE ROUTE
Name of the Student:
Name of the Institution:
Discussion:
What are your favourite problem solving strategies, what works for you and what doesn’t work? How do you approach the problem quantitative or qualitative? What is your weakest problem solving area?
Re: Discussion
By Daniel
Operation 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: Discussion
By Joseph
Wow, what an observation Daniel, since mathematical science aims at improving the business efficiency by always optimizing the cost that why all the techniques leans on greedy algorithm and that’s 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 doesn’t 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 don’t 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: Discussion
By Daniel
Thank 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 doesn’t 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: Discussion
By Brian
Thank 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 similar
Re: Discussion
By Daniel
Hi Brian,
It’s 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 Kruskal’s 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: Discussion
By Brian
Thank 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: Discussion
By Daniel
Thank you for the question, travelling salesman problem involves finding the trip of minimum cost that a salesman can visit the cities 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 on
1. The graph below shows 5 major cities in Texas i.e. Dallas, Austin, Houston, Galveston and Beaumont and their distances.
left28765500
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

Houston-Galves
ton

77.3

Austin-Beaumont

349.5

A table showing distance between the citiesfig 1.1
2. 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.2
The red squiggly line shows the route from Dallas –Houston – Galveston – Austin- Beaumont
The total distance Covered
283.4+301.1+77.3+125.5+394.5 = 1181.8km
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

(b) Using Austin as the Starting point (Tour 2)
Fig1.3
The 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.5km
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

(c) Using Houston as the starting point (Tour 3)
Fig 1.4
The purple squiggly line shows the route from Houston- Galveston- Beaumont- Austin- Dallas-Houston
The 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.5
Total Distance covered: 77.3+125.5+349.5+283.4+394.5+110.3 = 1340.5km
CONNECTION

DISTANCE

Dallas-Austin

283.4 km

Dallas-Beaumont

394.5 km

Dallas- Houston

362 km

Austin-Galveston

308.1 km