运输规划及优化

运输规划及优化运输规划与优化2第八章2023-07-24课前复习：2023-07-2432023-07-2442023-07-245u引导案例长江三角洲地区是我国经济最发达的地区之一。随着改革开放的不断深入，经济发展速度加快，原有的交通运输系统暴露出许多问题:•交通路线少；•各种运输方式的能力严重不足；•原有的运输基础设施严重老化等。2023-07-246为此，国家计委和世界银行共同对长江三角洲地区的综合运输进行规划研究。这是我国与世界银行合作的软课题中研究范围最广、投入资金最多的项目之一。在这个规划研究中，采用了先进的运输规划和优化理论，从400多个建设项目中，筛选出92个项目，并计划在10年内投入880亿元，用于相关交通基础设施建设。2023-07-24在20世纪60年代以前，运输规划通常以城市的机动车自然力调查（也称为起讫点调查）为基础，预测未来的机动车交通需求，进行道路规划；以定期月票利用者的站点间自然力调查等为基础预测将来的利用者数，进行轨道交通规划。20世纪60年代，在考虑未来的城市交通时，个体运输工具和大运量的运输工具之间的平衡，成了人们关注的焦点。人们逐渐认识到，解决大城市交通阻塞，仅仅通过对断面交通量采用某些局部数据进行运输分析、道路规划是远远不够的，必须以路线及道路网为对象进行全面分析。第一节运输规划理论与模型1运输规划的历史72023-07-248以定量数据为基础进行城市综合交通运输规划起源于美国，并且在世界范围内得到了迅速发展。1953年，美国大都市圈底特律首先开始进行交通调查。随之，则是称为“芝加哥范围运输学习”的芝加哥都市圈交通规划则对道路规划在内的四阶段交通需求预测法，开了城市综合运输规划的先河。1962年，美国制定的补充联邦道路法，进一步推动了“运输计划”在全美国的实施范围。在其他发达国家，如英国和日本，运输规划的理论和实践同样取得了很大的进展。改革开发以来，我国经济的高速发展、城市化进程加快和机动车辆保有量的迅猛增加，导致了交通运输需求的迅速增长，因此做好交通运输规划，对国民经济的持续快速发展极为重要。在我国，运输规划作为专门的应用学科已有20年的时间，大致经历三个阶段：2023-07-24运输规划在交通调查的基础上，对交通特征进行研究分析，将运输规划的四步模型理论与方法，交通预测技术应用到实际的道路运输规划中运输规划在方法上引进了发达国家的交通规划理论、计算机技术，开始探讨我国综合交通规划的理论与方法。运输规划人才素质的提高，市场需求加大，运输规划的基本原理、定量化预测技术等在各种类型的规划实践中得到了广泛的应用。1970-1980-1990-19801990now9三个阶段2023-07-242四步模型的基本概念运输规划的基本目的是为了改善客货流运输的条件。运输规划的实践集中在两个主要领域：城市和大都市区模型城市间货物和国家模型102023-07-24城市规划方法：112023-07-24运输窗口国外铁路智能运输系统研究现状所谓铁路智能运输系统，就是利用计算机技术、现代通信技术、现代信息处理技术、控制与系统技术、管理与决策支持技术和智能自动化技术等。实现信息采集、传输、处理和共享，通过高效利用与铁路运输相关的所有资源，以较低的成本达到保障安全、提高运输效率、改善经营管理和提高服务质量为目的新一代铁路运输系统。国外先进的铁路智能运输系统（RITS）主要包括欧洲的铁路运输系统（ERTMS）和日本的列车运行管理系统。前者优于后者。欧洲铁路运输管理系统的目标在于建立全欧洲铁路网统一的标准，保证各国列车在欧洲铁路网内的互通运营，并提高铁路运输管理水平。ERTMS的核心是欧洲列车控制系统（等等）和超速防护系统。日本从2000年初开始铁路（Cyber

Rail）的研究。Cyber

Rail是日本铁路系统发展的一个参考模型，是从智能运输系统的角度建立起通用的标准体系框架。目前Cyber

