The selective traveling salesman problem with draft limits

Shahin Gelareh (1) , Bernard Gendron (2) , Said Hanafi (3) , Rahimeh Neamatian Monemi (4) , Raca Todosijević (3)

1 Université d’Artois, IUT de Béthune, 62400, Béthune, France
2 CIRRELT - Centre Interuniversitaire de Recherche sur les Réseaux d'Entreprise, la Logistique et le Transport
3 LAMIH - Laboratoire d'Automatique, de Mécanique et d'Informatique industrielles et Humaines - UMR 8201
4 University of Southampton

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.

Mots clés: Selective traveling salesman problem with draft limits; Variable neighborhood search; Location neighborhood structures; Traveling salesman neighborhood structures; Mixed integer linear programming

Domaines: Informatique [cs]

Shahin Gelareh, Bernard Gendron, Said Hanafi, Rahimeh Neamatian Monemi, Raca Todosijević. The selective traveling salesman problem with draft limits. Journal of Heuristics, 2020, 26 (3), pp.339-352. ⟨10.1007/s10732-019-09406-z⟩. ⟨hal-03472173⟩