Program > By author > Ngueveu Sandra

The multi-vehicle Covering Tour Problem (m-CTP) belongs to the class of routing problems known as tour location problems (TLPs). Compared to classic routing problems, in TLPs there is an additional level of decision making regarding the choice of the customers to visit and the customers not to visit. Then the customers to visit are clustered in routes and the best visitation order is found for each route.

In the m-CTP, the goal is to find m minimal-length routes over a subset of vertices such that the vertices outside the routes lie within a given distance from a vertex in any route. This study focusses on the case with restriction on the number of vertices allowed in a route, but no restriction on the route length.

The problem is NP-hard, and few solution methods have been proposed. We present a resolution procedure centred on a Selector operator which is dynamic programming based, and uses some techniques to avoid unnecessary creation of states. This operator is embedded in an adaptive large neighbourhood search, local search framework composed of several competing destroy and repair sub-heuristics chosen during the search with a frequency corresponding to their historic performance. The method is competitive as shown by the results obtained through computational experiments conducted on standard instances, and evaluated using the output of a state-of-the-art heuristic and exact algorithm.