Your younger brother has just gotten a job as a newspaper de

Your younger brother has just gotten a job as a newspaper delivery boy, and every morning he will ride his bike to the 5 neighborhoods he is assigned to and make his deliveries. Being a generous sibling, you decide to help him order the neighborhoods he has to visit so he can minimize his delivery time. The table below shows the time, in minutes, for your brother to ride his bike between each pair of neighborhoods.

a) Write the optimization model for the TSP (traveling saleman problem) using the problem data. You do not have to write all of the subtour elimination constraints – 3 is sufficient.

b) Use nearest and farthest insertion TSP heuristics to compute a tour from your house to all of the neighborhoods and back that (nearly) minimizes the total time your brother will spend on his route each day. Show each of your iterations.

c) Which tour of the two above (if they are different) would you recommend using? What is its total time?

d) Suppose it will take your brother 15 minutes to deliver the papers in each of the neighborhoods. How much total time (travel and unloading) is required to complete your proposed tour?

e) Implement the nearest neighbor and cheapest insertion heuristics and compare their solutions to the one you chose in this problem

505250 N31-234 NS 30 35 40 400-50-44 NT 10-11 50-40 5 3528053 2500812 N2105-2 0 05500 m|1|2|3|4|5

Solution

The shortest path to cover all is to start with N4

1.Home to N4= 10 min

2.N4 to N3 = 5 min

3.N3 to N2 = 8 min

4.N2 to N1 = 10 min

5.N1 to N5 = 15 min

Total time = 10+5+8+10+15 = 48 min