Routing and Scheduling Coast Guard Buoy Tenders

We applied a best-schedule heuristic for solving a large class of real-world routing and scheduling problems to the routing and scheduling of buoy maintenance in real time by the United States Coast Guard. The best schedule method reduces a routing and scheduling problem to a traveling salesman problem with non-Euclidean distances. The service windows for the activities are used to prune potential routes without calculating a detailed schedule or evaluating the cost function.