A Hybrid Algorithm for the Drilling Rig Routing Problem

Under study is the drilling rig routing problem. We are given a set of facilities requiringwell-drilling work and a time window (i.e., some time interval during which all work has to becompleted). Several drilling rigs can operate at the same facility simultaneously, which allows usto speed up the work. The objective is to determine a set of routes for a fleet of drilling rigs toperform all well-drilling requests in time with minimal total traveling time. We constructed themixed integer linear programming (MILP) model for this problem. To find a feasible solution,we use the variable neighborhood search (VNS)metaheuristic. The algorithm also includes solving some MILP subproblem to redistribute thewell-drilling work. The obtained method combines the advantages of both exact and heuristicapproaches. We present the results of comparison of the developed algorithm with Gurobi andalternative VNS schemes.