Solving a robust capacitated arc routing problem using a hybrid simulated annealing algorithm: A waste collection application

The urban waste collection is one of the major municipal activities that involves large expenditures and difficult operational problems. Also, waste collection and disposal have high expenses such as investment cost (i.e. vehicles fleet) and high operational cost (i.e. fuel, maintenance). In fact, making slight improvements in this issue lead to a huge saving in municipal consumption. Some incidents such as altering the pattern of waste collection and abrupt occurrence of events can cause uncertainty in the precise amount of waste easily and consequently, data uncertainty arises.  In this paper, a novel mathematical model is developed for robust capacitated arc routing problem (CARP). The objective function of the proposed model aims to minimize the traversed distance according to the demand uncertainty of the edges. To solve the problem, a hybrid metaheuristic algorithm is developed based on a simulated annealing algorithm and a heuristic algorithm. Moreover, the results obtained from the proposed algorithm are compared with the results of exact method in order to evaluate the algorithm efficiency. The results have shown that the performance of the proposed hybrid metaheuristic is acceptable.