第7讲运输规划与优化ppt课件.ppt

《第7讲运输规划与优化ppt课件.ppt》由会员分享，可在线阅读，更多相关《第7讲运输规划与优化ppt课件.ppt（97页珍藏版）》请在三一办公上搜索。

1、2022/11/13,1,第7讲 运输规划与优化,1 运输规划的理论与模型2 综合运输规划方法3 货物运输需求的预测方法4 运输优化的数学模型5 运输优化的实际应用,2022/11/13,2,u 引导案例 长江三角洲地区是我国经济最发达的地区之一。随着改革开放的不断深入，经济发展速度加快，原有的交通运输系统暴露出许多问题，如交通路线少；各种运输方式的能力严重不足；原有的运输基础设施严重老化等等。为此，国家计委和世界银行共同对长江三角洲地区的共同对长江三角洲地区的综合运输进行规划研究。这是我国与世界银行合作的软课题中研究范围最广、投入资金最多的项目之一。在这个规划研究中，采用了先进的运输规划和优

2、化理论，从400多个建设项目中，筛选出92个项目，并计划在10年内投入880亿元，用于相关交通基础设施建设。,2022/11/13,3,第一节 运输规划理论与模型,1 运输规划的历史,在20世纪60年代以前，运输规划通常以城市的机动车自然力调查（也称为起讫点调查）为基础，预测未来的机动车交通需求，进行道路规划；以定期月票利用者的站点间自然力调查等为基础预测将来的利用者数，进行轨道交通规划。 20世纪60年代，在考虑未来的城市交通时，个体运输工具和大运量的运输工具之间的平衡，成了人们关注的焦点。人们逐渐认识到，解决大城市交通阻塞，仅仅通过对断面交通量采用某些局部数据进行运输分析、道路规划是远远不

3、够的，必须以路线及道路网为对象进行全面分析。,2022/11/13,4,以定量数据为基础进行城市综合交通运输规划起源于美国，并且在世界范围内得到了迅速发展。1953年，美国大都市圈底特律首先开始进行交通调查。随之，则是称为“芝加哥范围运输学习”的芝加哥都市圈交通规划则对道路规划在内的四阶段交通需求预测法，开了城市综合运输规划的先河。1962年，美国制定的补充联邦道路法，进一步推动了“运输计划”在全美国的实施范围。在其他发达国家，如英国和日本，运输规划的理论和实践同样取得了很大的进展。,改革开发以来，我国经济的高速发展、城市化进程加快和机动车辆保有量的迅猛增加，导致了交通运输需求的迅速增长，因此

4、做好交通运输规划，对国民经济的持续快速发展极为重要。在我国，运输规划作为专门的应用学科已有20年的时间，大致经历三个阶段：,2022/11/13,5,（1）20世纪70年代末到80年代初：在这一时期，运输规划在方法上引进了发达国家的交通规划理论、计算机技术，开始探讨我国综合交通规划的理论与方法。与此同时，国内几十个大城市开展了大规模的运输调查，利用计算机技术进行调查数据的统计和交通特征分析，运输规划迈开了定量化的第一步。 （2）20世纪80年代中到90年代初：结合这一时期的运输规划特点，运输规划在交通调查的基础上，对交通特征进行研究分析，将运输规划的四步模型理论与方法，交通预测技术应用到实际的

5、道路运输规划中，运输规划开始了定量与定性相结合的一步。 （3）20世纪90年代到现在：在这一时期，由于计算机技术的普及，运输规划人才素质的提高，市场需求加大，运输规划的基本原理、定量化预测技术等在各种类型的规划实践中得到了广泛的应用。研究重点侧重于运用定量的科学技术进行规划方案的分析、指导设计。与此同时，国内运输规划在调查方法、数据分析、模型精度、预测技术、战略研究、规划的层次划分、交通设计方面进行了广泛的探索研究。,2022/11/13,6,2 四步模型的基本概念,运输规划的基本目的是为了改善客货流运输的条件。 运输规划的实践集中在两个主要领域： （1）城市和大都市区模型 （2）城市间货物和

