Scheduling Boats to Sample Oil Wells in Lake Maracaibo

Sampling oil wells is a routine operation that involves withdrawing, near the wellhead, a fraction of the liquid that flows from the well. This operation is not performed at fixed intervals, but with a frequency that varies from well to well and that also changes in time. Lagoven, S. A. operates some 3,000 oil wells in Lake Maracaibo, Venezuela, for a production capacity of approximately a million barrels of oil a day. Since its implementation in April 1975, a computer system determines which of these wells require a sample and also schedules the routes for the launches that visit the selected wells. The launch-scheduling algorithm is a heuristic that schedules up to 400 points in several routes, each having up to 106 points. This algorithm solves a special case of the vehicle dispatch problem, where the constraints for using the launches are their traveling times and the number of points on their routes. The impact of the system on field operations has been an improvement in the timing of the samples and a reduction in the overall effort of gathering samples.