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

带有时间窗的车辆路径问题的优化研究 I 摘摘 要要 随着现代科学技术的迅猛发展以及全球经济一体化趋势的加强，各国都面临着 前所未有的机遇和挑战。现代物流作为一种先进的组织方式和管理技术，被广泛认 为是企业在降低物资消耗，提高劳动生产率以外的重要的利润源泉，在国民经济和 社会发展中发挥着重要作用。由于JIT理论和实践的成熟，现代产业对物流配送提 出了更高的要求将合适的零件以合适的数量在合适的时间送到生产线。这是为 适应消费需要变得多样化、个性化而建立的一种生产体系及为此生产体系服务的物 流体系。消费者需求趋于多样化，对送货时间的要求日趋严格，除了因缺货造成的 机会成本的损失外，由于配送不及时也会造成货物价值的大大降低。在配送运输上， 时间窗口显得越来越重要。因此，降低运输成本，提高配送的及时性和配送的服务 质量，优化车辆路径问题，是降低企业成本的迫切需要。 本文正是基于这种背景对物流配送路径的优化问题开展相关研究。详细阐述 了物流的概念，物流对产品价值、企业竞争力、宏观经济三大方面产生的影响，介 绍了配送的定义，分析了配送的评估指标；通过介绍物流配送在整个物流过程中具 有的重要意义,说明了解决带有时间窗的车辆路径问题的必要性及现实意义；同时 收集了国内外关于车辆路径问题研究的文献资料并进行整理、分类，详细介绍了国 内外研究现状；对现有的求解方法进行了具体介绍和整理归类；并详细阐述了遗传 算法的优劣点和具体操作过程，然后在现有多目标模型的基础上分析其不完善之处， 并从运输成本、顾客满意度（配送及时性）、以及配送车辆数三大角度出发，改进 了带有时间窗的车辆路径优化多目标模型，运用具有隐式并行性和全局搜索性两大 特点的遗传算法进行求解。在求解的过程中，根据自然数编码的特点，对遗传算法 的三个算子选择、交叉、变异进行了特别设计，最终得出了模型的解。 关键词关键词：车辆路径问题，遗传算法，时间窗，多目标规划 带有时间窗的车辆路径问题的优化研究 II Abstract With the development of science and technology, the economic 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. 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 transportation. 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 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 criterion 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 while 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 optimizing 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 it 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 XiZhao Keywords：VRPTW, Genetic Algorithm, time windows, multi-objective model 带有时间窗的车辆路径问题的优化研究 III 目目 录录 第一章第一章 引言引言 .1 1 1.1 论文研究背景 .1 1.2 国内外研究现状及存在的问题 .2 1.3 论文研究的目的和意义 .3 1.4 本文研究的内容及技术路线 .4 第二章第二章 物流及配送物流及配送概述概述 .6 6 2.1 物流的定义 .6 2.2 物流的作用 .7 2.2.1 物流对产品价值的贡献 .7 2.2.2 物流对企业竞争力的作用 .7 2.2.3 物流对宏观经济产生的影响作用 .8 2.3 配送的定义.9 2.4 配送的评估指标.11 第三章第三章 带有时间窗的车辆路径问题的算法回顾带有时间窗的车辆路径问题的算法回顾 .1313 3.1 带有时间窗的车辆路径问题的概念和研究现状 .13 3.1.1 概念和主要类型.13 3.1.2 求解算法回顾.15 3.2 遗传算法 .22 3.2.1 遗传算法的生物遗传学基础.22 3.2.2 遗传算法的基本概念.23 3.2.3 标准遗传算法.23 3.2.4 遗传算法的特点.23 3.2.5 遗传算法过程描述.25 第四章第四章 多目标多目标 VRPTWVRPTW 模型的改进和遗传算法实现模型的改进和遗传算法实现 .4343 4.1 改进的多目标 VRPTW 模型 .43 4.2 多目标 VRPTW 模型的处理 .46 4.3 算例数据 .48 4.4 遗传算法的设计 .52 4.4.1 编码设计.52 4.4.2 约束处理设计.52 4.4.3 适应度函数设计.53 4.4.4 三种遗传算子的 C 语言设计.53 4.5 运行结果 .57 第五章第五章 结论与展望结论与展望 .5858 5.1 研究结论 .58 带有时间窗的车辆路径问题的优化研究 IV 5.2 未来的研究展望 .58 致致 谢谢 .6060 参考文献参考文献 .6161 硕士期间已发表的论文硕士期间已发表的论文 .6363 附附 录录 .6464 带有时间窗的车辆路径问题的优化研究 1 第一章第一章 引言引言 1.11.1 论文研究论文研究背背景景 随着社会、经济、技术的高速发展，全球经济一体化趋势和市场竞争程度日益 加强。全球网络通信和信息技术的飞速发展使得现代商业逐渐呈现出新的特征:不 断增长的供货能力、不断增长的客户需求、不断增长的全球竞争等。以信息技术为 基础的物流服务在全球迅速崛起，其本身所具有的开放性、全球性、低成本和高效 率的特点能够更好地满足现代商业的要求，推动社会经济的进步。世界各国都已经 意识到物流的重要性，尤其是在工业发达国家，物流管理与物流技术己经得到了广 泛的应用与发展，包括生产、流通、消费等过程诸环节的物流系统，已成为适合于 市场经济发展的基础产业之一。 在此背景下，企业技术水平和内部管理水平的不断提高使得生产和销售领域内 降低成本的空间越来越小，在生产和销售领域以外的运输、仓储、配送、库存等环 节上的成本比重越来越高。企业经营决策者不得不把寻求成本优势的视角转向“第 三利润的源泉”物流领域。从运输成本看，我们还有很大的空间可以去努力。 据统计，各国运输成本占国民生产总值的10% 15%左右1。这就意味着运输系统的 效率提高一点就可以节约很多成本。只要我们能够将现有运输成本降低，我们的国 民经济总体水平就能出现一次新的飞跃，一次真正的飞跃。 但是，目前我国现阶段物流服务的实施有着不可回避的问题:物流技术、基础 设施和装备条件还不够完善；物流效率低下；物流业发展比发达国家落后；“物流 瓶颈”严重制约我国产业的发展等等，这些问题迫切需要加以重视和研究。在这种 严峻的形势下，大力推进现代物流产业发展，降低运输成本，增强物流环节的服务 质量，是提高物流效率的迫切需要。而运输是现代生产企业和物流管理中最重要的 一个环节，车辆路径问题又是运输问题中最关键的技术。有效的车辆调度,不仅可 以提高物流工作效率,而且能够为生产工序之间的物料传送得到运输上的保障,从而 实现物流管理科学化。 带有时间窗的车辆路径问题的优化研究 2 1.21.2 国内外研究现状及存在的问题国内外研究现状及存在的问题 1）国内研究现状）国内研究现状 目前，国内对于复杂的车辆路径问题的研究仍处于起步状态。通过中国期刊数 据库检索，19942005 年12年时间，在中国的正式期刊上已经发表该领域的文章 仅二十多篇。就这方面研究的深度和广度来说，远不能适应当前我国配送业以及物 流业迅速发展的需要。国内在车辆路径问题上的研究基本上着重于车辆路径问题的 启发式算法研究。如求宾松、符卓在解带软时间窗的车辆路径问题的改进遗传算 法中通过引用一种新的编码方法、交叉和变异概率的自适应机制，构造一个改进 的遗传算法来求解带软时间窗的车辆路径问题；陈火根、丁红钢等在物流配送中 心车辆调度模型与遗传算法设计中对带时间约束的物流配送中心车辆调度问题， 采用混合整数规划方法进行建模，分析了该模型用精确算法进行求解的复杂性，提 出了遗传算法与启发式算法相结合的求解方法，将该问题分解为车辆分配和单一车 辆路线安排两个相互关联的子问题进行求解；霍佳震、张磊在有时间窗的集货送 货一体化车辆路径规划启发式算法研究中通过对模型的分、分解和过虑，结合实 际情况，以修正的ClarkeWright节约启发式算法为基础进行插入式排序，以解决 带有时间窗口的集货和送货一体化路径规划问题；张炯、郎茂祥有时间窗配送车 辆调度问题的禁忌搜索算法中在对有时间窗配送车辆调度问题进行描述的基础上， 建立了该问题的基于直观描述的数学模型，通过设计一种新的解的表示方法构造了 求解该问题的禁忌搜索算法，并以21个节点的运输网络为例进行了实验计算。 2）国外研究现状）国外研究现状 国外关于车辆路径问题的研究较早，最初由Dantzig和Ramser于1959年首先提 出的，很快引起运筹学、应用数学、组合数学、网络分析、图论、计算机应用等学 科的专家与运输计划制定者和管理者的极大重视，他们进行了大量的理论研究及试 验分析，取得了很大进展。以Bodlin，Christofider，Golden，Assad, Ball为代 表的学者对该问题进行了较为深入的研究，完善了该问题的模型和算法。目前国外 着重研究各种车辆路径问题以及相关启发式算法的探索。如：OLATZ ARBELAITZ，CLEMENTE RODRIGUEZ在COMPARISON OF SYSTEMS BASED ON 带有时间窗的车辆路径问题的优化研究 3 EVOLUTIONARY SEARCH AND SIMULATED ANNEALING TO SOLVE THE VRPTW PROBLEM中介绍了几种解决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 TEST CASE GENERATION中 提出了两阶段方法来解决车辆路径问题，在第一阶段中运用了新的路径规划启发式 算法来获得初始解，第二阶段用禁忌算法来改进解。WEEKIT在A HIBRID SEARCH ALGORITHM FOR THE VEHICLE ROUTING PROBLEM WITH TIME WINDOWS中重 点研究了禁忌算法和遗传算法混合的启发式算法。禁忌搜索优势在于局部搜索，遗 传算法优势在于全局搜索，文章将两种优势结合起来寻求近最优解。 3）国内外研究中存在的问题）国内外研究中存在的问题 着重启发式算法研究，模型研究成果比较多，但多目标模型研究还不够完 善。 在多目标模型研究中，现有的模型中除路径和车辆数目外并没有考虑到其 他方面对物流效率的影响。 1.31.3 论文研究的目的和意义论文研究的目的和意义 在物流配送系统中，物流配送中心的成立可有效地简化配送程序与减少配送的 频率，而物流配送中心作业的重点是如何将车辆有效地使用并决定其最经济的行驶 路线图，使商品能在要求的时间内送到顾客的手中。国外将此类问题称之为带有时 间窗的车辆路径优化问题(Vehicle Routing Problem with Time Windows)，简称 为VRPTW3。 有效地解决带有时间窗的车辆路径问题，不仅可以能够提高物流工作效率，而 且能够为及时生产(JIT)模式的企业提供运输上的保障，从而实现物流管理科学化。 带有时间窗的车辆路径问题不但直接存在于物流管理当中,而且很多实际生产调度 也可以间接归结为该问题。该问题的理论涉及许多学科，应用前景广阔，已经引起 带有时间窗的车辆路径问题的优化研究 4 了运筹学、应用数学、图论及网络分析、物流科学、交通运输工程、管理科学与工 程、计算机应用等科学的专家，工程技术人员和管理者的极大重视。因此，该问题 一直成为运筹学与组合优化领域的前沿与研究热点。 1.41.4 本文研究的内容及本文研究的内容及技术路线技术路线 国内外绝大多数关于VRPTW的研究都集中在算法创新，目的是获得更接近最优 解的近似解，致使物流费用降低。在带有时间窗的车辆路径问题的模型研究方面已 有不少成果，但还不够完善。所以本文将对带有时间窗的车辆路径问题的模型进行 改进优化。 论文的主要思路是构建以配送成本最小、所用车辆数目最小、顾客满意度最大 为目标的新模型。利用遗传算法的原理和其特殊优势，为带有时间窗的车辆路径问 题的求解提供一个切实可行的算子设计，求得一个较优的可行解，并说明其有效性。 论文的内容如下: 1)介绍了物流的定义和作用，阐述了配送对物流的重要意义及配送评估的主要指标。 2)对基本车辆路径问题进行了描述，综述了基本车辆路径问题和带有时间窗的车辆 路径问题的研究现状，并指出了目前存在的一些问题，总结了求解方法。 3)对带有时间窗的车辆路径问题进行描述，并建立该问题的多目标数学规划模型。 4）运用改进的遗传算子求解模型。 带有时间窗的车辆路径问题的优化研究 5 图 1-1 论文技术路线 物流及配送的 定义、作用 配送评估指标 VRPTW 问题的优化研究 研究的背景、意义和现状 多目标模型改进 具体算法描表述 C 语言编程求 解 编码 适应度函数 选择、交叉、变异算子 设计 参数选择、算法终止 遗传算法算例实现 VRPTW 定义 及算法回顾 精确算法介绍 启发算法介绍 遗传算法基本 原理及其具体 操作过程 带有时间窗的车辆路径问题的优化研究 6 第二章第二章 物流及配送物流及配送概述概述 物流最初起源于美国，当时所研究的主要内容是企业为了把产品顺利销售出去 而进行一系列运输、储存、包装等活动。因此，物流在英语中称为 Physical Distribution。第二次世界大战期间，美军后勤组织运用了一套科学方法，成功地 将各种战略物资及时准确地送到全球各地，为美军实施全球化战略提供了保障，这 套方法在军事上被称为 Logistics (后勤)。第二次世界大战后，这套后勤补给理 论、方法也为企业和理论界认同，并广泛运用起来，他们将其称为商业物流或销售 物流(Business Logistics)，以力求合理有效地组织商品的供应、保管、运输、配 送，而且实践证明取得了相当大的成效。 2.12.1 物流的定义物流的定义 物流的定义很多，并且随社会的发展而不断变化。不少学者为物流下过定义， 典型的物流定义主要有以下几种： 美国物流管理协会对物流的定义是：物流是对货物、服务及相关信息从供应地 到消费地的有效率、有效益的流动和存储，以满足客户需求的过程，并对这个过程 进行计划、执行和控制，该过程包括输入、输出，内部和外部的移动以及以环境保 护为目的的物料回收。 欧洲物流协会于 1994 年发表的物流术语中将物流定义为：物流是在一个 系统内对人员或商品的运输、安排及与此相关的支持活动的计划、执行与控制，以 达到特定的目的。 日本后勤系统协会将物流改称后勤，并且该协会名称中的“后勤系统”几个字 并没有翻译成日文汉字，而是直接用注音。该协会的专务理事稻束原树 1997 年在 “这就是后勤 ”一文中对“后勤”下了定义：“后勤”是一种对于原材料、半 成品和成品的有效率流动进行规划、实施和管理的思路，它同时协调供应、生产和 带有时间窗的车辆路径问题的优化研究 7 销售各部门的个别利益，最终达到满足客户的需求。换言之， “后勤”意味着：按 要求的数量以最低的成本送达要求的地点，以满足客户的需要作为基本目标。 2001 年颁布的中国国家标准物流术语对物流的定义是：物流就是物品从 供应地向接收地的实体流动过程。根据实际需要，将运输、存储、装卸、搬运、包 装、流通加工、配送、信息处理等基本功能实现有机结合4。这里，物流的“物” 指的是一切有经济意义的物质实体，即指商品生产、流通、消费的物质对象，它既 包括生产过程中的物资，又包括流通过程中的商品，还包括消费过程中的废弃物品。 物流的“流”指的是物质实体的定向移动，既包含其空间位移，又包括其时间延续。 2.22.2 物流的作用物流的作用 商品流通是由商流和物流构成的，生产者将其产品的所有权转移给消费者，是 价值的让渡，这一过程称为商流；产品实体从生产者那里转移到消费者那里是实体 的转移，这一过程称为物流。物流与商流的结合构成了整个流通。物流，对于整个 社会经济体系来讲，其作用与意义如同梁柱构成的框架对于高楼大厦的价值。 2.2.12.2.1 物流对产品价值的贡献物流对产品价值的贡献 一件产品或一项服务的价值如果得到了市场的认可，那么它必然会给消费者提 供四种效用。 1）形态效用产品以其特有的外在形态或者属性为消费者服务而产生的效用。 2）空间效用产品通过在特定地点服务于消费者，给消费者带来的效用。 3）时间效用产品通过在特定时间服务于消费者，给消费者带来的效用。 4）占有效用通过使消费者占有产品而实现的效用。 2.2.22.2.2 物流对企业竞争力的作用物流对企业竞争力的作用 竞争优势归根结底产生于企业为客户所能创造的价值，或者在提供同等效益时 采取相对的低价格，或者其不同寻常的效益用于补偿溢价而有余。那么，如何通过 物流获得竞争优势呢? 带有时间窗的车辆路径问题的优化研究 8 1）成本领先 其优势直接来源于产品和服务的低成本。产品的总成本中包含物流成本，当前 物流费用占产品总成本的比重已经超过 40，这是一块“黑暗大陆” ，但又是“第 三利润源泉” ，企业可以通过优化物流管理大幅度降低物流成本，从而降低产品总 成本，确立企业在同行业成本领先的地位，在竞争中取胜。 2）标新立异 不同的产品和服务在消费者心目中是有独特之处的。对于一个企业来说，都希 望通过产品创新，或营销手段的配合使自己的产品和服务能在消费者心目中树立与 众不同的形象，并给消费者带来利益。但由于科学技术手段越来越先进，使得大多 数产品很容易被仿制。于是，产品的差异性和独特性就被大大的削弱。但如果企业 有一个一体化高效运营的物流系统的话，就可以运用娴熟的物流管理技术通过向客 户提供优质服务获得竞争优势。企业如果在存货的可得性、递送的及时性和交付的 一贯性等方面领先于同行业的平均水平，那它就能成为有吸引力的供应商和理想的 业务伙伴。物流管理已成为当今企业最具挑战性的领域之一。 3）目标集聚 企业将目标定位于产业内一种或一组细分市场，并量体裁衣，使其战略为特定 的目标市场服务。 企业必须明确自己的目标市场，确立顾客至上的营销观念，把握个性化消费趋 势。在物流管理上强调有效客户反应、快速反应、突出 7R 目标(Right Product or Service，Right Time，Right P1ace，Right Cost，Right Customer，Right Quality，Right Quantity)。同时，针对客户的不同要求优化物流管理系统，以适应 用户的特殊要求。 2.2.32.2.3 物流对宏观经济产生的影响作用物流对宏观经济产生的影响作用 1）促进经济发展 社会生产部门生产出来的产品必须经过流通过程才能进入消费领域，流通过程 既包含商流也包含物流。社会经济的发展物流业是不可或缺的，而且，物流业越是 发达，就越能促进社会经济的发展。运输条件的改善是促使批发商业产生的一个很 带有时间窗的车辆路径问题的优化研究 9 重要的因素。当然，批发商业的专业化服务使得大批量的买卖成为可能，促使市场 的范围不断扩大，也使消费品生产供应上的“时” 、 “空”矛盾得以解决，商品流通 速度加快，促使社会经济的发展。 2）有利于交换功能的发挥 在商品经济的社会里，有商品生产就必然有商品交换。一个国家的社会经济是 由许多部门和企业组成的，这些部门和企业分布在不同地区，它们一方面向社会提 供产品，同时也从社会其他部门和企业获得自己所需的原材料、零部件、辅助材料 和燃料等。企业之间相互依赖的交换关系必须靠有效的物流活动来维系。 商品生产的目的就是为了交换，是为他人生产的。商品必须进入市场才能实现 生产的目的。然而商品的产地与销地往往存在空间距离，商品的生产时间与消费时 间也存在差异，要克服产销之间的这些矛盾，只有通过物流来解决。在空间上，运 输架设空间的桥梁；在时间上，仓储、库存、服务等构筑时间的隧道。只有这样， 才能使交换功能得以发挥。 3）降低社会商品的价格水平 价格水平的降低有赖于成本的减少和市场规模的扩大，而物流是“降低成本的 宝库” ，通过物流合理化、现代化等一系列活动可以降低成本与价格，成为“第三 利润源泉” 。 此外，物流活动可以创造时间和空间效用，从而拓展商品市场的范围。由于大 规模生产和物流领域更多的成本权衡机会，使得外地产品的价格有可能低于本地产 品的价格，而且会促使产品的价格竞争，其结果使整个社会商品的价格水平趋于下 降。可见，有效的物流管理有利于社会商品价格水平的降低。 2.32.3 配送的定义配送的定义 配送指的是在经济合理区域范围内，根据用户要求，在物流中心对物品进行拣 选、加工、包装、组配等作业，以合理的方式按时送达指定地点的物流活动7。配 送对于物流有着非常重要的意义，具体体现在以下几个方面： 1)体现了商流和物流的紧密结合 带有时间窗的车辆路径问题的优化研究 10 配送是物流系统中由运输环节派生出的功能，是短距离的运输；是物流中一种 特殊的、综合的活动形式，是将商流与物流紧密结合，包含了商流活动，也包含了 物流中若干功能要素的一种形式。 从物流来讲，配送的距离较短，位于物流系统的最末端，处于支线运输、二次 运输和末端运输的位置，即到最终消费者的物流。但是在配送过程中，也包含着其 他的物流功能，如装卸、储存、包装等。可以说配送是物流在小范围中物流全部活 动的体现，也可以说是一个小范围的物流系统。 一般的配送集装卸、包装、保管、运输于一身，通过这一系列活动完成将货物 送达的目的。特殊的配送则还要以加工活动为支撑，所以包括的方面更广。但是， 配送的主体活动与一般物流却有不同，一般物流是运输及保管，而配送则是运输及 分拣配货，分拣配货是配送的独特要求，也是配送中有特点的活动，以送货为目的 的运输则是最后实现配送的主要手段，从这一主要手段出发，常常将配送简化地看 成运输中的一种。 从商流来讲，配送和物流不同之处在于，物流是商物分离的产物，而配送则是 商物合一的产物，配送本身就是一种商业形式。虽然配送具体实施时，也有以商物 分离形式实现的，但从配送的发展趋势看，商流与物流越来越紧密的结合是配送成 功的重要保障8。 2）完善了输送及整个物流系统 第二次世界大战之后，由于大吨位、高效率运输力量的出现，使干线运输在铁 路、海运、公路方面都达到了较高水平，长距离、大批量的运输实现了低成本化。 但是，在所有的干线运输之后，往往都要辅以支线运输和小搬运，这种支线运输及 小搬运成了物流过程的一个薄弱环节。这个环节和干线运输有着许多不同的特点， 如要求灵活性、适应性和服务性，它致使运力利用不合理、成本过高等问题难以解 决。采用配送方式，从范围来讲，将支线运输及小搬运统一起来，加上上述的各种 优点，使输送过程得以优化和完善。 3）提高了末端物流的效益 带有时间窗的车辆路径问题的优化研究 11 采用配送方式，通过增大经济批量来达到经济地进货，又通过将各种商品用户 集中起来进行一次发货，代替分别向不同用户小批量发货来达到经济地发货，使末 端物流经济效益提高。 4）通过集中库存使企业实现低库存或零库存 实现了高水平的配送之后，尤其是采取 JIT 配送方式之后，生产企业可以完全 依靠配送中心的准时配送而不需保持自己的库存。或者生产企业只需保持少量保险 储备而不必留有经常储备，这就可以实现生产企业多年追求的“零库存” ，将企业 从库存的包袱中解脱出来，同时解放出大量储备资金，从而改善企业的财务状况。 实行集中库存，集中库存的总量远低于不实行集中库存时各企业分散库存之总量。 同时增加了调节能力，也提高了社会经济效益。此外，采用集中库存可利用规模经 济的优势，使单位存货成本下降。 5）简化事务，方便用户 采用配送方式，用户只需向一处订购，或向一个进货单位联系就可订购到以往 需去许多地方才能订到的货物，只需组织对一个配送单位的接货便可代替现有的高 频率接货，因而大大减轻了用户工作量和负担，也节省了费用开支。 6）提高供应保证程度 生产企业自己保持库存，维持生产，供应保证程度很难提高，主要是受到库存 费用的制约。采取配送方式，配送中心可以比任何单位企业的储备量更大，因而对 每个企业而言，中断供应、影响生产的风险便相对缩小，使用户免去短缺之忧。 2.42.4 配送的评估指标配送的评估指标 配送是整个物流过程最末端的环节，车辆配送是物流中心作业最终及最具体的 服务表征。目前普遍采用的对配送服务进行评估的指标主要有以下内容。 1）时效性 时效性是流通领域内客户最重视的评价指标，也就是要确保能在指定的时间内 交货。配送是上游物流活动的末端活动，同时又是下游物流活动的开端。为了确保 下游物流活动的顺利进行，及时有效的送货是极其重要的要求，也是任何一个配送 系统必须承诺的。影响配送时效性的因素，除了送货司机的个人因素以外，还有选 带有时间窗的车辆路径问题的优化研究 12 择的配送路线不恰当，客户点卸货不方便，客户不配合等。对于配送中心，可以控 制的因素按照控制力的强弱依次为配送路线选择、送货司机、客户卸货点、客户。 因此配送路线的选择是配送中心工作的一个重点，也是众多专家进行研究的重点和 热点。但是，具体到一个实际的配送中心的工作状况，任何细小环节的失误都会在 过程中不断被放大，对最终的结果产生很大的影响。 2）可靠性 能否将货物按照客户的要求，保质保量、完好无缺地送达目的地是衡量配送系 统的另外一个重要的要素。可靠性的实现可以通过配送中心的努力达到相当的高度， 根据配送系统服务对象的要求，配送中心可以通过合适的设备和严格的规章制度， 以及良好的员工素质达到任何合理的可靠性要求。 可靠性完整地体现整个配送系统的设施能力和服务水平。在配送之前，快速准 确地验货，配送前的加工，货物的包装，货物的装卸，任何一个环节都体现配送系 统的技术水平和管理能力。包括员工装卸货时的细心程度，运送过程对货品的保护， 对客户地点及作业环境的了解，配送人员的素质等。 3）便利性 配送系统是一个服务系统，所提供的服务必须能够让客户轻松获得。对于送货 方式、送货计划的安排，应该采取具有较大弹性的柔性系统，能够为各种客户和要 求及时提供便利的服务，满足客户紧急送货、信息传送、顺道退货、辅助资源回收 等独特要求。 便利性的实现更多地体现在对配送系统的技术要求上，目前，在配送系统中广 泛采用先进的信息处理技术、通信技术、定位技术等辅助手段，帮助操作人员及时 响应客户的要求。 4）经济性 在一个公正的市场经济环境中，配送中心提供服务的价格，在正常状态下，主 要依赖于配送系统运作的成本。 配送系统的运作成本必须和配送系统其他性能参 数综合进行考评，单纯对成本进行评价没有任何实际意义。也就是说，要在保证配 带有时间窗的车辆路径问题的优化研究 13 送满足客户要求、提升客户满意度的同时，通过各种技术和管理手段，降低运作成 本。 第三章第三章 带有时间窗的车辆路径问题的算法回顾带有时间窗的车辆路径问题的算法回顾 3.13.1 带有时间窗的车辆路径问题的概念和研究现状带有时间窗的车辆路径问题的概念和研究现状 为了更好地完成配送，实现配送中心的目标，不仅需要关注选用合理的运输服 务，而且还需要根据已知的车辆状况、客户送货时间需求，选择一种合适的路线方 案。这就是本文下面需要研究的带有时间窗的车辆路径问题。 3.1.13.1.1 概念和主要类型概念和主要类型 车辆路径问题最初由GB.Dantzig于1959年提出9。从二十世纪六十年代以来， 许多学者对车辆路径问题进行了广泛的研究。 车辆路径问题(Vehicle Routing Problem,简称VRP)是指:给定一个配送中心点 (中心车库，central depot),一个车辆集合和一个顾客集合，车辆和顾客各有自己 的属性，每辆车都有车的容量，所装载货物不能超过它的车的容量，起初车辆都在 配送中心车库，顾客任意分布，车把货物从配送中心车库运送到每一个顾客(或从 每个顾客处把货物运到配送中心车库)，要求满足顾客的需求，车辆最后返回车库， 每个顾客只能被服务一次，设计车辆旅行路径使运输总费用最小10。 经过几十年来许多学者的不断努力，VRP包含的类型和相关的解法已经相当丰 富，按不同的划分标准可以分成不同的种类，如按照任务特征可以划分为集货问题 或者送货问题和集送货一体化问题；按车辆满载状况可以划分为满载问题和非满载 问题；按车场数目可划分为单车场问题和多车场问题；按优化目标数可以划分为单 目标优化和多目标优化等等。 带有时间窗的车辆路径问题的优化研究 14 根据上述分析可以将VRP问题的主要类型归结为如下表格 表3-1 车辆路径问题类型划分 划分标准车辆路径问题类型 集货问题或者送货问题任务特征 集送货一体化问题 对弧服务问题（如中国邮递员问题） 对点服务问题（如旅行商问题） 任务性质 混合服务问题（如交通车路线安排问题） 满载问题车辆满载状况 非满载问题 单车场问题车场数目 多车场问题 单车型问题（所有车辆容量相同）车辆类型数 多车型问题（车辆容量不全相同） 车辆开放问题（车辆可以不返回其出发车场）车辆对车场的所 属关系 车辆封闭问题（车辆必须返回其出发车场） 单目标问题优化目标数 多目标问题 在VRP问题的基本模型基础上还可以添加许多附加条件从而变成其它问题。主 要的附加条件有： 带有时间窗的车辆路径问题的优化研究 15 1) VRPLC(带有运行时间约束的VRP ):每辆汽车运行的时间不能超过预先给定的界 L。每辆汽车的运行时间由汽车在客户间的行驶时间和汽车为客户服务的时间所构 成。 2) MVRP(多处发点的VRP):允许从多个不同的出发点出发给客户供货。 3) SDVRP(可切分供货):一个客户的需求可以同时由若干辆汽车来满足。该模型下 求得的解至少都和正常的VRP一样好，因而可以充分利用汽车的资源，从而节省汽 车。 4)随机VRP(SVRP)。某些值，如客户的数目、客户的需求、客户的服务时间不是事 先确定的，而是随机变化的。 5) VRPTW: 带有时间窗的车辆路径问题。所谓带有时间窗的车辆路径问题是指假设 有n个等待服务的客户，一个出发点，K辆有一定载重量的汽车，己知:每个客户的 位置坐标、货物需求量、出发点的位置坐标、每辆汽车的最大载重量，允许服务的 时间窗口(时间窗口是指配送车辆或顾客希望服务或被服务的时间范围。一方面， 汽车可以在时刻之前到达该客户所在地，但它必须等待直到才可以为该客户服 i a i a 务，并且不允许迟于到达。另一方面，汽车也必须在出发点开门后才可以离开， i b 在关门前返回出发点)。要求设计每辆汽车的行驶路线满足约束条件:每个客户必 须而且只能被服务一次；每条路线必须起始于出发点，为最后一个客户服务完后 返回出发点；每条路线的总负荷不能超过该辆汽车的最大载重量；每个客户必 须在它的时间窗口内被服务，如果汽车提前到了客户所在地，也必须等待，直到允 许为该客户服务为止13。 由于JIT理论和实践的成熟，现代产业对物流配送提出了更高的要求将合 适的零件以合适的数量在合适的时间送到生产线，并且只将所需要的零件、只以所 需要的数量、只在正好需要的时间送到生产。这是为了适应消费需要变得多样化、 个性化而建立的一种生产体系及为此生产体系服务的物流体系。消费者需求趋于多 样化，对送货时间的要求日趋严格，除了因缺货造成的机会成本的损失外，由于配 送不及时也会造成货物价值的大大降低。在配送运输上，时间窗口显得越来越重要。 带有时间窗的车辆路径问题的优化研究 16 带有时间窗的车辆路径优化问题根据其时间约束的严格与否，可分为软时间窗 和硬时间窗。在实际情况中，软时间窗的车辆路径问题更加常见，也更加符合实际， 因此本文研究的时间窗主要是指软时间窗。它一般把最小的车辆数作为一个目标, 而最低的行驶成本作为另一目标；时间窗是双向的,即顾客应当在最早时间之后或 最