The target visitation arc routing problem
-
Jessica Rodríguez Pereira [1] ; Gilbert Laporte [2]
-
[1] Universitat Pompeu Fabra
Universitat Pompeu Fabra
Barcelona, España
-
[2] University of Bath
University of Bath
Reino Unido
-
- Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 30, Nº. 1, 2022, págs. 60-76
- Idioma: inglés
- Enlaces
-
Resumen
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 satisfed. The aim is to fnd a tour that traverses all required edges at least once, and ofers 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 difculty of the problem, the model can be used to solve to optimality around 62% of the test instances.
