A robust optimization approach for the road network daily maintenance routing problem with uncertain service time

•An arc routing problem with uncertain service times is studied.•Robust optimization is applied to obtain routes being less sensitive to uncertainty.•A branch-and-cut algorithm is developed to solve problems of real size.•The behavior of the solutions is analyzed using Monte Carlo simulation.

This paper studies the robust optimization approach for the routing problem encountered in daily maintenance operations of a road network. The uncertainty of service time is considered. The robust optimization approach yields routes that minimize total cost while being less sensitive to substantial deviations of service times. A robust optimization model is developed and solved by the branch-and-cut method. In computational experiments, the behavior of the robust solutions and their performance are analyzed using Monte Carlo simulation. The robust optimization model is also compared with a classic chance-constrained programming model. The experimental analysis provides managerial insights for decision makers to determine an appropriate routing strategy.