带软时间窗物流配送车辆路径问题的并行遗传算法

《带软时间窗物流配送车辆路径问题的并行遗传算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第23卷第10期(总第142期)　　　　　　系　统　工　程Vol.23,No.102005年10月　　　　　　　　　　　　SystemsEngineeringOct.,2005文章编号:100124098(2005)1020007205X带软时间窗物流配送车辆路径问题的并行遗传算法1,221刘　诚,陈治亚,封全喜(1.中南大学数学科学与计算技术学院,湖南长沙　410075;2.中南大学交通运输工程学院,湖南长沙　410075)摘　要:针对一般遗传算法在求解有时间窗车辆路径问题时初始种群的单一性,提出一种新的算法。该算法对不

2、同的种群用不同的初始化方法——随机初始化法和构造初始化法,这种算法改变了过去那种种群内部的平衡。并将该算法所得结果与其他算法进行比较,表明该算法的合理性。关键词:并行遗传算法;时间窗;车辆路径问题中图分类号:F252　　　文献标识码:A　　车辆路径是物流活动中的关键环节之一,其任务是选用单一的方式——随机初始化法,因此得到的解容易陷派合适的车辆,确定行车路线、时间及服务对象,以降低配入局部最优解或求解时间较长。送费用和提高服务质量为目标。车辆路径问题是K-TSP针对以上情况,本文提出一种新的算法,在初始化种问题,也是组合优

3、化问题中的一个NP完全难题。该问题群时,对不同的种群用不同的方法——随机初始化法和构产生于现实的公路交通运输领域,并在水运、航空、通讯、造初始化法。研究表明,该算法是求解物流配送车辆路径电力、工业管理、计算机应用以及VLSL设计等领域得到问题的有效方法。了广泛的应用。车辆路径问题按客户对货物取(送)时间的1带软时间窗车辆路径要求可分为两大类——有时间窗限制(带软时间窗和带硬时间窗)和没有时间窗限制。本文所研究的问题为有时间问题的数学模型窗限制中的带软时间窗这一类型,是数学和物流学的前沿　　有时间窗车辆路径问题描述为:一个中

4、心仓库,拥有[8]研究热点之一。一定数量容量为q的车辆,负责对N个客户进行货物配国内外学者已经提出了多种求解该问题的启发式算送工作,客户i的货物需求为gi,且gi

5、路组织难度,可预先估计一遗传算法是美国Michigan大学的J.Holland教授和个完成任务所需的车辆数K:他的学生于1975年提出的一种智能算法,它是模拟自然N∑gi界生物进化过程而提出的一种全局搜索算法。它对优化对K=i=1+1Aq象既不要求连续,也不要求可微,并具有极强的鲁棒性。其中[õ]表示不大于括号内数字的整数,A∈(0,1)可依据目前已经出现了多种改进的遗传算法,如遗传算法与爬[3,17]装车的复杂性及约束多少调整,一般装车越复杂,A越小,山法、神经网络算法结合的混合遗传算法,改进编码[1,2,4]反之则越大

6、。方式或交叉的改进遗传算法等。这些算法求解车辆路设仓库编码为0,客户编号为1,2,⋯,N,定义变量径问题均取得了较好的效果。但它们在初始化种群时均采X收稿日期:2005205218作者简介:刘诚(19662),女,江西永新人,中南大学数学科学与计算技术学院副教授,交通运输工程学院博士研究生,研究方向:组合优化,物流工程;陈治亚(19582),男,湖南临湘人,中南大学交通运输工程学院教授,博士生导师,研究方向:交通运输规划与管理,物流工程;封全喜(19802),男,湖南衡阳人,中南大学数学科学与计算技术学院研究生,研究方向:

7、规划理论及其应用。8系　统　工　程　　　　　　　　　　　　　　　　　　2005年1,　车辆k从客户i行驶到客户j个体。xijk=(1)0,　否则一般的遗传算法采用相同的初始化方法——随机初车辆到达客户j的时间始化法,运行一定的代数后,即使两个不同种群中的个体NK(解)的结构也是类似的,所以用不同种群的个体打破彼此tj=∑∑xijk(ti+tij+si),j∈{1,2,⋯,N}(2)i=1k=1内部的平衡,其作用也是有限的。为了彻底打破种群内部式中:tij表示车辆从客户i到客户j的行驶时间,i,j∈的平衡,本文设计算法时利用

8、由两种不同初始化方法而来{0,1,2,⋯,N};si表示客户i的服务时间,i∈{1,2,⋯,的两个种群平行运行一定代数后,分别从中选出若干个适N};t0=0,s0=0。设dij表示客户i到客户j的运输成本,应度较高的个体放到对方种群中打破平衡,如此进行多则运输成本为次。NNK∑∑∑dijõxijk(3)