《物流运筹方法与工具》第3版 课件 模块六单元二 线路选择的最短路法

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

CONTENTS物流运筹方法与工具概述物流决策分析物流资源配置规划物流任务指派运输方案优化运输路径规划物流项目计划物流需求预测库存水平控制模块六模块二模块三模块四模块五模块七模块八模块九模块一模块六运输路径规划运输路径规划概述应用举例线路选择的最短路法运输网流量分布的最大流法线路网布局的最小树法车辆配送路线的安排单元四单元三单元一单元二单元六单元五知识点1．理解图、网络、链、连通图、图模型的概念。2．理解最短路问题的含义；掌握求解最短路问题的Dijkstra算法步骤。3．理解可行流、最大流、增广链的概念；掌握求解最大流问题的标号算法步骤。4．理解最小树、图的中心和重心的含义；掌握最小树问题的逐步生长法步骤。5．理解单、多车辆配送路线安排问题及启发式算法的含义。6．掌握单回路路线优化的最近邻点法和最近插入法的求解步骤。7．掌握多回路路线优化的扫描法、节约法的求解步骤。本单元知识点能力点、素质点能力点：1．能够把相应的实际问题归结为最短路问题，并能够熟练运用Dijkstra算法求解。2．能够把相应的实际问题归结为最大流问题，并能熟练运用标号算法求解。3．能够把相应的实际问题归结为最小树问题，并能熟练运用逐步生长法求解。4．能够把相应的实际问题归结为回路运输路线优化问题，并能熟练运用最近邻点法和最近插入法、扫描法、节约法求解。素质点：1．提高对大数据及云计算、物联网、人工智能等新科技的应用兴趣，勇于实践创新。2．加强“互联网+高效物流”和“降本增效”理念。单元二线路选择的最短路法

一、最短路的含义

二、最短路的Dijkstra算法线路选择问题：最短路问题的一般提法：一、最短路的含义在已知的物流网络（通过各段线路所需的时间、距离或费用为已知）中，有一货物发点（供应点）对一货物收点（客户）专门送货，在这种直送情况下找出货物运送所需的最少时间、最短距离或最少费用的路径问题。二、最短路的Dijkstra算法用dij表示图中两点i与j相邻时的距离，即边[i,j]的长度。若点i与j不相邻时，dij=∞。显然dii=0。用

表示从点s到点i的最短路的长度。现在要求从点s到点t的最短路，相应的Dijkstra算法步骤如下：1从点s出发，逐一地给其它的点i标上记号：lsi

，把lsi

的数值标注在点i旁边的小方框内，表示点i已标号（标号说明点s到点i的最短路已找到）。首先，给点s标号lss=0。二、最短路的Dijkstra算法2找出与点s相邻的点中距离最小的一个，若有几个点同时达到最小，就都找出来。设找出的点为r，将lsr=lss+dsr

的值标注给点r，表明点r也已标号，同时把边[s,r]加粗。3从已标号的点出发，找出与这些点相邻的所有未标号的点。把每个已标号点旁标注的数字和与之相邻的点到这个已标号点间的距离加起来，从所有这些和中选出一个最小的来。再找出最小和对应的未标号点，然后给这个未标号点比如q标号：Lsq=lsk+dkg,，同时加粗边[k,q]。二、最短路的Dijkstra算法4重复第（3）步，直到给点t标上号

，而且相应的t的关联边加粗为止。例6-1

用Dijkstra算法求图6-1中从

到

的最短路。v1v2v3v4v5v6v752762247136二、最短路的Dijkstra算法v4v1v2v3v5v6v7527622471360图6-1（a）二、最短路的Dijkstra算法图6-1（b）v1v2v3v4v5v6v75276224713620二、最短路的Dijkstra算法图6-1（c）v1v2v3v4v5v6v752762247136205二、最短路的Dijkstra算法图6-1（d）v1v2v3v4v5v6v7527622471362605二、最短路的Dijkstra算法图6-1（e）v1v2v3v4v5v6v752762247136260577二、最短路的Dijkstra算法图6-1（f）v1v2v3v4v5v6v75276224