TY - GEN

T1 - A Matheuristic for the Drilling Rig Routing Problem

AU - Kulachenko, Igor

AU - Kononova, Polina

PY - 2020/1/1

Y1 - 2020/1/1

N2 - In this paper, we discuss the real-world Split Delivery Vehicle Routing Problem with Time Windows (SDVRPTW) for drilling rig routing in Siberia and the Far East. There is a set of objects (exploration sites) requiring well-drilling work. Each object includes a known number of planned wells and needs to be served within a given time interval. Several drilling rigs can operate at the same object simultaneously, but their number must not exceed the number of wells planned for this object. A rig that has started the work on a well completes it to the end. The objective is to determine such a set of rig routes (including the number of assigned wells for each object) to perform all well-drilling requests, respecting the time windows, that minimizes the total traveling distance. The main difference with traditional SDVRP is that it is the service time that is split, not the demand. We propose a mixed-integer linear programming (MILP) model for this problem. To find high-quality solutions, we design the Variable Neighborhood Search based matheuristic. Exact methods are incorporated into a local search to optimize the distribution of well work among the rigs. Time-window constraints are relaxed, allowing infeasible solutions during the search, and evaluation techniques are applied to treat them. Results of computational experiments for the algorithm and a state-of-the-art MILP solver are discussed.

AB - In this paper, we discuss the real-world Split Delivery Vehicle Routing Problem with Time Windows (SDVRPTW) for drilling rig routing in Siberia and the Far East. There is a set of objects (exploration sites) requiring well-drilling work. Each object includes a known number of planned wells and needs to be served within a given time interval. Several drilling rigs can operate at the same object simultaneously, but their number must not exceed the number of wells planned for this object. A rig that has started the work on a well completes it to the end. The objective is to determine such a set of rig routes (including the number of assigned wells for each object) to perform all well-drilling requests, respecting the time windows, that minimizes the total traveling distance. The main difference with traditional SDVRP is that it is the service time that is split, not the demand. We propose a mixed-integer linear programming (MILP) model for this problem. To find high-quality solutions, we design the Variable Neighborhood Search based matheuristic. Exact methods are incorporated into a local search to optimize the distribution of well work among the rigs. Time-window constraints are relaxed, allowing infeasible solutions during the search, and evaluation techniques are applied to treat them. Results of computational experiments for the algorithm and a state-of-the-art MILP solver are discussed.

KW - Logistics

KW - Mathematical models

KW - Metaheuristics

KW - Optimization problems

KW - Split delivery service

KW - Time windows

KW - Uncapacitated vehicles

UR - http://www.scopus.com/inward/record.url?scp=85087743564&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-49988-4_24

DO - 10.1007/978-3-030-49988-4_24

M3 - Conference contribution

AN - SCOPUS:85087743564

SN - 9783030499877

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 343

EP - 358

BT - Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings

A2 - Kononov, Alexander

A2 - Khachay, Michael

A2 - Kalyagin, Valery A.

A2 - Pardalos, Panos

PB - Springer Gabler

T2 - 19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020

Y2 - 6 July 2020 through 10 July 2020

ER -