A variable neighborhood search for solving the multi-vehicle covering tour problem

Manel Kammoun (1) , Houda Derbel (1) , Mustapha Ratli (2) , Bassem Jarboui (1)

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

In this article, we consider a transportation problem with different kinds of locations: V , T, and W. The set T ⊂ V consists of vertices that must be visited through the use of potential locations in V and W consists of locations that must be covered. The problem consists in minimizing vehicle routes on a subset of V including T. We develop a variable neighborhood search heuristic based on a variable neighborhood descent in which a set of locations must be visited, whereas another subset must be close enough to the planned routes. We tested and compared our algorithm on datasets based on TSP Library instances.

Mots clés: "Covering Tour Problem"; " "Variable neighborhood search"; "Heuristic algorithms"

Domaines: Informatique [cs]

Manel Kammoun, Houda Derbel, Mustapha Ratli, Bassem Jarboui. A variable neighborhood search for solving the multi-vehicle covering tour problem. Electronic Notes in Discrete Mathematics, 2015, 47, pp.285-292. ⟨10.1016/j.endm.2014.11.037⟩. ⟨hal-03401415⟩