摘要
针对装卸混合的车辆路径问题这一类典型的NP难题,采用四位数的遗传编码,并对解的可行性进行验证,降低对交叉算子和变异算子的要求,有效提高解的质量.最后对二十个客户点的装卸混合的问题作了数值试验,结果表明遗传算法作为一种有效的随机型全局搜索算法,体现出群体智能的分布型、鲁棒性和快速性的特点.
Genetic algorithm is an effective stochastic global searching algorithm which has some characteristics of distribution, robust and fast of swarm intelligence. The vehicle routing problem with backhaul is a typical category of NP-hard problems. This paper is aimed at the issue that it is easy to produce wrong solutions if used the coding method of ordinal number. We introduce the coding method of four-digit number to improve the quality of solution and decrease the difficulty of crossover operator and mutation operator. At last, we test this method through a 20-customer routing problem with backhaul, and the result shows the method is effective.
出处
《系统工程理论与实践》
EI
CSCD
北大核心
2007年第2期149-152,共4页
Systems Engineering-Theory & Practice
关键词
遗传算法
车辆路径问题
装卸混合的
四位数编码
genetic algorithm
vehicle routing problem
baekhaul
four-digit number coding