Research On Evolutionary Algorithms For Multi-traveling Salesman Problems With Access Constraint

This paper proposes the visiting constrained multiple traveling salesmen problem based on real logistics and path planning scenarios dealing with differential access.The model can be adapted to a variety of scheduling and routing problems with constrained access conditions,such as personalized logistics distribution,online ride-hailing dispatch,etc.,which helps to optimize resources and save costs in production and life.As a typical NP-hard problem,the multi-traveling salesman problem cannot be solved quickly by accurate methods,and the accessibility constraints make the traditional evolutionary algorithms unable to allocate the traveling salesmen reasonably,which brings the challenge to construct feasible solutions and decreases the efficiency and effectiveness.Therefore,this paper dives into the evolutionary algorithms to seek optimization for the visiting constrained multiple traveling salesmen problem.The paper is organized as follows.First,an accessibility matrix is devised to characterize the access relationship at the city level,and based on it,the visiting constrained multiple traveling salesmen problem is modeled.Substantial test cases of different scales based on the standard TSPLIB is devised to evaluate the following algorithms.Various traditional evolutionary algorithms designed for multi-traveling salesmen problem are improved and modified according to the characteristics of the problem,including genetic algorithm,ant colony optimization,variable neighborhood search,partheno-genetic algorithm,invasive weed optimization and artificial bee colony.They are detailed discussed both on the improvement strategies and remaining limitations in handling visiting constraints.To effectively solve the problem and cope with the visiting conflicts,a central decisionbased ant colony optimization is proposed.The wait-and-see mechanism is designed for ants to resolve city visiting conflicts while constructing routes in parallel.The assignment reasonability is evaluated through the central decision process.The most suitable individual among the ants will be preferentially selected for path construction by the approach of shortest distance biased dispatch,so as to improve the quality of solution and the convergence speed of the algorithm.In addition,a pheromone diffusion strategy based on the nearest neighborhood edges is designed to guide the ants to expand the search range and improve the global search ability of the algorithm.A memetic algorithm found on contrastive crossover is proposed to provide high quality feasible solutions.Its contrast crossover operator and inherent local search ability significantly improves the quality of the offspring solution while inheriting the key substructure from the parent solution.Moreover,a population diversity evaluation metric is proposed based on the information entropy theory,which assesses the diversity level of the population by calculating the probabilistic distribution of individuals in the population.Then,an offspring selection strategy based on information entropy is designed to intentionally screen out high-quality offspring that are conducive to maintaining population diversity and avoid the algorithm falling into local optima.The experimental results show that the proposed algorithms can effectively solve the visiting constrained multiple traveling salesmen problem,and have significant advantages in dealing with traveling salesman allocation and improving the quality of solutions.