Algorithm For Solving Undirected Capacitated Arc Routing Problem With Profits

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. In this paper a newextension of this problem, called the undirected capacitated arc routing problem withprofits (UCAPP), is considered. The biggest difference between CARP and UCARPPis that the latter do not have to serve all the customer edges, with which collectingprofit, traversal time and servicing demand are associated. The UCARPP model aimsat generating several routes, which are subject to capacity and travel time constraints,and primarily maximize the profit collected from the subset of customer edges. Manytraditional methods such as accuracy algorithm and lower bound method can’teffectively solve this kind of problem because it is NP-hard. However, a VariableNeighborhood Search (VNS) Algorithm, known as its simple practicality advantageand generality, has been proven to be a good solution to the capacitated arc routingproblem.In this paper, after comprehensive reviewed the literature on arc routing problem,we proposed a split algorithm and a Variable Neighborhood Search (VNS) to solveUCARPP. The main research work and results are as follows:1. CARP and its extensions are detailed described, and the undirected capacitatedarc routing problem with profits (UCAPP) is introduced. This paper established itsmathematical model and design corresponding algorithm to solve this kind of problemon the basis of summarized existing methods.2. According to the characteristic of UCARPP, this paper proposed a splitheuristic algorithm to obtain the initial solution, which speed up the program and atthe same time increase the optimization ability.3. In this paper, six kinds of neighborhood structure are designed to do the widearea search; for the selection of neighborhood structure, the rotary wheel algorithm isapplied. The results of experiments show that the split algorithm improves theefficiency of the algorithm, the design of the six kinds of neighborhood structureavoids the early convergence, the VNS algorithm can solve UCARPP in some scopeeffectively to establish the basis of the practical application.