M. Landete Ruiz, J. Alcaraz, E. M. García, J. F. Monge, J. Puerto Albandoz

In this paper we propose two new problems which combine the Rank Aggregation Problem with the Traveling Salesman Problem. The first problem that we propose and that we have called the Cyclic Rank Aggregation Problem consist in finding the cyclic order (tour) which is at minimum distance from all the tours in a weighted graph when the distance of a tour to a set of tours is sum of the Kendall Tau distances weighted by the cost of the tour. The second problem, that we have called the Permutated Asymmetric Traveling Salesman Problem consist in finding the tour with smaller expected cost in a weighted graph. Both problems are alternatives for the Target Visitation Problem which also combines the special case of the Rank Aggregation Problem called the Linear Ordering Problem with the Traveling Salesman Problem. Finally we establish certain relations between classical problems like Linear Ordering Problem and Rank Aggregation Problem and the new problems.

Keywords: Linear Ordering Problem, Rank Aggregation Problem, Target Visitation Problem, Traveling Salesman Problem.

F2 Routing 2
October 2, 2015  11:30 AM
Salón de actos

B. Domínguez Martín, I. Rodríguez Martín, J. J. Salazar Gonzalez

P. H. Vaz Penna, A. C. Santos, C. Prins

D. L. Huerta Muñoz, C. Archetti, E. Fernández