线路规划与成本控制

1、唐龙政 主要内容预备知识 运输优化与成本控制基本理论第一节 物流运输服务选择决策第二节 货物运输调配决策第三节 物流运输线路的优化第四节 行车路线及时刻表的制订第五节 运输工具与货载的最优分配2预备知识一、物流运输组织、规划的基本原理 二、物流运输的质量 三、物流运输的合理化3（一）规模经济（economy of scale） 思考：规模经济存在的原因？有关的固定费用可以按整批货物的质量分摊。4（二）距离经济（economy of distance） 指每单位距离的运输成本随距离的增加而减少。距离越长，固定费用分摊后的值越小，使得每单位距离支付的费用越小。距离经济的合理性类似于规模经济，尤其体

2、现在运输装卸费用上的分摊。 5（一）货运质量事故分类1、重大事故：货损金额在3000元以上的运输质量事故，以及经省级有关部门鉴定为珍贵、尖端、保密物品在运输过程中发生灭失、损坏的事故。2、大事故：货损金额在500-3000元的货运质量事故。3、一般事故：货损金额在50-500元的货运质量事故。4、小事故：货损金额在20-50元的货运质量事故。 货损金额在20元以下的货运质量事故，不作为事故统计上报，但企业要作为内部记录和处理。6物流运输的质量（二）货运质量事故考核指标 6 61010完成货运周转量完成货运周转量货运质量事故次数货运质量事故次数货运质量事故频率货运质量事故频率7物流运输的质量（二

3、）货运质量事故考核指标100%货运总吨数货损吨数货损率100%货运总吨数货差吨数货差率8物流运输的质量（二）货运质量事故考核指标100%100%货运总收入金额货运总收入金额质量事故赔偿金额质量事故赔偿金额货运质量事故赔偿率货运质量事故赔偿率100%100%完成总货运量吨数完成总货运量吨数的货运量吨数的货运量吨数按托运要求的时间完成按托运要求的时间完成完成运量及时率完成运量及时率9物流运输的合理化10（一）合理运输的概念（二）不合理运输的表现形式（三）运输合理化的措施物流运输的合理化（一）合理运输的概念 合理运输（Reasonable Transportation）： 11物流运输的合理化（二）

4、不合理运输的表现形式12对流运输迂回运输重复运输倒流运输过远运输运力选择不当无效运输表现形式13甲乙丙丁对流运输1、对流运输是指同类的或可以互相代替的货物的相向运输，它是不合理运输最突出、最普遍的一种。主要有两种表现形式：（1）明显对流（2）是隐蔽对流派生形式：倒流运输，即同一批货物或同批中的一部分货物，由发运站至目的站后，又从目的站往发运站方向运输表现形式14迂回运输迂回运输不经过最短路径的绕道运输，“近路不走走远路”。表现形式15甲乙丙3、重复运输-出现不必要的中转 指同一批货物由产地运抵目的地，没经任何加工和必要的作业，也不是为联运及中转需要，又重新装运到别处的现象。 重复运输是因物流仓

5、库设置不当或计划不周使其在中途卸下，导致增加运输环节、浪费运输设备和装卸搬运能力，延长运输时间的不合理运输方式。表现形式16甲乙丙4、倒流运输 指同一批货物或同一批中的部分货物，由始发站运往目的站，又从目的站往始发站方向运输。表现形式17过远运输5、过远运输 指凡是可以从附近取得所需物资的供应而不去就近组织，相反却从相反的地方运来，从而造成不必要的浪费，即在相同条件下舍近求远的物品运输方式。未考虑各种运输工具的经济技术特点而进行不适当的选择造成的不合理。常见的有以下几种形式：（1）违反水陆分工使用，弃水走陆的运输。（2）铁路短途运输。（3）水运的过近运输。187、运力选择不当三、物流运输的合理

6、化（三）运输合理化的措施19第一节:物流运输服务选择决策20一、物流运输方式选择的原则（一）安全性原则（二）及时性原则（三）准确性原则（四）经济性原则21二、基于物流总成本比较的运输方式选择22【例7-1】某公司欲将产品从位置A的工厂运往位置B的公司自有仓库，年运量D=700000件，年存货成本为产品价格的30%。公司希望选择使总成本最小的运输方式。据估计，运输时间每减少一天，平均库存成本可以减少1%。各种运输服务方式的有关参数见表7-1。 二、基于物流总成本比较的运输方式选择【例7-1】基于运输成本与库存成本的总成本分析方法：23成本类型成本类型计算公式计算公式铁路运输铁路运输驮背运输驮背运

