The Selective Traveling Salesman Problem with Draft Limits

Raca Todosijević (1) , Shahin Gelareh (1) , Said Hanafi (1)

1 LAMIH - Laboratoire d'Automatique, de Mécanique et d'Informatique industrielles et Humaines - UMR 8201

This paper introduces the selective traveling salesman problem with draft limits, an extension of the traveling salesman problem with draft limits, wherein the goal is to design a maximum profit tour respecting draft limit constraints at the visited nodes. We propose a mixed integer linear programming (MILP) formulation for this problem. This MILP model is used to solve—to optimality—small size instances and to assess the quality of solutions obtained using a general variable neighborhood search heuristic that explores several neighborhood structures. Our extensive computational experiments confirm the efficiency of the method and the quality of the reported solutions.

Domaines: Informatique [cs]

Raca Todosijević, Shahin Gelareh, Said Hanafi. The Selective Traveling Salesman Problem with Draft Limits. ROADEF 2016, 17ème conférence de la Société française de Recherche Opérationnelle et d’Aide à la Décision, Feb 2016, Compiègne, France. ⟨hal-03388331⟩