Rail正处于体系框架定义阶段。资料来源：贾利民，李平著，国外铁路智能运输系统研究现状122023-07-2413我国交通运输发展的长期目标是建立客运快速化和货运物流化的智能型综合交通运输体系，智能型综合交通运输体中的智能是以模型体系为核心的，其中现代化的规划方法和科学的决策体系是以规划模型和决策模型为基础的。2023-07-24四步模型由四个步骤组成：142023-07-24153四步模型的基本原理3.1交通量的生成根据所研究对象地区的特性直接求得生成交通量的步骤被称为交通量的生成（旅行产品）。2023-07-2416本文主要介绍两类方法：①增长率法②函数法所谓发生（或吸引）的交通量是指研究对象地区内由各运输小区内发生（或吸引）的交通量。而生成能力（包括产生和吸引）是土地利用和社会经济发展的函数。2023-07-24（1）增长率法（生长-因素模型）这种方法就是把现在的不同分区生成的交通量与到预测时点的增长率相乘从而求得各分区的交通生成量，即(7－1)(7－2)172023-07-24、 分别表示人口增加率，每人平均拥有自行车数量的增长率：即(7－3)(7—4)18这种方法的关键问题是如何确定增长率。通常可以用表示各运输小区活动的指标的增长率作为生成交通量的增长率。例如：2023-07-24(7－5)19对象地区外运输小区的生成交通量的增长率；对象地区外运输小区的常住人口的增长率；

对象地区内全体的常住人口的增长率。增长率法的最大优点是可以处理用原单位法和函数法都很难解决的问题。这就是，当我们进行区域的生成交通量预测时，研究对象地区外的预测也是必要的。这种时候，对于对象地区外的区域，通常只需要处理此区域与对象区域之间的交通。此类问题，通常采用增长率法.设定2023-07-24（2）函数模型法也被称为多元回归分析法（衰退分析）作为模型公式，多采用以下三个模型：(7－6)这里的 大多是表示运输小区的活动的人口指标202023-07-24213.2交通分布在交通的分布阶段，主要是预测交通生成量的来源和去向。在交通分布中最基本的概念是自然力表。O表示出发地（起点），D表示目的地（终点）。所谓交通量分布的预测是指给定发生交通量和吸引交通量，对于全部OD求i、j之间的分布的运输量。对运输量分布预测的方法主要分为两大类，即增长率法和构造模型法。下面对构造模型法中的重力模型法（重力模型）进行阐述。2023-07-24重力模型是模拟物理学中万有引力定律

而开发出来的运输分布模型。此模型假定i、j间的分布运输量与起点i发生的运输量与终点j吸引的运输量成正比，与两点之间的距离成反比。即(7－7)222023-07-24方式选择（形式的切分），某种方式的选择决定于运输成本、运输时间等因素，选择中最重要的特征是成本和时间（包括换

乘时间）。方式选择的模型很多，通常分为两大类。即集计模

型和非集计模型。非集计模型也叫个人选择模型（个人选择模

型），或分散选择模型（离散的(选择)模型）等。其中使用较多，又比较成熟的是非集计模型中的Logit模型。Logit模型的理论基础是数理统计理论与经济学理论。该模型中的许多参数必

须通过标定来完成。多项Logit模型（多项的Logit模型）的选择概率为：(7－9)233.3方式选择2023-07-2424路径分配（Assignment），根据路径上的不同成本、旅行时间函数进行分配。这一分配理论的基础是沃德罗普原理（1950年，欧洲），实际上是一种迭代分配法，什么时候路网平衡，就是分配完成。只介绍两种简单的路径分配方法①0-1分配法②增量分配法3.4路径分配2023-07-2425（1）0-1分配法0-1分配法，它有两个特点。第一个特点是不考虑拥挤对走行时间的影响，即认为所有

路段上的走行时间都是不随路段上交通流量

的大小而变化的常数；第二个特点是认为同

一组OD的所有驾驶员都选择完全相同的路线。因此，这种分配法的主要计算是寻找最短路

径。0-1分配法十分简单但却很近似。在道路稀少的偏远地区的交通量分配中可以采用这

种方法，一般城市道路网的交通量分配不宜

采用这种方法。2023-07-2426（2）增量分配法增量分配法（incrementalassignment

method）是一种近似平衡分配法。这种方法的基本思路是将OD运输量平分成若干等分，循环地分配每一等分的OD运输量到网络中。每一次循环分配一等分的OD交通量到相应的最短路径上，每循环分配一次重新计算并更新各路段的走行时间，然后按更新后的走行时间重新计算并更新各路段走行时间，然后按更新后的走行时间重新计算网络各OD间的最短路径。下一循环中按更新后的最短路径分配下一等分的OD运输量。2023-07-24运输窗口8-2美国未来的城市交通规划M.D.Muyer认为，在探讨美国的未来的城市交通规划，需要在下面十个领域进行研究，即：人口结构变化；经济与

