文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 经管营销 > 生产/经营管理 > 车辆路径问题的混合优化算法_汪祖柱
侵权投诉

车辆路径问题的混合优化算法_汪祖柱

第13卷 第6期

2004年12月

 运 筹 与 管 理OPERATIONSRESEARCHANDMANAGEMENTSCIENCEVol.13,No.6Dec.2004 

车辆路径问题的混合优化算法

汪祖柱1,2, 程家兴1, 方宏兵1, 钱付兰1

(1.安徽大学计算智能与信号处理实验室; 2.安徽大学管理学院,安徽合肥)

摘 要:讨论了一类车辆路径调度问题(VRP)及其数学模型,表示和有关遗传操作,然后结合2-optG2问题,试验结果说明了该算法的有效性和可行性。

关键词:运筹学;组合优化;);(GA)

中图分类号:   23221(2004)0620048205

AnAlgorithmSolvingVehicleRoutingProblems

WANGZu2zhu1,2,CHENGJia2xing1,FANGHong2bing1,QIANFu2lan1

(1.MinistryofEducation,KeyLaboratoryofIntelligentComputing&SignalProcessing,

AnhuiUniversity;2.ManagementSchool,AnhuiUniversity,Hefei230039,China)

Abstract:Akindofvehicleroutingproblems(VRP)anditsformulationaredisscused,andwhensolvingVRPusinggeneticalgorithm(GA),thesolutionpresentationandsomeGAoperationsareanalysed.Thenanhybridalgorithmisproposedtosolvethevehicleroutingproblems,someexperimentalresultsprovethatthealgo2rithmisfeasibleandefficient.

Keywords:operationalresearch;combinatorialoptimization;hybridoptimizationalgorithm;vehicleroutingproblems;geneticalgorithm

0 引言

车辆路径问题(VehicleRoutingProblem,VRP)由Dantzig于1959年提出,属于典型的复杂组合优化问题,考虑其特征该问题可以看做是两类经典的组合优化问题的结合—旅行商问题(TSP)和装箱问题(BinPackingProblem,BPP)。该问题的一些具体实例及其变化形式广泛出现于各种商业中的商品配送系统中,如物流快件公司的邮件收发、大型连锁超市的商品配送以及运输公司的旅客输送等。车辆路径问题是NP—Hardness,且有较强的实际应用背景,相关问题的研究者们提出许多求解问题的方法,设法求解该类问题的最优解、近似解或满意解,这些方法大体上归结为三类,即精确算法(exactalgorithms)、经典启发式算法(classicalalgorithms)和现代启发式算法(modernalgorithms,metaheuristics)。有关精确算法如文献

[1]中应用的最小K-树法(minimumK2trees),结合分支定界(branchandbound)的算法技巧来求解问题,这类方法对一些适当规模的问题求解是可行的。经典启发式算法如节约法(savingsalgorithm)[2]和两阶段法(two2phaseheuristic)[3]和扫描法(sweepalgorithm)[4],这类算法能够广泛应用于VRP问题的求解中,最近许多相关文献提出了一类算法—现代启发式算法设法求解VRP问题[5~8],这类算法主要包括遗传

收稿日期:2004203208

基金项目:安徽省青年教师科研基金资助项目(2004JQ108)

作者简介:汪祖柱(19692),男,安徽肥西人,在职博士生,研究方向为调度规划、组合优化问题的演化算法及多目标优化等。

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email