6、国家模型,2022/11/13,7, 运输窗口 国外铁路智能运输系统研究现状 所谓铁路智能运输系统，就是利用计算机技术、现代通信技术、现代信息处理技术、控制与系统技术、管理与决策支持技术和智能自动化技术等。实现信息采集、传输、处理和共享，通过高效利用与铁路运输相关的所有资源，以较低的成本达到保障安全、提高运输效率、改善经营管理和提高服务质量为目的新一代铁路运输系统。 国外先进的铁路智能运输系统（RITS）主要包括欧洲的铁路运输系统（ERTMS）和日本的列车运行管理系统。前者优于后者。欧洲铁路运输管理系统的目标在于建立全欧洲铁路网统一的标准，保证各国列车在欧洲铁路网内的互通运营，并提高铁路运输管

7、理水平。ERTMS的核心是欧洲列车控制系统（等等）和超速防护系统。日本从2000年初开始铁路（Cyber Rail）的研究。Cyber Rail是日本铁路系统发展的一个参考模型，是从智能运输系统的角度建立起通用的标准体系框架。目前Cyber Rail正处于体系框架定义阶段。,资料来源：贾利民，李平著，国外铁路智能运输系统研究现状,2022/11/13,8,我国交通运输发展的长期目标是建立客运快速化和货运物流化的智能型综合交通运输体系，智能型综合交通运输体中的智能是以模型体系为核心的，其中现代化的规划方法和科学的决策体系是以规划模型和决策模型为基础的。,2022/11/13,9,四步模型由四个步

8、骤组成：,即生成（产生）分布（发布）方式选择（形式的切分）路径分配（赋值）,2022/11/13,10,3 四步模型的基本原理,3.1 交通量的生成,根据所研究对象地区的特性直接求得生成交通量的步骤被称为交通量的生成（旅行产品）。,2022/11/13,11,本文主要介绍两类方法： 增长率法 函数法,所谓发生（或吸引）的交通量是指研究对象地区内由各运输小区内发生（或吸引）的交通量。而生成能力（包括产生和吸引）是土地利用和社会经济发展的函数。,2022/11/13,12,（1）增长率法（生长-因素模型）,这种方法就是把现在的不同分区生成的交通量与到预测时点的增长率相乘从而求得各分区的交通生成量

9、，即,2022/11/13,13,这种方法的关键问题是如何确定。通常可以用表示各运输小区活动的指标的增长率作为生成交通量的增长率。例如：,2022/11/13,14,(75),对象地区外运输小区的生成交通量的增长率；对象地区外运输小区的常住人口的增长率；对象地区内全体的常住人口的增长率。,增长率法的最大优点是可以处理用原单位法和函数法都很难解决的问题。这就是，当我们进行区域的生成交通量预测时，研究对象地区外的预测也是必要的。这种时候，对于对象地区外的区域，通常只需要处理此区域与对象区域之间的交通。此类问题，通常采用增长率法.设定,2022/11/13,15,（2）函数模型法 也被称为多元回归分

10、析法（衰退分析）作为模型公式，多采用以下三个模型：,(76),这里的 大多是表示运输小区的活动的人口指标,2022/11/13,16,3.2 交通分布,在交通的分布阶段，主要是预测交通生成量的来源和去向。在交通分布中最基本的概念是自然力表。O表示出发地（起点），D表示目的地（目的地）。较为简单的自然力表如下：,2022/11/13,17,所谓交通量分布的预测是指给定发生交通量和吸引交通量，对于全部自然力求、之间的分布的运输量。对运输量分布预测的方法主要分为两大类，即增长率法和构造模型法。下面对构造模型法中的重力模型法（重力模型）进行阐述。,2022/11/13,18,重力模型是模拟物理学中万有

