2011物流系统规划与设计(5)-运输系统规划与设计.ppt

1、5.1 物流运输系统概述,运输是指用设备和工具，将物品从某一地点向另一地点运送的物流活动。其中包括集货、分配、搬运、中转、装卸、分散等一系列操作。 物流运输系统的组成 运输基础设施，如货场、道路、桥梁、信号、隧道、公路、河道和码头等； 运输设备，如集装箱、汽车、牵引机车、拖车、飞机和船只等； 运输工作人员，如装卸人员、维修人员、操作人员及其他管理人员等。,5.1.1 物流运输系统的功能 货物的空间移动 货物的短期储存 5.1.2 物流运输系统的特点 物流运输系统是一个连续性的过程系统 物流运输系统生产的多环节、多功能等特点 物流运输系统生产具有网络特性 物流运输系统是一个动态系统,5.1.3

2、物流运输系统的结构 并联结构 串联结构 串并联结合的网络型结构,1）规划原则 经济发展原则 协调发展原则 局部服从整体原则 近期与远期相结合原则 需要与可能相结合原则 理论与实践相结合原则,5.1.4 物流运输系统规划,运输业务模式的选择 运输方式的选择 运输批量和运输时间的确定 运输线路的规划与选择 运输流量的分析 车输的配载与调度问题,2）物流运输系统规划的内容,5.1.5 现代交通运输系统的发展 1、现代科学技术进步的支持作用 运输设备和运载工具的发展，直接表现为运输供给能力的增长和运输服务水平的提高，依赖于现代科学技术进步的支持。 现代科技进步，突出表现在高速、重载、安全、信息和复杂系

3、统规划管理最优化五个技术领域对交通运输技术进步的支持。,现代交通运输系统发展的根本原因，是经济和社会发展，特别是市场经济发展对运输多样化需求的带动，有力地促进运输需求特征的发展和演变。而全球经济一体化的进程，进一步加速世界经济的运输化。,2、社会发展和市场经济的促进作用,可持续发展是当代新的发展观，是以新的人文理念对传统的生产方式、消费方式和思维方式的审视和扬弃，是从长远发展的角度对人类自身的生存和发展与资源、环境和生态等自然关系的正反历史经验的总结。 交通运输系统的规划、建设、运营和发展，理所当然地必须顺应可持续发展的要求。,3、经济和社会可持续发展要求的开拓作用,一体化交通运输（Integ

4、rated transportation）是指交通运输与整个经济社会发展的进一步融合。包括： 1.运输方式内部及运输方式之间的一体化； 2. 运输与能源环境的一体化； 3.运输与土地利用规划的一体化； 4.运输与国家、社会安全的一体化； 5.运输与教育、健康和财富创造政策的一体化。, 一体化交通运输,国际通达（INTERNATIONNAL IN REACH）; 多式联运（INTERMODAL IN FORM）； 智能运输（INTELLIGENT IN CHARACTER）； 全面服务（INCLUSIVE IN SERVICE）； 创新视野（INNOVATIVE IN SCOPE）.,面向21世

5、纪的一体化交通运输建设目标,5.2 运输系统经济理论与模型,运输需求是一种由其他经济或社会活动派生出来的需求，运输需求函数（或曲线）在理论上可以通过商品产地的供给函数和销售地的需求函数（或曲线）推导出来。但现实中，在多个商品产地和销地并存而且有多种可替代运输方式的情况下，运输需求以及运输市场上的供求均衡都会呈现十分复杂的状态。, 固定费用与运输业绩无关 各种基本设施的支出、装备、管理投资利息等。 可变费用随交通量的变化而变化 设备维修、运营等费用。,课 节 回 顾,运输系统结构 现代运输系统特征,运输营业成本包括载运工具燃料消耗和行车司乘人员工资等。,Ctot=Ccap+Cop Ctot运输总

6、成本 Ccap 资产费用 Cop运营费用,5.2.1 运输费用模型,Ccap=Cfac+Cequip Cfac 基础设施费用 Cequip载运工具费用,Cop=CFM+CEM +Ctrans +Ctraf +Cgen CFM 固定设施维修费用 CEM载运工具维修费用 Ctrans 运输费用 Ctraf 交通费用 Cgen 其他费用,5.2.2 运价率 基于重量的运价率 基于距离的运价率 基于运输需求的运价率 合同运价率 干线运输运价率 其他特殊的运价率,课 节 回 顾,运输系统结构 物流运输系统规划和设计的内容,运输业务模式的选择 运输方式的选择 运输批量和运输时间的确定 运输线路的规划与选择

