仓储与配送(龙)第十一章秋.ppt

《仓储与配送(龙)第十一章秋.ppt》由会员分享，可在线阅读，更多相关《仓储与配送(龙)第十一章秋.ppt（74页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第十一章第十一章配送运输配送运输一、配送运输概述一、配送运输概述二、配送合理化二、配送合理化三、配送路线优化三、配送路线优化四、配送车辆积载四、配送车辆积载五、配送优化调度五、配送优化调度20092009年年3 3月月龙桂先龙桂先一、配送运输概述1、概念与特点、概念与特点（二次运输、直线输送、终端输送）（二次运输、直线输送、终端输送）2、影响因素：、影响因素：供应链因素供应链因素上游、下游、终端上游、下游、终端环境因素环境因素信息技术、交通、能源信息技术、交通、能源3、作业流程、作业流程4、配送线路类型、配送线路类型20092009年年3 3月月龙桂先龙桂先2008-03龙桂先龙桂先3、作业流

2、程、作业流程划分基本配送区域划分基本配送区域车辆配载车辆配载暂定配送先后顺序暂定配送先后顺序车辆安排车辆安排完成车辆积载完成车辆积载选择配送路线选择配送路线确定配送顺序确定配送顺序客户分布地点客户分布地点货物特征货物特征交货时间交货时间交通状况交通状况客户具体位置客户具体位置送货时间限制送货时间限制货物货物车辆车辆费用费用货物货物20092009年年3 3月月龙桂先龙桂先4、配送线路类型、配送线路类型1）往复式）往复式单程有载、回程部分有载、双程有载单程有载、回程部分有载、双程有载2）环形式（封闭回路）环形式（封闭回路）简单环式简单环式交叉环式交叉环式三角环式三角环式复合环式复合环式3）汇集式

3、）汇集式分送式、聚集式、分送分送式、聚集式、分送-聚集式聚集式4）星型行驶线路（辐射状）星型行驶线路（辐射状）P21220092009年年3 3月月龙桂先龙桂先二、配送运输合理化1、不合理配送运输、不合理配送运输2、配送合理化表现形式、配送合理化表现形式3、配送合理化措施、配送合理化措施20092009年年3 3月月龙桂先龙桂先1、不合理、不合理配送运输配送运输资源筹措（规模化、计划性、战略性）资源筹措（规模化、计划性、战略性）库存决策（科学性、供应柔性）库存决策（科学性、供应柔性）价格价格直达直达不合理运输：不合理运输：运输不合理表现运输不合理表现空驶空驶对流运输对流运输迂回运输迂回运输重复

4、运输重复运输倒流运输倒流运输过远运输过远运输无效运输无效运输运力选择不当运力选择不当托运方式选择不当托运方式选择不当超限运输超限运输20092009年年3 3月月龙桂先龙桂先2、配送合理化表现形式、配送合理化表现形式库存标志库存标志资金标志资金标志成本和效益成本和效益供应保证供应保证社会运力节约标志社会运力节约标志客户的仓库、供应、进货等人力物力节约客户的仓库、供应、进货等人力物力节约标志标志物流合理化标志物流合理化标志20092009年年3 3月月龙桂先龙桂先3、配送合理化措施、配送合理化措施一定综合程度的专业化配送一定综合程度的专业化配送加工配送加工配送共同配送共同配送送取结合送取结合准时

5、配送准时配送即时配送即时配送20092009年年3 3月月龙桂先龙桂先游戏游戏十几个学员平均分为两队，要把放在地十几个学员平均分为两队，要把放在地上的两串钥匙捡起来，从队首到队尾。规上的两串钥匙捡起来，从队首到队尾。规则是必须按照顺序，并使钥匙接触到每个则是必须按照顺序，并使钥匙接触到每个人的手。人的手。怎么办？怎么办？20092009年年3 3月月龙桂先龙桂先方法与启示方法与启示比赛开始并记时。两队的第一反应都是按老比赛开始并记时。两队的第一反应都是按老师做过的示范：捡起一串，传递完毕，再传另一师做过的示范：捡起一串，传递完毕，再传另一串；结果都用了串；结果都用了15秒左右。秒左右。把两串钥

6、匙把两串钥匙拴在一起拴在一起同时传，这次只用同时传，这次只用5秒秒钟。钟。“只是要求按顺序从手上经过呀，不一定非得只是要求按顺序从手上经过呀，不一定非得传呀。传呀。”完全抛开了传递方式，开始飞快地把手扣成完全抛开了传递方式，开始飞快地把手扣成圆桶状，摞在一起，形成一个通道，让钥匙像圆桶状，摞在一起，形成一个通道，让钥匙像自自由落体由落体一样从上落下来，既按了顺序，同时也接一样从上落下来，既按了顺序，同时也接触了每个人的手，时间是触了每个人的手，时间是0.5秒。秒。启示启示20092009年年3 3月月龙桂先龙桂先三、配送路线优化三、配送路线优化1、线路设计的意义、线路设计的意义2、配送路线设计

