The target visitation arc routing problem

Jessica Rodríguez-Pereira; Gilbert Laporte

doi:10.1007/s11750-021-00601-5

The target visitation arc routing problem

Jessica Rodríguez-Pereira, Gilbert Laporte

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

1 Citation (SciVal)

92 Downloads (Pure)

Abstract

This paper studies the target visitation arc routing problem on an undirected graph. This problem combines the well-known undirected rural postman problem and the linear ordering problem. In this problem, there is a set of required edges partitioned into targets, which must be traversed and there are pairwise preferences for the order in which some targets are serviced, which generates a revenue if the preference is satisfied. The aim is to find a tour that traverses all required edges at least once, and offers a compromise between the revenue generated by the order in which targets are serviced, and the routing cost of the tour. A linear integer programming formulation including some families of valid inequalities is proposed. Despite the difficulty of the problem, the model can be used to solve to optimality around 62% of the test instances.

Original language	English
Pages (from-to)	60-76
Number of pages	17
Journal	TOP
Volume	30
Issue number	1
Early online date	4 May 2021
DOIs	https://doi.org/10.1007/s11750-021-00601-5
Publication status	Published - 30 Apr 2022

Bibliographical note

Funding Information:
Thanks are due to the referees for their valuable comments. This research was partially supported by the Spanish Ministry of Economy and Competitiveness through Grant MTM2015-63779-R (MINECO/FEDER), and by the Canadian Natural Sciences and Engineering Research Council under the Grant 2015-06189. This support is gratefully acknowledged.

Funding

Thanks are due to the referees for their valuable comments. This research was partially supported by the Spanish Ministry of Economy and Competitiveness through Grant MTM2015-63779-R (MINECO/FEDER), and by the Canadian Natural Sciences and Engineering Research Council under the Grant 2015-06189. This support is gratefully acknowledged.

Keywords

Arc routing
Linear ordering problem
Target visitation

ASJC Scopus subject areas

Modelling and Simulation
Discrete Mathematics and Combinatorics
Management Science and Operations Research
Information Systems and Management

Access to Document

10.1007/s11750-021-00601-5

RPL-TOP-21 (1)
This is a post-peer-review, pre-copyedit version of an article published in TOP. The final authenticated version is available online at: https://link.springer.com/article/10.1007/s11750-021-00601-5
Accepted author manuscript, 629 KB

Cite this

@article{da046d8eebc44d1e9f81e6f75005ec31,

title = "The target visitation arc routing problem",

abstract = "This paper studies the target visitation arc routing problem on an undirected graph. This problem combines the well-known undirected rural postman problem and the linear ordering problem. In this problem, there is a set of required edges partitioned into targets, which must be traversed and there are pairwise preferences for the order in which some targets are serviced, which generates a revenue if the preference is satisfied. The aim is to find a tour that traverses all required edges at least once, and offers a compromise between the revenue generated by the order in which targets are serviced, and the routing cost of the tour. A linear integer programming formulation including some families of valid inequalities is proposed. Despite the difficulty of the problem, the model can be used to solve to optimality around 62% of the test instances.",

keywords = "Arc routing, Linear ordering problem, Target visitation",

author = "Jessica Rodr{\'i}guez-Pereira and Gilbert Laporte",

note = "Funding Information: Thanks are due to the referees for their valuable comments. This research was partially supported by the Spanish Ministry of Economy and Competitiveness through Grant MTM2015-63779-R (MINECO/FEDER), and by the Canadian Natural Sciences and Engineering Research Council under the Grant 2015-06189. This support is gratefully acknowledged. ",

year = "2022",

month = apr,

day = "30",

doi = "10.1007/s11750-021-00601-5",

language = "English",

volume = "30",

pages = "60--76",

journal = "TOP",

issn = "1134-5764",

publisher = "Springer Nature",

number = "1",

}

TY - JOUR

T1 - The target visitation arc routing problem

AU - Rodríguez-Pereira, Jessica

AU - Laporte, Gilbert

N1 - Funding Information: Thanks are due to the referees for their valuable comments. This research was partially supported by the Spanish Ministry of Economy and Competitiveness through Grant MTM2015-63779-R (MINECO/FEDER), and by the Canadian Natural Sciences and Engineering Research Council under the Grant 2015-06189. This support is gratefully acknowledged.

PY - 2022/4/30

Y1 - 2022/4/30

N2 - This paper studies the target visitation arc routing problem on an undirected graph. This problem combines the well-known undirected rural postman problem and the linear ordering problem. In this problem, there is a set of required edges partitioned into targets, which must be traversed and there are pairwise preferences for the order in which some targets are serviced, which generates a revenue if the preference is satisfied. The aim is to find a tour that traverses all required edges at least once, and offers a compromise between the revenue generated by the order in which targets are serviced, and the routing cost of the tour. A linear integer programming formulation including some families of valid inequalities is proposed. Despite the difficulty of the problem, the model can be used to solve to optimality around 62% of the test instances.

AB - This paper studies the target visitation arc routing problem on an undirected graph. This problem combines the well-known undirected rural postman problem and the linear ordering problem. In this problem, there is a set of required edges partitioned into targets, which must be traversed and there are pairwise preferences for the order in which some targets are serviced, which generates a revenue if the preference is satisfied. The aim is to find a tour that traverses all required edges at least once, and offers a compromise between the revenue generated by the order in which targets are serviced, and the routing cost of the tour. A linear integer programming formulation including some families of valid inequalities is proposed. Despite the difficulty of the problem, the model can be used to solve to optimality around 62% of the test instances.

KW - Arc routing

KW - Linear ordering problem

KW - Target visitation

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

U2 - 10.1007/s11750-021-00601-5

DO - 10.1007/s11750-021-00601-5

M3 - Article

AN - SCOPUS:85105488616

SN - 1134-5764

VL - 30

SP - 60

EP - 76

JO - TOP

JF - TOP

IS - 1

ER -

The target visitation arc routing problem

Abstract

Bibliographical note

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this