带有时间窗的车辆路径问题的优化研究硕士学位论文

《带有时间窗的车辆路径问题的优化研究硕士学位论文》由会员分享，可在线阅读，更多相关《带有时间窗的车辆路径问题的优化研究硕士学位论文（78页珍藏版）》请在装配图网上搜索。

1、毕业设计（论文）原创性声明和使用授权说明毕业设计（论文）原创性声明和使用授权说明原创性声明原创性声明本人郑重承诺：所呈交的毕业设计（论文） ，是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得 及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。作 者 签 名： 日 期： 指导教师签名： 日期： 使用授权说明使用授权说明本人完全了解 大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文

2、）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。作者签名： 日 期： 学位论文原创性声明学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名： 日期： 年 月 日学位论文版权使用授权书学位论文版权

3、使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名：日期： 年 月 日导师签名： 日期： 年 月 日指导教师评阅书指导教师评阅书指导教师评价：指导教师评价：一、撰写（设计）过程1、学生在论文（设计）过程中的治学态度、工作精神 优 良 中 及格 不及格2、学生掌握专业知识、技能的扎实程度 优 良 中 及格 不及格3、学生综合运用所学知识和专业技

4、能分析和解决问题的能力 优 良 中 及格 不及格4、研究方法的科学性；技术线路的可行性；设计方案的合理性 优 良 中 及格 不及格5、完成毕业论文（设计）期间的出勤情况 优 良 中 及格 不及格二、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及格 不及格三、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意？设计是否有创意？ 优 良 中 及格 不及格3、论文（设计说明书）所体现的整体水平 优 良 中 及格 不及格建议成

5、绩：建议成绩： 优优 良良 中中 及格及格 不及格不及格（在所选等级前的内画“”）指导教师：指导教师： （签名） 单位：单位： （盖章）年年 月月 日日评阅教师评阅书评阅教师评阅书评阅教师评价：评阅教师评价：一、论文（设计）质量一、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及格 不及格二、论文（设计）水平二、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意？设计是否有创意？ 优 良 中 及格 不及格3、论文（设计说

6、明书）所体现的整体水平 优 良 中 及格 不及格建议成绩：建议成绩： 优优 良良 中中 及格及格 不及格不及格（在所选等级前的内画“”）评阅教师：评阅教师： （签名） 单位：单位： （盖章）年年 月月 日日带有时间窗的车辆路径问题的优化研究V教研室（或答辩小组）及教学系意见教研室（或答辩小组）及教学系意见教研室（或答辩小组）评价：教研室（或答辩小组）评价：一、答辩过程一、答辩过程1、毕业论文（设计）的基本要点和见解的叙述情况 优 良 中 及格 不及格2、对答辩问题的反应、理解、表达情况 优 良 中 及格 不及格3、学生答辩过程中的精神状态 优 良 中 及格 不及格二、论文（设计）质量二、论文（

7、设计）质量1、论文（设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及格 不及格三、论文（设计）水平三、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意？设计是否有创意？ 优 良 中 及格 不及格3、论文（设计说明书）所体现的整体水平 优 良 中 及格 不及格评定成绩：评定成绩： 优优 良良 中中 及格及格 不及格不及格（在所选等级前的内画“”）教研室主任（或答辩小组组长）：教研室主任（或答辩小组组长）： （签名）年年 月月 日日教学系意见：教学

8、系意见：系主任：系主任： （签名）年年 月月 日日带有时间窗的车辆路径问题的优化研究VI摘摘 要要随着现代科学技术的迅猛发展以及全球经济一体化趋势的加强，各国都面临着前所未有的机遇和挑战。现代物流作为一种先进的组织方式和管理技术，被广泛认为是企业在降低物资消耗，提高劳动生产率以外的重要的利润源泉，在国民经济和社会发展中发挥着重要作用。由于JIT理论和实践的成熟，现代产业对物流配送提出了更高的要求将合适的零件以合适的数量在合适的时间送到生产线。这是为适应消费需要变得多样化、个性化而建立的一种生产体系及为此生产体系服务的物流体系。消费者需求趋于多样化，对送货时间的要求日趋严格，除了因缺货造成的机会

9、成本的损失外，由于配送不及时也会造成货物价值的大大降低。在配送运输上，时间窗口显得越来越重要。因此，降低运输成本，提高配送的及时性和配送的服务质量，优化车辆路径问题，是降低企业成本的迫切需要。 本文正是基于这种背景对物流配送路径的优化问题开展相关研究。详细阐述了物流的概念，物流对产品价值、企业竞争力、宏观经济三大方面产生的影响，介绍了配送的定义，分析了配送的评估指标；通过介绍物流配送在整个物流过程中具有的重要意义,说明了解决带有时间窗的车辆路径问题的必要性及现实意义；同时收集了国内外关于车辆路径问题研究的文献资料并进行整理、分类，详细介绍了国内外研究现状；对现有的求解方法进行了具体介绍和整理归

10、类；并详细阐述了遗传算法的优劣点和具体操作过程，然后在现有多目标模型的基础上分析其不完善之处，并从运输成本、顾客满意度（配送及时性）、以及配送车辆数三大角度出发，改进了带有时间窗的车辆路径优化多目标模型，运用具有隐式并行性和全局搜索性两大特点的遗传算法进行求解。在求解的过程中，根据自然数编码的特点，对遗传算法的三个算子选择、交叉、变异进行了特别设计，最终得出了模型的解。关键词关键词：车辆路径问题，遗传算法，时间窗，多目标规划带有时间窗的车辆路径问题的优化研究VIIAbstractWith the development of science and technology, the econom

