Intelligent Optimization Algorithm Design For The Arc Routing Problem

In recent years,China’s road traffic construction has developed rapidly.However,the maintenance and management of expressways is lagging behind and lacks scientific scheduling.Among them,daily maintenance is a repetitive operation of road maintenance.It needs to decide in which order the vehicles to serve the road sections that need maintenance,which is a typical stochastic capacitated arc routing problem.As for this problem,the traditional manual decision-making process is facing huge challenges due to its low degree of intelligence and difficulty in technological precipitation.Therefore,this paper designs intelligent optimization algorithms with self-learning function for the stochastic capacitated arc routing problem derived from a road network monitoring service.The algorithms can solve new problems based on the past experience and can help to address the challenge to formalize the stochastic parameters and the decision-making preferences in the real-world optimization problems.This paper first proposes an intelligent optimization algorithm based on case-based reasoning,which realizes experience reuse by reusing a few cases that are most similar to the new problem.When solving a new problem,several routes are firstly retrieved from the case repository according to the preference criteria tailored to the addressed problem.Then,the retrieved routes are adapted by a heuristic algorithm to build the solution for the new problem.Finally,the case repository is updated according to this newly solved case.Experimental results show that the algorithm can reuse past experience and solve large-scale problems efficiently.Then this paper proposes another intelligent optimization algorithm based on sequential pattern mining.Different from the case-based reasoning algorithm,it extracts and summarizes information from all past solutions,and realizes experience reuse by using the integrated information.The algorithm is divided into two modules: data mining and problem solving.The data mining module uses a vertical mining algorithm to mine the maximal frequent sequential patterns from the past solutions,and then extracts the correlation information between the arcs in the patterns and integrates them into a correlation matrix;The problem solving module solves the multi-objective optimization problem based on the correlation matrix.A non-dominated sorting genetic algorithm that considers frequent sequential patterns is designed in the problem solving module.The experimental results show that the algorithm can better realize the reuse of past experience when solving small and medium-scale problems;it can always obtain great quality solutions.In order to analyze the pros and cons of the two algorithms,this paper finally compares the different performances of the two when solving the same problem,and provides theoretical guidance for the selection of algorithms in practical applications.