The target visitation arc routing problem

Jessica Rodríguez-Pereira, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

1 Citation (SciVal)
27 Downloads (Pure)


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 languageEnglish
Pages (from-to)60-76
Number of pages17
Issue number1
Early online date4 May 2021
Publication statusPublished - 30 Apr 2022


  • 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


Dive into the research topics of 'The target visitation arc routing problem'. Together they form a unique fingerprint.

Cite this