11、ic modernization is accelerating .All of the countries face both opportunity and challenge. Modern logistics , an advanced technology for companies, which plays a significant role in the development of economy and society ,is regarded as an important way of lowering cost and enhancing productivity.

12、Because of the maturity of Just-in-time theory, advanced industries make a high demand on the time and number of goods distribution.It is an indispensable product system and logistics system to satisfy the diversified demand .The diversified demand also makes a high demand on the time of goods trans

13、portation. Because the delay of distribution will decrease goods value, time window becomes more and more important in goods distribution. Obviously, lowering distribution cost, transporting goods timely, improving the service quality, optimizing vehicle routing problem with time windows is exigent

14、to enterprises. Based on such background, this paper will do some research on VRPTW which can help the enterprises to improve their condition.It states the definition of logistics and its infection on goods value, companies competetivity, macro economy. It also states the definition and evaluation c

15、riterion of distribution. By explaining the significance of goods distribution in logistics, it states the meaning and need to solve VRPTW. The paper collects both foreign and domestic VRPTW literatures, and introduces the status quo of research .It classifies the main method of resolving VRPTW whil

16、e introducing them and analyzes the merits and demerits of Genetic Algorithm as well as its detailed process. From three angles distribution cost, degree of customs satisfaction, vehicles number, the paper analyzes the unperfectness of existing models, builds an improved multi-objective model to opt

17、imizing VRPTW and applies Genetic Algorithm which has strong holistic searching ability and parallel running ability to the model. According to the characteristics of coding, the paper devises special arithmetic operators to get the resolution. This paper analyzes VRPTW mathematically and realizes i

18、t by C# . The algorithm given in this paper can obtain an optimized solution effectively and has been proven to be a good one. So, it has a high value to logistic enterprises. Sheng LiJun(Management Science)Directed by Associate Professor Zhou XiZhaoKeywords：VRPTW, Genetic Algorithm, time windows, m

19、ulti-objective model带有时间窗的车辆路径问题的优化研究VIII目目 录录第一章第一章 引言引言 .1 11.1 论文研究背景 .11.2 国内外研究现状及存在的问题 .21.3 论文研究的目的和意义 .31.4 本文研究的内容及技术路线 .4第二章第二章 物流及配送物流及配送概述概述 .6 62.1 物流的定义 .62.2 物流的作用 .72.2.1 物流对产品价值的贡献 .72.2.2 物流对企业竞争力的作用 .72.2.3 物流对宏观经济产生的影响作用 .82.3 配送的定义.92.4 配送的评估指标.11第三章第三章 带有时间窗的车辆路径问题的算法回顾带有时间窗的车辆

20、路径问题的算法回顾 .13133.1 带有时间窗的车辆路径问题的概念和研究现状 .133.1.1 概念和主要类型.133.1.2 求解算法回顾.153.2 遗传算法 .223.2.1 遗传算法的生物遗传学基础.223.2.2 遗传算法的基本概念.233.2.3 标准遗传算法.233.2.4 遗传算法的特点.233.2.5 遗传算法过程描述.25第四章第四章 多目标多目标 VRPTWVRPTW 模型的改进和遗传算法实现模型的改进和遗传算法实现 .43434.1 改进的多目标 VRPTW 模型 .434.2 多目标 VRPTW 模型的处理 .464.3 算例数据 .484.4 遗传算法的设计 .5

21、24.4.1 编码设计.524.4.2 约束处理设计.524.4.3 适应度函数设计.534.4.4 三种遗传算子的 C 语言设计.534.5 运行结果 .57第五章第五章 结论与展望结论与展望 .58585.1 研究结论 .58带有时间窗的车辆路径问题的优化研究IX5.2 未来的研究展望 .58致致 谢谢 .6060参考文献参考文献 .6161硕士期间已发表的论文硕士期间已发表的论文 .6363附附 录录 .6464带有时间窗的车辆路径问题的优化研究1第一章第一章 引言引言1.11.1 论文研究论文研究背背景景随着社会、经济、技术的高速发展，全球经济一体化趋势和市场竞争程度日益加强。全球网络

22、通信和信息技术的飞速发展使得现代商业逐渐呈现出新的特征:不断增长的供货能力、不断增长的客户需求、不断增长的全球竞争等。以信息技术为基础的物流服务在全球迅速崛起，其本身所具有的开放性、全球性、低成本和高效率的特点能够更好地满足现代商业的要求，推动社会经济的进步。世界各国都已经意识到物流的重要性，尤其是在工业发达国家，物流管理与物流技术己经得到了广泛的应用与发展，包括生产、流通、消费等过程诸环节的物流系统，已成为适合于市场经济发展的基础产业之一。在此背景下，企业技术水平和内部管理水平的不断提高使得生产和销售领域内降低成本的空间越来越小，在生产和销售领域以外的运输、仓储、配送、库存等环节上的成本比重

23、越来越高。企业经营决策者不得不把寻求成本优势的视角转向“第三利润的源泉”物流领域。从运输成本看，我们还有很大的空间可以去努力。据统计，各国运输成本占国民生产总值的10% 15%左右1。这就意味着运输系统的效率提高一点就可以节约很多成本。只要我们能够将现有运输成本降低，我们的国民经济总体水平就能出现一次新的飞跃，一次真正的飞跃。但是，目前我国现阶段物流服务的实施有着不可回避的问题:物流技术、基础设施和装备条件还不够完善；物流效率低下；物流业发展比发达国家落后；“物流瓶颈”严重制约我国产业的发展等等，这些问题迫切需要加以重视和研究。在这种严峻的形势下，大力推进现代物流产业发展，降低运输成本，增强物

