关键词: CVRP, 混合单亲遗传算法, 单亲操作, 邻域搜索, VPR算例

Abstract: In this paper we employ the Hybrid Partheno Genetic Algorithm(HPGA)to solve a vehicle transportation problem.The constrained optimization problem is transformed into an unconstrained optimization  problem by applying apenalty function,and the HPGA uses the serial number coding method to carry on the  computation.When generating the initial population,the vehicle serial number is inserted in the quasi-chro-mosome to generate the subpaths that meet the constraints as much as possible,and the subpaths are splicednto a complete transportation path to reduce the calculation amount of the penalty function.The elitist strategy  is embedded in the selection operation,which guarantees the global convergence of the algorithm.Parental  crossover operations are eliminated and each chromosome independently changes gene to produce new individual,to avoid premature convergence phenomenon.Neighborhood search are introduced so that HPGA can focus on some designated areas of search,to speed up the algorithm in the optimal solution near the optimization speed.Finally,the classical vehicle routing problem is used as the test model of HPGA,and the numerical ex-periments are carried out by Christofides and Eilon＇s standard VRP test.And by comparing to other algorithms it is verified that the HPGA has smaller calculation,faster convergence speed and does not produce premature convergence.

Key words:  , CVRP ；HPGA； Single parent operation； Local search； VRP example