搜索
龙源期刊网遗传算法研究作者：张亮杜培俊何兆芳来源：《物流科技》2014年第06期摘要：顾客的需求越来越被关注，时间要求变得越来越重要。文章基于此，建立有时间约束的车辆路径问题模型，并引入遗传算法，纳入禁忌搜索，来求解此车辆路径模型。关键词：软时间窗；遗传算法；VRP中图分类号：F252.14文献标识码：AAbstract:Withcustomer'sneedsgivenmoreandmoreattention,timeneedhasbeenmoreandmoreimportant,thispaperconstructsVRPmodelwithtimewindows,andusegeneticalgorithms,combinewithtabusearchtosolvethisproblem.Keywords:softtimewindow;geneticalgorithms;VRP1问题的描述及数学模型的建立1.1问题的描述本文所要研究的是多车型、单一配送中心、多个客户点、带有软时间窗的车辆路径问题。所要达到的目标是：总成本最小，车辆数目最少。为了方便起见，将车场编号为0，任务编号为1,2,…,L，任务及车场均以点ii=0,1,…,L来表示。以Q■表示车辆k的装载能力，t■为从i到j的行驶时间，c■为从i到j的行驶所花费的费用，d■为客户i的需求量。S■为第k辆车到达客户i的时间，T■为第k辆车在客户i的卸货时间，c为汽车的固定费用。E■,L■为客户i的时间窗口。E■为车从配送时间出发的时刻。x■为第k辆车是否从i出发后开向j，如果是，x■=1，否则为0。y■为客户i的任务是否由车辆k完成，如果是，y■=1，否则为0。z■为车辆k给客户点i的载货量。M表示惩罚系数。1.2模型的建立Min=Kc+■■■c■x■+■■p■S■（1）s.t■x■=■x■=1,k=1,2,…,K（2）■x■=■x■i=1,2,…,n,k=1,2,…,K（3）■y■≥1i=1,2,…,n（4）龙源期刊网■z■=d■i=1,2,…,n（5）■z■y■≤Q■k=1,2,…,K（6）S■+T■+t■+M1-x■≤S■i=1,2,…,n,k=1,2,…,K（7）■x■=y■i=1,2,…,n,k=1,2,…,K（8）（1）表示目标函数，由三部分组成：汽车的固定费用、可变费用和时间延误或者提前的惩罚；（2），（3）表示车辆从出发点出来完成任务后回到配送中心；（4）表示每个客户至少被服务一次；（5）表示客户需求量被满足；（6）是车辆载重约束；（7）是时间约束；（8）是客户车辆唯一性约束。2算法原理及步骤本文应用遗传算法来求解VRPTW问题，有如下步骤：2.1设计染色体结构首先要将问题解编码，常用的是自然数编码。0表示配送中心，1,2,…,n表示需求点集合。2.2生成初始群体Step1：随机给需求点排序。Step2：采用贪婪算法，从左到右计算，若第一辆车装载容量大于前a个需求点的需求量之和，且小于前a+1个客户需求量之和，则得到第一辆车负责送货的需求点子串l“12…a”。Step3：删去排序中的前a个物资需求点，同样方法计算确定第二辆车的负责送货的物资需求点子串2“a+la+2…b”。如此反复，直到所有车辆和客户被安排完。Step4：两子串间插入0后把所有子串连接，再首尾加0就可以得到一条初始染色体。Step5：重新给物资需求点随机排序，按照相同步骤可以得到另一条染色体。反复计算操作，直到染色体条数等于群体规模n时为止。2.3计算适应度根据公式：f■=■,h=1,2,…,n龙源期刊网式中，f■表示染色体h的适应度函数，Z■表示同代群体中最佳染色体的综合路权之和，Z■表示染色体h的综合路权之和。2.4复制算子Stepl：计算每条染色体的适应度f■，h=1,2,…,n。Step2：按适应度大小给n条染色体排序，复制适应度最大的染色体，将其作为下一代群体中第一个染色体。Step3：计算染色体选择概率w■：w■=■。Step4：计算染色体累计概率u■：u■=■w■,k=1,2,…,n。Step5：在0,1区间内产生均匀分布随机数R，若R≤u■，则复制父代群体中第一条染色体，否则复制第k条染色体，使得u■≤R≤u■成立k=2,…,n如此反复操作，复制新的染色体，直到符合群体规模为止。2.5交叉算子在车辆路径问题里，采用自然数编码，为了防止交叉过程中产生过多无效染色体，减弱对群体多样性的要求，采用改进的部分匹配交叉（PMX）方法。任意选取两个父代染色体，随机选取两个交叉点，将每一个染色体的交叉段移到对方染色体的首部，然后削去对方染色体的相同项得到子代个体。如：交叉率pc：交叉率一般来说应该比较大，0.4～0.99；推荐使用80％～95％，选择概率表示了被选择的种群总体被交叉的概率。交叉前随机次序，再逐组交叉。具体实施步骤过程说明如下所示:分别将双亲1中的3,4,5,6和双亲2中的6,9,2,1为映射段，在原始后代ａ中，城市1,2,9重复，城市3,4和5却丢失了。同理，在原始后代ｂ中，城市3,4和5重复，城市1,2,9丢失。根据确定的映射关系，重复的城市3,4和5分别被城市1,2和9代替，交换的子串保持不变。初始双亲：交换双亲的子串：映射将后代合法化：龙源期刊网变异算子由禁忌搜索算法来实现，变异率本来非常小，一般为5%以下，变异率也由本来的很小变成足够大。对于每一个染色体，生成0,1区间的随机数r，如果r≤P■（变异率），则对染色体进行TSM变异，否则考虑下一个染色体。2.7终止条件遗传算法的终止条件有两类常见条件：（1）采用设定最大（遗传）代数的方法，Ｔ：遗传运算终止进化代数，取50～500；一般可设定为100代。（2）根据个体的差异来判断，通过计算种群中基因多样性测度，即所有基因位相似程度来进行控制。具体有以下几种方式：①计算每代群体中染色体适应度的方差，当方差小于ε时，可认为算法收敛；②计算每代群体适应度均值，当均值与最佳染色体适应度的比值大于λ时，可认为算法收敛；③记录每代最佳染色体，若某染色体连续保持最佳达到Ｘ代，可终止算法。3结束语顾客对时间的需求变得越来越重要，作为物流配送方应当充分考虑时间性，将时间因素加入到问题的模型之中，运用现代启发式算法求解，得出的结果更合理，更符合实际。本文研究出了有时间窗车辆路径问题的模型和算法步骤，在实际应用中有关此类问题可以用上述方法来求解。参考文献：[1]徐小勇.有时间约束的非满载车辆调度问题的启发式改进算法[J].商场现代化，2009(2):137-138.[2]杨爱梅.带软时间窗的车辆路径问题研究[D].合肥：合肥工业大学（硕士论文），2009.[3]孟凡.有时间窗的物流配送车辆调度计划制定以及算法研究[D].武汉：武汉理工大学（硕士论文），2010.龙源期刊网[4]陈一永，许力.C-K节约算法在配载车辆调度问题中的应用研究[J].商场现代化，2009(1):149.