7、 运输流量的分析 车输的配载与调度问题, 启发式算法特点 禁忌搜索算法原理及步骤 模拟退火算法原理及步骤 遗传算法原理及步骤,5.3 现代优化算法,本节重点：,5.3.1 现代优化算法概述,传统的优化方法（？）,以数量分析为基础，以寻找系统最大限度地满足特定活动目标要求的方案为目的，帮助决策者或决策计算机构对其所控制的活动实现优化决策的应用性理论。,（牛顿法、运筹学方法）,现代优化方法,（启发式算法）,1）组合最优化问题 通过对数学方法研究寻找离散事件的最优编排、分组、次序或筛选等（从有限个状态选取最好的，其最优解是某一种方案）。,Min f(x) g(x) 0 x D,X*为最优解,2）启发

8、式算法,基于直观或经验构造的算法，在可以接受的花费下给出待解决组合优化问题实例的可行解，该可行解和最优解的偏离程度不一定事先可以预计。,不考虑所求可行解与最优解的偏离程度，只要达到预期目标即可。,（1）与导数无关性 在搜索使一个给定目标函数最小或者最大化的一组参数时，这些方法不需要函数的导数信息。相反，它们只依赖于对目标函数的重复求值运算，而且在每一次求值后的搜索方向遵循某种启发式的思路。 （2）直观的思路 这些搜索过程所遵循的思路通常建立在简单而直观的概念基础上。其中的一些概念是由所谓的自然界的智慧所促使，比如热力学和进化。,3）启发式算法的特点,（3）速度慢 对于连续优化问题，这些方法由于

9、不应用导数，一般比基于导数的优化方法速度慢。 （4）灵活性 不用导数意味着对目标函数的可微和可导性质没有要求，因此可以使用复杂的目标函数。,（5）随机性 所有的启发式优化算法都是随机的。理论上讲，启发式优化算法的随机性保证了在给定计算时间内得到最优解的概率非零。然而实际上，为了得到给定问题的最优解，往往花费非常可观的计算时间。 （6）难以解析 难于对启发式优化算法进行解析研究，主要是因为其随机性。,（7）迭代性质 所有的启发式优化算法在本质上都是迭代方法，因此需要某种停止判据来决定何时终止优化过程。常用的停止判据包括 计算时间：达到了制定的计算时间、函数求值次数或者迭代次数。 优化目标：目标函

10、数值达到某个预定的目标值。 最小改进量：相邻两次迭代目标函数差小于某个预定值。 相对最小改进量：相邻两次迭代目标函数之差的某一数学变形小于某个预定值。,例：现有一个连通图A=6，各点之间距离矩阵如表所示，相对位置如图1所示，假设两点之间的距离是对称的，求单回路运输问题。,D=6+4+6+7+6+9=38,用禁忌表记录下已经达到过的局部最优点，禁止重复工作。,局部搜索算法 1）Xbest=X0,P=N(Xbest) 2)若P= ，停止计算。否则继续搜索。,5.3.2 禁忌搜索算法,原理, 邻域概念 对于组合优化问题（D，F，f), D上的一个映射： N：S D N（S）2D 2D于表示D的所有子

11、集组成的集合，则N（S）称为S的邻域。 S N（S）称为S的一个邻居。,局部最小（最大）解： f(s*) () f(s),s D N（S*）,全局最小（最大）解： f(s*) () f(s),s D,1）禁忌对象、长度和侯选集合,解的简单变化：x y 向量分量的变化：（x1,xixn) （x1,yixn) 目标值的变化： x H(a) y H(b),（1）禁忌对象禁忌表中被禁的变化元素。,（2）禁忌长度被禁对象不允许超过的迭代次数。 tabu(x)=t； 每迭代一步， tabu(x)=t-1，直到tabu(x)=0。 t的选取有以下几种情况： t为常数 t (tmin,tmax),t可变化，其

12、变化依据被禁对象的目标值和邻域结构。 t (tmin,tmax), tmin,tmax动态选取。 t过短会造成循环出现，过长会造成计算时间增长。,（3）候选集合的确定 全部邻域中的邻居。 部分邻域中的邻居。 随机选取部分邻居。,2）评价函数,候选集合的元素通过评价函数值来选取。 （1）基于目标函数的评价函数 p(x)=f(x) p(x)=f(x)- f(xnow) p(x)=f(x)- f(xbest) （2）其他函数 替代函数为了减少计算的复杂性。,3）特赦规则,（1）基于评价值的规则: c(xnow) c(xbest) （2）基于最小错误的规则:所有对象均被禁时，选取一个评价值最小的状态解

