一类最小-最大车辆路线问题的启发式算法研究  

Heuristic Algorithm for Min-Max Vehicle Routing Problem

作　　者：王晓博[1] 任春玉[1] 元野[2] 

机构地区：[1]黑龙江大学信息管理学院,黑龙江哈尔滨150080 [2]哈尔滨工业大学管理学院

出　　处：《运筹与管理》2013年第6期26-33,共8页Operations Research and Management Science

基　　金：国家社会科学基金项目资助(电子商务物流配送体系优化研究10CGL076);教育部人文社会科学研究项目资助(非常规突发事件下应急物流网络优化及快速反应机制研究12YJC630160)

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

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

分 类 号：F224.31[经济管理—国民经济]