October 1997 Presentation Topic (continued)
PICTURE AVAILABLE IN GRAPHICAL VERSION ONLYObserve 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:
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
1 2 3 4
1 36 32 33 19 2 10 8 7 20 3 12 17 16 29 4 23 15 16 28
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 ijyields 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.
4 SUM x i=1 ijyields 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
Similarly, we find that, at any given time,
Thus, 131 ships are needed in all.