Algorithm For Solving Capacitated Arc Routing Problem With Refill Points And Multiple Loads

Capacitated Arc Routing Problem (CARP) stems from transportation servicesystem, a special case of arc routing problem, has been widely studied recentlybecause of its usage in practical issues such as urban garbage collection, streetcleaning, mail delivery, salt sprinkle and road maintenance. Capacitated Arc RoutingProblem with Refill Points and Multiple loads (CARP-RP-ML), considering usingRefilling Vehicle (RV) to refill Servicing Vehicle (SV) with raw material many times,belongs to the extension of CARP. Many traditional methods such as accuracyalgorithm and lower bound method can effectively solve this kind of problem becauseit is NP-hard. However, genetic algorithm, known as its powerful advantage ininherent self-learning ability, parallel computing and stability, has been proven to be agood solution to the capacitated arc routing problem.In this paper, after comprehensive reviewed the literature on arc routing problem,we proposed a split algorithm and a genetic algorithm to solve CARP-RP-ML. Themain research work and results are as follows:1. CARP and its extensions are detailed described, and the capacitated arcrouting problem with refill points and multiple loads are introduced. This paperestablished its mathematical model and design corresponding algorithm to solve thiskind of problem on the basis of summarized existing methods.2. According to the characteristic of CARP-RP-ML, this paper proposed a splitheuristic algorithm to obtain the shortest path of two kinds of vehicles and feasiblesolution for the problem, in which the split algorithm is used to split the randomordered demanding arc under the capacity constraints with the refill points taken asthe split point. The total cost of different vehicles between two continuous refill pointsis computed, and meanwhile the minimum cost from depot to current refill point iskept recording until finishing serve all demanding arcs.3. Based on the split algorithm, this paper further obtains the approximateoptimal solution by using strong robustness and inherent parallelism of geneticalgorithm. While genetic may fall to its local optimal easily, so this paper use localsearch as its mutation to extend the search space. The results of experiments show thatgenetic algorithm outperforms heuristic algorithm, which demonstrates that geneticalgorithm can more efficiently solve CARP-RP-ML.