11、引力定律而开发出来的运输分布模型。此模型假定、间的分布运输量与起点发生的运输量与终点吸引的运输量成正比，与两点之间的距离成反比。即,(77),2022/11/13,19,上式为线性函数，可用线性重回归分析求各系数。,2022/11/13,20,方式选择（形式的切分），某种方式的选择决定于运输成本、运输时间等因素，选择中最重要的特征是成本和时间（包括换乘时间）。方式选择的模型很多，通常分为两大类。即集计模型（合计模型）和非集计模型（使崩溃模型）。非集计模型也叫个人选择模型（个人选择模型），或分散选择模型（离散的(选择) 模型）等。其中使用较多，又比较成熟的是非集计模型中的Logit模型。Logi

12、t模型的理论基础是数理统计理论与经济学理论。该模型中的许多参数必须通过标定来完成。,多项Logit模型（多项的Logit模型）的选择概率为：,(79),3.3 方式选择,2022/11/13,21,模型的推导过程,这一模型虽可以由判别分析、刺激反映过程模型导出，但以随机效用理论为基础推导出来却是美国的McFadden的成绩。以随机效用为基础的多项Logit模型是在假定与独立的，而且选择支之间服从Gumbel分布（也叫Weibull分布）的前提下推导出来的。也就是说，假定各的密度函数的分布函数如下式所示：,(710),2022/11/13,22,(711),将此式代入下式,(712),即可得到（

13、79）式,2022/11/13,23,路径分配（Assignment），根据路径上的不同成本、旅行时间函数进行分配。这一分配理论的基础是沃德罗普原理（1950年，欧洲），实际上是一种迭代分配法，什么时候路网平衡，就是分配完成。 只介绍两种简单的路径分配方法 0-1分配法 增量分配法,3.4 路径分配,2022/11/13,24,（1）0-1分配法 0-1分配法（all-or-nothing assignment method）。它有两个特点。第一个特点是不考虑拥挤对走行时间的影响，即认为所有路段上的走行时间都是不随路段上交通流量的大小而变化的常数；第二个特点是认为同一组OD的所有驾驶员都选择完

14、全相同的路线。因此，这种分配法的主要计算是寻找最短路径。0-1分配法十分简单但却很近似。在道路稀少的偏远地区的交通量分配中可以采用这种方法，一般城市道路网的交通量分配不宜采用这种方法。,（2）增量分配法 增量分配法（incremental assignment method）是一种近似平衡分配法。这种方法的基本思路是将OD运输量平分成若干等分，循环地分配每一等分的OD运输量到网络中。每一次循环分配一等分的OD交通量到相应的最短路径上，每循环分配一次重新计算并更新各路段的走行时间，然后按更新后的走行时间重新计算并更新各路段走行时间，然后按更新后的走行时间重新计算网络各OD间的最短路径。下一循环中

15、按更新后的最短路径分配下一等分的OD运输量。其计算步骤如下：,2022/11/13,25,2022/11/13,26, 运输窗口7-2美国未来的城市交通规划 M.D. Muyer认为，在探讨美国的未来的城市交通规划，需要在下面十个领域进行研究，即：人口结构变化；经济与市场的作用；多方式的交通规划；运输系统管理目标；强化新技术的应用；新的社会团体意识；实行道路定价策略；加强土地使用管理；交通的可持续发展；公众参与交通规划。在进行美国城市未来的交通规划的时候，必须考虑以下几条：在交通规划的不同阶段，决策者注重于不同因素的影；在未来的规划中，交通与环境的联系将会越来越紧密，轨道交通将日益受到重视，规

16、划也将越来越注重于对环境的影响；社会上不同的关注及需要将影响规划的进行；技术及环境还会体现在今后对决策的评价中。,2022/11/13,27,4 四步模型的应用,在实际应用中，通常采用抽样调查的办法，并与发展政策、项目规划挂钩起来。这种方法通常被称为非完全矩阵法。非完全矩阵法不是将全部的交通流分配到路网上，与完全的现场OD调查得到数据会有一个区别。事实上，不能所有的OD流都考虑进去，当然有些应该纳入进去而未被纳入的OD流，要单独处理。,2022/11/13,28,在模型的应用过程中，通常把交通分成两大类: 一部分称为经过模型的交通流 另一部分称为未经模型的交通流 纳入模型中的交通流通常用矩阵表

