A robust optimization model for a location-arc routing problem with demand uncertainty

The present article considers a location-arc routing problem (LARP) where the demands are on the edges rather than nodes on an undirected network. A mixed integer programming model is developed for an LARP with vehicle and depot capacity constraints and a fleet of heterogeneous vehicles. To adapt with reality, it is assumed that the demand of each road is an uncertain value that belongs to a bounded uncertainty set. In order to have a less conservative decision, we employ the robust optimization model proposed by Bertsimas and Sim (2003) to handle uncertainty. The proposed robust model determines a subset of potential depots to be opened along with their allocated roads in order to have an efficient location-routing decision which is immune to different realization of uncertainties. The proposed robust model is less sensitive to demand variations and is validated through Monte-Carlo simulation and relative extra cost (REC) measure with promising results. The results of sensitivity analysis showed that by increasing the degrees of conservatism, planners may employ more vehicles. Also, more depots may be opened to service all required roads.