《物流运筹方法与工具》第3版 课件 模块六单元六 应用举例

物流运筹方法与工具（第3版）目录

CONTENTS物流运筹方法与工具概述物流决策分析物流资源配置规划物流任务指派运输方案优化运输路径规划物流项目计划物流需求预测库存水平控制模块六模块二模块三模块四模块五模块七模块八模块九模块一模块六运输路径规划运输路径规划概述应用举例线路选择的最短路法运输网流量分布的最大流法线路网布局的最小树法车辆配送路线的安排单元四单元三单元二单元六单元一单元五知识点1．理解图、网络、链、连通图、图模型的概念。2．理解最短路问题的含义；掌握求解最短路问题的Dijkstra算法步骤。3．理解可行流、最大流、增广链的概念；掌握求解最大流问题的标号算法步骤。4．理解最小树、图的中心和重心的含义；掌握最小树问题的逐步生长法步骤。5．理解单、多车辆配送路线安排问题及启发式算法的含义。6．掌握单回路路线优化的最近邻点法和最近插入法的求解步骤。7．掌握多回路路线优化的扫描法、节约法的求解步骤。能力点、素质点能力点：1．能够把相应的实际问题归结为最短路问题，并能够熟练运用Dijkstra算法求解。2．能够把相应的实际问题归结为最大流问题，并能熟练运用标号算法求解。3．能够把相应的实际问题归结为最小树问题，并能熟练运用逐步生长法求解。4．能够把相应的实际问题归结为回路运输路线优化问题，并能熟练运用最近邻点法和最近插入法、扫描法、节约法求解。素质点：1．提高对大数据及云计算、物联网、人工智能等新科技的应用兴趣，勇于实践创新。2．加强“互联网+高效物流”和“降本增效”理念。单元六应用举例一、车辆运输路线选择二、运输网送货能力分析三、运输网络中心和重心确定四、配送路线安排及效益评估一、车辆运输路线选择王健是一家运输公司的车辆调度员。他的公司已经签订了一项运输合同，要把沈阳的一批货物运送到北京附近地区。王健查看了这两个城市之间可选择的行车路线的地图，然后绘制了公路网络图，并在每一条公路上标出了里程数（公里），如图6-33所示。王健的任务是找出沈阳到北京的最短路线。一、车辆运输路线选择11023456789650沈阳北京01006003001502756005004001001504001252001502001753503001752752752002501009-108-106-9-102-6-9-105-8-104-6-9-107-8-103-5-8-101-4-6-9-106-34两城市间的交通网线王健运用Dijkstra算法寻找最短路线的过程如下：1．从终点开始逐步逆向推算：与终点10连接的有两个点，即9和8，先从9开始计算。9到10只有一条路线，因此没有选择余地，9-10就是最短的路线，它的里程为100，写在节点9上方的框中，并注上9-10。同样8至10也只有一条路线，最短路线为8-10，里程为150，也按相同方式记上。2．再看节点6：与6连接的只有一个节点9，因此最短路线为6-9，6至9的里程为200，而9至终点10的最短里程为100，因此6至终点的最短里程为200+100=300。记入方式同上，方框上注上6-9-10。一、车辆运输路线选择王健运用Dijkstra算法寻找最短路线的过程如下：3．再看节点5：与5连接的节点有9、8两个，5至9再至终点的最短里程为400+100=500，5至8再至终点的最短里程为250+150=400。400<500，所以5至终点的最短里程为400，写在节点5上方的方框中，方框上再注上5-8-10。点7至终点的最短里程为125+150=275。记入格式同上。4．再看节点4：与4连接的节点有5、6、7三个。4至6再到终点的最短里程为200+300=500，4至5再到终点的最短里程为175+400=575，4至7再到终点的最短里程为275+275=550。三个里程中以500为最小，所以把500写在节点4上方的方框中，方框上注上4-6-9-10。一、车辆运输路线选择王健运用Dijkstra算法寻找最短路线的过程如下：用同样的方法，算出了节点2到终点的最短里程为600，节点3到终点的最短里程也为600。记入的格式同上。5．最后看节点1，与节点1连接的路线有3条：1至2再到终点的最短里程100+600=700；1至4再到终点的最短里程150+500=650；1至3再到终点的最短里程175+600=775。；三个里程中以650为最小，这就是从沈阳到北京的最短里程，而对应的最短路线为1-4-6-9-10。如图6-34中加粗线所示。一、车辆运输路线选择二、运输网送货能力分析

甲市有一生产厂家生产A原料供应给乙市市场需求，该原料的分拨任务外包给了顺通运输公司。现在生产厂家为了应对市场需求高锋的到来，确保需求高锋期间有足够数量的原料销售，要求运输公司在需求高锋到来之前，一周内将22吨原料货物准时运送到乙市市场。