24、流环节的服务质量，是提高物流效率的迫切需要。而运输是现代生产企业和物流管理中最重要的一个环节，车辆路径问题又是运输问题中最关键的技术。有效的车辆调度,不仅可以提高物流工作效率,而且能够为生产工序之间的物料传送得到运输上的保障,从而实现物流管理科学化。带有时间窗的车辆路径问题的优化研究21.21.2 国内外研究现状及存在的问题国内外研究现状及存在的问题1）国内研究现状）国内研究现状目前，国内对于复杂的车辆路径问题的研究仍处于起步状态。通过中国期刊数据库检索，19942005 年12年时间，在中国的正式期刊上已经发表该领域的文章仅二十多篇。就这方面研究的深度和广度来说，远不能适应当前我国配送业以及

25、物流业迅速发展的需要。国内在车辆路径问题上的研究基本上着重于车辆路径问题的启发式算法研究。如求宾松、符卓在解带软时间窗的车辆路径问题的改进遗传算法中通过引用一种新的编码方法、交叉和变异概率的自适应机制，构造一个改进的遗传算法来求解带软时间窗的车辆路径问题；陈火根、丁红钢等在物流配送中心车辆调度模型与遗传算法设计中对带时间约束的物流配送中心车辆调度问题，采用混合整数规划方法进行建模，分析了该模型用精确算法进行求解的复杂性，提出了遗传算法与启发式算法相结合的求解方法，将该问题分解为车辆分配和单一车辆路线安排两个相互关联的子问题进行求解；霍佳震、张磊在有时间窗的集货送货一体化车辆路径规划启发式算法研

26、究中通过对模型的分、分解和过虑，结合实际情况，以修正的ClarkeWright节约启发式算法为基础进行插入式排序，以解决带有时间窗口的集货和送货一体化路径规划问题；张炯、郎茂祥有时间窗配送车辆调度问题的禁忌搜索算法中在对有时间窗配送车辆调度问题进行描述的基础上，建立了该问题的基于直观描述的数学模型，通过设计一种新的解的表示方法构造了求解该问题的禁忌搜索算法，并以21个节点的运输网络为例进行了实验计算。2）国外研究现状）国外研究现状国外关于车辆路径问题的研究较早，最初由Dantzig和Ramser于1959年首先提出的，很快引起运筹学、应用数学、组合数学、网络分析、图论、计算机应用等学科的专家与

27、运输计划制定者和管理者的极大重视，他们进行了大量的理论研究及试验分析，取得了很大进展。以Bodlin，Christofider，Golden，Assad, Ball为代表的学者对该问题进行了较为深入的研究，完善了该问题的模型和算法。目前国外着重研究各种车辆路径问题以及相关启发式算法的探索。如：OLATZ ARBELAITZ，CLEMENTE RODRIGUEZ在COMPARISON OF SYSTEMS BASED ON 带有时间窗的车辆路径问题的优化研究3EVOLUTIONARY SEARCH AND SIMULATED ANNEALING TO SOLVE THE VRPTW PROBLE

28、M中介绍了几种解决VRPTW的系统设计与分析，把搜索限制在小范围可行解之内,并把META启发方法和路线规划启发方法结合起来。JORG HOMBERGER AND HERMANN GEHRING 在TWO EVOLUTIONARY METAHEURISTICS FOR THE VEHICLE ROUTING PROBLEMB WITH TIME WINDOWS 中运用了两种进化策略来解决车辆路径问题，并充分利用了META启发技术。HOONG CHUIN LAU AND ZHE LIANG在PICK AND DELIVERY WITH TIME WINDOWS :ALGORITHMS AND TE

29、ST CASE GENERATION中提出了两阶段方法来解决车辆路径问题，在第一阶段中运用了新的路径规划启发式算法来获得初始解，第二阶段用禁忌算法来改进解。WEEKIT在A HIBRID SEARCH ALGORITHM FOR THE VEHICLE ROUTING PROBLEM WITH TIME WINDOWS中重点研究了禁忌算法和遗传算法混合的启发式算法。禁忌搜索优势在于局部搜索，遗传算法优势在于全局搜索，文章将两种优势结合起来寻求近最优解。3）国内外研究中存在的问题）国内外研究中存在的问题着重启发式算法研究，模型研究成果比较多，但多目标模型研究还不够完善。在多目标模型研究中，现有的

30、模型中除路径和车辆数目外并没有考虑到其他方面对物流效率的影响。1.31.3 论文研究的目的和意义论文研究的目的和意义在物流配送系统中，物流配送中心的成立可有效地简化配送程序与减少配送的频率，而物流配送中心作业的重点是如何将车辆有效地使用并决定其最经济的行驶路线图，使商品能在要求的时间内送到顾客的手中。国外将此类问题称之为带有时间窗的车辆路径优化问题(Vehicle Routing Problem with Time Windows)，简称为VRPTW3。有效地解决带有时间窗的车辆路径问题，不仅可以能够提高物流工作效率，而且能够为及时生产(JIT)模式的企业提供运输上的保障，从而实现物流管理科学

