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

5.1物流运输系统概述,运输是指用设备和工具，将物品从某一地点向另一地点运送的物流活动。其中包括集货、分配、搬运、中转、装卸、分散等一系列操作。物流运输系统的组成运输基础设施，如货场、道路、桥梁、信号、隧道、公路、河道和码头等；运输设备，如集装箱、汽车、牵引机车、拖车、飞机和船只等；运输工作人员，如装卸人员、维修人员、操作人员及其他管理人员等。,5.1.1物流运输系统的功能货物的空间移动货物的短期储存5.1.2物流运输系统的特点物流运输系统是一个连续性的过程系统物流运输系统生产的多环节、多功能等特点物流运输系统生产具有网络特性物流运输系统是一个动态系统,5.1.3物流运输系统的结构并联结构串联结构串并联结合的网络型结构,1）规划原则经济发展原则协调发展原则局部服从整体原则近期与远期相结合原则需要与可能相结合原则理论与实践相结合原则,5.1.4物流运输系统规划,运输业务模式的选择运输方式的选择运输批量和运输时间的确定运输线路的规划与选择运输流量的分析车输的配载与调度问题,2）物流运输系统规划的内容,5.1.5现代交通运输系统的发展1、现代科学技术进步的支持作用运输设备和运载工具的发展，直接表现为运输供给能力的增长和运输服务水平的提高，依赖于现代科学技术进步的支持。现代科技进步，突出表现在高速、重载、安全、信息和复杂系统规划管理最优化五个技术领域对交通运输技术进步的支持。,现代交通运输系统发展的根本原因，是经济和社会发展，特别是市场经济发展对运输多样化需求的带动，有力地促进运输需求特征的发展和演变。而全球经济一体化的进程，进一步加速世界经济的运输化。,2、社会发展和市场经济的促进作用,可持续发展是当代新的发展观，是以新的人文理念对传统的生产方式、消费方式和思维方式的审视和扬弃，是从长远发展的角度对人类自身的生存和发展与资源、环境和生态等自然关系的正反历史经验的总结。交通运输系统的规划、建设、运营和发展，理所当然地必须顺应可持续发展的要求。,3、经济和社会可持续发展要求的开拓作用,一体化交通运输（Integratedtransportation）是指交通运输与整个经济社会发展的进一步融合。包括：1.运输方式内部及运输方式之间的一体化；2.运输与能源环境的一体化；3.运输与土地利用规划的一体化；4.运输与国家、社会安全的一体化；5.运输与教育、健康和财富创造政策的一体化。,一体化交通运输,国际通达（INTERNATIONNALINREACH）;多式联运（INTERMODALINFORM）；智能运输（INTELLIGENTINCHARACTER）；全面服务（INCLUSIVEINSERVICE）；创新视野（INNOVATIVEINSCOPE）.,面向21世纪的一体化交通运输建设目标,5.2运输系统经济理论与模型,运输需求是一种由其他经济或社会活动派生出来的需求，运输需求函数（或曲线）在理论上可以通过商品产地的供给函数和销售地的需求函数（或曲线）推导出来。但现实中，在多个商品产地和销地并存而且有多种可替代运输方式的情况下，运输需求以及运输市场上的供求均衡都会呈现十分复杂的状态。,固定费用与运输业绩无关各种基本设施的支出、装备、管理投资利息等。可变费用随交通量的变化而变化设备维修、运营等费用。,课节回顾,运输系统结构现代运输系统特征,运输营业成本包括载运工具燃料消耗和行车司乘人员工资等。,Ctot=Ccap+CopCtot运输总成本Ccap资产费用Cop运营费用,5.2.1运输费用模型,Ccap=Cfac+CequipCfac基础设施费用Cequip载运工具费用,Cop=CFM+CEM+Ctrans+Ctraf+CgenCFM固定设施维修费用CEM载运工具维修费用Ctrans运输费用Ctraf交通费用Cgen其他费用,5.2.2运价率基于重量的运价率基于距离的运价率基于运输需求的运价率合同运价率干线运输运价率其他特殊的运价率,课节回顾,运输系统结构物流运输系统规划和设计的内容,运输业务模式的选择运输方式的选择运输批量和运输时间的确定运输线路的规划与选择运输流量的分析车输的配载与调度问题,启发式算法特点禁忌搜索算法原理及步骤模拟退火算法原理及步骤遗传算法原理及步骤,5.3现代优化算法,本节重点：,5.3.1现代优化算法概述,传统的优化方法（？）,以数量分析为基础，以寻找系统最大限度地满足特定活动目标要求的方案为目的，帮助决策者或决策计算机构对其所控制的活动实现优化决策的应用性理论。,（牛顿法、运筹学方法）,现代优化方法,（启发式算法）,1）组合最优化问题通过对数学方法研究寻找离散事件的最优编排、分组、次序或筛选等（从有限个状态选取最好的，其最优解是某一种方案）。,Minf(x)g(x)0 xD,X*为最优解,2）启发式算法,基于直观或经验构造的算法，在可以接受的花费下给出待解决组合优化问题实例的可行解，该可行解和最优解的偏离程度不一定事先可以预计。,不考虑所求可行解与最优解的偏离程度，只要达到预期目标即可。,（1）与导数无关性在搜索使一个给定目标函数最小或者最大化的一组参数时，这些方法不需要函数的导数信息。相反，它们只依赖于对目标函数的重复求值运算，而且在每一次求值后的搜索方向遵循某种启发式的思路。（2）直观的思路这些搜索过程所遵循的思路通常建立在简单而直观的概念基础上。其中的一些概念是由所谓的自然界的智慧所促使，比如热力学和进化。,3）启发式算法的特点,（3）速度慢对于连续优化问题，这些方法由于不应用导数，一般比基于导数的优化方法速度慢。（4）灵活性不用导数意味着对目标函数的可微和可导性质没有要求，因此可以使用复杂的目标函数。,（5）随机性所有的启发式优化算法都是随机的。理论上讲，启发式优化算法的随机性保证了在给定计算时间内得到最优解的概率非零。然而实际上，为了得到给定问题的最优解，往往花费非常可观的计算时间。（6）难以解析难于对启发式优化算法进行解析研究，主要是因为其随机性。,（7）迭代性质所有的启发式优化算法在本质上都是迭代方法，因此需要某种停止判据来决定何时终止优化过程。常用的停止判据包括计算时间：达到了制定的计算时间、函数求值次数或者迭代次数。优化目标：目标函数值达到某个预定的目标值。最小改进量：相邻两次迭代目标函数差小于某个预定值。相对最小改进量：相邻两次迭代目标函数之差的某一数学变形小于某个预定值。,例：现有一个连通图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：SDN（S）2D2D于表示D的所有子集组成的集合，则N（S）称为S的邻域。SN（S）称为S的一个邻居。,局部最小（最大）解：f(s*)()f(s),sDN（S*）,全局最小（最大）解：f(s*)()f(s),sD,1）禁忌对象、长度和侯选集合,解的简单变化：xy向量分量的变化：（x1,xixn)（x1,yixn)目标值的变化：xH(a)yH(b),（1）禁忌对象禁忌表中被禁的变化元素。,（2）禁忌长度被禁对象不允许超过的迭代次数。tabu(x)=t；每迭代一步，tabu(x)=t-1，直到tabu(x)=0。t的选取有以下几种情况：t为常数t(tmin,tmax),t可变化，其变化依据被禁对象的目标值和邻域结构。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)random(0,1),则xi=xj;重复）。）tk+1=d(tk);k=k+1;若满足终止条件，终止计算，否则回到）。,1）算法步骤,2）主要问题（1）温度T的初始值设置问题温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一。初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。,（2）退火速度问题模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索(退火)是相当必要的，但这需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。,（3）温度管理问题温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式：T(t+1)kT(t),式中k为正的略小于1.00的常数，t为降温的次数。,课节回顾,启发式算法禁忌算法模拟退火算法,5.3.4遗传算法,1）遗传算法的生物学基础借用生物学优胜劣汰、适者生存的规律。,进化发生在编码上。自然选择那些染色体产生超过平均数的后代。子女保持父母的特征变异会造成子代和父代的不同。,生成+检测的迭代搜索算法。编码初始群体生成适应度评估选择交叉变异,2）遗传算法的基本要素,3）算法步骤（1）选择问题的一个编码，给出一个有N个染色体的初始群体pop(t):t=1；（2）对群体中的每个染色体计算它的适应函数fi；（3）若停止规则满足，则算法停止；否则，计算概率pi，以此概率随机选择一些染色体作为一个种群。（4）以pc的结合概率得到一个有个染色体的群体crosspop(t+1)（5）以一个较小的概率p，使得一个染色体的一个基因发生变异，形成mutpop(t+1)，取新的种群pop(t+1)mutpop(t+1)，返回（2）。,）实现的技术问题（1）编码（）评价遗传算法的常用方法（）初始参数的选取和停止原则。（）进化过程中的技术问题。,思考题：启发式算法的应用案例,5.4.1各种运输方式的特点选择运输方式时应考虑：服务的频率、速度、中转时间、中转时间的波动性、费用、可利用性、安全、准确和顾客服务。,5.4运输方式的选择,铁路运输公路运输水路运输航空运输管道运输多式联运,货品特性运输速度和运距运输容量运输成本运输质量环境保护,5.4.2运输方式选择的考虑因素,）因素分析法模型（j)=S(i,j)（j)第j种运输工具的总分。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点点间运输例:如图所示为单行线交通网络，用Dijkstra算法中点到点的最短路。,5.5路径的选择,5.5.2多点间运输表上作业法,单回路运输问题时指在路线优化中，设存在节点集D，选择一条合适的路径遍历所有的节点，并且要求闭合。最近邻点法最近邻点法算法十分简单，但是得到的解并不十分理想，有很大的改善余地。由于该算法计算快捷，但精度低，可以作为进一步优化的初始解。最近邻点法可以由四步完成：1）从零点开始，作为整个回路的起点。2）找到离刚刚加入到回路的上一顶点最近的一个顶点，并将其加入到回路中。3）重复第二步，直到所有顶点都加入到回路中。4）将最后一个加入的顶点和起点连接起来。这样就构成了一个TSP问题的解。,5.5.3单回路运输TSP模型及求解,例：现有一个连通图A=6,它们的距离矩阵如表所示，他们的相对位置如图所示，假设,两点之间的距离时对称的。,D=6+4+6+7+6+9=38,5