| 一类最小-最大车辆路线问题的启发式算法研究 |
| |
| 引用本文： | 王晓博,任春玉,元野. 一类最小-最大车辆路线问题的启发式算法研究[J]. 运筹与管理, 2013, 22(6): 26-33 |
| |
| 作者姓名： | 王晓博 任春玉 元野 |
| |
| 作者单位： | 1.黑龙江大学 信息管理学院,黑龙江 哈尔滨 150080;2.哈尔滨工业大学 管理学院,黑龙江 哈尔滨 |
| |
| 基金项目： | 国家社会科学基金项目资助(电子商务物流配送体系优化研究10CGL076);教育部人文社会科学研究项目资助(非常规突发事件下应急物流网络优化及快速反应机制研究12YJC630160) |
| |
| 摘 要： | 针对个性化和多样性的需求,建立以缩短最长子线路为目标的最小-最大车辆路径问题模型, 并提出启发式算法求解。首先,采用自然数编码,使问题变得更简洁;用最佳保留选择法,以保证群体的多样性;引入爬山算法,加强局部搜索能力;其次,对遗传算法求得的精英种群再进行禁忌搜索,保证算法能够收敛到全局最优。最后,通过实例的计算,表明本算法均优于遗传算法和禁忌搜索算法,并为大规模解决实际问题提供思路。
|
| 关 键 词： | 运筹学与控制论 最小-最大的车辆路径问题 遗传算法 禁忌搜索算法 启发式算法 |
| 收稿时间： | 2012-10-27 |
Heuristic Algorithm for Min-Max Vehicle Routing Problem |
| |
| WANG Xiao-bo,REN Chun-yu,YUAN Ye. Heuristic Algorithm for Min-Max Vehicle Routing Problem[J]. Operations Research and Management Science, 2013, 22(6): 26-33 |
| |
| Authors: | WANG Xiao-bo REN Chun-yu YUAN Ye |
| |
| Affiliation: | 1. School of Information Management, Heilongjiang University, Harbin 150080, China;2. School of Management, Harbin Institute of Technology, Harbin 150001, China |
| |
| 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. |
| |
| Keywords: | operations research and cybernetics min-max vehicle routing problem genetic algorithm tabu searching algorithm heuristic algorithm |
|
| 点击此处可从《运筹与管理》浏览原始摘要信息 |
|
点击此处可从《运筹与管理》下载免费的PDF全文 |
|