31、化。带有时间窗的车辆路径问题不但直接存在于物流管理当中,而且很多实际生产调度也可以间接归结为该问题。该问题的理论涉及许多学科，应用前景广阔，已经引起带有时间窗的车辆路径问题的优化研究4了运筹学、应用数学、图论及网络分析、物流科学、交通运输工程、管理科学与工程、计算机应用等科学的专家，工程技术人员和管理者的极大重视。因此，该问题一直成为运筹学与组合优化领域的前沿与研究热点。1.41.4 本文研究的内容及本文研究的内容及技术路线技术路线国内外绝大多数关于VRPTW的研究都集中在算法创新，目的是获得更接近最优解的近似解，致使物流费用降低。在带有时间窗的车辆路径问题的模型研究方面已有不少成果，但还不够

32、完善。所以本文将对带有时间窗的车辆路径问题的模型进行改进优化。论文的主要思路是构建以配送成本最小、所用车辆数目最小、顾客满意度最大为目标的新模型。利用遗传算法的原理和其特殊优势，为带有时间窗的车辆路径问题的求解提供一个切实可行的算子设计，求得一个较优的可行解，并说明其有效性。论文的内容如下:1)介绍了物流的定义和作用，阐述了配送对物流的重要意义及配送评估的主要指标。2)对基本车辆路径问题进行了描述，综述了基本车辆路径问题和带有时间窗的车辆路径问题的研究现状，并指出了目前存在的一些问题，总结了求解方法。3)对带有时间窗的车辆路径问题进行描述，并建立该问题的多目标数学规划模型。4）运用改进的遗传算

33、子求解模型。带有时间窗的车辆路径问题的优化研究5图 1-1 论文技术路线物流及配送的定义、作用配送评估指标VRPTW 问题的优化研究研究的背景、意义和现状多目标模型改进具体算法描表述C 语言编程求解编码适应度函数选择、交叉、变异算子设计参数选择、算法终止遗传算法算例实现VRPTW 定义及算法回顾 精确算法介绍 启发算法介绍遗传算法基本原理及其具体操作过程带有时间窗的车辆路径问题的优化研究6第二章第二章 物流及配送物流及配送概述概述 物流最初起源于美国，当时所研究的主要内容是企业为了把产品顺利销售出去而进行一系列运输、储存、包装等活动。因此，物流在英语中称为 Physical Distribut

34、ion。第二次世界大战期间，美军后勤组织运用了一套科学方法，成功地将各种战略物资及时准确地送到全球各地，为美军实施全球化战略提供了保障，这套方法在军事上被称为 Logistics (后勤)。第二次世界大战后，这套后勤补给理论、方法也为企业和理论界认同，并广泛运用起来，他们将其称为商业物流或销售物流(Business Logistics)，以力求合理有效地组织商品的供应、保管、运输、配送，而且实践证明取得了相当大的成效。2.12.1 物流的定义物流的定义 物流的定义很多，并且随社会的发展而不断变化。不少学者为物流下过定义，典型的物流定义主要有以下几种： 美国物流管理协会对物流的定义是：物流是对货

35、物、服务及相关信息从供应地到消费地的有效率、有效益的流动和存储，以满足客户需求的过程，并对这个过程进行计划、执行和控制，该过程包括输入、输出，内部和外部的移动以及以环境保护为目的的物料回收。 欧洲物流协会于 1994 年发表的物流术语中将物流定义为：物流是在一个系统内对人员或商品的运输、安排及与此相关的支持活动的计划、执行与控制，以达到特定的目的。 日本后勤系统协会将物流改称后勤，并且该协会名称中的“后勤系统”几个字并没有翻译成日文汉字，而是直接用注音。该协会的专务理事稻束原树 1997 年在“这就是后勤 ”一文中对“后勤”下了定义：“后勤”是一种对于原材料、半成品和成品的有效率流动进行规划、

36、实施和管理的思路，它同时协调供应、生产和带有时间窗的车辆路径问题的优化研究7销售各部门的个别利益，最终达到满足客户的需求。换言之， “后勤”意味着：按要求的数量以最低的成本送达要求的地点，以满足客户的需要作为基本目标。 2001 年颁布的中国国家标准物流术语对物流的定义是：物流就是物品从供应地向接收地的实体流动过程。根据实际需要，将运输、存储、装卸、搬运、包装、流通加工、配送、信息处理等基本功能实现有机结合4。这里，物流的“物”指的是一切有经济意义的物质实体，即指商品生产、流通、消费的物质对象，它既包括生产过程中的物资，又包括流通过程中的商品，还包括消费过程中的废弃物品。物流的“流”指的是物质

37、实体的定向移动，既包含其空间位移，又包括其时间延续。2.22.2 物流的作用物流的作用商品流通是由商流和物流构成的，生产者将其产品的所有权转移给消费者，是价值的让渡，这一过程称为商流；产品实体从生产者那里转移到消费者那里是实体的转移，这一过程称为物流。物流与商流的结合构成了整个流通。物流，对于整个社会经济体系来讲，其作用与意义如同梁柱构成的框架对于高楼大厦的价值。2.2.12.2.1 物流对产品价值的贡献物流对产品价值的贡献一件产品或一项服务的价值如果得到了市场的认可，那么它必然会给消费者提供四种效用。1）形态效用产品以其特有的外在形态或者属性为消费者服务而产生的效用。2）空间效用产品通过在特

38、定地点服务于消费者，给消费者带来的效用。3）时间效用产品通过在特定时间服务于消费者，给消费者带来的效用。4）占有效用通过使消费者占有产品而实现的效用。2.2.22.2.2 物流对企业竞争力的作用物流对企业竞争力的作用 竞争优势归根结底产生于企业为客户所能创造的价值，或者在提供同等效益时采取相对的低价格，或者其不同寻常的效益用于补偿溢价而有余。那么，如何通过物流获得竞争优势呢? 带有时间窗的车辆路径问题的优化研究81）成本领先 其优势直接来源于产品和服务的低成本。产品的总成本中包含物流成本，当前物流费用占产品总成本的比重已经超过 40，这是一块“黑暗大陆” ，但又是“第三利润源泉” ，企业可以通