市场的作用；多方式的交通规划；运输系统管理目标；强化

新技术的应用；新的社会团体意识；实行道路定价策略；加

强土地使用管理；交通的可持续发展；公众参与交通规划。在进行美国城市未来的交通规划的时候，必须考虑以下几条：在交通规划的不同阶段，决策者注重于不同因素的影响；在

未来的规划中，交通与环境的联系将会越来越紧密，轨道交

通将日益受到重视，规划也将越来越注重于对环境的影响；社会上不同的关注及需要将影响规划的进行；技术及环境还

会体现在今后对决策的评价中。272023-07-24284四步规划模型的应用在实际应用中，通常采用抽样调查的办法，并与发展政策、项目规划挂钩起来。这种方法通常被称为非完全矩阵法。非完全矩阵法不是将全部的交通流分配到路网上，与完全的现场

OD调查得到数据会有一个区别。事实上，不能所有的OD流都考虑进去，当然有些应该纳入进去而未被纳入的OD流，要单独处理。2023-07-2429在模型的应用过程中，通常把交通分成两大类:一部分称为经过模型的交通流另一部分称为未经模型的交通流纳入模型中的交通流通常用矩阵表示，用观测值导出现状

OD矩阵，预测OD矩阵通过推算求出。对一部分未经模型的交通流，按区段分别导出。简单的方法是，观测的交通流减去模型交通流就是未经模型的交通流，这意味着交通流矩阵外还要有许多其它的数据，如每一区段的总交通量，这些数据各运输管理部门都有，在每个区段上究竟有多少交通流量被模型化，这要做具体的研究，如所有的大宗货物运输要进模型，城市间的旅客运输要进入模型，市郊短途运输不纳入模型等等。在实践中要靠模型开发和应用专家在实际的应用过程中不断地总结。交通均衡分配理论30所谓交通分配就是将各种出行方式的OD矩阵按照一定的规则符合实际地分配到交通网络中的各条道路上，求出各路段上的流量及相关的交通指标，从而为交通网络的设计、评价等提供依据。交通分配问题中的一个关键点是假设出行者遵循什么样的行为原则。有两个广泛使用的原则，即Wardrop(1952)第一和第二原则。2023-07-24第一原则假定，所有出行者独立地作出令自己的行驶时间最2023-07-24小的决策，在所导致的网络流量分布状态里，同一OD对之间所有被使用的路径的时间是相等的，并小于或等于任何未被使用路径的时间。这样一种流量分布状态被称为用户均衡态，在这种状态下，没有人能够通过单方面改变自己的路径来达到降低自己时间的目的。第二原则假定，所有人的出行能够令网络总时间最小，即有一个中央组织者协调所有人的路径选择行为，所有出行者服从该组织的指挥，这样事项的流量分配状态称为系统最优。31运输规划的原则321．运输规划要符合国家长远规划运输业的规划，应在国家的发展规划指导下制订。交通运输建设规模和发展速度要适应经济和社会发展的需要，使运输能力的增长与经济和社会的运输需求保持着合理的比例关系；交通运输网的布局要适应工农业生产的布局、商业外贸布局、旅游布局以及人口分布的需要。2023-07-242．运输规划要符合国情33制订运输规划既要考虑国际惯例，也要符合中国国情。我国地势西高东低。东部和中部的经济、交通较发达；西部地域广阔，多为高原、大山，自然条件较差，交通不便，但资源丰富，极有发展前途。编制运输规划既要看到发展，也要考虑我国实际情况。对于资源密集的西部地区，运输规划应因地制宜采用大规模、大运量、低成本的运输方式，如水运、铁路水路联运、公路水路联运等。总之，编制运输规划应根据我国的具体情况，不宜贪大求全，要讲究经济效益，讲究实用。2023-07-243．运输规划要适应社会生产发展和市场需求发展生产，交通运输应先行。事实上，交通运输是构造和奠定市场经济体制的重要物质基础，是社会主义市场不可缺少的组成部分34，不发展运输市场，难以建设统一、有序、高效的全国市场体系。所以，编制运输规划，要注意适应社会生产的发展和市场要求。2023-07-244．运输规划要科学合理35运输规划是对未来运输的一种调控方式，应做到科学合理。具体来说，制订运输规划时既要考虑当前利益，也要考虑长远利益；既要考虑局部利益，也要考虑整体利益；既要考虑运输企业内部的利益，也要考虑与运输企业相关的各方面的利益；所采用的方法，应将定性与定量方法结合起来。2023-07-24运输规划的内容362023-07-24在交通运输业的发展中，运输网的发展占有十分重要的地位。因此，运输规划主要就是进行综合运输网的规划。进行综合运输网规划时，考虑的主要内容有：货流特点，包括货物的发点和到点，表现为货物的流量和流向；运输方式，就是在一定货流的条件下，可能采用的运输方式和运输工具；运输线路，在货物到发点之间可能有多条线路相通，通过不同的线路就使运输网有不同的布局，并使几种运输方式有不同的连接方式(4)运输技术装备，这是构成运输网规划方案的技术因素，对每一种运输方式来说，装备技术水平不同，它所形成的运输能力也不同37(5)营运组织特点，在一定的技术装备条件下采用不同的营运组织方式所表现出来的运输能力是不同的。2023-07-242023-07-2438第二节综合运输规划方法国外综合运输规划方法的发展综合运输方法的概念综合运输即多种运输方式综合协调发展，其规划就是确定综合运输发展目标，设计达到该目标的过程。前者主要包括运输需求预测，后者主要涉及运输供给方案的设计、评价和选择等。2023-07-24运输需求预测是运输物质设施需求预测的基础和关键。运输需求预测过程包括建模和预测两大部分。392023-07-241.2综合运输规划方法的发展402023-07-2441①解释城市土地利用和出行活动间关系的城市运输需求模型。②贝克曼（Beckmann,1955）等人的研究：将一般经济的需求和供给的微观形式用于运输中，很明确地构造出运输需求与供给间的平衡。随后，运输需求分析出现了两大发展：2023-07-2442运输需求分析的最新进展大量的概念和分析方法的应用①出行行为概念的采用。②被假定为一个有理性的人，并力求使其社会经济活动的效用最大化。确认旅行和运输决策中所包括的重要随机因素2023-07-24目前运输存在的主要问题包括：能源短缺环境影响公众参与社会公平2综合运输规划的一般步骤432023-07-24442023-07-24453综合运输规划的一般方法运输规划方法的主要类型地区运输规划方法一般分为三类：运输需求—标准法单一运输方式模拟－评价法多种运输方式模拟－评价法（综合运输规划法）2023-07-2446（1）运输需求－标准法当用这种方法时，要求制定适用于不同运输方式的标准，如网络结构设计和安全标准。然后对系统的未来状态进行预测。标准的状态和对未来的预测的状态间存在的任何差别被认为是“需求”。优点是简单易行。缺点是标准的选择不容易完成，运输方式间的关系无法确定，且用户和非用户的收益量不能直接测量。2023-07-2447制定地区运输规划，分4步完成：①是陈述规划的目标和任务。②是制定达到这些目标和任务的多种规划方案③是对现有的网络和规划方案所提出的未来的网络进行模拟④是对新制订的规划方案进行评价（2）单一运输方式模拟—评价法。2023-07-2448优点是可根据用户和非用户的目标来评价规划方案，可对该种运输方式直接进行处理，可对多种运输方式进行某种类型的评价。缺点是数据收集困难，执行比较困难。（2）单一运输方式模拟—评价法。2023-07-2449包含以下几个步骤：①对所有运输方式的客货运输需求量进行预测；②将预测的需求量分配给多种运输方式，然后进行网络模拟，并进行信息反馈，以考虑这种运输方式运量的分担率的变化（3）综合运输规划方法2023-07-2450（3）综合运输规划方法优点是在理想的情况下可对各种运输方式同时进行处理，因此，可大大提高网络的运营效率，并加强各种运输方式间的协调配合。缺点是其结构极端复杂，所需的数据量巨大，且这些数据不易收集。2023-07-2451综合运输规划方法一般包括5类模型：①出行需求、模拟和影响预测模型②经济、土地利用、经济活动布局模型③资源分配、财政政策和计划模型④分析和评价模型⑤观测（数据收集和监测）模型3.2综合运输规划方法的组成2023-07-24第三节货物运输需求预测1运输需求预测未来运输服务的预测运输需求预测设施需求的预测需求预测模型建模最常用的方法，是确定并说明变量和交通流量间的关系。522023-07-242运输需求的分析方法532023-07-24543货流的微观经济分析在这种方法中，货运需求分析的基本决策单位是潜在的运输用户。用这种方法分析货运需求时，一般将运输企业视为企业生产或销售过程的投入物之一。企业为了生产自己的产品或服务，可能需要运进某些类型的货物，因此，其本身变成运输的消费者。生产函数和成本函数运输需求函数2023-07-2455货物空间互动模型是一种聚类模型。在其最常用的场合下，这种方法是以重力模型的形式来实现的。在重力模型中，两区之间的货流量与其经济活动量的积函数成正比；与货物运输总成本的减函数成正比。除重力模型外，一些优化模型也属于此类。这些优化模型有两类,其主要区别是优化过程中所用的目标函数不同。4货物运输需求的空间互动模型2023-07-24(1)

