A comparison of three metaheuristics for the workover rig routing problem

Glaydston Mattos Ribeiro; Gilbert Laporte; Geraldo Regis Mauri

doi:10.1016/j.ejor.2012.01.031

A comparison of three metaheuristics for the workover rig routing problem

Glaydston Mattos Ribeiro, Gilbert Laporte, Geraldo Regis Mauri

Research output: Contribution to journal › Article › peer-review

37 Citations (SciVal)

Abstract

The workover rig routing problem (WRRP) is a variant of the Vehicle Routing Problem with Time Windows (VRPTW) and arises in the operations of onshore oil fields. In this problem, a set of workover rigs located at different positions must service oil wells requesting maintenance as soon as possible. When a well requires maintenance, its production is reduced or stopped for safety reasons and some workover rig must service it within a given deadline. It is therefore important to service the wells in a timely fashion in order to minimize the production loss. Whereas for classical VRPTWs the objective is to minimize route length, in the WRRP the objective is to minimize the total lost production, equal to the sum of arrival times at the wells, multiplied by production loss rates. The WRRP generalizes the Delivery Man Problem with Time Windows by considering multiple open vehicle routes and multiple depots. This paper compares three metaheuristics for the WRRP: an iterated local search, a clustering search, and an Adaptive Large Neighborhood Search (ALNS). All approaches, in particular ALNS, have yielded good solutions for instances derived from a real-life setting.

Original language	English
Pages (from-to)	28-36
Number of pages	9
Journal	European Journal of Operational Research
Volume	220
Issue number	1
DOIs	https://doi.org/10.1016/j.ejor.2012.01.031
Publication status	Published - 1 Jul 2012

Funding

Glaydston Mattos Ribeiro and Geraldo Regis Mauri acknowledge Espírito Santo Research Foundation (Process 45391998/09) and National Council for Scientific and Technological Development (Processes 201509/2009-1, 300747/2010-1 and 477148/2011-5) for their financial support. Gilbert Laporte acknowledges the Canadian Natural Sciences and Engineering Research Council (Grant 39682-05 ). The authors thank Tiago Araújo Neves from Fluminense Federal University for kindly providing the data sets and ILS code used in this paper and for answering questions regarding the data sets and the problem. Thanks are due to the referees for their valuable comments.

Keywords

Adaptive large neighborhood search
Clustering search
Iterated local search
Metaheuristics
Workover rig routing problem

ASJC Scopus subject areas

General Computer Science
Modelling and Simulation
Management Science and Operations Research
Information Systems and Management

Access to Document

10.1016/j.ejor.2012.01.031

Cite this

@article{cb74e46b017e45e0bf717fb0d92dbee4,

title = "A comparison of three metaheuristics for the workover rig routing problem",

abstract = "The workover rig routing problem (WRRP) is a variant of the Vehicle Routing Problem with Time Windows (VRPTW) and arises in the operations of onshore oil fields. In this problem, a set of workover rigs located at different positions must service oil wells requesting maintenance as soon as possible. When a well requires maintenance, its production is reduced or stopped for safety reasons and some workover rig must service it within a given deadline. It is therefore important to service the wells in a timely fashion in order to minimize the production loss. Whereas for classical VRPTWs the objective is to minimize route length, in the WRRP the objective is to minimize the total lost production, equal to the sum of arrival times at the wells, multiplied by production loss rates. The WRRP generalizes the Delivery Man Problem with Time Windows by considering multiple open vehicle routes and multiple depots. This paper compares three metaheuristics for the WRRP: an iterated local search, a clustering search, and an Adaptive Large Neighborhood Search (ALNS). All approaches, in particular ALNS, have yielded good solutions for instances derived from a real-life setting.",

keywords = "Adaptive large neighborhood search, Clustering search, Iterated local search, Metaheuristics, Workover rig routing problem",

author = "Ribeiro, {Glaydston Mattos} and Gilbert Laporte and Mauri, {Geraldo Regis}",

year = "2012",

month = jul,

day = "1",

doi = "10.1016/j.ejor.2012.01.031",

language = "English",

volume = "220",

pages = "28--36",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - A comparison of three metaheuristics for the workover rig routing problem

AU - Ribeiro, Glaydston Mattos

AU - Laporte, Gilbert

AU - Mauri, Geraldo Regis

PY - 2012/7/1

Y1 - 2012/7/1

N2 - The workover rig routing problem (WRRP) is a variant of the Vehicle Routing Problem with Time Windows (VRPTW) and arises in the operations of onshore oil fields. In this problem, a set of workover rigs located at different positions must service oil wells requesting maintenance as soon as possible. When a well requires maintenance, its production is reduced or stopped for safety reasons and some workover rig must service it within a given deadline. It is therefore important to service the wells in a timely fashion in order to minimize the production loss. Whereas for classical VRPTWs the objective is to minimize route length, in the WRRP the objective is to minimize the total lost production, equal to the sum of arrival times at the wells, multiplied by production loss rates. The WRRP generalizes the Delivery Man Problem with Time Windows by considering multiple open vehicle routes and multiple depots. This paper compares three metaheuristics for the WRRP: an iterated local search, a clustering search, and an Adaptive Large Neighborhood Search (ALNS). All approaches, in particular ALNS, have yielded good solutions for instances derived from a real-life setting.

AB - The workover rig routing problem (WRRP) is a variant of the Vehicle Routing Problem with Time Windows (VRPTW) and arises in the operations of onshore oil fields. In this problem, a set of workover rigs located at different positions must service oil wells requesting maintenance as soon as possible. When a well requires maintenance, its production is reduced or stopped for safety reasons and some workover rig must service it within a given deadline. It is therefore important to service the wells in a timely fashion in order to minimize the production loss. Whereas for classical VRPTWs the objective is to minimize route length, in the WRRP the objective is to minimize the total lost production, equal to the sum of arrival times at the wells, multiplied by production loss rates. The WRRP generalizes the Delivery Man Problem with Time Windows by considering multiple open vehicle routes and multiple depots. This paper compares three metaheuristics for the WRRP: an iterated local search, a clustering search, and an Adaptive Large Neighborhood Search (ALNS). All approaches, in particular ALNS, have yielded good solutions for instances derived from a real-life setting.

KW - Adaptive large neighborhood search

KW - Clustering search

KW - Iterated local search

KW - Metaheuristics

KW - Workover rig routing problem

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

U2 - 10.1016/j.ejor.2012.01.031

DO - 10.1016/j.ejor.2012.01.031

M3 - Article

AN - SCOPUS:84857912135

SN - 0377-2217

VL - 220

SP - 28

EP - 36

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 1

ER -

A comparison of three metaheuristics for the workover rig routing problem

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this