39、过优化物流管理大幅度降低物流成本，从而降低产品总成本，确立企业在同行业成本领先的地位，在竞争中取胜。2）标新立异 不同的产品和服务在消费者心目中是有独特之处的。对于一个企业来说，都希望通过产品创新，或营销手段的配合使自己的产品和服务能在消费者心目中树立与众不同的形象，并给消费者带来利益。但由于科学技术手段越来越先进，使得大多数产品很容易被仿制。于是，产品的差异性和独特性就被大大的削弱。但如果企业有一个一体化高效运营的物流系统的话，就可以运用娴熟的物流管理技术通过向客户提供优质服务获得竞争优势。企业如果在存货的可得性、递送的及时性和交付的一贯性等方面领先于同行业的平均水平，那它就能成为有吸引力的

40、供应商和理想的业务伙伴。物流管理已成为当今企业最具挑战性的领域之一。3）目标集聚 企业将目标定位于产业内一种或一组细分市场，并量体裁衣，使其战略为特定的目标市场服务。 企业必须明确自己的目标市场，确立顾客至上的营销观念，把握个性化消费趋势。在物流管理上强调有效客户反应、快速反应、突出 7R 目标(Right Product or Service，Right Time，Right P1ace，Right Cost，Right Customer，Right Quality，Right Quantity)。同时，针对客户的不同要求优化物流管理系统，以适应用户的特殊要求。2.2.32.2.3 物流对宏

41、观经济产生的影响作用物流对宏观经济产生的影响作用1）促进经济发展 社会生产部门生产出来的产品必须经过流通过程才能进入消费领域，流通过程既包含商流也包含物流。社会经济的发展物流业是不可或缺的，而且，物流业越是发达，就越能促进社会经济的发展。运输条件的改善是促使批发商业产生的一个很带有时间窗的车辆路径问题的优化研究9重要的因素。当然，批发商业的专业化服务使得大批量的买卖成为可能，促使市场的范围不断扩大，也使消费品生产供应上的“时” 、 “空”矛盾得以解决，商品流通速度加快，促使社会经济的发展。2）有利于交换功能的发挥 在商品经济的社会里，有商品生产就必然有商品交换。一个国家的社会经济是由许多部门和

42、企业组成的，这些部门和企业分布在不同地区，它们一方面向社会提供产品，同时也从社会其他部门和企业获得自己所需的原材料、零部件、辅助材料和燃料等。企业之间相互依赖的交换关系必须靠有效的物流活动来维系。商品生产的目的就是为了交换，是为他人生产的。商品必须进入市场才能实现生产的目的。然而商品的产地与销地往往存在空间距离，商品的生产时间与消费时间也存在差异，要克服产销之间的这些矛盾，只有通过物流来解决。在空间上，运输架设空间的桥梁；在时间上，仓储、库存、服务等构筑时间的隧道。只有这样，才能使交换功能得以发挥。3）降低社会商品的价格水平 价格水平的降低有赖于成本的减少和市场规模的扩大，而物流是“降低成本的

43、宝库” ，通过物流合理化、现代化等一系列活动可以降低成本与价格，成为“第三利润源泉” 。此外，物流活动可以创造时间和空间效用，从而拓展商品市场的范围。由于大规模生产和物流领域更多的成本权衡机会，使得外地产品的价格有可能低于本地产品的价格，而且会促使产品的价格竞争，其结果使整个社会商品的价格水平趋于下降。可见，有效的物流管理有利于社会商品价格水平的降低。2.32.3 配送的定义配送的定义 配送指的是在经济合理区域范围内，根据用户要求，在物流中心对物品进行拣选、加工、包装、组配等作业，以合理的方式按时送达指定地点的物流活动7。配送对于物流有着非常重要的意义，具体体现在以下几个方面：1)体现了商流和

44、物流的紧密结合带有时间窗的车辆路径问题的优化研究10 配送是物流系统中由运输环节派生出的功能，是短距离的运输；是物流中一种特殊的、综合的活动形式，是将商流与物流紧密结合，包含了商流活动，也包含了物流中若干功能要素的一种形式。 从物流来讲，配送的距离较短，位于物流系统的最末端，处于支线运输、二次运输和末端运输的位置，即到最终消费者的物流。但是在配送过程中，也包含着其他的物流功能，如装卸、储存、包装等。可以说配送是物流在小范围中物流全部活动的体现，也可以说是一个小范围的物流系统。 一般的配送集装卸、包装、保管、运输于一身，通过这一系列活动完成将货物送达的目的。特殊的配送则还要以加工活动为支撑，所以

45、包括的方面更广。但是，配送的主体活动与一般物流却有不同，一般物流是运输及保管，而配送则是运输及分拣配货，分拣配货是配送的独特要求，也是配送中有特点的活动，以送货为目的的运输则是最后实现配送的主要手段，从这一主要手段出发，常常将配送简化地看成运输中的一种。 从商流来讲，配送和物流不同之处在于，物流是商物分离的产物，而配送则是商物合一的产物，配送本身就是一种商业形式。虽然配送具体实施时，也有以商物分离形式实现的，但从配送的发展趋势看，商流与物流越来越紧密的结合是配送成功的重要保障8。2）完善了输送及整个物流系统 第二次世界大战之后，由于大吨位、高效率运输力量的出现，使干线运输在铁路、海运、公路方面

