有时间约束的非满载VRP遗传算法研究.doc

龙源期刊网 有时间约束的非满载VRP遗传算法研究作者：张亮 杜培俊 何兆芳来源：物流科技2014年第06期摘要：顾客的需求越来越被关注，时间要求变得越来越重要。文章基于此，建立有时间约束的车辆路径问题模型，并引入遗传算法，纳入禁忌搜索，来求解此车辆路径模型。 关键词：软时间窗；遗传算法；VRP 中图分类号：F252.14文献标识码：A Abstract: With customers needs given more and more attention, time need has been more and more important, this paper constructs VRP model with time windows, and use genetic algorithms, combine with tabu search to solve this problem. Key words: soft time window; genetic algorithms; VRP 1问题的描述及数学模型的建立 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+cx+pS（1） s.t x=x=1, k=1,2,K（2） x=xi=1,2,n, k=1,2,K（3） y1i=1,2,n（4） z=di=1,2,n （5） zyQk=1,2,K （6） S+T+t+M1-xSi=1,2,n, k=1,2,K（7） x=yi=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“12a”。 Step3：删去排序中的前a个物资需求点，同样方法计算确定第二辆车的负责送货的物资需求点子串2“a+l a+2b”。如此反复，直到所有车辆和客户被安排完。 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，若Ru，则复制父代群体中第一条染色体，否则复制第k条染色体，使得uRu成立k=2,n如此反复操作，复制新的染色体，直到符合群体规模为止。 2.5交叉算子 在车辆路径问题里，采用自然数编码，为了防止交叉过程中产生过多无效染色体，减弱对群体多样性的要求，采用改进的部分匹配交叉（PMX）方法。任意选取两个父代染色体，随机选取两个交叉点，将每一个染色体的交叉段移到对方染色体的首部，然后削去对方染色体的相同项得到子代个体。如： 交叉率pc：交叉率一般来说应该比较大，0.40.99；推荐使用8095，选择概率表示了被选择的种群总体被交叉的概率。 交叉前随机次序，再逐组交叉。 具体实施步骤过程说明如下所示: 分别将双亲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代替，交换的子串保持不变。 初始双亲： 交换双亲的子串： 映射将后代合法化： 2.6变异算子 由禁忌搜索算法来实现，变异率本来非常小，一般为5%以下，变异率也由本来的很小变成足够大。 对于每一个染色体，生成0,1区间的随机数r，如果rP（变异率），则对染色体进行TSM变异，否则考虑下一个染色体。 2.7终止条件 遗传算法的终止条件有两类常见条件： （1）采用设定最大（遗传）代数的方法，：遗传运算终止进化代数，取50500；一般可设定为100代。 （2）根据个体的差异来判断，通过计算种群中基因多样性测度，即所有基因位相似程度来进行控制。具体有以下几种方式： 计算每代群体中染色体适应度的方差，当方差小于时，可认为算法收敛； 计算每代群体适应度均值，当均值与最佳染色体适应度的比值大于时，可认为算法收敛； 记录每代最佳染色体，若某染色体连续保持最佳达到代，可终止算法。 3结束语 顾客对时间的需求变得越来越重要，作为物流配送方应当充分考虑时间性，将时间因素加入到问题的模型之中，运用现代启发式算法求解，得出的结果更合理，更符合实际。本文研究出了有时间窗车辆路径问题的模型和算法步骤，在实际应用中有关此类问题可以用上述方法来求解。 参考文献： 1 徐小勇. 有时间约束的非满载车辆调度问题的启发式改进算法J. 商场现代化，2009(2):137-138. 2 杨爱梅. 带软