One of the primary missions of the U. S. Coast Guard (USCG) is to maintain tens of thousands of aids to navigation called buoys. The Coast guard has approximately 40 buoy tenders, which are ships used to maintain buoys. Each of these ships services several hundred buoys in its geographical region each year. Annual servicing consists of inspecting the buoy and its mooring chain, recharging its batteries, and replacing burned out lights. At regular intervals, the buoy is replaced. The buoy tender's captain must plan the ship's activities so that each buoy is serviced within a one-month service window.
The routing and scheduling of a buoy tender is complicated by a number of important real-world considerations:
- Buoy servicing should be done in daylight. Thus, the operating schedule varies with the season, sea conditions, and locale.
- The buoy tender itself undergoes annual maintenance typically lasting about four weeks.
- A buoy tender can carry only a limited number of new buoys, so only a limited number of buoys can be replaced on each cruise.
- A buoy tender may use a number of ports other than its homeport.
- The captain of a buoy tender usually tries to schedule its activities so as to minimize crew fatigue.
The routing and scheduling of a buoy tender was investigated as part of a simulation project of the USCG Research and Development Center. The solution has applicability to a wide range of routing and scheduling problems. The solution that was developed separates the routing and scheduling portions of the problem. For any given route, optimum arrival times are determined for each buoy. The problem then reduces to finding the optimum route. To do so, a pruning strategy was developed which greatly reduces the number of potential routes, which must be examined. This pruning strategy uses the service windows for each buoy in such a way that only a small number of deviations from the originally planned route must be made.
After this method of routing and scheduling buoy tenders was developed, it was tested by computer simulation of several years of buoy-tending activity in which emergencies and adverse weather conditions were randomly introduced. The method was efficient enough to dynamically alter the schedule in response to such phenomena.