D2 June 2006 Q3

EdexcelOld spec11 marksTravelling Salesman

3. A college wants to offer five full-day activities with a different activity each day from Monday to Friday. The sports hall will only be used for these activities. Each evening the caretaker will prepare the hall by putting away the equipment from the previous activity and setting up the hall for the activity next day. On Friday evening he will put away the equipment used that day and set up the hall for the following Monday.

The 5 activities offered are Badminton (\(B\)), Cricket nets (\(C\)), Dancing (\(D\)), Football coaching (\(F\)) and Tennis (\(T\)). Each will be on the same day from week to week.

The college decides to offer the activities in the order that minimises the total time the caretaker has to spend preparing the hall each week.

The hall is initially set up for Badminton on Monday.

The table below shows the time, in minutes, it will take the caretaker to put away the equipment from one activity and set up the hall for the next.

To
Time\(B\)\(C\)\(D\)\(F\)\(T\)
From\(B\)–10815064100
\(C\)108–5410460
\(D\)15054–150102
\(F\)64104150–68
\(T\)1006010268–
(a) Explain why this problem is equivalent to the travelling salesman problem. (2)

A possible ordering of activities is

MondayTuesdayWednesdayThursdayFriday
\(B\)\(C\)\(D\)\(F\)\(T\)
(b) Find the total time taken by the caretaker each week using this ordering. (2)
(c) Starting with Badminton on Monday, use a suitable algorithm to find an ordering that reduces the total time spent each week to less than 7 hours. (3)
(d) By deleting \(B\), use a suitable algorithm to find a lower bound for the time taken each week. Make your method clear. (4)
‹ Previous22 of 24 in Travelling SalesmanNext ›