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

20112011物流系统规物流系统规划与设计划与设计(5)-(5)-运运输系统规划与设输系统规划与设计计5.1.1 物流运输系统的功能物流运输系统的功能 l货物的空间移动 l货物的短期储存5.1.2 物流运输系统的特点物流运输系统的特点 l物流运输系统是一个连续性的过程系统 l物流运输系统生产的多环节、多功能等特点 l物流运输系统生产具有网络特性 l物流运输系统是一个动态系统 5.1.3 物流运输系统的结构物流运输系统的结构 l并联结构并联结构 l串联结构串联结构 l串并联结合的网络型结构串并联结合的网络型结构 1）规划原则）规划原则 经济发展原则经济发展原则 协调发展原则协调发展原则 局部服从整体原则局部服从整体原则 近期与远期相结合原则近期与远期相结合原则 需要与可能相结合原则需要与可能相结合原则 理论与实践相结合原则理论与实践相结合原则5.1.4 物流运输系统规划物流运输系统规划 u运输业务模式的选择运输业务模式的选择 u运输方式的选择运输方式的选择u运输批量和运输时间的确定运输批量和运输时间的确定u运输线路的规划与选择运输线路的规划与选择 u运输流量的分析运输流量的分析 u车输的配载与调度问题车输的配载与调度问题 2）物流运输系统规划的内容）物流运输系统规划的内容5.1.5 现代交通运输系统的发展现代交通运输系统的发展1 1、现代科学技术进步的支持作用、现代科学技术进步的支持作用n运运输输设设备备和和运运载载工工具具的的发发展展，直直接接表表现现为为运运输输供供给给能能力力的的增增长长和和运运输输服服务务水水平平的的提提高高，依依赖赖于于现现代代科科学技术进步的支持。学技术进步的支持。n现现代代科科技技进进步步，突突出出表表现现在在高高速速、重重载载、安安全全、信信息息和和复复杂杂系系统统规规划划管管理理最最优优化化五五个个技技术术领领域域对对交交通通运输技术进步的支持。运输技术进步的支持。现现代代交交通通运运输输系系统统发发展展的的根根本本原原因因，是是经经济济和和社社会会发发展展，特特别别是是市市场场经经济济发发展展对对运运输输多多样样化化需需求求的的带带动动，有有力力地地促促进进运运输输需需求求特特征征的的发发展展和和演演变变。而而全全球球经经济济一一体体化化的的进进程程，进进一一步步加加速速世世界经济的运输化。界经济的运输化。2、社会发展和市场经济的促进作用、社会发展和市场经济的促进作用n可可持持续续发发展展是是当当代代新新的的发发展展观观，是是以以新新的的人人文文理理念念对对传传统统的的生生产产方方式式、消消费费方方式式和和思思维维方方式式的的审审视视和和扬扬弃弃，是是从从长长远远发发展展的的角角度度对对人人类类自自身身的的生生存存和和发发展展与与资资源源、环环境境和和生生态态等等自自然然关关系系的的正正反反历史经验的总结。历史经验的总结。n交交通通运运输输系系统统的的规规划划、建建设设、运运营营和和发发展展，理理所所当然地必须顺应可持续发展的要求。当然地必须顺应可持续发展的要求。3、经济和社会可持续发展要求的开拓作用、经济和社会可持续发展要求的开拓作用 一体化交通运输（一体化交通运输（Integrated transportation）是指）是指交通运输与整个经济社会发展的进一步融合。包括：交通运输与整个经济社会发展的进一步融合。包括：1.运输方式内部及运输方式之间的一体化；运输方式内部及运输方式之间的一体化；2.运输与能源环境的一体化；运输与能源环境的一体化；3.运输与土地利用规划的一体化；运输与土地利用规划的一体化；4.运输与国家、社会安全的一体化；运输与国家、社会安全的一体化；5.运输与教育、健康和财富创造政策的一体化。运输与教育、健康和财富创造政策的一体化。一体化交通运输一体化交通运输q国际通达（国际通达（INTERNATIONNAL IN REACH）;q多式联运（多式联运（INTERMODAL IN FORM）；）；q智能运输（智能运输（INTELLIGENT IN CHARACTER）；）；q全面服务（全面服务（INCLUSIVE IN SERVICE）；）；q创新视野（创新视野（INNOVATIVE IN SCOPE）.面向面向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 运价率运价率基于重量的运价率基于重量的运价率基于距离的运价率基于距离的运价率基于运输需求的运价率基于运输需求的运价率合同运价率合同运价率干线运输运价率干线运输运价率其他特殊的运价率其他特殊的运价率课课 节节 回回 顾顾运输系统结构运输系统结构物流运输系统规划和设计的内容物流运输系统规划和设计的内容u运输业务模式的选择运输业务模式的选择 u运输方式的选择运输方式的选择u运输批量和运输时间的确定运输批量和运输时间的确定u运输线路的规划与选择运输线路的规划与选择 u运输流量的分析运输流量的分析 u车输的配载与调度问题车输的配载与调度问题 启发式算法特点启发式算法特点 禁忌搜索算法原理及步骤禁忌搜索算法原理及步骤 模拟退火算法原理及步骤模拟退火算法原理及步骤 遗传算法原理及步骤遗传算法原理及步骤5.3 现代优化算法现代优化算法本节重点：本节重点：5.3.1 现代优化算法概述现代优化算法概述传统的优化方法（？）传统的优化方法（？）以以数量分析数量分析为基础，以寻找系统为基础，以寻找系统最大限度地满足最大限度地满足特定活动目特定活动目标要求的方案为目的，帮助决策者或决策计算机构对其所控制的标要求的方案为目的，帮助决策者或决策计算机构对其所控制的活动活动实现优化决策实现优化决策的应用性理论。的应用性理论。（牛顿法、运筹学方法）（牛顿法、运筹学方法）现代优化方法现代优化方法（启发式算法）（启发式算法）1）组合最优化问题）组合最优化问题 通过对数学方法研究寻找离散事件的最优编排、通过对数学方法研究寻找离散事件的最优编排、分组、次序或筛选等（分组、次序或筛选等（从有限个状态选取最好的，其从有限个状态选取最好的，其最优解是某一种方案最优解是某一种方案）。）。Min f(x)g(x)0 x DX*为最优解为最优解2）启发式算法）启发式算法 基于直观或经验构造的算法，在可以接受的花费下给出待解决组合优化问题实例的可行解，该可行解和最优解的偏离程度不一定事先可以预计。不考虑所求可行解与最优解的偏离程度，只要不考虑所求可行解与最优解的偏离程度，只要达到预期目标即可。达到预期目标即可。（1）与导数无关性与导数无关性 在搜索使一个给定目标函数最小或者最大化的一组参数时，在搜索使一个给定目标函数最小或者最大化的一组参数时，这些方法不需要函数的导数信息。相反，它们只依赖于对目标这些方法不需要函数的导数信息。相反，它们只依赖于对目标函数的重复求值运算，而且在每一次求值后的搜索方向遵循某函数的重复求值运算，而且在每一次求值后的搜索方向遵循某种种启发式的启发式的思路。思路。（2 2）直观的思路直观的思路 这些搜索过程所遵循的思路通常建立这些搜索过程所遵循的思路通常建立在简单而直观在简单而直观的概念的概念基础上。其中的一些概念是由所谓的自然界的智慧所促使，比基础上。其中的一些概念是由所谓的自然界的智慧所促使，比如热力学和进化。如热力学和进化。3）启发式算法的特点）启发式算法的特点（3 3）速度慢速度慢 对于连续优化问题，这些方法由于不应用导数，对于连续优化问题，这些方法由于不应用导数，一般比一般比基于导数的优化方法速度慢。基于导数的优化方法速度慢。（4 4）灵活性灵活性 不用导数意味着对目标函数的可微和可导性质没有要求，不用导数意味着对目标函数的可微和可导性质没有要求，因此可以因此可以使用复杂的目标函数使用复杂的目标函数。（5 5）随机性随机性 所有的启发式优化算法都是随机的。理论上讲，启发式优所有的启发式优化算法都是随机的。理论上讲，启发式优化算法的随机性保证了在给定计算时间内化算法的随机性保证了在给定计算时间内得到最优解的概率非得到最优解的概率非零零。然而实际上，为了得到给定问题的最优解，往往花费非常。然而实际上，为了得到给定问题的最优解，往往花费非常可观的计算时间。可观的计算时间。（6 6）难以解析难以解析 难于对启发式优化算法进行解析研究，主要难于对启发式优化算法进行解析研究，主要是因为是因为其其随机随机性。性。（7）迭代性质迭代性质 所有的启发式优化算法在本质上都是迭代方法，因此需要所有的启发式优化算法在本质上都是迭代方法，因此需要某种停止判据来决定何时终止优化过程。某种停止判据来决定何时终止优化过程。常用的停止判据包括常用的停止判据包括 计算时间：计算时间：达到了制定的计算时间、函数求值次数或者迭达到了制定的计算时间、函数求值次数或者迭代次数。代次数。优化目标：优化目标：目标函数值达到某个预定的目标值。目标函数值达到某个预定的目标值。最小改进量：最小改进量：相邻两次迭代目标函数差小于某个预定值。相邻两次迭代目标函数差小于某个预定值。相对最小改进量：相对最小改进量：相邻两次迭代目标函数之差的某一数学相邻两次迭代目标函数之差的某一数学变形小于某个预定值。变形小于某个预定值。例：现有一个连通图例：现有一个连通图 A=6，各点之间距离矩阵如表所示，相，各点之间距离矩阵如表所示，相对位置如图对位置如图1所示，假设两点之间的距离是对称的，求单回路所示，假设两点之间的距离是对称的，求单回路运输问题。运输问题。123456图1123456图图2 2（最近邻点法）（最近邻点法）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 DD N N（S S）22D D 2 2D D于表示于表示D的所有子集组成的集合，则的所有子集组成的集合，则N N（S S）称为）称为S S的邻的邻域。域。S NN（S S）称为）称为S S的一个邻居。的一个邻居。局部最小（最大）解：局部最小（最大）解：f(s f(s*)()f(s),s D()f(s),s D N N（S S*）全局最小（最大）解：全局最小（最大）解：f(s f(s*)()f(s),s D ()f(s),s D 1）禁忌对象、长度和侯选集合）禁忌对象、长度和侯选集合 解解的简单变化：的简单变化：x yy 向量分量向量分量的变化：（的变化：（x x1 1,x,xi ixxn n)（x x1 1,y,yi ixxn n)目标值目标值的变化：的变化：x H(a)H(a)y H(b)H(b)（1）禁忌对象）禁忌对象禁忌表中被禁的变化元素。禁忌表中被禁的变化元素。（2 2）禁忌长度）禁忌长度被禁对象不允许超过的迭代次数。被禁对象不允许超过的迭代次数。tabu(x)=ttabu(x)=t；每迭代一步，每迭代一步，tabu(x)=t-1 tabu(x)=t-1，直到，直到tabu(x)=0tabu(x)=0。t t的选取有以下几种情况：的选取有以下几种情况：t t为常数为常数t(t(tminmin,t,tmaxmax),t),t可变化，其变化依据被禁对象的目标可变化，其变化依据被禁对象的目标值和邻域结构。值和邻域结构。t(t(tminmin,t,tmaxmax),t),tminmin,t,tmaxmax动态选取。动态选取。t t过短会造成循环出现，过长会造成计算时间增长。过短会造成循环出现，过长会造成计算时间增长。（3 3）候选集合的确定）候选集合的确定 全部邻域中的邻居。全部邻域中的邻居。部分邻域中的邻居。部分邻域中的邻居。随机选取部分邻居。随机选取部分邻居。2）评价函数）评价函数 候选集合的元素通过评价函数值来选取。候选集合的元素通过评价函数值来选取。（1 1）基于目标函数的评价函数）基于目标函数的评价函数 p(x)=f(x)p(x)=f(x)p(x)=f(x)-f(x p(x)=f(x)-f(xnownow)p(x)=f(x)-f(x p(x)=f(x)-f(xbestbest)（2 2）其他函数）其他函数 替代函数为了减少计算的复杂性。替代函数为了减少计算的复杂性。3）特赦规则）特赦规则（1 1）基于评价值的规则）基于评价值的规则:c(xc(xnownow)c(x)random(0,1),)random(0,1),则则x xi i=x=xj j;重复）。重复）。）t tk+1k+1=d(t=d(tk k););k=k+1;k=k+1;若满足终止条件，终止计算，否若满足终止条件，终止计算，否则回到）。则回到）。1）算法步骤）算法步骤2 2）主要问题）主要问题（1 1）温度温度T T的初始值设置问题的初始值设置问题温度温度T T的初始值设置是影响模拟退火算法全局搜索性能的的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一。初始温度高，则搜索到全局最优解的可能性大，重要因素之一。初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。全局搜索性能可能受到影响。实际应用过程中，初始温度一般实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。需要依据实验结果进行若干次调整。（2 2）退火速度问题）退火速度问题模拟退火算法的全局搜索性能也与退火速度密切相关。一模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，般来说，同一温度下的同一温度下的“充分充分”搜索搜索(退火退火)是相当必要的，但是相当必要的，但这需要计算时间。实际应用中，要针对具体问题的性质和特征这需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。设置合理的退火平衡条件。（3 3）温度管理问题）温度管理问题温度管理问题也是模拟退火算法难以处理的问题之一。实温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式：采用如下所示的降温方式：T(t+1)T(t+1)kT(t),kT(t),式中式中k k为正的略小于为正的略小于1.001.00的常数，的常数，t t为降温的次数。为降温的次数。课课 节节 回回 顾顾 启发式算法启发式算法 禁忌算法禁忌算法 模拟退火算法模拟退火算法 5.3.4 遗传算法遗传算法1）遗传算法的生物学基础）遗传算法的生物学基础 借用生物学优胜劣汰、适者生存的规律。借用生物学优胜劣汰、适者生存的规律。进化发生在编码上。进化发生在编码上。自然选择那些染色体产生超过平均数的后代。自然选择那些染色体产生超过平均数的后代。子女保持父母的特征子女保持父母的特征变异会造成子代和父代的不同。变异会造成子代和父代的不同。生成生成+检测的迭代搜索算法。检测的迭代搜索算法。编码编码初始群体生成初始群体生成适应度评估适应度评估选择选择交叉交叉变异变异2）遗传算法的基本要素）遗传算法的基本要素3 3）算法步骤）算法步骤 （1 1）选择问题的一个编码，给出一个有）选择问题的一个编码，给出一个有N N个染色体的初始群个染色体的初始群体体pop(t):t=1pop(t):t=1；（2 2）对群体中的每个染色体计算它的适应函数）对群体中的每个染色体计算它的适应函数f fi i；（3 3）若停止规则满足，则算法停止；否则，计算概率）若停止规则满足，则算法停止；否则，计算概率p pi i，以，以此概率随机选择一些染色体作为一个种群。此概率随机选择一些染色体作为一个种群。（4 4）以）以p pc c的结合概率得到一个有个染色体的群体的结合概率得到一个有个染色体的群体crosspop(t+1)crosspop(t+1)（5 5）以一个较小的概率）以一个较小的概率p p，使得一个染色体的一个基因发生，使得一个染色体的一个基因发生变异，形成变异，形成mutpop(t+1)mutpop(t+1)，取新的种群取新的种群pop(t+1)pop(t+1)mutpop(t+1)mutpop(t+1)，返回（返回（2 2）。）。）实现的技术问题）实现的技术问题（1）编码）编码（）评价遗传算法的常用方法（）评价遗传算法的常用方法（）初始参数的选取和停止原则。（）初始参数的选取和停止原则。（）进化过程中的技术问题。（）进化过程中的技术问题。思考题：启发式算法的应用案例思考题：启发式算法的应用案例5.4.1 各种运输方式的特点各种运输方式的特点选择运输方式时应考虑：服务的频率、速度、中转时间、中选择运输方式时应考虑：服务的频率、速度、中转时间、中转时间的波动性、费用、可利用性、安全、准确和顾客服务。转时间的波动性、费用、可利用性、安全、准确和顾客服务。5.4运输方式的选择运输方式的选择n铁路运输铁路运输 n公路运输公路运输 n水路运输水路运输 n航空运输航空运输 n管道运输管道运输 n多式联运多式联运 l货品特性货品特性l运输速度和运距运输速度和运距l运输容量运输容量 l运输成本运输成本 l运输质量运输质量 l环境保护环境保护 5.4.2 运输方式选择的考虑因素运输方式选择的考虑因素）因素分析法模型）因素分析法模型（j)=S(i,j)j)=S(i,j)（j)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算法中点到点的最短路。46437462555.5 路径的选择路径的选择5.5.2 多点间运输多点间运输 表上作业法表上作业法 单回路运输问题时指在路线优化中，设存在节点集单回路运输问题时指在路线优化中，设存在节点集D，选，选择一条合适的路径遍历所有的节点，并且要求闭合。择一条合适的路径遍历所有的节点，并且要求闭合。最近邻点法最近邻点法 最近邻点法算法十分简单，但是得到的解并不十分理想，有最近邻点法算法十分简单，但是得到的解并不十分理想，有很大的改善余地。由于该算法计算快捷，但精度低，可以作为进很大的改善余地。由于该算法计算快捷，但精度低，可以作为进一步优化的初始解。一步优化的初始解。最近邻点法可以由四步完成：最近邻点法可以由四步完成：1）从零点开始，作为整个回路的起点。从零点开始，作为整个回路的起点。2）找到离刚刚加入到回路的上一顶点最近的一个顶点，并将找到离刚刚加入到回路的上一顶点最近的一个顶点，并将其加入到回路中。其加入到回路中。3）重复第二步，直到所有顶点都加入到回路中。重复第二步，直到所有顶点都加入到回路中。4）将最后一个加入的顶点和起点连接起来。将最后一个加入的顶点和起点连接起来。这样就构成了一个这样就构成了一个TSP问题的解。问题的解。5.5.3 单回路运输单回路运输TSP模型及求解模型及求解 例：现有一个连通图例：现有一个连通图 A=6,它们的距离矩阵如表所示，他们的它们的距离矩阵如表所示，他们的相对位置如图所示，假设相对位置如图所示，假设,两点之间的距离时对称的。两点之间的距离时对称的。123456图1123456图2D=6+4+6+7+6+9=385.5.4 多回路运输多回路运输VRP模型及求解模型及求解 对一系列发货点和收获点，组织调用一定的车对一系列发货点和收获点，组织调用一定的车辆，安排适当的行车路线，使车辆有序地通过，在满辆，安排适当的行车路线，使车辆有序地通过，在满足指定的约束条件下（货物的需求量与发货量，交货足指定的约束条件下（货物的需求量与发货量，交货发货时间，车辆可载量限制，行驶里程限制，行驶时发货时间，车辆可载量限制，行驶里程限制，行驶时间限制等），力争实现一定的目标（车辆空驶总里程间限制等），力争实现一定的目标（车辆空驶总里程最短、运输总费用最低、车辆按一定时间到达、使用最短、运输总费用最低、车辆按一定时间到达、使用的车辆数量小等）。的车辆数量小等）。例例5.7：现有一个仓库：现有一个仓库V0，需要对，需要对8个客户提供货物，它们的需求量及极坐标个客户提供货物，它们的需求量及极坐标的角坐标值见表的角坐标值见表5-14，它们的位置关系如图，它们的位置关系如图5-11所示。设每个车辆的运输能所示。设每个车辆的运输能力时力时14个单位的货物，并现有足够多的车辆。试用扫描算法对该运输问题进个单位的货物，并现有足够多的车辆。试用扫描算法对该运输问题进行求解。行求解。