Navigation Panel: Previous | Up | Graphical Version | PostScript version | SIMMER Home Page | Fields Institute Home | U of T Math Network Home

SIMMER

October 1997 Presentation Topic (continued)

# Solution to Question 3 (the hard problem)

A rough map will help focus our thinking:
PICTURE AVAILABLE IN GRAPHICAL VERSION ONLY
Observe that routes have been numbered according to the statement of the problem.

Also observe that in order to make shipping a continuous steady state process, to have one ship per day arriving (or leaving) a given port, there will have to be a queue of ships spaced one day apart along the adjoining route. Furthermore, once a ship has finished a cargo route, it may have to travel empty to another port in order to begin another route.

For example, in order to have 1 ship per day shifting from route 2 to route 1, there will need to be a queue of 10 ships spaced out along the itinerary MA -> IS ->DH. This is because it takes a ship 10 days from the time it begins route 2 until the time it is ready to begin route 1: 1 day loading cargo at Marseilles, 3 days travelling along route 2 to Istanbul, 1 day unloading at Istanbul, and 5 days travelling empty from Istanbul to Dhahran in preparation for beginning route 1.

In general, in order to have 1 ship per day shifting from route i to route j, there must always be a queue of c_(ij) ships involved in servicing route i then travelling to begin route j, where c_(ij) is 2 plus the time taken to travel route i plus the time taken to travel from the endpoint of route i to the starting point of route j.

The values of c_(ij) are tabulated below:

```  1 2   3  4

1   36 32 33 19
2   10  8  7 20
3   12 17 16 29
4   23 15 16 28
```
If we let x_(ij) be the number of ships shifting from route i to route j daily, then the total number of ships servicing route i at any one time (where "servicing route i" includes getting ready for the next route after finishing route i) is
```           4
SUM  x  c  .
j=1   ij ij
```

Our goal is to choose the x_(ij) so as to minimize the total number of ships, which is

```           4
SUM   x  c  .
i,j=1   ij ij
```

The only constraints are that the daily number of ships completing a route must equal the daily number of ships beginning it, and this must equal the number specified in the problem (3 for route 1, 2 for route 2, and 1 for routes 3 and 4).

Under our definition for x_(ij),

```          4
SUM x
j=1  ij
```
yields the daily number of ships completing route i. This gives constraints SUM_j x_(1j) = 3, SUM_j x_(2j) = 2, SUM_j x_(3j) = 1, SUM_j x_(4j) = 1.

Similarly

```          4
SUM x
i=1  ij
```
yields the daily number of ships beginning route i. This gives constraints SUM_i x_(i1) = 3, SUM_i x_(i2) = 2, SUM_i x_(i3) = 1, SUM_i x_(i4) = 1.

Eureka! a transportation problem of modest size. Its solution is

```               (1 1 0 1)
x   =  (1 0 1 0)
ij    (1 0 0 0)
(0 1 0 0)
```

Which we interpret as follows:

Of the three ships servicing route 1 daily, one goes back to begin route 1 again, one goes on to route 1, and one goes on to route 4. Referring back to the table for C_(ij), this means that at any given time

• 36 ships are occupied travelling route 1 (DH -> NY) then returning empty in preperation for another route 1 trip.

• 32 ships are occupied travelling route 1 then going empty to MA in preparation for a route 2 (MA -> IS) cargo journey;

• 19 ships are occupied travelling route 1 then reloading in preparation for a loaded journey to MA (route 4).

Similarly, we find that, at any given time,

• 10 ships are occupied travelling route 2 (MA -> IS) then going empty to DH in preparation for a route 1 (DH -> NY) cargo journey;

• 7 ships are occupied travelling route 2 then going empty to NA in preparation for a route 3 (NA -> BO) cargo journey;

• 12 ships are occupied travelling route 3 (NA -> BO) then going empty to DH in preparation for a route 1 (DH -> NY) cargo journey;

• 15 ships are occupied travelling route 4 (NY -> MA) then reloading in in preparation for a route 2 (MA -> IS) cargo journey.

Thus, 131 ships are needed in all.