17、示，用观测值导出现状OD矩阵，预测OD矩阵通过推算求出。对一部分未经模型的交通流，按区段分别导出。简单的方法是，观测的交通流减去模型交通流就是未经模型的交通流，这意味着交通流矩阵外还要有许多其它的数据，如每一区段的总交通量，这些数据各运输管理部门都有，在每个区段上究竟有多少交通流量被模型化，这要做具体的研究，如所有的大宗货物运输要进模型，城市间的旅客运输要进入模型，市郊短途运输不纳入模型等等。在实践中要靠模型开发和应用专家在实际的应用过程中不断地总结。,2022/11/13,29,第二节综合运输规划方法,综合运输即多种运输方式综合协调发展，其规划就是确定综合运输发展目标，设计达到该目标的过程。

18、前者主要包括运输需求预测主要包括运输需求预测，后者主要涉及运输供给方案的设计、评价和选择等。,1 国外综合运输规划方法发展综述,1.1 综合运输方法的概念,2022/11/13,30,最早的运输需求分析:考尔（Kohl,1850）研究了资源的地区分布与运网形状间的关系。重力模型的最早形式是莱文斯（Ravensteina, 1895）在研究城市间人口迁移方式时提出的。雷利（Reilly，1929）对零售重力模型的研究。斯托芬（Stouffer，1948）对空间互作用模型的研究。济普（Zipf,1946）对城间出行重力模型的研究。,1.2 综合运输规划方法的发展,2022/11/13,31,解释城

19、市土地利用和出行活动间关系的城市运输需求模型贝克（Beckmann,1955）等人的研究。,随后，运输需求分析出现了两大发展：,2022/11/13,32,出行行为概念被假定为一个有理性的人，并力求使其社会经济活动的效用最大化。,运输需求分析的最新进展,(2) 确认旅行和运输决策中所包括的重 要随机因素,(1) 大量的概念和分析方法的应用,2022/11/13,33,目前运输存在的主要问题包括： 能源短缺 环境影响 公众参与 社会公平,2 综合运输规划的一般步骤,2022/11/13,34,运输规划包括5个主要步骤建立目标和任务确定系统的各个组成部分建立这些组成部分间相互作用的模型分析、评价各

20、种政策方案的全部参考数据建立进行工程项目决策的必要框架,2022/11/13,35,地区运输规划方法一般分为三类： （1）运输需求标准法 （2）单一运输方式模拟评价法 （3）多种运输方式模拟评价法 （综合运输规划法）,3 综合运输规划的一般方法,3.1 运输规划方法的主要类型,2022/11/13,36,当用这种方法时，要求制定适用于不同运输方式的标准，如网络结构设计和安全标准。然后对系统的未来状态进行预测。标准的状态和对未来的预测的状态间存在的任何差别被认为是“需求”。,（1）运输需求标准法,优点是简单易行。缺点是标准的选择不容易完成，运输方式间的关系无法确定，且用户和非用户的收益量不能直接

21、测量。,2022/11/13,37,制定地区运输规划，分4步完成：是陈述规划的目标和任务。是制定达到这些目标和任务的多种规划方案是对现有的网络和规划方案所提出的未来的网络进行模拟是对新制订的规划方案进行评价,（2）单一运输方式模拟评价法。,2022/11/13,38,包含以下几个步骤：对所有运输方式的客货运输需求量进行预测；将预测的需求量分配给多种运输方式，然后进行网络模拟，并进行信息反馈，以考虑这种运输方式运量的分担率的变化,（3）综合运输规划方法,2022/11/13,39,综合运输规划方法一般包括5类模型：出行需求、模拟和影响预测模型经济、土地利用、经济活动布局模型资源分配、财政政策和计

