A Hybrid Algorithm for the Drilling Rig Routing Problem

I. N. Kulachenko; P. A. Kononova

doi:10.1134/S1990478921020071

A Hybrid Algorithm for the Drilling Rig Routing Problem

Переведенное название: Гибридный алгоритм решения задачи маршрутизации буровых установок

I. N. Kulachenko, P. A. Kononova

Результат исследования: Научные публикации в периодических изданиях › статья › рецензирование

Аннотация

Исследуется задача маршрутизации буровых установок. Известно множество объектов, требующих изыскательских работ, и временное окно, т. е. период, в который необходимо успеть провести работы. На одном объекте может работать несколько установок, в этом случае работы будут проведены быстрее. Необходимо определить маршруты и график работ буровых установок на объектах так, чтобы все работы были выполнены вовремя, а суммарное время переезда было минимальным. Для этой новой задачи составлена модель задачи смешанного целочисленного линейного программирования (СЦЛП). Для поиска допустимого решения используется метаэвристика поиска с чередующимися окрестностями. Алгоритм также включает в себя решение подзадачи СЦЛП для перераспределения работ на объектах. Полученный метод сочетает в себе достоинства как точных, так и эвристических подходов. Представлены результаты сравнения разработанного алгоритма с Gurobi и альтернативными схемами поиска с чередующимися окрестностями.

Переведенное название	Гибридный алгоритм решения задачи маршрутизации буровых установок
Язык оригинала	английский
Страницы (с-по)	261-276
Число страниц	16
Журнал	Journal of Applied and Industrial Mathematics
Том	15
Номер выпуска	2
DOI	https://doi.org/10.1134/S1990478921020071
Состояние	Опубликовано - апр. 2021

Предметные области OECD FOS+WOS

1.01 МАТЕМАТИКА
2.03 МЕХАНИКА И МАШИНОСТРОЕНИЕ

ГРНТИ

27 МАТЕМАТИКА

Доступ к документу

10.1134/S1990478921020071

Другие файлы и ссылки

Ссылка на публикацию в Scopus

Fingerprint

Подробные сведения о темах исследования «Гибридный алгоритм решения задачи маршрутизации буровых установок». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать

@article{8a8e9fb8d2054b8f89b248162aa3f358,

title = "A Hybrid Algorithm for the Drilling Rig Routing Problem",

abstract = "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.",

keywords = "matheuristics, split delivery service, time window, uncapacitated vehicle",

author = "Kulachenko, {I. N.} and Kononova, {P. A.}",

note = "Funding Information: The authors were supported by the State Task to the Sobolev Institute of Mathematics (project no. 0314–2019–0014). Publisher Copyright: {\textcopyright} 2021, Pleiades Publishing, Ltd.",

year = "2021",

month = apr,

doi = "10.1134/S1990478921020071",

language = "English",

volume = "15",

pages = "261--276",

journal = "Journal of Applied and Industrial Mathematics",

issn = "1990-4789",

publisher = "Maik Nauka-Interperiodica Publishing",

number = "2",

}

TY - JOUR

T1 - A Hybrid Algorithm for the Drilling Rig Routing Problem

AU - Kulachenko, I. N.

AU - Kononova, P. A.

PY - 2021/4

Y1 - 2021/4

N2 - 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.

AB - 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.

KW - matheuristics

KW - split delivery service

KW - time window

KW - uncapacitated vehicle

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

U2 - 10.1134/S1990478921020071

DO - 10.1134/S1990478921020071

M3 - Article

AN - SCOPUS:85117140306

VL - 15

SP - 261

EP - 276

JO - Journal of Applied and Industrial Mathematics

JF - Journal of Applied and Industrial Mathematics

SN - 1990-4789

IS - 2

ER -