Abstract: This paper studies the vehicle routing problem for daily maintenance operations of a road network suffered from the uncertainty of service time. A robust optimization model is formulated to minimize total cost and the optimal problem is solved by the branch-and-cut method. In computational experiments, the performances of the robust solutions are analyzed using Monte Carlo simulation. The experimental analysis demonstrates that the robust optimization approach can yield routes that minimize total cost and are less sensitive to substantial deviations of service times. Decision makers may obtain some managerial insights from robust optimization solution to determine an appropriate routing strategy.

Key words: arc routing planning, robust optimization, uncertainty, branch and cut