Study On Capacitated Arc Routing Problem With Time Constraint

Capacitated Arc Routing Problem (CARP) with time constraints is an extension of Arc Routing Problem. On the basis of some critical paths to make the time limit, this expansion has practical significance, such as some of the main road in the city only in certain period of time for service, which requires all path planning completed in such period, while giving priority to ensuring the service time of these paths. If not each path can meet the time constraints, the minimum time delay of the path planning program should be considered. The specific costs of delay can be made based on the punishment of important level, based on the total delay time could be in the least.In this paper, comprehensive study of routing problem in a large-scale problems with heuristic-based algorithm has been made, including focus on genetic algorithm. Genetic algorithm, because of its global convergence in solving multi-objective Optimization problems, has excellent results. It has strong robustness and inherent parallel computer system, particularly suitable for the complex multi-space extreme optimization and combinatorial optimization problems, but the basic genetic algorithm has premature convergence phenomenon, and is easy to fall into local optimal solution. By constructing the population structure and improve the genetic operators, in order to enrich the academic achievements of path planning and provide a reference about routing applications. The major research results are as follows:â‘ The problems are described about the CARP and the introduction of the problem with time constraints of the CARP (CARPTC) is introduced. And this paper established its mathematical model, apply genetic algorithm as a base to solve the problem with the time constraints of CARP (CARPTC).â‘¡According to the characteristics of CARPTC proposed in this paper, an improved genetic algorithm uses a chromosome and population initialization suitable to their problems. An improved evolutionary operator, mutation terms, and adaptation value of fitness function also were made to this improved genetic algorithm. As for the critical path with time constraints, the algorithm adds the time penalty function, to those which have not met the time requirements for routing planning. Through the survival of the fittest principle of genetic algorithm, it can select the best fitness value with the minimum penalty cost of routing planning in order to meet the requirements with time constraints. â‘¢A number of complex constraints, such as the one-way street, restricting left turns, simultaneously services as well as the bilateral path and slope, have been introduced. Designed a hierarchical genetic algorithm, it firstly initiates the population into several sub-groups according to certain requirements or restrictions and respectively in each sub-group endures the genetic evolution of independent operation. In appropriate moments it implements information exchange between sub-groups. It will not only faster iterative evolution, but also maintain the population diversity, while population size has been reduced because of increased efficiency of the algorithm.â‘£According to the real road data for the establishment of a data set for CARPTC problem, a number of important roads have been set with time constraints. The simulation road system can achieve the goal for path planning with the improved genetic algorithms, and finally come to a good result.In this paper, sprinkler path planning for the study, in the context of this application into practical road restrictions, and make traffic route planning, with guidance on the practical application. Optimal path through the program can reduce the waste consumption of previous performed by human, do great benefit to the environment construction of resource saving.