A branch-price-and-cut algorithm for the workover rig routing problem

In an onshore oil field, the productivity of oil wells decreases when they require maintenance. To restore full productivity at a well, it must be visited by a specially equipped vehicle, called a workover rig. Given a set of wells needing maintenance and a heterogeneous fleet of workover rigs, the workover rig routing problem (WRRP) consists of finding rig routes that minimize the total production loss of the wells over a finite horizon. The wells have different loss rates, require various services, and may not be serviced within the horizon due to rig availability. The rigs have initial positions and do not have the same equipment. This paper presents the first exact algorithm for the WRRP, namely, a branch-price-and-cut algorithm that relies on some of the most recent techniques introduced for the vehicle routing problem with time windows. Our computational experiments show that this exact algorithm can solve practical-sized instances in reasonable computational times.