基于蚁群算法的VRPTW问题优化研究附属材料

湖州师范学院————————————————商学院毕业论文附属过程管理材料专业物流管理学号11012645学生姓名屠娟湖州师范学院教务处印制目录1.湖州师范学院本科生毕业论文诚信承诺书2.湖州师范学院本科毕业论文开题报告3.文献综述4.湖州师范学院本科毕业论文指导教师审阅表5.湖州师范学院本科毕业论文评阅人评阅表6.湖州师范学院本科毕业论文答辩记录表7.湖州师范学院本科毕业论文评分表湖州师范学院本科生毕业论文诚信承诺书毕业论文题目中文：基于蚁群算法的VRPTW问题优化研究外文：OptimizationoftheVRPTWbasedonAntColonyAlgorithm学生姓名屠娟年级2011级学号2011012645系别电子商务所学专业物流管理学生承诺我承诺在毕业论文活动中遵守学校有关规定，恪守学术规范，在本人的毕业论文内容除特别注明和引用外，均为本人观点，不存在剽窃、抄袭他人的学术观点、思想和成果，不存在伪造、篡改数据。如有违规行为发生我愿承担一切责任，接受学校的处理，并承担相应的法律责任。学生（签名）：2015年4月25日指导教师承诺我承诺在指导学生毕业论文活动中，遵守学校有关规定，认真指导，教育学生遵守学术规范，禁止、杜绝剽窃、抄袭他人学术观点、思想和成果的行为。指导教师（签名）：2015年4月30日湖州师范学院毕业论文开题报告学生姓名屠娟班级110126学号11012645专业电子商务指导教师张慧涛开题时间2014.9.26设计（论文）题目基于蚁群算法的VRTW问题优化研究选题意义、研究现状及存在问题选题意义：随着企业的发展，作为第三利润源的物流的重要性便越发突出。而在企业经营中，物流配送能力的高低已成为衡量企业竞争力的一大方面。设计一个高效的物流配送路径优化方案不仅可以提高配送效率，对进行配送活动的资源（如车辆等）做到物尽其用，可以最大化地降低配送成本，提高配送车辆利用率；此外，在客户规定的时间内高效地将货物送达，将会极大程度地提高客户的满意度，提升企业服务质量，从而提升企业的潜在效益；这些都将有利于企业提高运营效益，增强企业的核心竞争力。路径优化理论与方法的系统研究是物流集约化发展、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。研究现状：VRP优化问题的研究在理论上具有重要的意义，实际中具有广泛的应用，得到了国内外学者的大量而深入的研究。在近几十年里，国外对物流配送车辆路径优化问题作了大量深入的研究，而在国内对此方面的研究在20世纪90年代才逐渐兴起，与国外相比，相对落后。虽然在车辆路径问题研究方面有些落后，但也有一些成果，如李大为等把TSP的最近距离启发式作为基础，并通过对评价函数的设置来处理带有时间窗约束的简单VR问题；蒋忠中等（2006）研究了考虑车辆行驶时间和顾客服务时间的不确定性的车辆路径优化问题，提出了将物流配送网络由配送中心和顾客两类节点构成的不完全无向图表示，建立了物流配送车辆路径优化的模糊规划模型。存在问题：总体来说，我国目前对车辆路径问题的理论研究虽然还相对薄弱，需作进一步研究，但也取得了许多有意义、有价值的成果。许多研究在理论观点及研究方法上为我们进一步探讨物流配送路径优化提供了帮助。但由于我国现有的信息技术手段不强，较好的优化技术无法实施，因此如何结合优化算法与计算机技术并应用与实际仍是重要课题。同时，路径优化的目标属性不够充分，与现实差距较大，目前针对路径优化的研究目标是不一样,单目标的往往是从某一个角度去考虑问题,而很少是全面的系统的考虑,即使有,也是多目标的,相应的增加了计算的复杂度,尤其是各目标之间的权重分配,极大的影响了寻优方案的结果。可以说目标属性不能贴近现实,与现实的差距比较大。因此迫切需要一种可以解决上述问题的寻优策略模型。本文将综合国内外相关研究成果，运用蚁群算法对物流配送路径优化问题进行分析，结合实例提出优化方案，以达到降低物流配送成本，增加企业效益的目的樟子松大连婚纱摄影研究目标和内容研究目标：本文从企业物流资源（车辆等）的利用最大化出发，研究了国内外对物流配送路径优化的相关优秀成果，分析了配送路径优化的现状及研究趋势，总结归纳各类算法的优劣势，以期在以往研究的基础上,建立更接近实际的物流配送网络路径优化模型,研究更加有效的优化算法，为物流配送网络路径优化问题的研究和实践提供理论依据和实际方法。研究内容：随着中国经济的愈加繁荣，物流配送业也得到了快速发展，对于车辆路径优化也就显得愈发重要，而物流配送车辆优化属于软件技术问题,主要涉及利用各种先进的信息技术和方法对车辆及其路线的组合进行合理的规划安排,这是本文主要研究的问题，将从以下方面进行分析研究：（1）VRP问题及蚁群算法相关理论知识。（2）对VRTWP模型进行假定并确定模型。（4）对基于集群算法的VRPTW问题求解。（5）应用上述模型进行算例验证。研究方法、步骤和措施研究方法：1.文献分析法：通过对相关文献的总结归纳搜集基于蚁群算法下的VRP问题优化的理论概述。2.综合分析法：结合国内外相关研究，对VRP问题优化进行现状分析3.定量分析法：运用蚁群算法构建VRTWP问题优化模型，并进行算例分析。研究步骤：1.搜集资料：互联网相关资料、数据库相关文献。2.在搜集到的资料进行整理和分析，对其中的观点进行归纳和整合，最后建立理论框架。3.对资料中的VRP问题解决模型进行研究，确定VRP问题前提条件，建立假定模型，最后确定VRP问题模型并求解。研究措施：1.将搜集的资料根据信息源的不同完成信息的汇总工作。在思想体系整合阶段则转为在导师的引导和帮助下完成。2.期间经过若干次调整和完善后，在导师的指导下，通过与导师的直接交流和意见交换来完成，同时后两者的操作过程中仍需不断进行材料的补充和修改。研究的总体安排与进度根据学院总院总体安排与要求，了解本论文所涉及问题的研究现状，提出大纲，在老师指导并通过后，进入撰写。2014年9月22日-9月26日，拟定论文题目，最后在指导老师指导下确定题目。9月27日-10月8日：查阅资料，完成开题报告及文献综述等附属材料的初稿及论文大纲。10月9日-10月15日：在指导老师指导下对附属材料及大纲进行修改、定稿。10月16日-10月中旬：收集资料，论文写作开始并完成一稿。11月底：提交论文的中期报告及论文二稿。2015年3月：完善和修改论文。4月：论文基本定稿。主要参考文献[1]靳向宇.基于蚁群算法的邯郸市世佳连锁超市配送路线优化问题研究[D].中国海洋大学,2013.[2]姜红.佳佰嘉连锁超市配送路线优化研究[D].中国海洋大学,2013.[3]高蓉.基于蚁群算法的旅游交通线路优化问题研究[D].北京交通大学,2008.[4]张怀峰.蚁群算法在物流配送路径问题上的应用研究[D].江苏大学,2009.[5]蒋忠中,汪定伟.B2C电子商务中物流配送路径优化的模型与算法[J].信息与控制,2005,04:481-485.[6]刘云忠,宣慧玉.车辆路径问题的模型及算法研究综述[J].管理工程学报,2005,01:124-130.[7]陈君兰,叶春明.物流配送车辆调度问题算法综述[J].物流科技,2012,03:8-12.[8]张红霞,黄晓霞.物流企业配送车辆调度问题研究综述[J].电脑知识与技术,2009,13:3419-3421+3445.[9]李化.配送路线优化模型研究[J].商场现代化,2009,05:130-131.[10]钟敏,刘兴.农产品收集(配送)路径模型及算法[J].中国农机化,2007,04:49-52[11]薛戈丽,王建平.一种基于蚁群算法的物流配送VRP解决方案[J].计算机系统应用,2012,02:200-203.[12]孙丽君,胡祥培,王征.车辆路径规划问题及其求解方法研究进展[J].系统工程,2006,11:31-37.[13]贾楠,吕永波,付蓬勃,任远.物流配送问题中VRP的数学模型及其求解算法[J].物流技术,2007,04:54-56.[14]刘勇,崔炳谋,王小东.物流配送路径优化问题的模型及改进混合算法[J].物流科技,2008,04:26-30.[15]龚国清,基于分枝定界法的旋转货架存取路径优化[J].物流科技,2007,12:23-25.[16]尹晓峰,杜艳萍.车辆路径问题的蚁群算法研究[J].太原科技人学学报.2005.04:279-283.[17]B.GillettandL.RMiller,AHeuristicAlgorithmfortheVehicleDispatchProblem[J].OperationsResearch,1974,340-349.[18]DuanB,YeS,AMixedMethodforShapeOptimizationofSkeletalStructures[J].EngineeringOptimization,1986,10(3):16-19.[19]HongtaoShi,YucaiDong,LianghaiYi,DongyunZheng,HongJu,ErchangMa,WeidongLi.StudyontheRouteOptimizationofMilitaryLogisticsDistributioninWartimeBasedontheAntColonyAlgorithm[J].ComputerandInformationScience,2010,Vol.3(1).[20]RuixueTang,YongbinQin,LiZhang.ResearchonHeuristicsLogisticsDistributionAlgorithmBasedonParallelMulti-antColonies[J].JournalofSoftware,2011,Vol.6(4):612-619.指导教师审核意见指导教师（签名）2015年4月27日文献综述11012645屠娟摘要：物流配送已经成为企业经营发展的关键环节，而合理的配送路径优化能够有效利用现有资源进行车辆调度，从而缩减成本，实现利润最大化。本综述评述了物流配送路径优化的基本概况，从货物、客户的相关属性等方面指出了目前配送路径优化的实施难点，并对物流配送路线优化问题的分类以及配送路径优化问题的解决算法即精确算法、传统启发式算法和现代启发式算法的现有文献进行总结分析，以期对未来路径优化问题的解决提供帮助。关键词：VRP问题;路径优化问题;物流配送前言随着企业的发展，作为第三利润源的物流的重要性便越发突出。而在企业经营中，物流配送能力的高低已成为体现企业竞争力的一大方面，配送中心的配送决定了物流配送效率,而配送效率的高低是衡量企业盈利能力的重要指标。为了实现高效率的配送，就需要根据企业配送模式进行配送路线优化,实现配送资源的充分利用。通过对配送路径的优化，能够使货物在客户规定的时间内高效送达，实现对企业资源利用的最大化，提高客户的满意度，提升企业服务质量，从而达到降低配送成本，提升企业的潜在效益的目的。目前对于物流配送路径优化有许多研究，本文拟对物流配送路径优化基本概况及问题的解决算法进行了解与综述，为物流配送路径优化问题的解决提供相应建议。主题一、物流配送路径优化基本概况随着中国经济的愈加繁荣，物流配送业也得到了快速发展。但在物流配送环节中，仍存在许多优化问题有待解决。优化配送路径问题类似“旅行商”（TSP）问题,要求遍历所有的客户点,不同的是,物流配送问题是由多辆车对客户点进行遍历,每辆车负责配送的客户点以及配送路径都是不确定的,这正是配送路径优化所要解决的问题。1、物流配送路径优化问题的分类勒向宇（2013）认为配送路线优化的本质是研究配送车辆的路径优化选择问题。最常见的有VRP即(VehicleRoutingProblem,即车辆路径问题)、VSP(VehicleSchedulingProblem,即车辆调度问题)和TSP(Traveling