A column generation approach for the multi-vehicle covering tour problem

The multi-vehicle covering tour problem (m-CTP) is defined on a graph G = (V ∪ W, E), where V is a set of vertices that can be visited and W is a set of vertices that must be covered but cannot be visited. Each vertex in V covers a subset of W. Given the costs of edges (v_i, v_j) ∈ E, the objective of the m-CTP is to obtain a set of total minimum cost tours on subset of V, while covering all v_l ∈ W by up to m vehicles. In this paper, we propose algorithms for the m-CTP using column generation approach. Computational experiments show that our algorithms outperform the existing algorithms.