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$)$

$210$

$312$

$49$

$57$

$615$

$75$

$811$

$913$

$104$

$($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 Q$2($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.