Splitting procedures for the mixed capacitated arc routing problem under time restrictions with intermediate facilities

Abstract

This paper develops optimal and quick near-optimal splitting procedures for the Mixed Capacitated Arc Routing Problem under Time restrictions with Intermediate Facilities. Splitting procedures are a key component of giant tour-based solution methods for Arc Routing Problems. The optimal and near-optimal splitting procedures are tested within a multi-start constructive heuristic, and a fixed execution-time limit is imposed. Results on benchmark instances show that the constructive-heuristic linked with the new optimal splitting algorithm performs better than the near-optimal versions.