7、方法、配送路线设计方法20092009年年3 3月月龙桂先龙桂先2008-03龙桂先龙桂先1、线路设计的意义配送线路设计配送线路设计综合分析了配送运输的各因素综合分析了配送运输的各因素后，及时、安全、方便、经济的将客户所需的不后，及时、安全、方便、经济的将客户所需的不同物资准确送达客户手中，以便提供优良的物流同物资准确送达客户手中，以便提供优良的物流配送服务。配送服务。影响因素影响因素客户群特点、要求客户群特点、要求道路状况道路状况车流量车流量车辆定额载重量车辆定额载重量车辆最大行驶里程数车辆最大行驶里程数司机最长工作时间司机最长工作时间运输规章限制运输规章限制配送中心选址配送中心选址原则原则

8、效益最高效益最高路程最短路程最短服务最优服务最优消耗最小消耗最小20092009年年3 3月月龙桂先龙桂先2008-03龙桂先龙桂先2、配送线路设计方法1）经验判断法：）经验判断法：行车人员经验行车人员经验2）综合评分法综合评分法：方案、指标、评分方案、指标、评分3）数学计算方法）数学计算方法一对一配送一对一配送一对多配送一对多配送多对多配送多对多配送20092009年年3 3月月龙桂先龙桂先2008-03龙桂先龙桂先2)综合评分法某配送企业配送路线方案指标某配送企业配送路线方案指标序号序号评价指标评价指标极差极差差差较好较好良好良好最优最优0分分1分分2分分3分分4分分1全过程距离全过程距离

9、2行车时间行车时间3配送准时性配送准时性4行车难易行车难易5动用车辆数动用车辆数6油耗油耗7车辆状况车辆状况8运送量运送量9配送客户数配送客户数10配送总费用配送总费用20092009年年3 3月月龙桂先龙桂先3）数学计算方法）数学计算方法一对一配送一对一配送一对多配送一对多配送多对多配送多对多配送20092009年年3 3月月龙桂先龙桂先一对一配送一对一配送最短路径法最短路径法标号法（标号法（DijkStra算法）算法）P22020092009年年3 3月月龙桂先龙桂先2008-03龙桂先龙桂先一对多配送一对多配送节约算法节约算法PPBBBAAAP20092009年年3 3月月龙桂先龙桂先原