22、划模型分析和评价模型观测（数据收集和监测）模型,3.2 综合运输规划方法的组成,2022/11/13,40,第三节 货物运输需求预测,1 运输需求预测,需求预测模型建模最常用的方法，是确定并说明变量和交通流量间的关系。,2022/11/13,41,货运需求分析有三种基本方法微观经济分析法空间互动建模法宏观经济分析法,2 运输需求的分析方法,2022/11/13,42,一般工序可用下面形式的一族函数表示： P(Z,X)=0 (713)式中，P-生产函数。 Z-产品向量 X-输入物向量输入物的组合满足生产函数： Min C(Z, W)=WX (714)式中，C(Z,W)-总生产成本满足约束条件 P

23、(Z , X)=0,(1) 生产函数和成本函数,3 货流的微观经济分析,2022/11/13,43,(2) 运输需求函数,2022/11/13,44,式中， 分别是铁路和卡车的单位运输成本； 上述两种运输方式的货物特点和运输特点，这些特点包括评价运距和货物批量等； X输入物资向量（不包括运输），如资本和劳动力等； Z产出水平。,(717),Friedlaendes和Spady成本函数具有下面的形式：,2022/11/13,45,货物空间互动模型是一种聚类模型。在其最常用的场合下，这种方法是以重力模型的形式来实现的。在重力模型中，两区之间的货流量与其经济活动量的积函数成正比；与货物运输总成本的减

24、函数成正比。除重力模型外，一些优化模型也属于此类。这些优化模型有两类,其主要区别是优化过程中所用的目标函数不同。,4 货物运输需求的空间互动模型,2022/11/13,46,式中， 在i区生产并运到j区的货物k的总数量（吨）； 发自i区对货物k的总需求量； 阻抗系数（等于 ，其中 是i区和j区的欧氏距离， 是经验指数值，该值可能随所分析的货类而变）。,(1) 重力模型,(718),Black的重力模型的形式如下：,2022/11/13,47,式中， 运输方式m从i区到j区的货流量； 起点区和终点区的总产值； 工业特征指标； 从i区到j区的最小运输时间； i区到j区的最低运输成本； 运输方式m的

25、成本除以i区到j区的的最低运输成本 服务于i区和j区的运输方式数。,Mathematica模型数学表述如下：,(719),2022/11/13,48,设 是i点的超额供给量， 是j点的需求过大量。 是i点和j点间单位货物的运输成本。用线性规划方程找出i点和j点间的货流量 ，并取运输总成本的最小值。,(2) 优化模型,2022/11/13,49,在运输需求分析中所用的宏观经济建模法有两种： 经济法 投入产出法,5 货物运输需求的宏观经济模型,宏观经济模型力求解决部门间的货物和服务的流动问题。,2022/11/13,50,(722),将部门间的货物和服务流量记为 。其中，i表示生产部门，j表示消费

26、部门。任何经济部门的总产出由下式给出：,式中，E是构成国民经济各部门的集合。,2022/11/13,51,式中，P表示国民经济中全部生产部门的集合； 是对i部门产品的最终需求量； 是生产部门间的货流量。有可能通过一组简化的假设条件，来改进投入产出分析法。,(723),2022/11/13,52,假设：（1）每个部门生产一组同类产品，每类产品仅由一个部门生产。（2）在一个部门内的全部企业采用十分相似的生产技术；这些技术完全可用一中等技术来代表。（3）生产产品的总供给和总需求间可达到平衡。（4）各部门的生产技术变化不快，因此，可假定在短时期内不变。,2022/11/13,53,对每两个部门来说，技

27、术系统可定义为在j部门生产单位产品直接消耗i部门产品量。换言之：,(724),也被称为直接消耗系数。,将方程（10）和（11）联立得下面的方程：,(725),2022/11/13,54,上述方程也可用矩阵的记号更好表示为： X=AX+Y 或 Y=(IA)X (726)式中，Y表示最终需求向量；X表示产出向量；A表示矩阵 ，而I表示单位矩阵。假设（IA）矩阵是非奇异矩阵，则方程（13）变换成能够根据给定（或预测）的最终需求预测产出的模型： (727)式中， 是（IA）的逆阵，称为直接和间接消耗系数矩阵。该逆阵中的每一个元素，如 将给出i部门满足j部门一单位最终需求所需生产的产品量。于是，在i和j

