(Solved): Individual Project: Question 1&2 Question 1. Consider the 10 -city travelling salesman problem ...
Individual Project: Question 1&2 Question 1. Consider the 10 -city travelling salesman problem (TSP) whose links have associated distances in the following table (Table 1). Assume City 1 as the home city (depot) and rest of the cities are customer locations. (a) By considering City 1 as the home city (depot) and rest of the cities are customer locations, perform the following three tasks. (i) Apply the Nearest Neighbourhood heuristic method to the above problem to generate a TSP tour. (ii) Produce an alternative TSP tour that exists. Briefly comment on the results of both tours. (iii) Use the Clarke & Wright sequential procedure to the above problem to find a TSP tour. (iv) Briefly comment on the solution quality as compared to the solution obtained in (i). (v) Use Lin's 2-opt heuristic method to check whether the solution produced in (ii) can be improved. (vi) Briefly comment on the 2-opt solution comparing the solutions obtained in (i) and (iii) above. Question 2. Consider the distance matrix in Table 1 of Question 1 for the following Vehicle Routing Problem (VRP). Where City 1 is the depot and rest of the cities are customer locations with known demands. All vehicles leave and terminate at the depot. There are 2 lorries available, each with 50-ton capacity. (Assume there are no restrictions on driver-time or the distance travelled by each vehicle.) Also consider the following customer demand information. Cities (customers) Requirements (in tons) 2 10 3 12 4 9 5 7 6 15 7 5 8 11 9 13 10 4 (i) Solve the above VRP using the Clarke & Write sequential method (you may use the list of savings found in Question 1(a)(iii)) to satisfy the customer demand at a minimum total distance travelled the lorries subject to the given constraints. List the sequences of customers in the routes and their distances. Calculate total distance travelled by the lorries. (ii) By looking at the results obtained in Q2(i) above briefly describe why the total distance travelled by two lorries is greater than the distance of the TSP tour produced by C&W method. (iii) Provide a brief description of a real-life VRP application that fits with the above scenario.