7、输公路运输公路运输航空运输航空运输运输成本运输成本R D70 000105 000140 000980 000在途库存在途库存ICDT/365362 466241 64486 30134 521工厂存货工厂存货ICQ/2900 000418 500378 000182 250仓库存货仓库存货I(C+R)Q/2903 000420 593380 520190 755总成本总成本 2 235 4661 185 737984 8211387526三、承运人的选择与评价24三、承运人的选择与评价假设一共有N个评价指标。对于某备选承运商来说，客户可通过统计分析、专家打分或其他信息获取途径，得出该承运商的

8、N个指标（取值）得分情况，分别用X1、X2，.Xn表示。 则，该承运商的综合得分为： 25专注专业、持续改善专注专业、持续改善26表7-3 承运商评估报告示例最高分评价标准承运人分数备注13满足接货时间表1313满足搬运109运输时间910运输时间一致性77费率53附加费1高的住宅搬运5运营比率396.5增长4收益性33索赔频率33索赔解决310账单错误79跟踪能力711设备可用性l无平台装货卡车100总分72第二节 货物运输调配决策一、多起讫点间的直达运输二、存在中间转运的物资调配三、图上作业法27表上作业法一、多起讫点间的直达运输对于多点间直达运输问题，描述如下：28 a1 a2 am b

9、1 b2 bn Cij Xij 供供 应应 地地 需需 求求 地地 图7-1 多点之间的物资运输调拨问题示意图一、多起讫点间的直达运输 销地销地产地产地B1B2Bn产量A A1 1x x1111x x1212x x1n1na a1 1A A2 2x x2121x x2222x x2n2na a2 2A Am mx xm1m1x xm2m2x xmnmna am m销量销量b b1 1b b2 2b bn n29一、多起讫点间的直达运输（一）产销平衡的运输问题（ai= bj）1产销平衡运输问题数学模型30 一、多起讫点间的直达运输（二）运输问题数学模型的特点31专注专业、持续改善专注专业、持续改

