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

有时间约束的非满载VRP遗传算法研究 　　摘要：顾客的需求越来越被关注，时间要求变得越来越重要。文章基于此，建立有时间约束的车辆路径问题模型，并引入遗传算法，纳入禁忌有哪些信誉好的足球投注网站，来求解此车辆路径模型。 　　关键词：软时间窗；遗传算法；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+■■■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+l a+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交叉算子