46、都达到了较高水平，长距离、大批量的运输实现了低成本化。但是，在所有的干线运输之后，往往都要辅以支线运输和小搬运，这种支线运输及小搬运成了物流过程的一个薄弱环节。这个环节和干线运输有着许多不同的特点，如要求灵活性、适应性和服务性，它致使运力利用不合理、成本过高等问题难以解决。采用配送方式，从范围来讲，将支线运输及小搬运统一起来，加上上述的各种优点，使输送过程得以优化和完善。3）提高了末端物流的效益带有时间窗的车辆路径问题的优化研究11 采用配送方式，通过增大经济批量来达到经济地进货，又通过将各种商品用户集中起来进行一次发货，代替分别向不同用户小批量发货来达到经济地发货，使末端物流经济效益提高。4

47、）通过集中库存使企业实现低库存或零库存 实现了高水平的配送之后，尤其是采取 JIT 配送方式之后，生产企业可以完全依靠配送中心的准时配送而不需保持自己的库存。或者生产企业只需保持少量保险储备而不必留有经常储备，这就可以实现生产企业多年追求的“零库存” ，将企业从库存的包袱中解脱出来，同时解放出大量储备资金，从而改善企业的财务状况。实行集中库存，集中库存的总量远低于不实行集中库存时各企业分散库存之总量。同时增加了调节能力，也提高了社会经济效益。此外，采用集中库存可利用规模经济的优势，使单位存货成本下降。5）简化事务，方便用户 采用配送方式，用户只需向一处订购，或向一个进货单位联系就可订购到以往需

48、去许多地方才能订到的货物，只需组织对一个配送单位的接货便可代替现有的高频率接货，因而大大减轻了用户工作量和负担，也节省了费用开支。6）提高供应保证程度 生产企业自己保持库存，维持生产，供应保证程度很难提高，主要是受到库存费用的制约。采取配送方式，配送中心可以比任何单位企业的储备量更大，因而对每个企业而言，中断供应、影响生产的风险便相对缩小，使用户免去短缺之忧。2.42.4 配送的评估指标配送的评估指标配送是整个物流过程最末端的环节，车辆配送是物流中心作业最终及最具体的服务表征。目前普遍采用的对配送服务进行评估的指标主要有以下内容。1）时效性 时效性是流通领域内客户最重视的评价指标，也就是要确保

49、能在指定的时间内交货。配送是上游物流活动的末端活动，同时又是下游物流活动的开端。为了确保下游物流活动的顺利进行，及时有效的送货是极其重要的要求，也是任何一个配送系统必须承诺的。影响配送时效性的因素，除了送货司机的个人因素以外，还有选带有时间窗的车辆路径问题的优化研究12择的配送路线不恰当，客户点卸货不方便，客户不配合等。对于配送中心，可以控制的因素按照控制力的强弱依次为配送路线选择、送货司机、客户卸货点、客户。因此配送路线的选择是配送中心工作的一个重点，也是众多专家进行研究的重点和热点。但是，具体到一个实际的配送中心的工作状况，任何细小环节的失误都会在过程中不断被放大，对最终的结果产生很大的影

50、响。2）可靠性 能否将货物按照客户的要求，保质保量、完好无缺地送达目的地是衡量配送系统的另外一个重要的要素。可靠性的实现可以通过配送中心的努力达到相当的高度，根据配送系统服务对象的要求，配送中心可以通过合适的设备和严格的规章制度，以及良好的员工素质达到任何合理的可靠性要求。 可靠性完整地体现整个配送系统的设施能力和服务水平。在配送之前，快速准确地验货，配送前的加工，货物的包装，货物的装卸，任何一个环节都体现配送系统的技术水平和管理能力。包括员工装卸货时的细心程度，运送过程对货品的保护，对客户地点及作业环境的了解，配送人员的素质等。3）便利性 配送系统是一个服务系统，所提供的服务必须能够让客户轻

51、松获得。对于送货方式、送货计划的安排，应该采取具有较大弹性的柔性系统，能够为各种客户和要求及时提供便利的服务，满足客户紧急送货、信息传送、顺道退货、辅助资源回收等独特要求。 便利性的实现更多地体现在对配送系统的技术要求上，目前，在配送系统中广泛采用先进的信息处理技术、通信技术、定位技术等辅助手段，帮助操作人员及时响应客户的要求。4）经济性在一个公正的市场经济环境中，配送中心提供服务的价格，在正常状态下，主要依赖于配送系统运作的成本。 配送系统的运作成本必须和配送系统其他性能参数综合进行考评，单纯对成本进行评价没有任何实际意义。也就是说，要在保证配带有时间窗的车辆路径问题的优化研究13送满足客户

52、要求、提升客户满意度的同时，通过各种技术和管理手段，降低运作成本。第三章第三章 带有时间窗的车辆路径问题的算法回顾带有时间窗的车辆路径问题的算法回顾3.13.1 带有时间窗的车辆路径问题的概念和研究现状带有时间窗的车辆路径问题的概念和研究现状为了更好地完成配送，实现配送中心的目标，不仅需要关注选用合理的运输服务，而且还需要根据已知的车辆状况、客户送货时间需求，选择一种合适的路线方案。这就是本文下面需要研究的带有时间窗的车辆路径问题。3.1.13.1.1 概念和主要类型概念和主要类型 车辆路径问题最初由GB.Dantzig于1959年提出9。从二十世纪六十年代以来，许多学者对车辆路径问题进行了广

