Amy Jim John and Kelly are standing on the east bank of a ri

Amy, Jim, John, and Kelly are standing on the east bank of a river and wish to cross to the west side using a canoe. The canoe can hold at most two people at a time. Amy, being the most athletic, can row across the river in 1 minute. Jim, John, and Kelly would take 2, 5, and 10 minutes, respectively. If two people are in the canoe, the slower person dictates the crossing time. The objective is for all four people to be on the other side of the river in the shortest time possible.

(a) Identify at least two feasible plans for crossing the river (remember, the canoe is the only mode of transportation, and it cannot be shuttled empty).

(b) Define the criterion for evaluating the alternatives.

(c) What is the smallest time for moving all four people to the other side of the river?

Solution

(a)

Two feasible plans

Step 1: Let John and Kelly go in the first attempt: max(5,10) = 10

Step 2: Let John come back = 5

Step 3: Let John go with Jim max(5,2) = 5

Step 4: Let Jim come back = 2

Step 5: Amy and Jim go together max(2,1) = 2

Total time taken = 10 + 5 + 5 + 2 + 2 = 24

This is one of the possible solutions, but not optimized

Other solution Possible:

Step 1: Let Amy and Jim go in the first attempt: max(1,2) = 2

Step 2: Amy come back = 1

Step 3: Let John and Kelly go max(5,10) = 10

Step 4: Let Jim come back = 2

Step 5: Both Amy and Jim go max(2,1) = 2

Time taken = 2 + 1 + 10 + 2 + 2 = 17 minutes

b) The criterion for evaluating the alternatives is that atleast one of the fast swimmer must be available on both the end, so the empty row can be minimized which will minimized the overall time taken to cross the boat

c) Smallest time will be equal to 17 minutes with the below procedure

Step 1: Let Amy and Jim go in the first attempt: max(1,2) = 2

Step 2: Amy come back = 1

Step 3: Let John and Kelly go max(5,10) = 10

Step 4: Let Jim come back = 2

Step 5: Both Amy and Jim go max(2,1) = 2

Time taken = 2 + 1 + 10 + 2 + 2 = 17 minutes