Abstract: The searching algorithm for efficient paths set has a great influence on traffic assignment. Considering the travellers’ heterogeneous risk-taking behavior for path and traffic restriction in real road network, the concept of efficient paths is redefined. Moreover, a Hybrid Genetic Algorithm（HGA） is designed based on vertices out degree. This algorithm adopts positive integer coding method considering the unequal creating probability. Furthermore, the probabilities of crossover and mutation are adjusted based on adaptive algorithm and the selection process is adopted simulated annealing algorithm to maintain the diversity and convergence of population. Moreover, this algorithm does not need to repair chromosome which can make up the shortage of priority - based GA when searching paths. While decoding, the delay in the intersection and turn prohibition are considered and efficient path sets are generated through the iterative process. In addition, the efficient path sets of multi-OD（Origination-Destination） can be found at the same time by decoding simultaneously, which can improve the computation efficiency. At last, a case study is given for verifying the efficiency.

Key words: hybrid genetic algorithm, efficient path, simulated annealing algorithm, traffic assignment, road network, delay in intersection

摘要： 有效路径集的计算对交通分配有较大的影响，根据用户选择路径的特点以及交通限制的情况，重新定义了有效路径；并设计了基于顶点出度的混合遗传算法求解有效路径集合。算法采用正整数编码方法，编码产生时考虑了其生成概率，并采用了自适应调节算法来控制交叉、变异概率和模拟退火算法进行选择以保持群体的多样性及收敛性；算法不需要对染色体进行修补，弥补了基于优先权遗传算法计算路径时的不足。算法在解码过程中考虑了交叉口延误及交通限制情况，并利用算法的寻优迭代过程来产生有效路径的集合，采用同时解码的方式，同时对多对OD间计算有效路径，提高了计算多点对之间有效路径的效率。最后的计算实例分析表明该算法的有效性。

关键词: 混合遗传算法, 有效路径, 模拟退火, 交通分配, 道路网络, 交叉口延误