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.