$\mathbf { 5 }$ & 4 & - & - & 2 \\
\hline


\begin{enumerate}[label=(\roman*)]
\item Draw the complete 5-node network of shortest times. (You are not required to use an algorithm to find the shortest times.)
\item Write down the final time matrix and the final route matrix for the complete 5 -node network. (You do not need to apply Floyd's algorithm.)
\item (A) Apply the nearest neighbour algorithm to the complete 5-node network of shortest times, starting at node 1. Give the time for the cycle you produce.\\
(B) Starting at node 3, a possible cycle in the complete 5-node network of shortest times is $\mathbf { 3 2 1 5 4 3 . }$ Give the actual cycle to which this corresponds in the incomplete 5-node network of journey times.
\item By deleting node 5 and its arcs from the complete 5 -node network of shortest times, and then using Kruskal's algorithm, produce a lower bound for the solution to the associated practical travelling salesperson problem. Show clearly your use of Kruskal's algorithm.
\item In the incomplete 5-node network of journey times, find a quickest route starting at node $\mathbf { 5 }$ and using each of the 7 arcs at least once. Give the time of your route.

4 Helen has a meeting to go to in London. She has to travel from her home in G on the south coast to KC in London. She can drive from G to the west to A to catch a train, or she can drive to the east to W to catch a train on a different line. From both A and W she can travel to mainline terminuses V or LB in London. She will then travel by tube either from V to KC , or from LB to KC .

The times for the various steps of her journey are shown in the tables. Both train services and tube services are subject to occasional delays, and these are modelled in the tables.

\begin{center}
\begin{tabular}{ | l | c | c | }
\hline
Driving times & to A & to W \\
\hline
From G & 20 min & 15 min \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
\multirow{2}{*}{Train journey} & \multicolumn{3}{|l|}{To V} & \multicolumn{3}{|l|}{To LB} \\
\hline
 & normal time & probability of delay & delay & normal time & probability of delay & delay \\
\hline
From A & 1 hr 40 min & 0.05 & 10 min & 1 hr 45 min & 0.05 & 10 min \\
\hline
From W & 1 hr 30 min & 0.10 & 20 min & 1 hr 35 min & 0.10 & 20 min \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ | l | c | c | c | }
\hline
\multirow{2}{*}{\begin{tabular}{ l }
Tube \\
journey \\
\end{tabular}} & \multicolumn{3}{|l|}{To KC} \\
\cline { 2 - 4 }
 & normal time & probability of delay & delay \\
\hline
From V & 7 min & 0.20 & 2 min \\
\hline
From LB & 9 min & 0.10 & 2 min \\
\hline
\end{tabular}
\end{center}

Helen wants to choose the route which will give the shortest expected journey time.
\item Draw a decision tree to model Helen's decisions and the possible outcomes.
\item Calculate Helen's shortest expected journey time and give the route which corresponds to that shortest expected journey time.

As she gets into her car, Helen hears a travel bulletin on the radio warning of a broken escalator at V. This means that routes through V will take Helen 10 minutes longer.
\item Find the value of the radio information, explaining your calculation.
\item Why might the shortest expected journey time not be the best criterion for choosing a route for Helen?
\end{enumerate}

\hfill \mbox{\textit{OCR MEI D2 2015 Q5}}