An Efficient Algorithm Based Tabu Search for the Robust Sparse CARP Under Travel Costs Uncertainty

We previously studied the capacitated arc routing problem over sparse underlying graphs under travel costs uncertainty. In this paper, we study the same problem by recalling the mathematical formulation of the problem given in [29]. The problem is characterized by the uncertainty of the travel costs and by the sparse network over which it is defined. In fact, a Multiple-Scenario Min-Max CARP over sparse underlying graphs is studied. More numerical instances applying the greedy heuristic algorithm developed in [29] and the adapted tabu-search algorithm are introduced in which these computational experiments show the effectiveness of these two algorithms.