Abstract: In order to satisfy the individual and various demands, this paper establishes min-max vehicle routing problem for shortening the longest sub-lines, and the heuristic algorithm is used to get the optimization solution. First, a natural number coding is used so as to simplify the problem, and the best retention selection method is used so as to make the diversity of group. The study adopts the hill-climbing algorithm to strengthen the partial searching ability. Secondly, the stock elite group obtained by genetic algorithm is searched again with tabu searching algorithm in order to guarantee the algorithm converging to the global optimization. Finally, the results demonstrate that the algorithm is better than both genetic algorithm and tabu searching algorithm. This algorithm provides the thought to settle the large scale practical problem.

Key words: operations research and cybernetics, min-max vehicle routing problem, genetic algorithm, tabu searching algorithm, heuristic algorithm

摘要： 针对个性化和多样性的需求,建立以缩短最长子线路为目标的最小-最大车辆路径问题模型, 并提出启发式算法求解。首先,采用自然数编码,使问题变得更简洁;用最佳保留选择法,以保证群体的多样性;引入爬山算法,加强局部搜索能力;其次,对遗传算法求得的精英种群再进行禁忌搜索,保证算法能够收敛到全局最优。最后,通过实例的计算,表明本算法均优于遗传算法和禁忌搜索算法,并为大规模解决实际问题提供思路。

关键词: 运筹学与控制论, 最小-最大的车辆路径问题, 遗传算法, 禁忌搜索算法, 启发式算法