重力模型56Black的重力模型的形式如下：(7－18)式中，——在i区生产并运到j区的货物k的总数量（吨）；——发自i区对货物k的总需求量；——阻抗系数（等于 ，其中 是i区和j区的欧氏距离，是经验指数值，该值可能随所分析的货类而变）。2023-07-24Mathematica模型数学表述如下：57(7－19)式中， ——运输方式m从i区到j区的货流量；——起点区和终点区的总产值；——工业特征指标；——从i区到j区的最小运输时间；——i区到j区的最低运输成本；——运输方式m的成本除以i区到j区的的最低运输成本——服务于i区和j区的运输方式数。2023-07-24(2)优化模型58设是i点的超额供给量，是j点的需求过大量。是i点和j点间单位货物的运输成本。用线性规划方程找出i点和j点间的货流量，并取运输总成本的最小值。(7－20)满足约束方式：(7－21)2023-07-245货物运输需求的宏观经济模型宏观经济模型力求解决部门间的货物和服务的流动问题。在运输需求分析中所用的宏观经济建模法有两种：①

经济法②

投入产出法592023-07-24将部门间的货物和服务流量记为。其中，i表示生产部门，j表示消费部门。任何经济部门的总产出由下式给出：60(7－22)式中，E是构成国民经济各部门的集合。2023-07-24式中，P表示国民经济中全部生产部门的集合；是对i部门产品的最终需求量； 是生产部门间的货流量。有可能通过一组简化的假设条件，来改进投入产出分析法。(7－23)612023-07-2462假设：（通过一组简化的假设条件，来改进投入产出分析法）每个部门生产一组同类产品，每类产品仅由一个部门生产。在一个部门内的全部企业采用十分相似的生产技术；这些技术完全可用一中等技术来代表。生产产品的总供给和总需求间可达到平衡。各部门的生产技术变化不快，因此，可假定在短时期内不变。2023-07-24对每两个部门来说，技术系统可定义为在j部门生产单位产品直接消耗i部门产品量。换言之：(7－24)也被称为直接消耗系数。将方程（10）和（11）联立得下面的方程：(7－25)632023-07-24上述方程也可用矩阵的记号更好表示为：X=AX+Y或

