The split-delivery mixed capacitated arc-routing problem: Applications and a forest-based tabu search approach

Motivated by practical applications such as the water sprinkling services of urban administration bureaus in big cities, we study a split-delivery mixed capacitated arc-routing problem. In this problem, a fleet of capacitated vehicles need to serve a set of arcs/edges in a split delivery manner by traversing a mixed graph. We provide a mathematical formulation and analyze some properties of the problem that could be utilized to accelerate the search process of a meta-heuristic algorithm. A forest-based tabu search algorithm is proposed to efficiently solve the problem. Numerical experiments show that our algorithm can quickly produce high quality solutions compared with the state-of-the-art approaches. In addition, we analyze how different patterns of a mixed graph affect the quality of solutions.