如果运输公司不能按时将22吨原料送到乙市市场，将影响来年生产厂家与运输公司的合同是否续约问题。为了保证厂家运输任务的及时、可靠，运输公司经理要求调度人员对本公司的运输网络送货能力进行评估，以便做好相应的准备安排工作。二、运输网送货能力分析运输网送货能力分析过程如下：调度人员首先绘制了本公司运输网络图。101041151124甲市厂家610718乙市市场3图6-34运输专线网络图二、运输网送货能力分析运输网送货能力分析过程如下：运输网络送货能力评估问题转化为求解最大流问题。1．任意先选一条从甲市到乙市的送货线路，如：甲→1→4→乙，最多可安排送货6吨，在图上作标记，图中线路旁的数字为

，见图6-35。2．再选第二条从甲市到乙市的送货线路，可选：甲→2→4→乙，最多可安排送货10吨，在图上作标记，见图6-35。二、运输网送货能力分析10（5）10411（10）5（5）1124甲市厂家6（6）10（10）7（6）18(6)(10)乙市市场3图6-36线路流量调整1二、运输网送货能力分析3．再选第三条从甲市到乙市的送货线路，可选：甲→3→乙，最多可安排送货5吨，在图上作标记。目前流量安排情况见图6-35所示，此时，支线甲→1，甲→2，3→乙已无剩余送货能力，这三条支线不再考虑安排送货，可从图中去掉，见图6-36所示。图6-37线路流量调整27(6)(1)18(6)(10)(1)(1)10(5)(1)(1)10(0)4（1）11(10)(1)1（1）124甲市厂家乙市市场3二、运输网送货能力分析4．再选第四条线路：甲→3→2→4→乙，最多可安排送货1吨，在图上标记，见图6-36。5．再选第五条线路：甲→3→1→4→乙，最多可安排送货1吨，在图上标记，见图6-36。现在通往乙市市场的最后一条支线4→乙已无多余的送货能力，因此该网络最大流量值已经求得，各支线流量分配如图6-37所示。二、运输网送货能力分析10（10）10（7）10（0）4（1）11（11）5（5）1（1）124甲市厂家6（6）7（7）18（18）乙市市场3图6-38

运输网络最大送货量分布方案最大送货量=6吨（1线）+10吨（2线）+5吨（3线）+1吨（4线）+1吨（5线）=23吨。23吨>22吨，测算结果表明，顺通运输公司现有的运输网络能够完成一周内22吨的送货任务，不必另想计划措施。三、运输网络中心和重心确定（一）网络中心图6-39所示为华阳物流公司在某一市区的零担运输网点布局图。其中点表示该公司的营运站点，边表示各站点间已有的交通路线，边旁的数字表示两点间的距离长度（公里）。（1）现在公司要确定能保证各站点互通且使运输专线总长度最小的运营线路网。（2）在公司运营线路网中，确定适合建集货中心的站点，保证使离该中心最远的站点往中心仓库送货时所走的路程最短？图6-39地区交通线路图三、运输网络中心和重心确定三、运输网络中心和重心确定所谓图的中心，是在最小树中先分别找出各顶点之间的最大距离，然后在各点的最大距离中找出一最小距离的点，则该点即为图的中心，用数学公式描述，即上述第一个问题很明显是个最小树问题，而第二个问题就是最小树的中心问题。三、运输网络中心和重心确定（1）确定线路总长度最小的公司运营线路网，可以用逐步生长法或破圈法求得最小树，该最小树就是总长度最小的运营网络，如图6-39所示。

图6-40公司运营线路网三、运输网络中心和重心确定居民点V1V2V3V4V5V6V7d(vi)V10356.39.34.569.3V23023.36.31.536.3V35205.38.33.558.3V46.33.35.3031.83.36.3V59.36.38.3304.86.39.3V64.51.53.51.84.801.54.8V76353.36.31.506.3表6-6各点间的最大距离表三、运输网络中心和重心确定得：三、运输网络中心和重心确定（二）网络重心接上述华阳物流公司问题，公司7个营运站点除了上述揽货任务外，还负责各自所在区域的商超百货店的快速消费品配送任务。这些货物由公司中心贮存库提前统一分发给各站点，然后由站点完成配送工作。今已知各站点每周快速消费品的配送量如图6-41所示，那么公司中心贮存库设在哪个站点，能使每周总的运输量为最小？三、运输网络中心和重心确定图6-41图的重心问题三、运输网络中心和重心确定三、运输网络中心和重心确定三、运输网络中心和重心确定表6-7各站点对应的每周总运输量v1122300v5131600v271300v672800v389300v795300v492600三、运输网络中心和重心确定四、配送路线安排及效益评估四、配送路线安排及效益评估上述优化问题利用节约里程法求解如下：四、配送路线安排及效益评估四、配送路线安排及效益评估