Y=(I－A)X

(7－26)式中，Y表示最终需求向量；X表示产出向量；A表示矩阵{

}，而I表示单位矩阵。假设（I－A）矩阵是非奇异矩阵，则方程（13）变换成能够根据给定（或预测）的最终需求预测产出的模型：(7－27)式中， 是（I－A）的逆阵，称为直接和间接消耗系数矩阵。该逆阵中的每一个元素，如 将给出i部门满足j部门一单位最终需求所需生产的产品量。于是，在i和j相同时，是直接消耗系数；在i和j不同时，

就是间接消耗系数。642023-07-24656.1

三次指数平滑法指数平滑法是根据历史资料的上期实际数和预测值，用指数加权法进行预测的一种方法，此法实质上是由加权移动平均法演变而来的。主要优点是适用所有实际问题和不需要特别大的信息量，并且能有效地解决货物性的运输需求预测问题6货物运输需求预测实用方法2023-07-24（1）运输需求预测模型的建立设有N个数据为最近N年运输需求量。取近N年的货物运输需求数据的加权平均值作为下一时期的货物运输需求量，即把参加计算的各年数据按时间的先后赋予不同的权数，且权数之和等于1。令其权数按几何级数排列(7－28)且(7－29)662023-07-24式中， 为第t周期的一次指数平滑值，其值就是t+1年货物运输需求的预测值；的货物运输量； 是平滑常数，0<为第t周期<1；r是公(7－30)(7－31)比，r=1— <1

