物流配送车辆路径问题的并行遗传算法研究.docVIP

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