10、理原理:由由一一个个点点向向二二个个点点送送货货，如如果果能能够够实实行行配配送送则则其其运运杂费的节约量为杂费的节约量为:CC1212C-CC-C(2C(2C0101十十2C2C0202)-(C)-(C0101+C+C0202+C+C1212)=C=C0101+C+C0202-C-C1212A0C01C02B1B2A0C01C02B1B2C1220092009年年3 3月月龙桂先龙桂先原理:按按这这种种方方式式推推广广到到多多个个用用户户的的情情况况，则则可可以以得得到到更大的节约量。更大的节约量。如如果果我我们们优优先先选选出出节节约约量量最最大大的的点点连连在在一一起起，组组成成配配送送

11、回回路路，且且满满足足回回路路中中各各点点需需求求量量的的总总和和不不大大于于一一辆辆车车的的载载重重量量，则则就就构构造造出出了了一一条条配配送送回回路路，选选好好一一条条配配送送回回路路以以后后，再再在在剩剩下下的的网网点点中中同同样样构构造造新新的的配配送送回回路路，直直到到所所有有点点都都被被选选进进配配送计划中为止。送计划中为止。20092009年年3 3月月龙桂先龙桂先节约法基本思路节约法基本思路当一个配送中心向几个不同方当一个配送中心向几个不同方向收货点发货时，选择最短的向收货点发货时，选择最短的里程。即尽量节省费用。里程。即尽量节省费用。20092009年年3 3月月龙桂先龙桂

12、先案例案例下页图示为一配送网络，现要利用两种下页图示为一配送网络，现要利用两种2吨和吨和4吨的厢式卡车，将货物配送到各个客户，并限吨的厢式卡车，将货物配送到各个客户，并限制车辆一次运行距离在制车辆一次运行距离在30公里以内。公里以内。P22220092009年年3 3月月龙桂先龙桂先配送中心的配送网络图P22220092009年年3 3月月龙桂先龙桂先各客户之间距离各客户之间距离P0P110P1P294P2P3795P3P4814105P4P58181496P5P68181715137P6P7313121011106P7P84141311121282P8P910111517181817119P

13、9P10748131515151011820092009年年3 3月月龙桂先龙桂先配送路线节约行程表配送路线节约行程表P1P1P215P2P3811P3P44710P4P503310P5P600039P6P7000015P7P80000045P8P994000125P9P101381000009P01+P02-P12=10+9-420092009年年3 3月月龙桂先龙桂先配送中心节约行程排序表20092009年年3 3月月龙桂先龙桂先初始解初始解20092009年年3 3月月龙桂先龙桂先二次解二次解20092009年年3 3月月龙桂先龙桂先最优解最优解20092009年年3 3月月龙桂先龙桂先

14、多对多配送多对多配送供销平衡供销平衡供销不平衡供销不平衡20092009年年3 3月月龙桂先龙桂先三、配送车辆积载车辆按照核定吨位满载运行车辆按照核定吨位满载运行充分利用充分利用流量、流向，流时，流距，及运行中问题流量、流向，流时，流距，及运行中问题亏载亏载or超载超载车辆早期损坏，过度磨损，燃料、润料消耗；车辆早期损坏，过度磨损，燃料、润料消耗；运行事故。运行事故。20092009年年3 3月月龙桂先龙桂先2008-03龙桂先龙桂先三、配送车辆积载1、评价：、评价：吨位利用率吨位利用率=（实际完成周转量（实际完成周转量/载运形成在质量）载运形成在质量）100%装载标准，装载顺序，装载技术、操

15、作水平装载标准，装载顺序，装载技术、操作水平货物品种数量货物品种数量2、拼装、拼装案例案例http:/ 3月月龙桂先龙桂先A:一辆载重为一辆载重为25吨吨60立方米的卡车立方米的卡车,怎么配载就可以使怎么配载就可以使货车满载货车满载(25吨吨,60立方米立方米)呢呢?方案只能做到其中一项方案只能做到其中一项,很难做到合理配载很难做到合理配载B:问题模型是拼箱，最基本的问题原型是背包问题，如问题模型是拼箱，最基本的问题原型是背包问题，如果装载还涉及一个线路问题，那么就得再加一个中国邮果装载还涉及一个线路问题，那么就得再加一个中国邮路问题得模型进来。如果你每次得货物都是不同的话，路问题得模型进来。

16、如果你每次得货物都是不同的话，那么你需要一个完整优化算法软件为你每次都不同的货那么你需要一个完整优化算法软件为你每次都不同的货物和路径进行优化运算。可惜这种东西目前好象也只能物和路径进行优化运算。可惜这种东西目前好象也只能提供一个参考的优化结果。好象目前这种操作更多是依提供一个参考的优化结果。好象目前这种操作更多是依靠人的经验。靠人的经验。C:你给的前提条件有点模糊，因为车子的装载量是固定你给的前提条件有点模糊，因为车子的装载量是固定的，那么货物的大小，尺寸，质量，重量和包装都直接的，那么货物的大小，尺寸，质量，重量和包装都直接影响货物的配载，所以没有货物的规格，尺寸，和包装影响货物的配载，所

17、以没有货物的规格，尺寸，和包装特征，以及先后卸货的顺序，怎么能帮上你的忙呢？特征，以及先后卸货的顺序，怎么能帮上你的忙呢？A:货物一般都是些散货货物一般都是些散货,货物的包装规格货物的包装规格大小都不一样大小都不一样,但但是卸货地点都是一样的是卸货地点都是一样的,到目的地后再进行转货到目的地后再进行转货,这这里的问题是在我们公司货场装货的时候有时候很难做到里的问题是在我们公司货场装货的时候有时候很难做到载重和体积都做到最好载重和体积都做到最好,我想在这里找一个货车吨位与我想在这里找一个货车吨位与体积之间的黄金分割点体积之间的黄金分割点!20092009年年3 3月月龙桂先龙桂先B：问题难度降低

18、了一半！：问题难度降低了一半！很明显你们每次运输的货物都不一样的，那么这就需要每很明显你们每次运输的货物都不一样的，那么这就需要每次动态的优化你们的配载方案，需要用一个拼箱或是配载次动态的优化你们的配载方案，需要用一个拼箱或是配载的优化算法。的优化算法。不过前提条件是你们的货物数据都需要详尽如实的记录到不过前提条件是你们的货物数据都需要详尽如实的记录到系统中，这样才能进行优化配载，要实现这个目的，基础系统中，这样才能进行优化配载，要实现这个目的，基础信息化有很长路需要走，当然你们可能走完了前面的步骤信息化有很长路需要走，当然你们可能走完了前面的步骤除了上述方案，目前好象更多的是基于经验。大概的

19、知道除了上述方案，目前好象更多的是基于经验。大概的知道货物的密度，由经验进行重泡货的搭载和匹配，这种经验货物的密度，由经验进行重泡货的搭载和匹配，这种经验好象是难以复制的好象是难以复制的C：你们是做零担或者是专线运输的吗？配载问题一直是你：你们是做零担或者是专线运输的吗？配载问题一直是你们这个行业的难题，还没有任何一种物流软件可以帮的上们这个行业的难题，还没有任何一种物流软件可以帮的上帮，因为货物、包装，质量的多样性，以及不稳定（每次帮，因为货物、包装，质量的多样性，以及不稳定（每次变化）所以决定货物的配载难度变化）所以决定货物的配载难度现在的操作都是以人的实际经验来进行配载的，这不断需现在的

20、操作都是以人的实际经验来进行配载的，这不断需要一个零散货物配载经验丰富的人，也需要一个能领悟领要一个零散货物配载经验丰富的人，也需要一个能领悟领导的意图的装卸工班，所以我们也是爱莫能助啊！因为它导的意图的装卸工班，所以我们也是爱莫能助啊！因为它是人去实地，看到实物才能给你意见的，不能凭空想象，是人去实地，看到实物才能给你意见的，不能凭空想象，物流是不能纸上谈兵的。物流是不能纸上谈兵的。20092009年年3 3月月龙桂先龙桂先D：装载量与路线优化的问题确实相当麻烦，我目前接触：装载量与路线优化的问题确实相当麻烦，我目前接触过客户使用中的系统也都只能提供一个理想化环境下的参过客户使用中的系统也都

21、只能提供一个理想化环境下的参考数值，不过问题在环境绝对不是理想化的，变化太多了，考数值，不过问题在环境绝对不是理想化的，变化太多了，也太快了，所以每天他们在系统算完后，还是必须人工再也太快了，所以每天他们在系统算完后，还是必须人工再去确认调整装载与路线问题，这个部分真的就只能依靠经去确认调整装载与路线问题，这个部分真的就只能依靠经验法则了。验法则了。至于楼主的问题因为已经排除掉路线了，所以剩下的至于楼主的问题因为已经排除掉路线了，所以剩下的只有装载量部分。如果货物的基本大小，重量等资料都相只有装载量部分。如果货物的基本大小，重量等资料都相当完整而且正确，那问题就在计算装载时究竟要选择体积当完整

22、而且正确，那问题就在计算装载时究竟要选择体积或是重量来作为计算的基准？或是重量来作为计算的基准？建议可以对货物本身作一个特性的设定，如果这种货建议可以对货物本身作一个特性的设定，如果这种货物本身的密度大，那就以重量为计算基准，如果密度小，物本身的密度大，那就以重量为计算基准，如果密度小，就以体积来计算，至于密度的算法最简单的就是用：（货就以体积来计算，至于密度的算法最简单的就是用：（货物的重量物的重量/货物的体积）比对（卡车的重量货物的体积）比对（卡车的重量/卡车的体积），卡车的体积），如果货物的密度比卡车大，就算重量，如果密度小，就算如果货物的密度比卡车大，就算重量，如果密度小，就算体积。不

23、过这也是理想化的算法，必须加上经验去调整才体积。不过这也是理想化的算法，必须加上经验去调整才行，不然还是会发生虽然算的很准，却装不上或是空太多行，不然还是会发生虽然算的很准，却装不上或是空太多的问题。的问题。20092009年年3 3月月龙桂先龙桂先没有了路线就容易点。没有了路线就容易点。有了各种货物的尺寸和重量，对比车厢内的尺寸。有了各种货物的尺寸和重量，对比车厢内的尺寸。应该可以最充分的填充车厢。应该可以最充分的填充车厢。用用EXCEL可以将就一下可以将就一下:1、全车货临界点是：、全车货临界点是：25T/60立方米立方米=416KG/立立方米；方米；2、按货物密度顺序排出最重的货与最轻的

24、货，、按货物密度顺序排出最重的货与最轻的货，不轻不重（即接近不轻不重（即接近416的货放在一边，最后再考的货放在一边，最后再考虑；虑；3、拿最重的货与最轻的货在、拿最重的货与最轻的货在EXCEL中配比（这中配比（这个过程用语言表达比较麻烦，要熟悉个过程用语言表达比较麻烦，要熟悉EXCEL才才好办），配比值接近好办），配比值接近416的货物拿出来放在一边，的货物拿出来放在一边，将全部货物配比值都达到将全部货物配比值都达到416即可即可20092009年年3 3月月龙桂先龙桂先办法不错！办法不错！比较麻烦的问题应该是货物基础数据的收集，每件货物的重量和比较麻烦的问题应该是货物基础数据的收集，每件货

25、物的重量和体积都需要比较准确的数据。体积都需要比较准确的数据。信息化，规范化，标准化是优化的基础。信息化，规范化，标准化是优化的基础。希望做希望做IT的能够做出一个软件来的能够做出一个软件来,剩的我们有时候发一次货物还剩的我们有时候发一次货物还要赔钱要赔钱!如果有了这样的好东西如果有了这样的好东西,那就是救命啊那就是救命啊!这样的软件是有的，但是能应用智能工具，前期的基础和投入是这样的软件是有的，但是能应用智能工具，前期的基础和投入是需要一步一步的积累和走过；不然应用了如此的软件也是没有用需要一步一步的积累和走过；不然应用了如此的软件也是没有用的。因为逻辑上的东西需要精确，不像经验，感性的估计

26、就能差的。因为逻辑上的东西需要精确，不像经验，感性的估计就能差不离。不离。你可以采购一个装箱软件，基本能达到你的要求，但你每次作数你可以采购一个装箱软件，基本能达到你的要求，但你每次作数据量会非常大。据量会非常大。建议，你们可否推出一些标准的包装尺寸，这样你每次的工作强建议，你们可否推出一些标准的包装尺寸，这样你每次的工作强度就要小很多。度就要小很多。瓦赛，太难了，瓦赛，太难了，excel的应用是高深莫测啊，怪不得很多合资企的应用是高深莫测啊，怪不得很多合资企业都招收业都招收excel的高手呢。的高手呢。这个用这个用EXCEL完成不了优化功能，只是凑数而已。完成不了优化功能，只是凑数而已。20

27、092009年年3 3月月龙桂先龙桂先合理配货只能是一个经验，对零担货物涉及的方面太多，合理配货只能是一个经验，对零担货物涉及的方面太多，货物本身的比重，形状，形态；外包装材质，形状等等，货物本身的比重，形状，形态；外包装材质，形状等等，如果用软件配货前提要有一个数据的累积过程，这不是如果用软件配货前提要有一个数据的累积过程，这不是软件公司所能提供的。所以说如果真的想要达到理想状软件公司所能提供的。所以说如果真的想要达到理想状态应该是软件公司和贵公司需要一个长期的合作才有可态应该是软件公司和贵公司需要一个长期的合作才有可能达成。能达成。A：我们也想把包装做到合理化：我们也想把包装做到合理化,可

28、是我们公司做的是零可是我们公司做的是零担货物运输担货物运输,很难让客户做到标准很难让客户做到标准,我想这也是现在零担我想这也是现在零担运输企业都存在的一个问题吧运输企业都存在的一个问题吧!不过还是谢谢大家的提议不过还是谢谢大家的提议!这个最好做成标准化这个最好做成标准化把运输的商品分类包装把运输的商品分类包装再做成托盘：再做成托盘：一一可以提高效率；二可以提高效率；二可以增加运量可以增加运量这个涉及到线形代数方面的问题，也是我最头痛的，想这个涉及到线形代数方面的问题，也是我最头痛的，想请问是否物流必须要有这样高深的数学分析能力呢？请问是否物流必须要有这样高深的数学分析能力呢？请教？请教看本运筹

29、学一切看本运筹学一切OK。没办法没办法,有的时候就得多知道点东西有的时候就得多知道点东西,这就是中国物流的这就是中国物流的一个现状一个现状!20092009年年3 3月月龙桂先龙桂先思考思考咱们应该干些什么？咱们应该干些什么？咱们能做些什么？咱们能做些什么？20092009年年3 3月月龙桂先龙桂先3、背包问题背包问题是一个一般化的货箱装载问题，即每个货箱所背包问题是一个一般化的货箱装载问题，即每个货箱所获得的价值不同。获得的价值不同。货箱装载问题转化为背包问题的形式为：货箱作为背包，货箱装载问题转化为背包问题的形式为：货箱作为背包，货作为可装入背包的物品。货作为可装入背包的物品。例，例，在杂

30、货店比赛中你获得了第一名，奖品是一车免在杂货店比赛中你获得了第一名，奖品是一车免费杂货。店中有费杂货。店中有n种不同的货物。规则规定从每种货物种不同的货物。规则规定从每种货物中最多只能拿一件，车子的容量为中最多只能拿一件，车子的容量为c，物品，物品i需占用需占用wi的空间，价值为的空间，价值为pi。你的目标是使车中装载的物品价值。你的目标是使车中装载的物品价值最大。当然，所装货物不能超过车的容量，且同一种物最大。当然，所装货物不能超过车的容量，且同一种物品不得拿走多件。品不得拿走多件。20092009年年3 3月月龙桂先龙桂先背包问题背包问题有一个背包，背包容量是有一个背包，背包容量是M=15

31、0。有。有7个物品，物品个物品，物品可以分割成任意大小。可以分割成任意大小。要求尽可能让装入背包中的物品总价值最要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。大，但不能超过总容量。物品物品重量重量价值价值A3510B3040C6030D5050E4035F1040G2530分析：分析：目标函数：目标函数：pi最大最大约束条件是装入的物品总重量不超过背包容量：约束条件是装入的物品总重量不超过背包容量：wi=M(M=150)1）根据贪婪的策略，每次挑选价值最大的物品装入背包，得到）根据贪婪的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？的结果是否最优？2）每次挑选所占空间最

32、小的物品装入是否能得到最优解？）每次挑选所占空间最小的物品装入是否能得到最优解？3）每次选取单位容量价值最大的物品，成为解本题的策略。）每次选取单位容量价值最大的物品，成为解本题的策略。20092009年年3 3月月龙桂先龙桂先贪婪准则贪婪准则1为：从剩余的物品中，选出可以装入背包的为：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。物品，如此继续下去。这种策略不能保证得

33、到最优解。例如，考虑例如，考虑n=2,w=100,10,10,p=20,15,15,c=105。当利用价值贪婪准则时，获得的解为。当利用价值贪婪准则时，获得的解为x=1,0,0，这种方案的总价值为，这种方案的总价值为20。而最优解为。而最优解为0,1,1，其，其总价值为总价值为30。重量贪婪准则重量贪婪准则2是：从剩下的物品中选择可装入背包的是：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑最优解，但在一般情况下则不一定能得到最优解。考虑n=2,w=10,20,p=5

34、,100,c=25。当利用重量贪婪。当利用重量贪婪策略时，获得的解为策略时，获得的解为x=1,0,比最优解比最优解0,1要差。要差。价值密度价值密度pi/wi贪婪算法，这种选择准则为：从剩余物贪婪算法，这种选择准则为：从剩余物品中选择可装入包的品中选择可装入包的pi/wi值最大的物品，这种策略也值最大的物品，这种策略也不能保证得到最优解。利用此策略试解不能保证得到最优解。利用此策略试解n=3,w=20,15,15,p=40,25,25,c=30时的最优解时的最优解.20092009年年3 3月月龙桂先龙桂先背包问题是一个背包问题是一个NP-复杂问题。对于这类问题，复杂问题。对于这类问题，也许根

35、本就不可能找到具有多项式时间的算法。也许根本就不可能找到具有多项式时间的算法。虽然按虽然按pi/wi非递（增）减的次序装入物品不能非递（增）减的次序装入物品不能保证得到最优解，但它是一个直觉上近似的解。保证得到最优解，但它是一个直觉上近似的解。我们希望它是一个好的启发式算法，且大多数时我们希望它是一个好的启发式算法，且大多数时候能很好地接近最后算法。候能很好地接近最后算法。在在600个随机产生的背包问题中，用这种启发式个随机产生的背包问题中，用这种启发式贪婪算法来解有贪婪算法来解有239题为最优解。有题为最优解。有583个例个例子与最优解相差子与最优解相差10%，所有，所有600个答案与最优个

36、答案与最优解之差全在解之差全在25%以内。该算法能获得好性能。以内。该算法能获得好性能。我们也许会问，是否存在一个我们也许会问，是否存在一个x(x100)，使得，使得贪婪启发法的结果与最优值相差在贪婪启发法的结果与最优值相差在x%以内。答以内。答案是否定的。案是否定的。20092009年年3 3月月龙桂先龙桂先实例实例某仓库某次运输水泥和玻璃两种货物，水泥质量体积为某仓库某次运输水泥和玻璃两种货物，水泥质量体积为0.9m3/吨，玻璃是吨，玻璃是1.6m3/吨，计划使用车辆的载重量为吨，计划使用车辆的载重量为11吨，车厢容积为吨，车厢容积为15m3。试问，如何装载才能使车辆。试问，如何装载才能使

37、车辆的载重能力和车厢容积都能得到充分利用？的载重能力和车厢容积都能得到充分利用？解：设水泥的装载量为解：设水泥的装载量为Wa，玻璃为，玻璃为WbWa+Wb=WWa*Ra+Wb*Rb=VWa=(V-W*Rb)/(Ra-Rb)=(15-11*1.6)/(0.9-1.6)=3.71Wb=(V-W*Ra)/(Rb-Ra)=(15-11*0.9)/(1.6-0.9)=7.2920092009年年3 3月月龙桂先龙桂先2008-03龙桂先龙桂先4、积载原则轻重搭配轻重搭配限重限重同一地点一次积载同一地点一次积载大小搭配大小搭配合理堆码合理堆码货物性质搭配货物性质搭配均匀分布均匀分布避免碰撞、玷污避免碰撞、

38、玷污20092009年年3 3月月龙桂先龙桂先案例：全在海上案例：全在海上参考消息参考消息5月月8日讯【英国经济学家周刊日讯【英国经济学家周刊5月月2-8日一期文章】美军海上基日一期文章】美军海上基地作战观念源自地作战观念源自1994年海地政治危机。当年年海地政治危机。当年9月，美军舰队在海地周边水域游月，美军舰队在海地周边水域游弋，以武力支持海地总统阿里斯蒂德复职。为了这次行动的需要，舰队核心弋，以武力支持海地总统阿里斯蒂德复职。为了这次行动的需要，舰队核心“艾森豪威尔号艾森豪威尔号”航母没有携带舰载喷气式战斗机，而是摇身一变成了陆军航母没有携带舰载喷气式战斗机，而是摇身一变成了陆军直升机起

39、降平台以及直升机起降平台以及2000多名海军陆战队出击的大本营。多名海军陆战队出击的大本营。美军早期概念的机动海上基地是一种类似于使用钢筋、混凝土和大型浮箱美军早期概念的机动海上基地是一种类似于使用钢筋、混凝土和大型浮箱建造起来的人造岛屿，这种基地可提供美军满足运输机起降的机场。而近来，建造起来的人造岛屿，这种基地可提供美军满足运输机起降的机场。而近来，该概念逐步发展成为包括各种军事设施的海上基地，以供美军事人员和装备该概念逐步发展成为包括各种军事设施的海上基地，以供美军事人员和装备进行前沿部署，满足美军的维护和医疗需要，防御来自水面、空中和水下的进行前沿部署，满足美军的维护和医疗需要，防御来

40、自水面、空中和水下的威胁，允许海上基地具备威胁，允许海上基地具备C4I系统和系统和ISR系统网络作战能力。这一概念的发展系统网络作战能力。这一概念的发展要求多种作战平台能够迅速集成，然后重新部署到不同的联合体中，为美军要求多种作战平台能够迅速集成，然后重新部署到不同的联合体中，为美军在不同冲突环境下和作战阶段下提供必要的作战能力。此外，海上基地还可在不同冲突环境下和作战阶段下提供必要的作战能力。此外，海上基地还可以扮演港口的角色，规模为陆战队远征旅或是陆军旅级部队可在此进行重新以扮演港口的角色，规模为陆战队远征旅或是陆军旅级部队可在此进行重新组合投入未来的作战行动，而在重型部队抵达作战区域前，

41、海上基地还可先组合投入未来的作战行动，而在重型部队抵达作战区域前，海上基地还可先行接收军事装备。行接收军事装备。据透露，这种大型机动式海上基地由一组分别自带动力装置的海上浮动模据透露，这种大型机动式海上基地由一组分别自带动力装置的海上浮动模块组成，可以根据需要组合成长达块组成，可以根据需要组合成长达2公里、宽公里、宽152.4米的平台，并拥有米的平台，并拥有46万平万平方米的存贮空间，为装备储存和修理提供近方米的存贮空间，为装备储存和修理提供近28万平方米的空间，可装载万平方米的空间，可装载3000人的重型远征旅，储存人的重型远征旅，储存450万升的油料，以执行多种保障任务。它的浮移速度万升的

42、油料，以执行多种保障任务。它的浮移速度可高达可高达15节，在节，在3级海况下仍可进行装卸货作业。它能在飓风中生存，使用寿级海况下仍可进行装卸货作业。它能在飓风中生存，使用寿命为命为40年。根据初步预算，单个基地模块费用为年。根据初步预算，单个基地模块费用为15亿美元，一个长亿美元，一个长2公里的完公里的完整机动海上基地约花费整机动海上基地约花费50亿美元至亿美元至80亿美元。第一个机动基地计划建于亿美元。第一个机动基地计划建于2009年。年。20092009年年3 3月月龙桂先龙桂先尽管尽管“浮动基地浮动基地”建成将为美海军发展提供更大空间，但如何维建成将为美海军发展提供更大空间，但如何维护其

43、正常运营却是一大难题。护其正常运营却是一大难题。首先，基地内众多设备的运转将消耗大量的能源，如何对此进行首先，基地内众多设备的运转将消耗大量的能源，如何对此进行有效和及时补给是对美军的考验。有效和及时补给是对美军的考验。此外，基地由大大小小的各类战舰和货船组成，仅货物装卸就是此外，基地由大大小小的各类战舰和货船组成，仅货物装卸就是一件麻烦的事情，因为海上浮动基地有时要在第一件麻烦的事情，因为海上浮动基地有时要在第4级海况的状态级海况的状态下作业，风速达每小时下作业，风速达每小时24英里，浪高英里，浪高6英尺。诸如集装箱装卸这英尺。诸如集装箱装卸这些在陆上看似平凡的任务，在恶劣的海上环境中却形同

44、恶梦。美些在陆上看似平凡的任务，在恶劣的海上环境中却形同恶梦。美海军工程师米奇认为，舰与舰之间集装箱的运输将是基地后勤保海军工程师米奇认为，舰与舰之间集装箱的运输将是基地后勤保障中的一个瓶颈。障中的一个瓶颈。基地中大部分装备不用时都放在标准的集装箱中。不过战争就是基地中大部分装备不用时都放在标准的集装箱中。不过战争就是战争，事先并不总能知道是么时候需要什么装备。如果发现某个战争，事先并不总能知道是么时候需要什么装备。如果发现某个关键装备被押在中间，而不是放在最上面，可是有急需该装备，关键装备被押在中间，而不是放在最上面，可是有急需该装备，这是问题就出现了。为了解决这一难题，国防部请佛罗里达州的

45、这是问题就出现了。为了解决这一难题，国防部请佛罗里达州的一家公告称公司一家公告称公司BEC工业公司专门设计了一套集装箱管理系统。工业公司专门设计了一套集装箱管理系统。系统于今年系统于今年2月设计完成。该系统能够在月设计完成。该系统能够在10分钟内调整分钟内调整6个集装箱个集装箱的位置。的位置。20092009年年3 3月月龙桂先龙桂先2008-03龙桂先龙桂先5、装载与卸载装卸：省力、节能、减少损失、快速、低装卸：省力、节能、减少损失、快速、低成本成本堆积堆积绑扎绑扎物流技术2009第8期胡贵彦，货物配载方法最优化研究20092009年年3 3月月龙桂先龙桂先2008-03龙桂先龙桂先四、配送

46、优化调度方法四、配送优化调度方法1、车辆调度的原则、车辆调度的原则2、经验调度法、经验调度法3、运输定额比法运输定额比法4、表上作业、表上作业5、图上作业、图上作业12345678981635749220092009年年3 3月月龙桂先龙桂先1、车辆调度的原则、车辆调度的原则统一领导指挥，分级管理、分工负责；统一领导指挥，分级管理、分工负责；全局出发；全局出发；均衡和完成生产任务计划；均衡和完成生产任务计划；最低资源（运力）投入，最大效益获得。最低资源（运力）投入，最大效益获得。具体：少数，局部，次要，当日，可缓运，整批。具体：少数，局部，次要，当日，可缓运，整批。内部内部20092009年年

47、3 3月月龙桂先龙桂先案例某建材配送中心某日需运输水泥某建材配送中心某日需运输水泥580吨、盘条吨、盘条400吨和吨和不定量的平板玻璃。该中心有大型车不定量的平板玻璃。该中心有大型车20辆、中型车辆、中型车20辆、辆、小型车小型车30辆，各种车每日只运输一种物资。辆，各种车每日只运输一种物资。车辆种类车辆种类运水泥运水泥运盘条运盘条运玻璃运玻璃大型车大型车201714中型车中型车181512小型车小型车16131020092009年年3 3月月龙桂先龙桂先2008-03龙桂先龙桂先2、经验调度法车辆种类车辆种类运水泥运水泥运盘条运盘条运玻璃运玻璃大型车大型车201714中型车中型车181512

48、小型车小型车161310车辆车辆种类种类运水泥运水泥车辆数车辆数运盘条运盘条车辆数车辆数运玻璃运玻璃车辆数车辆数车辆车辆总数总数大型车大型车2020中型车中型车101020小型车小型车201030货运量货运量58040010020092009年年3 3月月龙桂先龙桂先2008-03龙桂先龙桂先3、运输定额比法、运输定额比法车辆种类车辆种类运水泥运水泥/运盘条运盘条运盘条运盘条/运玻璃运玻璃运水泥运水泥/运玻璃运玻璃大型车大型车1.181.211.44中型车中型车1.21.251.5小型车小型车1.231.31.6车辆种类车辆种类运水泥运水泥车辆数车辆数运盘条运盘条车辆数车辆数运玻璃运玻璃车辆数

49、车辆数车辆总数车辆总数大型车大型车56920中型车中型车2020小型车小型车3030货运量货运量58040212620092009年年3 3月月龙桂先龙桂先2008-03龙桂先龙桂先4、表上作业方法、表上作业方法1）初始方案（西北角法、最小元素法）初始方案（西北角法、最小元素法）2）位势值检验）位势值检验3）闭回路）闭回路20092009年年3 3月月龙桂先龙桂先4、表上作业案例、表上作业案例B1B2B3产量产量/tA116152510A21924128销量销量/t5672020092009年年3 3月月龙桂先龙桂先1）初始方案初始方案西北角法西北角法B1B2B3产量产量/tA11615251

50、0A21924128销量销量/t56720551720092009年年3 3月月龙桂先龙桂先1）初始方案）初始方案最小元素法最小元素法B1B2B3产量产量/tA116152510A21924128销量销量/t56720764120092009年年3 3月月龙桂先龙桂先原则原则产量产量ai销量销量bj，按销量，按销量bj产量产量ai销量销量bj，按产量，按产量aj产量产量ai=销量销量bj，一次完成，一次完成检查空格检查空格20092009年年3 3月月龙桂先龙桂先2）位势法）位势法构造位势表构造位势表确定位势值确定位势值(西北角法初始方案）西北角法初始方案）假设假设A1=0，令圈出来的安排运输