资源描述：
《物流配送车辆路径问题的并行遗传算法研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、物流配送车辆路径问题的并行遗传算法研究第2卷第4期2005年8月铁道科学与工程JOURNALOFRAllWAYSCIENCEANDENGINEERINGVOI.2NO.4Aug.2005物流配送车辆路径问题的并行遗传算法研究封全喜.刘诚(中南大学数学科学与计算技术学院,湖南长沙410075)摘要:针对一般遗传算法在初始种群上的单一性提出一种新的算法.该算法对不同的种群采用不同的初始化方法:随机初始化法和构造初始化法,这些方法改变了过去那种种群内部的平衡算法,并将该算法所得结果与其他算法进行比较,表明该算法的合理性.关键词:并行遗传算法;
2、物流配送;部分匹配算子中图分类号:U292.6l文献标识码:A文章编号:1672—7029(2005)04—0088—04ThestudyofparallelgeneticalgorithmforvehicleroutingproblemoflogisticdistributionFENGQuan—xi,LIUCheng(SchoolofMathematicalSciencesandComputingTechnolo~',CentralSouthUniversity,Changsha410075,China)Abstract:Accor
3、dingtotheonenessontheinitialpopulationingeneralgeneticalgorithms,anewalgorithm,parallelgeneticalgorithm,isproposed.Itusestwodifferentmethodsonpopulation,i.e.randomizationandconstructionmethod.ItCanbreakthebalanceofinter—populationthoroughlyandmadeoptima/solutionevolvingt
4、ohigh—leve1.Comparedtheresultofparallelalgorithmwithotheralgorithms,itshowsthatparallelalgorithmisanefficientmethodforvehiclemutingproblem.Keywords:parallelgeneticalgorithm;logistiesdistribution;partialmatchingCROSS—overoperator随着物流业在世界各地的兴起,其竞争也日益激烈.车辆路径是物流活动中的关键环节之一,其任
5、务是选派合适的车辆,确定行车路线,时间及服务对象,以降低配送费用和提高服务质量为目标.车辆路径问题是K—TSP问题,也是组合优化问题中的一个NP完全难题.国内外学者已经提出了多种求解该问题的启发式算法,如禁忌搜索算法l¨,节约算法2,蚁群算法l,模拟退火算法l,神经网络算法5以及混合启发式算法_6J.这些算法都只能求出某一特殊类型或规模较小问题的近似最优解或最优解.遗传算法是1975年由美国Michigan大学的J.Holland教授和他的学生提出的一种智能算法,它是模拟自然界生物进化过程而产生的,是求解近似最优解或最优解的一种有效方法
6、.目前已经出现了多种改进的遗传算法,如遗传算法与神经网络算法l7j,爬山法8结合的混合遗传算法,改进交yc-lO]或编码方式[11]的改进遗传算法等.这些算法求解车辆路径问题均取得了较好的效果.但它们在初始化种群时均采用单一的方式:随机初始化法,因此得到的解容易陷入局部最优解或求解时间较长.针对以上情况,本文提出一种新的算法,在初始化种群时用两种不同的方法:随机初始化法和构造初始化法.研究表明,该算法在求解物流配送车辆路径问题时优于一般的算法.l物流配送车辆路径问题的数学模型物流配送路径问题可以描述为:从某物流中心用多台车辆向多个客户送
7、货,每个客户的位置和货物需求量一定,每台物流配送车辆的载重量一定,收稿日期:2005—06—08作者简介:封全喜(1980一),男,湖南衡阳人,中南大学硕士研究生,从事规划理论及其应用的研究第4期封全喜,等:物流配送车辆路径问题的并行遗传算法研究89其一次配送的最大行驶距离一定,要求合理的安排车辆路径,使目标函数最优,并且满足以下条件:1)每条配送路径上各客户的需求量之和不超过配送车辆的载重量;2)每条配送路径的长度不超过配送车辆一次配送的最大行驶距离;3)每个客户的需求必须满足,且只能由一台配送车辆送货.设物流中心有K台配送车辆,每台
8、车辆的载货量为Q(k:1,2,…,K),其一次配送的最大行驶距离为D(k=1,2,…,K),需要向L个客户送货,每个客户的货物需求量为q(i=1,2,…,L),客户到客户的距离为d,(i,=1,2,…,L)