28、相同时， 是直接消耗系数；在i和j不同时， 就是间接消耗系数。,2022/11/13,55,指数平滑法是根据历史资料的上期实际数和预测值，用指数加权法进行预测的一种方法，此法实质上是由加权移动平均法演变而来的。 主要优点是适用所有实际问题和不需要特别大的信息量，并且能有效地解决货物性的运输需求预测问题,6.1 三次指数平滑法,6 货物运输需求预测实用方法,2022/11/13,56,设有N个数据为最近N年运输需求量。取近N年的货物运输需求数据的加权平均值作为下一时期的货物运输需求量，即把参加计算的各年数据按时间的先后赋予不同的权数，且权数之和等于1。,（1）运输需求预测模型的建立,2022/1

29、1/13,57,式中， 为第t周期的一次指数平滑值，其值就是t+1年货物运输需求的预测值； 为第t周期的货物运输量； 是平滑常数，0 1；r是公比，r=1 1 所以,(730),(731),整理得,可见，指数平滑法预测的区间的货物运输需求值实际上等于最近几年的货物运输需求与原来估计值的不同比例之和。从（319）可知， 取决于 和 ，而 是对第t年货物运输需求的预测误差。,2022/11/13,58,为了使预测结果更加准确和可靠，采用适用性广泛的三次指数平滑法。由（319）可以得到三次指数平滑估计值公式： (732) 三次指数平滑预测模型具有以下形式： (733)式中， 表示基年为第t年，预测周

30、期为T年的运输预测值；T表示预测周期； ， ， 均为平滑系数，其计算公式如下：,2022/11/13,59,用三次指数平滑法进行预测时，必须首先估算初始值 ， ， 。其数据较多，初始值可以用货物运输的初始值 代替。这是因为当数据点多时，初始值对预测的影响极小。若数据较少，则由于初始值有相当大的权重，因此需要采用一定的方法对初始值进行合理的估算。,（2）货物运输需求初始值的估算,2022/11/13,60,设共有n1自变量 ，并记因变量 ,对所有获得的m个样本 计算各变量的均值 及偏差平方和得算术根 由公式,6.2 逐步回归在货物运输需求预测中的应用,(737),(738),于是 对 的均值 有

31、：,2022/11/13,61,2022/11/13,62,2022/11/13,63,2022/11/13,64,2022/11/13,65,第四节 物流运输优化方法,1.1 最优点搜索方法 简单地说，最优化问题就是在可行空间 中找出一个点 ，使目标函 数f(x)达到最大或最小值。即 (745)对于连续可微函数，可以微分计算法求得最优值。但是在很多情况下，难以满足这种要求，则可以通过使用搜索方法求得最优值。,1 数学规划求解方法,2022/11/13,66,穷举法总的计算次数： N=1/h+1 (746)式中，方括号表示取整数。 h-分点间隔 在图7-1中，分隔点h=0.1，则计算次数为N=

32、11次。,(1) 穷举搜索,2022/11/13,67,穷举法事先确定自变量的取值，然后计算对应的函数值。序贯搜索方法则不能事先确定自变量的取值，自变量的取值顺序取决于前几次计算的函数值。序贯搜索要求函数f(x)在货物a,b上呈单峰性质，即函数在a,b上只有一个极值。 序贯搜索方法有很多种，如两分搜索、等区间多点搜索、黄金分割搜索和Fibonacci搜索等。本书重点介绍Fibonacci搜索法和两分搜索法。,(2) 序贯搜索,2022/11/13,68,2022/11/13,69,2022/11/13,70,2022/11/13,71,2022/11/13,72,2022/11/13,73,2

33、022/11/13,74,Subject to: r=1,2,m (756)所有 上式中的M是一个很大的正数，它是人工变量对应的价值系数，满足条件： (757) 由于人工变量对应的价值系数远比其他变量所对应的价值系数大，所以在求解过程中，人工变量最终取值都为零。为了使用单纯形法求解线性规划问题，上述表达式可以列成表格形式，称之为单纯形表，如下表：,2022/11/13,75,2022/11/13,76,2022/11/13,77,2022/11/13,78,2022/11/13,79,2022/11/13,80,2022/11/13,81,对于运输问题，一般采用单纯形法求解，运用线性规划模型解