53、泛的研究。车辆路径问题(Vehicle Routing Problem,简称VRP)是指:给定一个配送中心点(中心车库，central depot),一个车辆集合和一个顾客集合，车辆和顾客各有自己的属性，每辆车都有车的容量，所装载货物不能超过它的车的容量，起初车辆都在配送中心车库，顾客任意分布，车把货物从配送中心车库运送到每一个顾客(或从每个顾客处把货物运到配送中心车库)，要求满足顾客的需求，车辆最后返回车库，每个顾客只能被服务一次，设计车辆旅行路径使运输总费用最小10。经过几十年来许多学者的不断努力，VRP包含的类型和相关的解法已经相当丰富，按不同的划分标准可以分成不同的种类，如按照任务特征

54、可以划分为集货问题或者送货问题和集送货一体化问题；按车辆满载状况可以划分为满载问题和非满载问题；按车场数目可划分为单车场问题和多车场问题；按优化目标数可以划分为单目标优化和多目标优化等等。带有时间窗的车辆路径问题的优化研究14根据上述分析可以将VRP问题的主要类型归结为如下表格表3-1 车辆路径问题类型划分划分标准车辆路径问题类型集货问题或者送货问题任务特征集送货一体化问题对弧服务问题（如中国邮递员问题）对点服务问题（如旅行商问题）任务性质混合服务问题（如交通车路线安排问题）满载问题车辆满载状况非满载问题单车场问题车场数目多车场问题单车型问题（所有车辆容量相同）车辆类型数多车型问题（车辆容量不

55、全相同）车辆开放问题（车辆可以不返回其出发车场）车辆对车场的所属关系车辆封闭问题（车辆必须返回其出发车场）单目标问题优化目标数多目标问题在VRP问题的基本模型基础上还可以添加许多附加条件从而变成其它问题。主要的附加条件有：带有时间窗的车辆路径问题的优化研究151) VRPLC(带有运行时间约束的VRP ):每辆汽车运行的时间不能超过预先给定的界L。每辆汽车的运行时间由汽车在客户间的行驶时间和汽车为客户服务的时间所构成。2) MVRP(多处发点的VRP):允许从多个不同的出发点出发给客户供货。3) SDVRP(可切分供货):一个客户的需求可以同时由若干辆汽车来满足。该模型下求得的解至少都和正常的

56、VRP一样好，因而可以充分利用汽车的资源，从而节省汽车。4)随机VRP(SVRP)。某些值，如客户的数目、客户的需求、客户的服务时间不是事先确定的，而是随机变化的。5) VRPTW: 带有时间窗的车辆路径问题。所谓带有时间窗的车辆路径问题是指假设有n个等待服务的客户，一个出发点，K辆有一定载重量的汽车，己知:每个客户的位置坐标、货物需求量、出发点的位置坐标、每辆汽车的最大载重量，允许服务的时间窗口(时间窗口是指配送车辆或顾客希望服务或被服务的时间范围。一方面，汽车可以在时刻之前到达该客户所在地，但它必须等待直到才可以为该客户服iaia务，并且不允许迟于到达。另一方面，汽车也必须在出发点开门后才

57、可以离开，ib在关门前返回出发点)。要求设计每辆汽车的行驶路线满足约束条件:每个客户必须而且只能被服务一次；每条路线必须起始于出发点，为最后一个客户服务完后返回出发点；每条路线的总负荷不能超过该辆汽车的最大载重量；每个客户必须在它的时间窗口内被服务，如果汽车提前到了客户所在地，也必须等待，直到允许为该客户服务为止13。由于JIT理论和实践的成熟，现代产业对物流配送提出了更高的要求将合适的零件以合适的数量在合适的时间送到生产线，并且只将所需要的零件、只以所需要的数量、只在正好需要的时间送到生产。这是为了适应消费需要变得多样化、个性化而建立的一种生产体系及为此生产体系服务的物流体系。消费者需求趋于

58、多样化，对送货时间的要求日趋严格，除了因缺货造成的机会成本的损失外，由于配送不及时也会造成货物价值的大大降低。在配送运输上，时间窗口显得越来越重要。带有时间窗的车辆路径问题的优化研究16带有时间窗的车辆路径优化问题根据其时间约束的严格与否，可分为软时间窗和硬时间窗。在实际情况中，软时间窗的车辆路径问题更加常见，也更加符合实际，因此本文研究的时间窗主要是指软时间窗。它一般把最小的车辆数作为一个目标,而最低的行驶成本作为另一目标；时间窗是双向的,即顾客应当在最早时间之后或最晚时间之前得到服务,否则就会发生车辆早到等待或服务延误。3.1.23.1.2 求解算法回顾求解算法回顾目前，求解VRPTW问题

59、的方法大致可以概括为两大类：精确算法和启发式算法。精确算法是指可以确定求得最优解的算法。主要的VRPTW问题的精确算法可分为如下几种:1)动态规划法。该方法最初由Kolen (1987)等人提出，可被看作Christofides (1981)对VRPTW的状态空间分解方法的扩展，该方法对小规模问题有效。2) 拉格朗日分解方法。Fisher(1985),Jomstern(1986),Madsen(1990)和Halse(1992)等人用不同的拉格朗日分解方法求解VRP问题，目的是产生一个接近最优解的下界。采用拉格朗日分解和分枝定界的组合方法，能够有效求解规模不超过100个顾客问题。3) 列生成方

