开题报告带时间窗约束的VRP的节约算法讲述.doc

毕业论文开题报告 题 目： 带时间窗约束的VRP的节约算法  毕 业 设 计（论 文）开 题 报 告 1．文献综述：结合毕业设计（论文）课题情况，根据所查阅的文献资料，每人撰写2500字以上的文献综述，文后应列出所查阅的文献资料。 在人类征服自然、改造自然的进程中,一直伴随着各式各样的物流活动,可以这样说,人类的文明史就是一部物流发展和变革的历史,经济的发展和科学技术的进步促进了物流活动的广度和深度,而物流活动的扩大和深化又进一步推动了经济和社会的发展。亚当.斯密在《国富论》中指出,市场经济的发展由社会分工所支持,社会分工的广度依存于市场的扩大,进而市场的扩大又是以运输为中心的物流活动所支持。 尽管物流活动自古有之,但直到1915年,“物流”这一名词才第一次出现在阿齐.肖的《市场流通中的若干问题》一书中,经过数十年的理论研究和实际运作,人们认识到合理、高效的物流能够从以下几方面创造社会财富: （1）Vehicle Routing Problems,简称VRP)的理论和应用研究非常具有代表性,Canen 和Seott 将VRP称为“最近十年运筹学领域最成功的研究之一”。具有学术背景的运筹学学者不仅设计和改进了形式多样的模型和算法,而且对推动路径系统在实际中的应用也起到重要作用;另一方面,由于符合生产需要的计算机软件的成功研制,工商业者对车辆路径问题的重视也日益加强。 随着现代科学技术的迅猛发展以及全球经济一体化趋势的加强，各国都面临着前所未有的机遇和挑战。现代物流作为一种先进的组织方式和管理技术，被广泛认为是企业在降低物资消耗，提高劳动生产率以外的重要的利润源泉，在国民经济和社会发展中发挥着重要作用。由于JIT理论和实践的成熟，现代产业对物流配送提出了更高的要求——将合适的零件以合适的数量在合适的时间送到生产线。这是为适应消费需要变得多样化、个性化而建立的一种生产体系及为此生产体系服务的物流体系1994～2005年12年时间，在中国的正式期刊上已经发表该领域的文章仅二十多篇。就这方面研究的深度和广度来说，远不能适应当前我国配送业以及物流业迅速发展的需要。国内在车辆路径问题上的研究基本上着重于车辆路径问题的启发式算法研究。如王雷[1]《用节约法解带有时间窗的车辆调度问题》中通过建立带时间窗的非满载车辆优化调度的数字模型，并利用节约算法对带时间窗的非满载车辆调度问题模型进行研究，并应用此算法对带有时间窗车辆调度问题进行仿真，得到最优解，证明此算法的优越性；李大卫、王莉、王梦光[2]《一个求解带有时间窗口约束的车辆路径问题的启发式算法》对适用于旅行商问题的最近距离有哪些信誉好的足球投注网站启发式算法进行修正，构造出评价函数，并依此提出一个求解有时间窗约束的车辆路径问题的启发式算法。求解具体算例表明，此算法是有效的；王科峰，叶春明，唐国春在[6]《带时间窗分车运输同时收发车辆路径问题及其启发式算法》结合汽车零部件第三方物流的实际背景,提出了带时间窗的可分车运输同时收发车辆路径问题,并给出了问题的数学模型,同时提出两个求解该问题的启发式算法,最后进行了数值试验；霍佳震、张磊在[7]《有时间窗的集货送货一体化车辆路径规划启发式算法研究》中通过对模型的分析、分解和过虑，结合实际情况，以修正的Clarke－WrightDantzig和Ramser于1959年首先提出的，很快引起运筹学、应用数学、组合数学、网络分析、图论、计算机应用等学科的专家与运输计划制定者和管理者的极大重视，他们进行了大量的理论研究及试验分析，取得了很大进展。以Bodlin，Christofider，Golden，Assad, Ball该问题进行了较为深入的研究 Olatz Arbelaitz,Clemente Rodriguez在[19]《Comparison of ystems based on evolutionary search and simulated annealing to solve the VRPTW》VRPTW的系统设计与分析，把有哪些信誉好的足球投注网站限制在小范围可行解之内,并把META启发方法和路线规划启发方法结合起来。Hoong Chuin Lau , Zhe Liang在[20]《Pick and delivery with ime windows :algorithms and test case generation》中提出了两阶段方法来解决问题，在第一阶段中运用了新的路径规划启发式Wee—Ki ,A Hbrid.t在[21]《Search lgorithm for the vehicle routing problem with time wi