10、善32 一、多起讫点间的直达运输专注专业、持续改善专注专业、持续改善33 min f = 6x11+4x12+6x13+6x21+5x22+5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij0 (i=1,2；j=1,2,3）一、多起讫点间的直达运输（二）运输问题数学模型的特点专注专业、持续改善专注专业、持续改善34 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 一、多

11、起讫点间的直达运输（二）运输问题数学模型的特点专注专业、持续改善专注专业、持续改善35模型系数矩阵特征一、多起讫点间的直达运输（二）运输问题数学模型的特点、 西北角法 最小元素法 沃格尔法（vogel）2、解的最优性检验（判断是否为最优调运方案） 闭回路法 位势法（对偶变量法）3、解的改进4、重复2、3两步，经有限次调整，得到最优解。 36一、多起讫点间的直达运输（三）用表上作业发求解运输问题的基本步骤 销地销地产地产地B B1 1B B2 2B B3 3B B4 4产量A A1 11616A A2 21010A A3 32222销量销量8 81414121214144837412431110

12、28511961、确定初始基本可行解西北角法8864814（三）用表上作业发求解运输问题的基本步骤一、多起讫点间的直达运输 销地销地产地产地B B1 1B B2 2B B3 3B B4 4产量A A1 11616A A2 21010A A3 32222销量销量8 8141412121414483841243111028511961、西北角法得到的初始调运方案为：8864814总运输费用为：372（怎么计算？）（三）用表上作业发求解运输问题的基本步骤一、多起讫点间的直达运输 销地销地产地产地B B1 1B B2 2B B3 3B B4 4产量A A1 11616A A2 21010A A3 32

13、222销量销量8 81414121214144839 销地销地产地产地B B1 1B B2 2B B3 3B B4 4产量A A1 11616A A2 21010A A3 32222销量销量8 814141212141448401、确定初始基本可行解沃格尔（Vogel）法（三）用表上作业发求解运输问题的基本步骤一、多起讫点间的直达运输 销地销地产地产地B B1 1B B2 2B B3 3B B4 4产量行罚数A A1 11616A A2 21010A A3 32222销量销量8 814141212141448列罚数 销地销地产地产地B B1 1B B2 2B B3 3B B4 4产量A A1

14、11616A A2 21010A A3 32222销量销量8 8141412121414484243 销地销地产地产地B B1 1B B2 2B B3 3B B4 4产量A A1 11616A A2 21010A A3 32222销量销量8 814141212141448 2、解的最优性检验闭回路法44 销地销地产地产地B B1 1B B2 2B B3 3B B4 4产量A A1 11 12 21616A A2 21 1- 1- 11010A A3 3101012122222销量销量8 814141212141448检验数计算结果（三）用表上作业发求解运输问题的基本步骤一、多起讫点间的直达运输

15、 2、解的最优性检验位势(对偶变量)法45 销地销地产地产地B B1 1B B2 2B B3 3B B4 4产量uiA A1 11616 u1A A2 21010 u2A A3 32222 u3销量销量8 814141212141448vjv1v2v3v4（三）用表上作业发求解运输问题的基本步骤一、多起讫点间的直达运输 2、解的最优性检验位势(对偶变量)法46 销地销地产地产地B B1 1B B2 2B B3 3B B4 4产量uiA A1 11616 u1( )A A2 21010 u2( )A A3 32222 u3 销量销量8 81414121214144848vjv1 ( )v2 (

16、)v3 ( )v4 ()（三）用表上作业发求解运输问题的基本步骤一、多起讫点间的直达运输47 销地销地产地产地B B1 1B B2 2B B3 3B B4 4产量A A1 11616A A2 21010A A3 32222销量销量8 814141212141448练习：求解如下运输问题48 销地销地产地产地B B1 1B B2 2B B3 3B B4 4产量A A1 18 8A A2 25 5A A3 35 5销量销量4 43 35 56 6要求：用三种方法求出初始方案，用两种方法对最小元素法得到的初始方案进行检验，如果初始方案不是最优，请调整到最优。1总产量大于总销量：则增加一个假想的销地B

17、n+1，其销量为：2总销量大于总产量：则增加一个假想的产地Am+1，其产量为：49njjmiinbab111miinjjmaba111njjmiiba11miinjjab11（四）产销不平衡问题一、多起迄点间的直达运输50 销地销地产地产地B1B2BnBn+1(贮存)产量A A1 1x x1111x x1212x x1n1nx x1.n+11.n+1a a1 1A A2 2x x2121x x2222x x2n2nx x2.n+12.n+1a a2 2A Am mx xm1m1x xm2m2x xmnmnx xm.n+1m.n+1a am m销量销量b b1 1b b2 2b b3 3b bn

18、 n a ai i- - b bj j（四）产销不平衡问题一、多起迄点间的直达运输二、存在中间转运的物资调配51 t1 t2 tm b1 b2 bn Ckij Xkij 供应地供应地 需求地需求地 a1 af 中转站中转站 二、存在中间转运的物资调配目标函数为：约束条件为：（1）配送量生产能力的限制： k=1，2，f； （2）流通中心发送能力的限制： i1，2，m；（3）满足零售店需求量： j=1，2，n；（4）变量非负：52minjkijkijfkXCZ111minnjkkijmiaX11njikijfktX11fkjkijmibX110kijX（二）数学模型二、存在中间转运的物资调配例7-

19、2某公司生产变压器，一个工厂在A市，每天生产能力为150 ，另一个工厂在B市，每天生产能力为200 。需求点C市和D市的需求量均为130。公司还需要两中间转运站E市和F市进行整合运输。各点间运输单位费用见表7-4。试确定从工厂到需求点的最优路线。 53二、存在中间转运的物资调配（三）求解方法 1、将运输模型转为简单的运输问题 （1）增加一虚拟的行或列来平衡需求 （2）构造一个包括所有城市（起点、终点和中间点）作为供需点的运输表（包括虚拟列）。 （3）根据表7-5的规则，得到最终运输表转运问题中转运问题中点的性质点的性质在运输表中的在运输表中的供应值供应值在运输表中的在运输表中的需求值需求值供应

20、点供应点起始供应起始供应+总供应总供应总供应总供应转运点转运点总供应总供应总供应总供应需求点需求点总供应总供应起始需求起始需求+总供应总供应空空 点点0起始供应起始需求起始供应起始需求54需求和供应量确定准则需求和供应量确定准则专注专业、持续改善专注专业、持续改善55表7-6 最终运输表二、存在中间转运的物资调配（三）求解方法专注专业、持续改善专注专业、持续改善56表7-7 初始调运方案二、存在中间转运的物资调配（三）求解方法三、图上作业法 57（一）图上作业法要解决的问题回顾一下什么是对流运输？5820303020243(20)(20)(30)(30)这是对流这是对流20303020243(

21、20)(20)(30)(30)(10)什么又是迂回运输呢？59206040402463(20)(20)(40)圈长：圈上每一条边的长度之和（记为 l）l =15 先用“丢边破圈”方法，得到无圈图，再产生一个没有对流的方案。内圈长 l内=8外圈长 l外=4是最优解码？8,2ll 内不是最优的.称为迂回运输调整方案：对内圈各流量中最小调运量，进行反向调运(40)(20)(20)准则：内外圈长都小于圈长的一半的无对流的调运方案 为最优方案67.22llll外内此时为最优调运方案三、图上作业法1、交通图的符号 发点用“ ”表示，并将发货量记在里面，收点用“ ”表示，并将收货量记在里面。两点间交通线的长

22、度记在交通线旁边。2、调运物资的流向图 物资调运的方向（流向）用“ ”表示，并把 “ ” 按调运方向画在交通线的右边，把调运物资的数量记在“ ”的右边并加上括号。在交通图成圈时，若运输方向沿逆时针方向，则需将流向“ ”画在圈外，称为外圈流向，反之，若运输方向沿顺时针方向，则需将流向“ ”画在圈内，称为内圈流向，60（二）交通图三、图上作业法 1、交通图不含圈 没有对流运输即是最优方案。61（三）基本步骤三、图上作业法6252378135A1A2B1A3B2B3A4B4(5)(7)(1)(2)(1)(5)(2)（三）基本步骤三、图上作业法63（三）基本步骤三、图上作业法64 销地销地产地产地B

23、B1 1B B2 2B B3 3B B4 4产量A A1 15 57 73 3A A2 23 32 23 3A A3 34 44 43 31 1销量销量2 23 31 11 17（三）基本步骤三、图上作业法653131132A1A2B1A3B2B3B475344432(3)(1)(2)(1)(1)（三）基本步骤（三）基本步骤三、图上作业法663131132A1A2B1A3B2B3B475344432(3)(1)(1)(1)(1)(2)(2)(1)（三）基本步骤三、图上作业法 销地销地产地产地B B1 1B B2 2B B3 3B B4 4产量A A1 12 21 13 3A A2 22 21

24、13 3A A3 31 11 1销量销量2 23 31 11 1767最优调运方案（三）基本步骤三、图上作业法练习：682030A30502070100206030BCDEFGHI234523251813(20)(10)(50)(20)(80)(60)(20)(30)（三）基本步骤三、图上作业法练习：692030A30502070100206030BCDEFGHI234523251813(20)(10)(50)(20)(80)(60)(20)(30)(30)(40)(20)（三）基本步骤 2、交通图含圈第三节 物流运输线路的优化一、起迄点不同的单一路线优化二、起迄点重合的单一路线优化70一、起

25、迄点不同的单一路线优化 71AB1B2B3C1C2C3D1D2E3541584642469751242（一）动态规划法（逆序递推）72一、起迄点不同的单一路线优化n=4n=3n=2n=1AB1B2B3C1C2C3D1D2E3541584642469751242（二）标号法（Dijkstra方法）例7-373OABCDET225417443175起点终点OABCDET225417443175起点终点图7-5 运输网络图一、起迄点不同的单一路线优化表7-8 Dijkstra算法步骤表74二、起迄点重合的单一路线优化（一）旅行商问题（TSP）模型1、问题描述75 C A B D 38 18 31 2

26、2 27 45 444241242221141211.xxxxxxxxxXs0382745380183127180224531220ijCninjijijXCZ11min专注专业、持续改善专注专业、持续改善76二、起迄点重合的单一路线优化（一）旅行商问题（TSP）模型 2、解决办法 枚举、分支定界、现代优化方法（遗传算法等）启发式算法。 贪婪算法： 选择距离出发点最近的顾客位置； 再从剩下的位置中选距离已选择的位置最近的顾客位置。 如果所有位置都被选择了，则停止，否则返回。 C A B D 38 18 31 22 27 45 专注专业、持续改善专注专业、持续改善77（二）中国邮递员问题预备知识

27、：图论的相关概念“顶点”表示某对象节点（设施地点或企业单位）。“边”表示对象之间的某种特性（如距离）。边上的非负数字称为“权”。以V为顶点的边的数目称为顶点V的“次”。次为奇数的点，称为奇点；次为偶数的点，称为偶点。由点、边交替构成的序列称为“链”；起点与终点相同的链就称为“圈”。二、起迄点重合的单一路线优化专注专业、持续改善专注专业、持续改善78（二）中国邮递员问题预备知识：图论的相关概念二、起迄点重合的单一路线优化（二）中国邮递员问题1确定可行方案（如果有奇点存在 ）79 V2 V9 5 9 4 3 4 2 4 5 6 4 3 V4 V8 V6 4 V5 V3 V1 V7 V3 V1 V2

28、 V44 V5 V6 V7 V8 V9 二、起迄点重合的单一路线优化图图7-8 街道图街道图 图图7-9 加重复边后的街道图（可行方案）加重复边后的街道图（可行方案） 专注专业、持续改善专注专业、持续改善80（二）中国邮递员问题2判断最优方案（两条标准） V2 V3 V44 V9 3 5 5 4 6 9 2 3 3 4 4 4 4 V7 V6 V5 V8 V1 V2 V3 V44 V9 3 5 5 4 6 9 2 3 3 4 4 4 4 V7 V6 V5 V8 V1 V2 V3 V4 V9 3 5 5 4 6 9 2 3 4 4 4 4 V7 V6 V5 V8 V1 （a）调整方案一）调整方案

29、一 （b）调整方案二）调整方案二 （c）调整方案三（最佳方案）调整方案三（最佳方案） 第四节 行车路线及时刻表的制定81一、运输路线及时刻表制订的原则1同一车辆服务的客户按距离聚类82 仓 库 仓 库 2避免行车路线交叉3尽可能使用大载重量车辆，减少出车数量4取货/送货混合安排5从距仓库最远的站点开始设计线路83图7-13 合理与不合理的行车线路一、运输路线及时刻表制订的原则二、行车路线制订的扫描法1、基本原理 先以仓库(物流中心)为原点，将所有需求点的极坐标算出，然后依角度大小以逆时针或顺时针方向扫描，若满足车辆装载量即划分为一群，将所有点扫描完毕后在每个群内用最短路径法求出车辆最佳行驶路径

30、。2、基本步骤 第一步：求出各客户点的极坐标。 第二步：扫描划分客户群。 第三步：确定每辆车的最佳路径（TSP算法 ）。84专注专业、持续改善专注专业、持续改善85二、行车路线制订的扫描法【例7-4】某运输公司为其客户企业提供取货服务，货物运回仓库集中后，将以更大的批量进行长途运输。所有取货任务均由载重量为10吨的货车完成。现在有13家客户有取货要求，各客户的去货量、客户的地理位置坐标见表7-10。运输公司仓库的坐标为（19.50，5.56）。要求合理安排车辆，并确定各车辆行驶路线，使总运输里程最短。 86 3 2 2.4 2.8 3.11.8 2.5 2.25 2.6 2.11.5 1.9

31、1.6 1#线路 2#线路 3#线路 11 12 9 10 7 8 2 1 5 4 3 13 6 0 二、行车路线制订的扫描法三、行车路线制订的节约法基本思想：如果将运输问题中的两个回路合并成一个回路，就可缩短线路总里程（即节约了距离），并减少了一辆卡车。87 COA CBO A B O 仓库 A B O 仓库 （a）初始路线 总里程= COA + CAO + COB + CBO CAO COB （b）将两个站点合并成同一线路 总里程= COA + CAB + CBO CAB COA CBO 图7-15 节约法的图形描述专注专业、持续改善专注专业、持续改善88【例7-5】某配送中心要为13个客

32、户提供配送服务，配送中心的位置、客户的坐标及客户的订单规模见表7-11。配送中心共有4辆卡车，每辆车的载重量是200件。 由于送货成本与车辆行驶总里程之间密切相关，公司经理希望获得总行驶距离最短的方案。如何分配客户？如何确定车辆行驶路径？ 三、行车路线制订的节约法89三、行车路线制订的节约法1确定距离方阵9022)()(BABAAByyxxC三、行车路线制订的节约法2计算节约矩阵91三、行车路线制订的节约法3将客户划归到不同的运输路线92三、行车路线制订的节约法93三、行车路线制订的节约法94三、行车路线制订的节约法95 11 7 8 9 10 12 13 5 2 3 4 6 1 0 X Y

33、三、行车路线制订的节约法第五节 运输工具与货载的最优分配一、航线配船优化问题二、多车多品种货载配车优化96一、航线配船优化问题（一）问题概述 设船公司经营n条航线。第j条航线上规划期正向货运量预测为Qj，公司拥有装载能力分别为Ni的m种船型；i型船的船舶艘数为mi，一艘i型船在j航线上规划期可以完成的最大往返航次数为nij；一艘i型船在j航线上完成一个往返航次所花费的全部成本为kij。要求将这些船合理地安排在这几条航线上，使公司的经济效益最好。 97专注专业、持续改善专注专业、持续改善98一、航线配船优化问题（二）数学模型的建立1参数说明I 船型编号，i=1,2，m；J 航线编号，j=1,2，

34、n；Xij i型船在j航线上每季度完成的往返航次数，是决策变量；Yj j航线上未被船舶承运的货物量，也是决策变量；Kij 每艘i型船在j航线上完成一个往返航次所花费的运营成本； j航线上单位货物未被承运产生的费用损失； 每艘i型船在j航线上每季度可以完成的最大往返航次数； i型船的集装箱装载能力； i型船的船舶数量； j航线的正向运量。 jijniNimjQ专注专业、持续改善专注专业、持续改善99一、航线配船优化问题（二）数学模型的建立2目标函数3约束条件jnjjijminjijyxKk 111min0, 0111jijjjijmiiiijnjijyxQyxNmxn专注专业、持续改善专注专业、

35、持续改善100一、航线配船优化问题（三）航线配船优化举例【例7-6】假设某船公司拥有3种吨位的集装箱船舶共30搜，分别是1500TEU的8艘、850TEU的12艘、500TEU的10艘。现开辟班轮航线6条，各航线季度集装箱运输量、船舶在每条航线每季度最多能完成的航次数、每艘船在各航线每往返航次的成本（万元）以及每条航线发现的机会成本（万元/TEU）如表7-17至表7-19所示。求不同航线的船舶最佳配置方案。 一、航线配船优化问题（三）航线配船优化举例101102一、航线配船优化问题（三）航线配船优化举例专注专业、持续改善专注专业、持续改善103解：（1）目标函数： 一、航线配船优化问题3323

36、13232221213121115 .202528125. 020242515. 0182430minxxxyxxxyxxxK2414324251 . 0 xxy26165352515434283215. 02030351 . 05 .18xxyxxxyx636125. 032yx专注专业、持续改善专注专业、持续改善104解：（2）约束条件： 一、航线配船优化问题且均为整数, 0, 0,7000500850150030005008501500450050085015005000500850150080005008501500600050085015001021514141411231214131413182131213121613611636261653525154342414333231323222121312111363534333231262524232221161514131211yyxxyxxxyxxxyxxxyxxxyxxxyxxxxxxxxxxxxxxxxxxxxx专注专业、持续改善专注专业、持续改善105解：（3）求解结果一、航线配船优化问题二、多车多品种货载配车优化（一）问题描述 已知有m辆零担作业车，其载重量和容积分别为G1，G2，Gm和V1，V2，Vm。现有n批货物H1，H2，Hn，其重量和体积分别为g1，g2，gn和v1，v2，vn。 试确定一个