13、禁。 （3）基于影响力的规则:关注影响力大的变化。,4）记忆频率信息 记忆解集合、有序被禁对象组、目标值集合等出现频率。 （1）静态频率信息：解、对换或目标值出现的频率。 （2）动态频率信息：一个解、对换或目标值变化的趋势。,5）终止规则,确定步数终止； 频率控制终止； 目标值变化原则； 目标值偏离程度规则。,（1）随机产生初始解x，置禁忌表为空。 （2）判断算法终止条件是否满足？若是，则结束算法并输出优化结果；否则，继续以下步骤。 （3）利用当前解的邻域函数产生所有（或若干）邻域解，并从中确定若干候选解。 （4）对候选解判断特赦准则是否满足？若成立，则用满足特赦准则的最佳状态y替代x成为新的

14、当前解，即x=y，并用与y对应的禁忌对象替换最早进入禁忌表的禁忌对象，同时用y替换“best”状态，然后转步骤6；否则，继续以下步骤。 （5）判断候选解对应的各对象的禁忌属性，选择候选解集中非禁忌对象对应的最佳状态为新的当前解，同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象元素。 （6）转步骤（2）。,6）算法步骤,课堂讨论,一种求解车辆路径问题的禁忌算法探究,5.3.3 模拟退火算法,模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。,

15、根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-E/(kT)，其中E为温度T时的内能，E为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解计算目标函数差接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解。,退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子t、每个t值时的迭代次数L和停止条件S。,1）任选初始解x0: xi=x0;k=0;t0=tmax 2

16、）若在该温度达到内循环停止条件，则转至）； 否则，从邻域（xi)中随机选择xj， fij=f(xj)-f(xi);若 fij 0,则xi=xj，否则若exp(- fij/tk)random(0,1), 则xi=xj;重复）。 ）tk+1=d(tk);k=k+1;若满足终止条件，终止计算，否则回到）。,1）算法步骤,2）主要问题 （1） 温度T的初始值设置问题温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一。初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次

17、调整。,（2）退火速度问题 模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索(退火)是相当必要的，但这需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。,（3）温度管理问题 温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式： T(t+1)kT(t), 式中k为正的略小于1.00的常数，t为降温的次数。,课 节 回 顾, 启发式算法 禁忌算法 模拟退火算法,5.3.4 遗传算法,1）遗传算法的生物学基础 借用生物学优胜劣汰、适者生存的规律。,进化发生在编码上。

18、 自然选择那些染色体产生超过平均数的后代。 子女保持父母的特征 变异会造成子代和父代的不同。,生成+检测的迭代搜索算法。 编码 初始群体生成 适应度评估 选择 交叉 变异,2）遗传算法的基本要素,3）算法步骤 （1）选择问题的一个编码，给出一个有N个染色体的初始群体pop(t) :t=1； （2）对群体中的每个染色体计算它的适应函数fi； （3）若停止规则满足，则算法停止；否则，计算概率pi，以此概率随机选择一些染色体作为一个种群。 （4）以pc的结合概率得到一个有个染色体的群体crosspop(t+1) （5）以一个较小的概率p，使得一个染色体的一个基因发生变异，形成mutpop(t+1)，

19、取新的种群pop(t+1) mutpop(t+1)，返回（2）。,）实现的技术问题 （1）编码 （）评价遗传算法的常用方法 （）初始参数的选取和停止原则。 （）进化过程中的技术问题。,思考题：启发式算法的应用案例,5.4.1 各种运输方式的特点 选择运输方式时应考虑：服务的频率、速度、中转时间、中转时间的波动性、费用、可利用性、安全、准确和顾客服务。,5.4运输方式的选择,铁路运输 公路运输 水路运输 航空运输 管道运输 多式联运,货品特性 运输速度和运距 运输容量 运输成本 运输质量 环境保护,5.4.2 运输方式选择的考虑因素,）因素分析法模型 （j)=S(i,j) （j)第j种运输工具的

20、总分。 S(i，j)标尺i对运输工具j的分数。 n准则总数目。,5.4.3 运输方式选择模型,例1：某公司对货品A的运输有公路、铁路、航空三种运输方式可以选择，根据货品特性、数量、运距和到达要求等对各运输方式的评分如表，求取应该选择的运输方式。,用因素评价法评分： =6+7+8+8+8=37； =7+8+7+7+7=36； =8+6+6+8+6=34 因此，按照评分结果选择公路运输方式。,（j)=W(i)S(i,j) （j)第j种运输工具的总分。 W(i)因素i的权重。 S(i,j)标尺i对运输工具j的分数。 n准则总数目。,）权重因素分析法模型,3）层次分析法模型,1.结构：分析体系结构，列出模型结构组织图； 2.函数：使用数学语言把规划模型函数化； 3.推算：规划评价函数的计算过程和步骤； 4.结论：根据规划的最优综合评价函数得出结论 。,4）多式联运运输方式选择模型,见教材例题P111.,5.5.1 点点间运输 例: 如