The target visitation arc routing problem

Jessica Rodríguez-Pereira, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review


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
Early online date4 May 2021
Publication statusE-pub ahead of print - 4 May 2021


  • 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

Cite this