所以整理得可见，指数平滑法预测的区间的货物运输需求值实际上等于最近几年的货物运输需求与原来估计值的不同比例之和。从（3－19）可知，取决于

和 ，而 是对第t年货物运输需求的预测误差。672023-07-24为了使预测结果更加准确和可靠，采用适用性广泛的三次指数平滑法。由（3－19）可以得到三次指数平滑估计值公式：(7－32)三次指数平滑预测模型具有以下形式：(7－33)式中， 表示基年为第t年，预测周期为T年的运输预测值；T表示预测周期；

，

， 均为平滑系数，其计算公式如下：(7－34)68(7－35)(7－36)2023-07-24用三次指数平滑法进行预测时，必须首先估算初始值

，

， 。其数据较多，初始值可以用货物运输的初始值 代替。这是因为当数据点多时，初始值对预测的影响极小。若数据较少，则由于初始值有相当大的权重，因此需要采用一定的方法对初始值进行合理的估算。（2）货物运输需求初始值的估算692023-07-24706.2

逐步回归在货物运输需求预测中的应用回归分析是研究各种变量相关关系的一种数学工具。一般来说，社会经济系统中的各种变量之间的关系多为非确定性关系。交通运输中的交通量与国民经济增长和人口增长的关系就是属于非确定性关系，因此回归分析在这一领域中运用极为广泛。2023-07-24第四节物流运输优化方法数学规划求解方法与应用实际最优点搜索方法简单地说，最优化问题就是在可行空间中找出一个点，使目标函数f(x)达到最大或最小值。即对于连续可微函数，可以微分计算法求得最优值。但是在很多情况下，难以满足这种要求，则可以通过使用搜索方法求得最优值。712023-07-2472(1)

穷举搜索顾名思义，穷举搜索就是将自变量全部列举出来。如果自变量个数有限，则可计算出有限个点的函

数值，比较之后，取最优值。(2)

序贯搜索穷举法事先确定自变量的取值，然后计算对应

的函数值。序贯搜索方法则不能事先确定自变

量的取值，自变量的取值顺序取决于前几次计

算的函数值。序贯搜索要求函数f(x)在货物[a,b]上呈单峰性质，即函数在[a,b]上只有一个极值。2023-07-24序贯搜索方法有很多种，如两分搜索、等区间多点搜索、黄金分割搜索和Fibonacci搜索等。732023-07-2474图上作业法对于比较简单的物资调运问题，可以用图上作业法或表上作业法求解，这里只介绍图上作业法。这种方法可把运输网络转化成树型结构，便于建立运输网络数据库，从而进一步进行路线规划和车辆调度。运输浪费运输力的不合理现象有两种对流现象迂回运输2数学规划的优化方法实际应用2023-07-24752023-07-24762023-07-24772023-07-2478第一步：在每个回路中，去掉一段路线，变成不含回路的情况，按上述方法作出调运方案第二步：检查有无迂回现象。分别检查每个回路，如果圈内和圈外流向的总长度都不超过回路总长度的一半，那么，这个回路上就没有迂回现象了，这个方案就是最优方案。否则转第三步第三步：改变原来的去段和破圈方式，转第二步运输道路中含有回路，可以分三步寻求最优方案2023-07-24792.2车辆路线安排问题（VRP）概述车辆路线安排问题（VRP，Vehicle

RoutingProblem）是指对物流配送的车辆进行优化调度。在VRP问题中最常见的约束条件有：容量约束优先约束车型约束时间约束相容性约束➢…….2023-07-24大多数模型都可以看成是下面三个模型的变形与组合：以车流为基础的模型以物流为基础的模型聚覆盖模型2.2.2

VRP问题的模型及算法802023-07-24精确式算法一般运用线性规划和非线性规划等数学规划技术，以便求得问题的最优解。精确式算法一般有以下几种方法：分枝定界法割平面法网络流算法动态规划方法精确式算法812023-07-2482为了克服精确优化方法的不足，可以运

用一些经验法则来降低优化模型的数学精度，并通过模仿人的跟踪校正过程来求取运输问

