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.
