开题报告带时间窗约束的VRP的节约算法剖析

毕业论文开题报告题 目： 带时间窗约束的VRP的节约算法 毕 业 设 计（论 文）开 题 报 告1文献综述：结合毕业设计（论文）课题情况，根据所查阅的文献资料，每人撰写2500字以上的文献综述，文后应列出所查阅的文献资料。在人类征服自然、改造自然的进程中,一直伴随着各式各样的物流活动,可以这样说,人类的文明史就是一部物流发展和变革的历史,经济的发展和科学技术的进步促进了物流活动的广度和深度,而物流活动的扩大和深化又进一步推动了经济和社会的发展。亚当.斯密在国富论中指出,市场经济的发展由社会分工所支持,社会分工的广度依存于市场的扩大,进而市场的扩大又是以运输为中心的物流活动所支持。尽管物流活动自古有之,但直到1915年,“物流”这一名词才第一次出现在阿齐.肖的市场流通中的若干问题一书中,经过数十年的理论研究和实际运作,人们认识到合理、高效的物流能够从以下几方面创造社会财富:（1）促进国民经济合理布局,有利于社会资源的优化配置;（2）有效地使用流通设施和设备,节约社会资源;（3）减少流通环节,缩短生产周期,加速资金周转;（4）促进社会分工,加速生产的集中化、规模化。人们对物流合理化进行了坚持不懈的探索,其中对车辆路径问题(Vehicle Routing Problems,简称VRP)的理论和应用研究非常具有代表性,Canen 和Seott 将VRP称为“最近十年运筹学领域最成功的研究之一”。具有学术背景的运筹学学者不仅设计和改进了形式多样的模型和算法,而且对推动路径系统在实际中的应用也起到重要作用;另一方面,由于符合生产需要的计算机软件的成功研制,工商业者对车辆路径问题的重视也日益加强。随着现代科学技术的迅猛发展以及全球经济一体化趋势的加强，各国都面临着前所未有的机遇和挑战。现代物流作为一种先进的组织方式和管理技术，被广泛认为是企业在降低物资消耗，提高劳动生产率以外的重要的利润源泉，在国民经济和社会发展中发挥着重要作用。由于JIT理论和实践的成熟，现代产业对物流配送提出了更高的要求将合适的零件以合适的数量在合适的时间送到生产线。这是为适应消费需要变得多样化、个性化而建立的一种生产体系及为此生产体系服务的物流体系。消费者需求趋于多样化，对送货时间的要求日趋严格，除了因缺货造成的机会成本的损失外，由于配送不及时也会造成货物价值的大大降低。在配送运输上，时间窗口显得越来越重要。因此，降低运输成本，提高配送的及时性和配送的服务质量，优化车辆路径问题，是降低企业成本的迫切需要。车辆路径问题是研究如何通过合理规划行驶路线来实现运输成本优化的一类优化调度问题,其相关理论和算法对于降低物流成本具有重要的应用价值,因此一直是运筹学和组合优化领域的研究热点。多年来车辆路径问题已衍生出众多研究分支,如开放式车辆路径问题、多站点车辆路径问题、装卸货车辆路径问题、带时间窗车辆路径问题和周期性车辆路径问题等,并取得了大量的研究成果,同时车辆路径问题也广泛应用于生产和生活的各个方面,如信件投递、货物配送、车辆调度等,产生了巨大的经济效益。在实际生活中,常常存在这样一类车辆路径问题:用户对时间有较为严格的要求,他们希望在事先指定的时间区间内进行服务,因此在规划车辆的行驶路线时,不仅要考虑车辆的负载限制,还要同时考虑用户时间要求的满足。这一类问题可以抽象为带时间窗的车辆路径问题,其中用户指定的时间区间称为时间窗。由于时间窗约束的引进,带时间窗的车辆路径问题的求解更加困难,因此带时间窗的车辆路径问题一直是车辆路径问题中最重要的研究分支之一。目前，我国物流业处于快速发展阶段，2006-2011年社会物流总费用年复合增速17%。但物流效率不高，物流总费用占GDP比例17.8%，两倍于欧美日等发达国家。通过中国期刊数据库检索，19942005年12年时间，在中国的正式期刊上已经发表该领域的文章仅二十多篇。就这方面研究的深度和广度来说，远不能适应当前我国配送业以及物流业迅速发展的需要。国内在车辆路径问题上的研究基本上着重于车辆路径问题的启发式算法研究。如王雷1用节约法解带有时间窗的车辆调度问题中通过建立带时间窗的非满载车辆优化调度的数字模型，并利用节约算法对带时间窗的非满载车辆调度问题模型进行研究，并应用此算法对带有时间窗车辆调度问题进行仿真，得到最优解，证明此算法的优越性；李大卫、王莉、王梦光2一个求解带有时间窗口约束的车辆路径问题的启发式算法对适用于旅行商问题的最近距离搜索启发式算法进行修正，构造出评价函数，并依此提出一个求解有时间窗约束的车辆路径问题的启发式算法。求解具体算例表明，此算法是有效的；王科峰，叶春明，唐国春在6带时间窗分车运输同时收发车辆路径问题及其启发式算法结合汽车零部件第三方物流的实际背景,提出了带时间窗的可分车运输同时收发车辆路径问题,并给出了问题的数学模型,同时提出两个求解该问题的启发式算法,最后进行了数值试验；霍佳震、张磊在7有时间窗的集货送货一体化车辆路径规划启发式算法研究中通过对模型的分析、分解和过虑，结合实际情况，以修正的ClarkeWright节约启发式算法为基础进行插入式排序，以解决带有时间窗口的集货和送货一体化路径规划问题；赵建有,吴利清,刘大学在15带时间窗车辆路径问题的启发式遗传算法为了在运输生产中按时间要求合理安排车辆路径，建立了带时间窗车辆路径问题数学模型，用启发式遗传算法进行求解。先构造染色体，产生初始群，再对其进行优化，根据个体生存能力的体现进行性能估计，并计算优化值。运用Visual Basic编写相应计算程序，设定迭代代数为100,运算次数为10次，对有时间窗限制的有1个中心仓库与8个分仓库的实际问题进行求解。模拟结果显示需要3辆车按照3条运输线路进行物流配送服务，总运行距离为483 km，总运行时间为15. 55 h，车辆未出现闲置时间，且全部仓库得到及时服务。可见启发式遗传算法有效、可行；龚延成、郭晓汾、田光均、钱秋生在17带时间窗约束的物流配送线路启发式算法提出带时间窗约束的物流配送线路选择模型，阐述启发式算法的构造原理和计算程序，并通过算例验证模型的可行性和启发式算法的优良特性。国外关于车辆路径问题的研究较早，最初由Dantzig和Ramser于1959年首先提出的，很快引起运筹学、应用数学、组合数学、网络分析、图论、计算机应用等学科的专家与运输计划制定者和管理者的极大重视，他们进行了大量的理论研究及试验分析，取得了很大进展。以Bodlin，Christofider，Golden，Assad, Ball为代表的学者对该问题进行了较为深入的研究，完善了该问题的模型和算法。目前国外着重研究各种车辆路径问题以及相关启发式算法的探索。如： Olatz Arbelaitz,Clemente Rodriguez在19Comparison of systems based on evolutionary search and simulated annealing to solve the VRPTW中介绍了几种解决VRPTW的系统设计与分析，把搜索限制在小范围可行解之内,并把META启发方法和路线规划启发方法结合起来。Hoong Chuin Lau , Zhe Liang在20Pick and delivery with time windows :algorithms and test case generation中提出了两阶段方法来解决车辆路径问题，在第一阶段中运用了新的路径规划启发式算法来获得初始解，第二阶段用禁忌算法来改进解。WeeKi ,A Hbrid.t在21Search algorithm for the vehicle routing problem with time windows中重点研究了禁忌算法和遗传算法混合的启发式算法。禁忌搜索优势在于局部搜索，遗传算法优势在于全局搜索，文章将两种优势结合寻求近最优解。二. 参考文献1 王雷.用节约法解带有时间窗的车辆调度问题J. 黑龙江工程学院学报:自然科学版,2011，25(3):18-20. 2 李大卫,王莉,王梦光.一个求解带有时间窗口约束的车辆路径问题的启发式算法J .系统工程,1998,16(4):56-58.3 陆琳.不确定信息车辆路径问题及其智能算法研究M.北京:科学出版社,2010:8-13.4 张炯,郎茂祥.有时间窗配送车辆调度问题的禁忌搜索算法J.北方交通大学学报,2004,28(2):103-110.5 舒永钢.基于真实街道的规模配送车辆线路优化问题研究D.硕士.杭州：杭州商学院,200 王科峰,叶春明，唐国春.带时间窗分车运输同时收发车辆路径问题及其启发式算法J.运筹与管理,2012.4,21(2):48-50. 7 霍佳震,张磊.用节约法解决带有时间窗的满载车辆调度问题J.工业工程与管理,2006(4):64-66.8 陈火根,丁红钢,程耀东.物流配送中心车辆调度模型与遗传算法设计J.浙江大学学报(工学版),2003.9,37(5):513-516.9 赵冰洁.配送中心配送方案优化研究D.四川：四川大学,2004.6.1. 10 曹亮.用多种群自适应混合遗传算法求解车辆路径问题D.硕士.广州:中山大学,2004.6.1. 11 刘小兰.有时间窗的车辆路径问题（VRPTW）的近似算法研究D.吉林:东北大学,2003.5.20. 12 魏百鑫,史海波.基于整车配送的多仓库开路VRPTW问题的研究与实现J.信息与控制,2005.6,34(3):64-71.13 黄岚,庞巍,王康平等.遗传算法求解带时间窗的车辆路由问题J.小型微型计算机系统,2005.2,26(2):84-89. 14 陈一永,韩江,龚延成.带时间窗约束的配载车辆调度问题研究流技术J. 物流技术,2005,3(3):48-50.15 赵建有,吴利清,刘大学.带时间窗车辆路径问题的启发式遗传算法J.交通运输工程学报,2008,8(1):26-28.16 宋伟刚,张宏霞,佟玲.有时间窗约束非满载车辆调度问题的节约算法J.东北大学学报,2006,27(1):65-68.17 龚延成,郭晓汾,田光均，钱秋生.带时间窗约束的物流配送线路启发式算法J.交通与计算机,2003,6(21):11-14.18 杨霞芳,吴华,杨晟.现代物流技术M.上海：上海财经大学出版社,2004:7-12.19 Hoong Chuin Lau , Zhe Liang. Pick and delivery with time windows :Algorithms and test case generation J. International Journal on Artificial Intelligence Tools,2002,11(3):455-472.20 WeeKit ,A Hbrid. Search algorithm for the vehicle routing problem with time windows J. International Journal On Artificial Intelligence Tools,2001,10(3):431-449.21 Olatz Arbelaitz,Clemente Rodriguez. Comparison of systems based on evolutionary search and simulated annealing to solve the VRPTWJ .International Journal of Computational Intelligence and Applications .2004,(4).1：27-39.22 PotVin J.Y,Rousseau J. A parallel route building algorithm for the vehicle routing and scheduling problem with time windowsJ. European Journal of Operational Research,1993,66 (4):331-340.23 Madsen O.B.G, Ravn H.F,Voelds J. A heuristic method for dispatching repair menJ.Annals of Operations Research,1995,11(61):193-208. 毕 业 设 计（论 文）开 题 报 告开题报告：一、课题的目的与意义；二、课题发展现状和前景展望；三、课题主要内容和要求；四、研究方法、步骤和措施一、课题的目的与意义交通运输是国民经济的动脉，它对社会经济发展和人民生活起着极为重要的作用。据资料报道，在发达国家，由于物流业发达，运输成本占国民经济成本的比例只有10%，而我国则占30%，有的商品高达60%-70%，如果采用第三方物流的方式，可以使企业成本降低10%。本文研究意义如下:（1）车辆路径问题(VRP)是运输组织优化中的核心问题，对其进行广泛和深入的研究，建立其相应的理论和方法，既可以促进运筹学学科的发展，又可以将其应用到物流配送管理和交通运输管理学科中，改进现有的运输组织优化理论和方法，以适应新时代对物流配送和交通运输生产组织提出的新要求，对改进运输管理水平，提高运输效益，具有非常重要的实际意义。（2）本文通过对车辆路径问题(VRP)的系统研究，建立起VRP数学模型。同时，利用节约算法，构建了车辆路径问题的节约算法解决方案。对我国物流行业改良车辆运输路线方案有着积极的作用，也对基于节约算法的物流的车辆路径问题的研究有着一定的参考价值。（3）由于从事物流配送的汽车货运工作尤其是从事城市配送的汽车货运工作条件复杂，不仅货运点多、车辆满载与非满载等。所以VRP的影响因素也多，本文尝试在一个数学模型中去考虑满载与非满载VRP的影响，努力使构建的VRP数学模型能够和实际情况更加贴近。二、课题发展现状和前景展望经过几十年的研究发展，车辆路线问题研究取得了大量成果。 企业技术水平和内部管理水平的不断提高，使得生产和销售领域内降低成本的空间越来越小，在生产和销售领域以外的运输、仓储、配送、库存等环节上的成本比重越来越高。企业经营决策者不得不把寻求成本优势的视角转向“第三利润的源泉”物流领域。从运输成本看，我们还有很大的空间可以去努力。据统计，各国运输成本占国民生产总值的10% 15%左右。这就意味着运输系统的效率提高一点就可以节约很多成本。只要我们能够将现有运输成本降低，我们的国民经济总体水平就能出现一次新的飞跃，一次真正的飞跃。三、三、课题主要内容和要求论文的主要思路是构建以配送成本最小、所用车辆数目最小、顾客满意度最大为目标的新模型。利用节约算法的原理和其特殊优势，建立了带有时间窗的非满载和满载车辆调度模型，并对模型的解法进行了完整的描述。通过实例验证说明采用节约算法求解车辆调度问题，要优于一对一配送。论文的内容如下:（1）介绍VRP的概念，意义，研究现状与背景以及研究存在的问题。（2）对VRP基本理论,分类及约束条件进行描述。（3）建立带有时间窗的非满载和满载车辆调度模型，并对模型的解法进行完整的描述。（4）通过实例验证说明采用节约算法求解VRP。 四、研究方法、步骤和措施研究方法（1）文献资料法：通过查看理论的文献资料，对VRP问