题的满意解。启发式算法：启发式算法中最具有代表性的就是克拉克（Clarke）和怀特（Wright）提出的节约法(Saving

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

Path）是运输路径计划优化中一类最基本的问题。其中常见的是带权图的

最短路径问题，即求两个顶点间长度最短的路径。

其中：路径长度不是指路径上边数的总和，而是指

路径上各边的权值总和。路径长度的的具体含义取

决于边上权值所代表的意义由于交通网络存在有向

性，所以一般以有向网络表示交通网络。最短路径不仅仅指一般地理意义上的距离最短，还可以引申到其他的度量，如时间、费用、线路容量等。但是，无论是距离最短、时间最快还是费用最低，它们的核心算法都是最短路径算法。经典的最短路径算法——Dijkstra算法是目前多数系统解决最短路径问题采用的理论基础，只是不同系统对Dijkstra算法采用了不同的实现方法。2023-07-24旅行商问题(TSP，TRAVELING

SALESMANPROBLEM)86是运筹学、图论和组合优化中的著名问题，在实际生活中有着广泛的应用前景。TSP不仅可以解

决最优巡回路线等类TSP问题，在交通车辆巡回、学校教师课程计划安排、工厂装配线进度管理以及民航机组人员轮班等问题上也有着广泛的应用前景。TSP问题一般可以描述如下:一个旅行者从出发地

出发，经过所有要到达的城市后，返回到出发地。要求合理安排其旅行路线，使得总旅行距离(或旅行费用、旅行时间等)最短。在处理现实生活中的具体问题时，可以对TSP附加一些限制性条件，例如在模型中假设该旅行者的时间有限，进而添加相应的时间约束等，从而衍生出许多和TSP相关的问题。2023-07-24VRP和PDP问题87车辆路线安排问题(VRP，Vehicle

Routing

Problem)是对进行物流配送的车辆进行优化调度。该问题一般可以描述如下:对一系列装货点或(和)卸货点，组织适当合理的行车路线，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、发送量，交发货时间，车辆容量、数目限制，车辆行驶里程、时间限制等)下，达到一定的目标(如最短路程、最小费用、最短时间、最少车辆等)PDP问题（Pickupand

Delivery

Problem,装卸货问题，以下简称PDP问题）。PDP问题是VRP问题在现实中的演化，与VRP不同的是，PDP不仅仅是在所要求的目的地完成一次访问（对于VRP问题来讲，这种访问就是进行一次送货或者取货服务，送货和取货任务不同时发生在同一点上），同时需要完成送货和取货两种作业任务。这样一来PDP问题较之VRP更加复杂，对于车辆容量限制条件的考虑也更加难以确定2023-07-24精确式算法及其应用的局限性88TSP、VRP、PDP等系列问题属于组合优化领域著名的NP难题。其求解方法一般相当复杂，通常的做法是应用相关技术将问题分解或者转化为一个或者多个已经研究过的基本问题，再使用相对比较成熟的基本理论和方法进行求解，以求得原运输车辆调度问题的最优解或满意解精确式算法一般运用线性规划(包括经过了专门处理的分枝定界法、割平面方法和标号法)和非线性规划等数学规划技术，以便求得问题的最优解。精确式算法一般有以下几种方法:①分枝定界法(Branch

and

Bound Approach)；②割平面法(Cutting

Planes

Approach)；③网络流算法

(Network

Flow

Approach)；④动态规划方法(Dynamic

Programming Approach)等。精确算法随着运输系统的复杂和调度目标的增加，其计算 量呈指数递增，使得获取整个系统的精确最优解越来越困难，而用计算 机求解大型优化问题的时间和费用又太大，因此，此类优化方法和算法 现在一般仅用于求解运输调度的局部优化问题。2023-07-24启发式算法89为了克服精确优化方法的不足，可以运用一些经验法则来降低优化模型的数学精确程度，并通过模仿人的跟踪校正过程来求取运输系统的满意解。启发式算法能同时满足详细描绘和求解问题的需要，较精确式算法更加实用。现在比较成熟的启发式算法很多，它们的区别主要在于求解过程的收敛速度和收敛程度不同。按照这个标准，可以分为四类：构造算法两阶段算法不完全优化算法改进算法2023-07-24商用车辆装载优化90本部分讨论企业物流日常运作中经常碰到的运输车