Algorithm For The Capacitated Arc Routing Problem With Stochastic Demands

The Capacitated Arc Routing Problem (CARP), arises in practical issues likewaste collection, winter gritting and mail delivery, is an extension of Arc-RoutingProblem(ARP).In reality, it has been receiving increasing research recently for itscrucial value of application. The Capacitated Arc-Routing Problem with StochasticDemands (CARPSD), studied in this paper and considering the demand of everyrequired arc is stochastic, is a spreading form of traditional Capacitated Arc RoutingProblem. Many traditional methods such as branch and bound algorithm can’t solvethis large size of problem because it is NP-hard. But, meta-heuristic, known as itspowerful advantage in inherent self-adaptive ability, parallel computing and stability,have promising to give a good solution to the capacitated arc routing problem.This paper made CARPSD as the research object, bases on extensively reviewingthe literature on arc routing problem, we proposed a Partition Algorithm, an AdaptiveLocal Search Heuristic (ANS) and an Adaptive Neighborhood Search Heuristic (ANS)to effectively solve CARPSD. The main research work and results are as follows:Firstly, the traditional CARP are detailed described, The Capacitated Arc RoutingProblem with Stochastic Demands are introduced. This paper established itsmathematical model, attempted relational theoretical proof, and finally finished thebasic assumptions on the feasibility of the problem.Secondly, according to characteristics of CARPSD, Stochastic Path Scanning(SPS) and Partition Algorithm are implemented to obtain feasible solution and theshortest path under stochastic conditions, in which designed Partition Algorithm toresort and split feasible solution in order to calculate the minimum cost in all possiblecircumstances. As a final judgment, the expectations of the minimum cost should berecorded and saved, until all the demands of arc have been satisfied.Finally, depended on self-adaptive ability of algorithm, this paper further obtainsthe approximate optimal solution by using strong robustness and inherent parallelismof heuristic algorithm. While standard heuristic algorithm may fall to its local optimaleasily, so two relatively effective heuristic algorithms are designed: an Adaptive LocalSearch Heuristic (ALS) and an Adaptive Neighborhood Search Heuristic (ANS). Theresults of experiments show that two algorithm outperforms other heuristic algorithm,which demonstrates that CARPSD are efficiently solved in the paper.