The generalized travelling salesman problem(GTSP),a generalization of the well-known travelling salesman problem(TSP),is considered for our study.Since the GTSP is NP-hard and very complex,finding exact solutions is h...The generalized travelling salesman problem(GTSP),a generalization of the well-known travelling salesman problem(TSP),is considered for our study.Since the GTSP is NP-hard and very complex,finding exact solutions is highly expensive,we will develop genetic algorithms(GAs)to obtain heuristic solutions to the problem.In GAs,as the crossover is a very important process,the crossovermethods proposed for the traditional TSP could be adapted for the GTSP.The sequential constructive crossover(SCX)and three other operators are adapted to use in GAs to solve the GTSP.The effectiveness of GA using SCX is verified on some GTSP Library(GTSPLIB)instances first and then compared against GAs using the other crossover methods.The computational results show the success of the GA using SCX for this problem.Our proposed GA using SCX,and swap mutation could find average solutions whose average percentage of excesses fromthe best-known solutions is between 0.00 and 14.07 for our investigated instances.展开更多
It is difficult to solve complete coverage path planning directly in the obstructed area. Therefore, in this paper, we propose a method of complete coverage path planning with improved area division. Firstly, the bous...It is difficult to solve complete coverage path planning directly in the obstructed area. Therefore, in this paper, we propose a method of complete coverage path planning with improved area division. Firstly, the boustrophedon cell decomposition method is used to partition the map into sub-regions. The complete coverage paths within each sub-region are obtained by the Boustrophedon back-and-forth motions, and the order of traversal of the sub-regions is then described as a generalised traveling salesman problem with pickup and delivery based on the relative positions of the vertices of each sub-region. An adaptive large neighbourhood algorithm is proposed to quickly obtain solution results in traversal order. The effectiveness of the improved algorithm on traversal cost reduction is verified in this paper through multiple sets of experiments. .展开更多
通过对不同伪随机数发生器PRNG(Pseudo Random Number Generator)进行统计性质测试,指出不同的PRNG之间有着不同的统计性质。将各种不同的PRNG应用于随机局部搜索SIS(Stochastic Local Search)算法的典型应用之一:3Opt优化旅行商问题TSP...通过对不同伪随机数发生器PRNG(Pseudo Random Number Generator)进行统计性质测试,指出不同的PRNG之间有着不同的统计性质。将各种不同的PRNG应用于随机局部搜索SIS(Stochastic Local Search)算法的典型应用之一:3Opt优化旅行商问题TSP(Traveling Salesman Problem),并对其结果利用有显著意义的统计检验进行测试分析,结果表明不同PRNG对3Opt-TSP的影响是不同的。展开更多
基金the Deanship of Scientific Research,Imam Mohammad Ibn Saud Islamic University(IMSIU),Saudi Arabia,for funding this research work through Grant No.(221412020).
文摘The generalized travelling salesman problem(GTSP),a generalization of the well-known travelling salesman problem(TSP),is considered for our study.Since the GTSP is NP-hard and very complex,finding exact solutions is highly expensive,we will develop genetic algorithms(GAs)to obtain heuristic solutions to the problem.In GAs,as the crossover is a very important process,the crossovermethods proposed for the traditional TSP could be adapted for the GTSP.The sequential constructive crossover(SCX)and three other operators are adapted to use in GAs to solve the GTSP.The effectiveness of GA using SCX is verified on some GTSP Library(GTSPLIB)instances first and then compared against GAs using the other crossover methods.The computational results show the success of the GA using SCX for this problem.Our proposed GA using SCX,and swap mutation could find average solutions whose average percentage of excesses fromthe best-known solutions is between 0.00 and 14.07 for our investigated instances.
文摘It is difficult to solve complete coverage path planning directly in the obstructed area. Therefore, in this paper, we propose a method of complete coverage path planning with improved area division. Firstly, the boustrophedon cell decomposition method is used to partition the map into sub-regions. The complete coverage paths within each sub-region are obtained by the Boustrophedon back-and-forth motions, and the order of traversal of the sub-regions is then described as a generalised traveling salesman problem with pickup and delivery based on the relative positions of the vertices of each sub-region. An adaptive large neighbourhood algorithm is proposed to quickly obtain solution results in traversal order. The effectiveness of the improved algorithm on traversal cost reduction is verified in this paper through multiple sets of experiments. .
文摘通过对不同伪随机数发生器PRNG(Pseudo Random Number Generator)进行统计性质测试,指出不同的PRNG之间有着不同的统计性质。将各种不同的PRNG应用于随机局部搜索SIS(Stochastic Local Search)算法的典型应用之一:3Opt优化旅行商问题TSP(Traveling Salesman Problem),并对其结果利用有显著意义的统计检验进行测试分析,结果表明不同PRNG对3Opt-TSP的影响是不同的。
