带有时间窗的车辆路径问题的优化研究

上海海事大学硕士学位论文带有时间窗的车辆路径问题的优化研究姓名：盛丽俊申请学位级别：硕士专业：管理科学与工程指导教师：周溪召20060601带有时间窗的车辆路径问题的优化研究作者：盛丽俊学位授予单位：上海海事大学相似文献(10条)1.期刊论文符卓.聂靖.FUZhuo.NIEJing求解带装载能力限制的开放式车辆路径问题的遗传算法-系统工程2008,26(2)对带装载能力限制的开放式车辆路径问题的求解进行了研究,提出了一种用于求解该问题的遗传算法.对算法中几个关键操作的不同实现方式的性能进行了比较.给出了算法对标准测试算例的运算结果,并与文献中目前最好的结果进行了比较和分析.2.学位论文曾凡超车辆路径问题的改进遗传算法2007在计算机飞速发展的今天，车辆路径问题(VehicleRoutingProblems，简称VRP)一直以来是众多计算机学者研究的焦点。如何针对车辆路径问题的特点，构造运算简单、性能优异的启发式算法，对物流系统及许多可以转化为车辆路径问题的组合优化问题都有十分重要的意义。因此，本文针对传统遗传算法求解车辆路径问题所存在的不足，将《作物育种学》中的理论分别应用于目前遗传算法求解车辆路径问题的两种最典型的算法：即广泛使用的单种群遗传算法和寻优效率较高的双种群遗传算法，并通过仿真实验验证了本文所设计的算法的性能。本文研究内容及成果如下：①针对传统遗传算法在求解车辆路径问题中存在的“早熟收敛”、易陷入局部极值点等不足，本文提出了将作物育种学中的差异性原理应用于遗传算法求解车辆路径问题的算法设计中的改进思路。我们将该原理应用到单种群遗传算法交叉前的父染色体选择过程，以及双种群遗传算法的种群交叉过程，通过模拟自然界中的进化规律来提高遗传算法的优化性能。②基于上述改进思路，本文设计了一种改进的单种群遗传算法。该算法通过采用新的父染色体选择策略以及新的交叉算子，能够保证一对适应值有一定差异的染色体进行交叉，使产生的后代性状分离。这样就可以增加种群中个体的多样性，扩展解的搜索空间，避免过早陷入局部最优，在优化性能的提高方面取得更好的效果。③基于上述改进思路，本文还设计了一种改进的双种群遗传算法。该算法采用了一种新的种群交叉策略，主要是针对种群间互换染色体这一步骤，对传统的双种群遗传算法做了改进。同时还提出了一种新的染色体交叉与变异策略，让两个种群使用不同的交叉和变异算子，以及不同的交叉和变异概率。通过新的种群交叉策略的引入和新的染色体交叉与变异策略的引入，改进后的算法能更有效地模拟现实物种进化过程，以保证种群内物种多样性，有利于整个种群的进化。④采用广泛使用的标准测试数据，对本文提出的单种群遗传算法和双种群遗传算法与传统遗传算法作了较为充分的实验测试和对比分析。实验结果表明，文中的方法能更为有效的求得车辆路径问题的优化解，克服传统遗传算法求解车辆路径问题中“早熟收敛”和易陷入局部极值的不足。上述研究成果，在基于遗传算法求解车辆路径问题领域中具有较好的学术参考价值，对物流系统的开发有很好的应用价值。3.期刊论文肖天国.符卓.XIAOTian-guo.FUZhuo求解带软时间窗的开放式车辆路径问题的遗传算法-铁道科学与工程学报2008,5(2)通过应用交叉、变异概率的自适应机制和交叉算子A等技术,构造了一个求解带软时间窗的开放式车辆路径问题的遗传算法.用标准测试算例对算法进行测试,并将运算结果与文献中相关算法的运算结果相比较.结果表明,该算法具有较好的性能.4.学位论文吴斌车辆路径问题的粒子群算法研究与应用2007物流被称为“第三利润源泉”，越来越受到人们的关注，日益成为国民经济的基础产业。运输是物流中的重要环节，占物流成本的60％以上。车辆路径问题主要研究物流配送中车辆线路优化以降低运输成本。该问题是运筹学和组合优化领域中的著名NP问题，在航班调度、列车编组等众多领域都有应用。由于NP问题求解的复杂性，目前车辆路径问题的求解方法主要使用各种智能优化算法。本文主要研究了以下四种模型的车辆路径问题：有能力约束的车辆路径问题，开放式车辆路径问题，基于客户满意度的开放式车辆路径问题，开放式动态网络车辆路径问题。研究了粒子群及其改进算法对上述模型的求解。具体的研究内容如下：(1)首先介绍了本论文的研究背景及意义，给出了车辆路径问题的定义，分析了车辆路径问题的组成要素。然后在对国内外大量文献总结提炼的基础上，从车辆路径问题的模型和求解算法两方面，深入分析了车辆路径问题的国内外研究现状。(2)系统研究了基于粒子群算法的有能力约束车辆路径问题(CapacityVehicleRoutingProblem，CVRP)。提出了整数编码、实数编码两种求解CVRP的方法。在整数编码中，以交换数为基础，对粒子的速度重新定义，并对速度的加、减等操作进行了定义，提出了“换位减”算子作为整数编码的速度计算方法：针对整数编码算法存在的问题，提出了一种实数编码方法求解CVRP，用实数的整数部分表示客户所在的车辆，小数部分表示在该车辆中配送的次序，融合遗传算法的思想，引入交叉算子以增加种群的多样性，详细讨论了粒子群算法的各个参数对算法结果的影响。为了与其他智能优化算法比较，研究了遗传算法、人工鱼群算法在CVRP中的应用。将双种群遗传算法用于CVRP的求解；提出了人工鱼群算法在CVRP中的应用，针对车辆路径问题的特点，定义了鱼群的距离、领域等概念，提出了人工鱼根据自身在鱼群中的排序，自适应选择移动算子的策略。(3)通过引入虚拟配送中心的概念，建立了开放式车辆路径问题的三下标数学模型。提出了开放式车辆路径问题的粒子群求解方法，将最邻近插入、最远插入、2-Opt、3-Opt等启发式算法作为再优化过程引入粒子群算法，通过这些启发式算法调整线路内和线路间的客户来改进解，从理论上分析了这些算法的计算复杂度。通过实验分析，找出合适的启发式算子，并和其他的算法进行了比较。(4)以客户满意度为首要优化目标，建立了基于客户满意度的开放式车辆路径问题的数学模型，使用梯形模糊数表示客户满意度。综合考虑距离、等待时间、客户的满意度等因素，定义了广义的距离和节约费用的概念，提出了改进的最邻近法和最廉价插入法，将这两个算法作为初始化和改进算子结合粒子群算法进行优化求解。分析了算法的复杂度，对算法的各个参数进行了讨论，通过实验仿真对这几种方法进行了分析比较。(5)动态网络车辆路径问题目前研究的热点和难点问题，将动态网络与开放式两个因素结合起来研究车辆路径问题还未见报道。本文针建立了开放式动态网络车辆路径问题的数学模型，提出了一种连续时间依赖函数模型。提出了自适应惯性权重调整的粒子群算法，定义了粒子的“位置比”概念，充分利用粒子的已有知识，动态的调整惯性权重。在算法中，引入公告板策略，根据粒子适应度的高低分类更新粒子状态，对于优秀粒子使用一种新的状态更新公式，以使其跳出局部极值点。对于适应度低的粒子，通过统计其在公告板中出现的频率，用新的粒子替换以保持种群的多样性。通过实验讨论了算法的参数设置，对几种惯性权重方案进行了分析比较，实验结果证明了算法的有效性。(6)在上述理论工作的基础上，针对第三方物流在国内的迅速发展，而相应的车辆调度软件功能不够完善，开发了智能车辆调度系统。该系统包括智能车辆调度、承运单的管理、电子地图的显示等功能。该系统可以处理有时间窗、有能力约束等多种情况的车辆调度问题，提供遗传算法、粒子群算法等多种优化算法供用户使用。系统在杭州某物流公司应用，取得了良好的效果。最后，对全文研究工作进行了总结，展望了车辆路径问题的模型和算法研究的前景。5.期刊论文隆颖.LONGYing用遗传算法求解带回程取货的车辆路径问题-辽宁师专学报（自然科学版）2005,7(3)带回程取货的车辆路径问题可以同时服务路径上的取货送货节点,通过对该问题的研究,利用改进的遗传算法对其求解,并通过实例证明其有效性.6.学位论文商丽媛车辆路径问题遗传算法的设计与分析2006物流是一个新兴学科，配送是现代物流的一个重要内容，合理安排车辆配送路线可以降低运输成本，提高经济效益。车辆路径问题是一类在物流配送调度中具有广泛应用的组合优化问题，属于强NP难题。有时间窗装卸问题比具有简单约束的车辆路径问题更加难以求解。本文首先介绍了遗传算法在解决简单约束车辆路径问题上的应用，改进了交叉算子，为研究有时间窗装卸问题的遗传算法作了充分准备。本文详细分析了有时间窗装卸问题的数学模型，深入研究解决此问题的分组编码遗传算法，将禁忌思想用于产生可行解的启发式插入搜索算法之中，并构造出适用于多目标的适应度函数，设计新的数据结构，对分组编码遗传算法进行有效实现。在分组编码遗传算法中提出路径调整思想，设计出一种多策略分组编码遗传算法。采用多组通用算例测算，将多策略分组编码遗传算法与其它算法进行比较，其求解结果和计算时间都有明显改进，验证了多策略分组编码遗传算法能够有效稳定地收敛到所求问题的解。7.期刊论文曾凡超.朱征宇.邓欣.何兴无.ZENGFan-chao.ZHUZheng-yu.DENGXin.HEXing-wu车辆路径问题的改进的双种群遗传算法-计算机工程与设计2007,28(20)提出了一种基于车辆路径问题的改进双种群遗传算法.该改进双种群遗传算法主要通过两个种群同时进行进化操作,并结合新交叉算子和种群交叉策略,以克服传统双种群遗传算法在求解车辆路径问题上所存在的不足.通过仿真实验,将改进的双种群遗传算法与其它几种遗传算法进行比较,改进的双种群遗传算法比其它几种遗传算法显著提高了优化效果.实验结果表明,该算法可以有效求得该问题的优化解,是解决车辆路径问题的好方法.8.期刊论文赵燕伟.吴斌.蒋丽.董红召.王万良车辆路径问题的双种群遗传算法求解方法-计算机集成制造系统2004,10(3)针对标准遗传算法在求解车辆路径问题中出现的早熟、收敛,易陷入局部极值点的问题,提出双种群遗传算法求解车辆路径问题的方法.在求解过程中,初始化两个种群,分别选择不同的交叉、变异概率,在一次迭代完成后,交换种群间的优秀个体所携带的遗传信息,以打破种群内的平衡态,跳出局部最优解.通过实验仿真,将双种群遗传算法与其他各种启发式算法进行比较,双种群遗传算法比标准遗传算法显著提高了全局收敛性能,是解决车辆路径问题的有效方法.9.学位论文肖鹏遗传算法及其在车辆路径问题中的应用研究2000遗传算法是基于自然选择与遗传概念上的搜索算法.它通过模拟自然界的生物进化过程,达到搜索寻优的目的.该文自选在理论上系统地介绍了遗传算法的特点和运行机理,然后研究了遗传算法在车辆路径问题中的应用.该文分别用PMX算子的遗传算法、单亲遗传算法求解了车辆路径问题.计算机上的仿真试验结果表明,遗传算法是求解车辆路径问题的一个较好的方案.另一方面,通过比较这两种遗传算法以及它们的改型算法,发现新颖的单亲遗传算法在志优效率和早熟收敛问题上,比传统遗传算法更具优势.10.期刊论文黄明.林广智.梁旭.王德广.HUANGMing.LINGuang-zhi.LIANGXu.WANGDe-guang改进的遗传算法在车辆路径问题中的应用-大连交通大学学报2010,31(1)通过对车辆路径问题的深入分析,针对遗传算法中种群多样性和选择压力两个最重要因素,对交叉算子和变异算子进行了改进,并和一般的遗传算法进行了比较,通过计算结果证明:在算法性能方面,改进的算法收敛速度较快,所求得的最优解质量较高,且计算结果稳定;在车辆配送路径方面,改进算法得到四条最优配送路线,并且四条线路没有交叉,完全形成回路,又同时满足车辆满载率的限制,而一般的遗传算法得到五条配送路线,最低装载量仅为3.1t,并不能达到车辆相应的满载率,因此,改进的遗传算法明显优于传统的遗传算法.本文链接：授权使用：上海海事大学(wflshyxy)，授权号：3e481b3e-c3b7-4e7b-b6e8-9e0600aff39e下载时间：2010年10