60、法。该方法由Desrochers等人在1992年给出，许多不超过100个顾客的问题可用该方法产生最优解，它是目前精确算法中最好的方法。4) K一树方法。Fisher(1994)把解VRP的1-树方法扩展为K一树方法。5)整数线性规划方法。6)割平面法。7)网络流算法。在过去的较长时间内，大多数研究者对带有时间窗的车辆路径问题的研究集中在用精确算法寻求最优解的方向上，不过这种情况没有持续多久，在随后出现的大规模问题上，这些方法都存在“组合爆炸”的问题，求解时间随着问题规模成指数级增长。直到1985年Savelsbergh证明了车辆路径问题是NP完全问题以后，研究的重点才转向寻求问题的近似最优解上

61、，这时所采用的是启发式方法。目前为止，带有时间窗的车辆路径问题的优化研究17VRPTW问题的启发式算法有如下几种主要的算法:（一）初始启发式算法（一）初始启发式算法1）Clarke and Wright 算法这是1964年由Clarke and Wright第一次提出的经典算法，又叫做节约法。这个算法解决CVRP(容量车辆路径问题)，在这里车辆数目不限。这个方法开始假设每条路线包括车库和一个另外的点(顾客)，每一步按照最大节省费用原则合并两条路线。这个算法的复杂性是(n2logn)。后来Golden et al(1977),Nelson et al(1985 ), Fisher(1988)对这

62、个算法进行了改进。节约法是构造启发式算法的一种。2）扫描算法这个算法的起源可以追溯到1971年Wren和Wren and Hollieday的论文，它假设有一个车库或者几个车库，点(顾客)坐落在欧基里德平面上，由极坐标来表示每个点(顾客)的位置(i,i)，从i=0的任意一点i开始，随着角度的增加把一些顾客包括进一条路线，保持车的容量不被超过。确定了这样一条路线的各点以后再对这条路线通过解一个相应的TSP问题进行优化。3）ChristofidesMingozziToth 两阶段算法两阶段算法将问题分为两阶段求解，第一阶段得到一可行解，第二阶段通过对点的调整，在始终保持解可行的情况下，力图向最优目

63、标靠近，每一步都产生另一个可行解来代替原来的解，使目标函数值得以改进，一直继续到不能再改进目标函数值为止。一般在第一阶段用构造方法，第二阶段用一些改进方法对初始解进行改进，如扫描法。一些基于数学规划的算法也属于两阶段法，把问题直接描述成一个数学规划问题，根据其模型的特殊构形，应用一定的技术(如分解)进行分划，进而求解己被广泛研究过的子问题。在两阶段法求解过程中，常常采用交互式优化技术，把人的主观能动作用结合到问题的求解过程中，其主要思想是:有经验的决策者具有对结果和参数的某种判断能力，并且根据知识直感，把主观的估计加到优化模型带有时间窗的车辆路径问题的优化研究18中去。这样做通常会增加模型最终

64、实现并被采用的可能性。两阶段法是目前成果最丰富、应用最多的一类方法。每一种方法讨论的情况不尽一致，适用范围也不完全相同。4）插入法该法是通过每次将一个请求插入到某条路径而构造一组路径的过程。其基本步骤是:第一，所有的车辆指派空路径；设L为所有未安排的客户的集合；第二，从L里任取一个客户(包括一装货点和一卸货点)；将此客户插在能使目标函数值增加最小的可行插入位置；如果没有可行插入位置，新建一条路径，将此客户插到新路径里；然后从L里删除此客户。重复第二步骤直到L为空。( (二二) )改进启发式算法改进启发式算法所有的改进启发式方法的优化流程都采用“邻域搜索”的方式。首先根据问题的初始解，按照某种邻

65、域生成机制先生成当前解的邻域解，根据目标函数对邻域解进行评价，然后采用某种接受准则(确定性、概率性、混沌性等)来决定接受哪个邻域解，取代当前解继续搜索，直至满足算法停止准则。通过邻域搜索可以深入探索当前解的邻近空间，找到相对当前解使目标更优的解，最终实现对解的优化。改进方法根据对邻域解进行搜索的策略不同可以分为局部优化和全局优化方法两类。1 1）局部优化方法）局部优化方法局部优化方法就是传统的“下降”算法，从解空间的某个解出发搜索当前解的邻域，如果某个邻近解比当前解更优，则用此邻近解取代当前解，然后继续搜索直至满足搜索停止条件。当搜索无法使目标函数进一步改进时，得到一个局部最优解。局部优化方法

66、的搜索是单方向的，新解的生成只依赖于搜索过程中收集到的信息。一旦目标函数值无法有进一步地改进，搜索就会中断，因此很容易陷入局部极值中。典型的如爬山法。根据改进方法中邻域生成机制涉及到的路径数目，可将局部改进方法分为两类:路径内和路径间改进方法。路径内方法通过重新排列单个路径中客户的访问顺序来减带有时间窗的车辆路径问题的优化研究19少车辆行驶的总距离，从而改进初始解的性能。常用的路径内优化方法有2-opt, 3-opt方法。路径内改进方法主要通过交换或移动路径之间的边或客户来改进初始可行解，其不仅可减少车辆行驶的总路程，还可减少服务客户所需的车辆数。2)2)全局优化方法全局优化方法全局优化方法也称为“元启发式方法”，许多资料上又称亚启发式方法，其由当前解生成新解的过程是嵌入在决定搜索策略的启发式方法之中的。全局优化方法往往基于局部优化方法，但全局优化方法不仅接受使目标函数值优化的操作，还在一定程度接受使目标函数值恶化的操作。在解集中搜索最优解的同时，保持候选解的群体多样性，更广泛、更深入地对解空间进行搜索，能避免搜索陷入局部极值，找到全局最优解的可能性相对较大14。常用的模拟退火算法、禁