34、决运输优化问题也可以使用现有的软件。 使用求解软件时，只要知道运输表即可，不一定要列出繁琐的数学模型，例如3个起运站，4个目的地，供应量为50，50，75，需求量为40，55，60，20，各起运站到目的地的单位运费为：,2.1.2 运输表,2022/11/13,82,2022/11/13,83,对于比较简单的物资调运问题，可以用图上作业法或表上作业法求解，这里只介绍图上作业法。这种方法可把运输网络转化成树型结构，便于建立运输网络数据库，从而进一步进行路线规划和车辆调度。,2.1.3 图上作业法,运输浪费运输力的不合理现象有两种 对流现象 迂回运输,2022/11/13,84,2022/11/1

35、3,85,2022/11/13,86,2022/11/13,87,第一步：在每个回路中，去掉一段路线，变成不含回路的情况，按上述方法作出调运方案第二步：检查有无迂回现象。分别检查每个回路，如果圈内和圈外流向的总长度都不超过回路总长度的一半，那么，这个回路上就没有迂回现象了，这个方案就是最优方案。否则转第三步第三步：改变原来的去段和破圈方式，转第二步,运输道路中含有回路，可以分三步寻求最优方案,2022/11/13,88,车辆路线安排问题（VRP，Vehicle Routing Problem）是指对物流配送的车辆进行优化调度。,2.2 车辆路线安排问题（VRP）,2.2.1 概述,在VRP问题

36、中最常见的约束条件有： 容量约束 优先约束 车型约束 时间窗约束 相容性约束.,2022/11/13,89,大多数模型都可以看成是下面三个模型的变形与组合： （1）以车流为基础的模型 （2）以物流为基础的模型 （3）聚覆盖模型,2.2.2 VRP问题的模型及算法,2022/11/13,90,精确式算法一般运用线性规划和非线性规划等数学规划技术，以便求得问题的最优解。精确式算法一般有以下几种方法： （1）分枝定界法 （2）割平面法 （3）网络流算法 （4）动态规划方法,精确式算法,2022/11/13,91,为了克服精确优化方法的不足，可以运用一些经验法则来降低优化模型的数学精度，并通过模仿人的

37、跟踪校正过程来求取运输问题的满意解。启发式算法：启发式算法中最具有代表性的就是克拉克（Clarke）和怀特（Wright）提出的节约法(Saving Method)。,经验法,2022/11/13,92,下面通过克拉克和怀特的论文中的例子来说明节约法思考的基本思路。设配送中心是 ，m个用户分别是 ； 之间的最短距离 ，且 已知（i, j=1，2，3，m）。 如果发货车辆的吨位已知，并且每一辆车都可以满载，则研究的目标转化为使所有的参加发送的车辆的总发送距离在满足约束条件的基础上最小。,2022/11/13,93,2022/11/13,94,2022/11/13,95,2022/11/13,96

38、,（1）构造算法 根据一些规则，每一次将不在线路上的点依次增加到路线中去，直到所有的点都安排在路线上为止。（2）两阶段算法 对构造算法进行改进，提出了两阶段算法。第一阶段得到一个可行解，第二阶段则对解进行调整。在保持解是可行的基础上，尽力向最优解接近，每一步都用产生的新可行解取代原来的可行解，使得目标函数值得到改进，一直进行到目标函数值再也得不到改进为止。,一般可以把启发式算法分为以下四类：,2022/11/13,97,（3）不完全算法 精确算法中的决策原则，在规模很大的问题中，导致计算量的指数增长。在不完全优化算法中，用启发式准则代替，可以有效缩小解的收缩空间。（4）改进算法 从一个初始解开始，通过对当前的解进行反复的局部扰乱，以求得问题的满意解。,