情境8--配送运输作业设计.ppt

学习目标 工作任务描述 二、配送运输线路设计 线路设计的意义 配送线路设计就是整合影响配送运输的各因素，适时适当地利用现有的运输工具和道路状况，及时、安全、方便经济地将客户所需的不同物资准确送到客户手中，以便提供优良的物流配送服务。在运输线路设计中，需根据不同客户群的特点和要求，选择不同的线路设计，最终达到节省时间、缩短运行距离和降低运行费用的目的。 最短路径设计 1．最短路径设计的适用范围 在配送路线设计中，当由一个配送中心向一个特定的客户进行专门送货时，客户的需求量接近或大于可用车辆的额定载重量，需专门派一辆车一次或多次送货。如果送货成本和配送路线有较强的相关性，而与其他因素关联度不大时，可以采取路程最短为设计目标。由于这种设计方法忽略了许多不易计算的影响因素，因而容易掌握，方法简单。 计算网络中两点间最短路线的方法有许多种，目前公认的最好的方法是由Dijkstra于1959年提出来的，该种方法也叫标号法。 用dij表示运输线路中两点i与j相邻时的距离，用Lsi表示从s到点i的最短路线长度。 现要求从点ps到点pt的最短路线，该算法步骤如下： （1）从初始点ps出发，逐一地给其他点标号：给点vi标上（αi，βi），其中αi为初始点到点pi的最短路长，即αi =Lsi；βi为点pi在最短路线上来源点（亦即pi是从哪一点来的）的代号；Lsi的数值标注在点pi的旁边的小方框内；至此表示点pi已标号。首先给初始点标号：（0，0），Lss=0。 2．最短路径设计的步骤（续） （2）找出与点ps相邻点中路长最小的一个，若几个点同时达到最小，就都找出来。设找出的点为r，将（αr，βr）（其中βr=s）和Lsr=LSS+dsr的值标注给点pr，表明点pr也已标号。 （3）从已标号的点出发，找出这些点相邻的所有点。把每个已标号点（如点pi）旁标注的数字[如（αi，βi）和Lsi]和与之相邻的点（如点pj）到这个已标号点（如点pi）间的距离dij [边（pi，pj）的长度]加起来，从所有这些和中选出一个最小的来，如这个最小的和是Lsk+dkq。再找出最小和对应的末标号点，比如q（当有几个都为最小时，把它们对应的不同的末标号的都找出来），然后给这个点（比如q点）标号：（αq，βq）（其中βq =k）和Lsq=Lsk+dkq。 2．最短路径设计的步骤（续） （4）重复第（3）步，直到给点pt标上号（αt，βt）和Lst为止。 （5）从点pt开始根据各点的标号（αi，βi）反向寻找点ps到点pt的最短路线所关联的边（pi，pj），并将其加粗。 上面得到的由加粗边构成的点ps到点pt的路径即为点ps到点pt间的最短路线，其长度为Lst。 3．最短路径设计的应用举例 例：已知如图10-1所示的交通网，用DijkStra算法求图中从点P1到点P8的最短路线。 解：（1）从p1出发，首先给p1标号（0，0），L11=0（标注于图10-1中的小方框中）； (2)对点p1，与其相邻的末标号点有p2,p3,p4三点，min(L11+d12,L11+d13,L11+d14)= min(0+8, 0+2,0+11)=2, 故给三个点中对应最小值的点p3标号（2，1），L13=2； （3）对已标号点p1,p3，与其相邻的末标号点有p2,p4,p6三点，min(L11+d12,L13+d32,L11+d14, L13+d34,L13+d36)=min(0+8,2+4,0+11,2+2,2+5)=4,故给三个点中对应最小值的点p4标号（4，3），L14=4； （4）对已标号点p1,p3,p4，与其相邻的末标号点有p2,p6,p7三点，min(L11+d12,L13+d32,L13+d36,L14+d46,L14+d47) =min(0+8,2+4,2+5,4+1,4+12)=5,故给三个点中对应最小值的点p6标号（5，4），L16=5； （5）对已标号点p1,p3,p4,p6，与其相邻的末标号点有p2,p5,p7,p8四点，min(L11+d12, L13+ d32,L16+d65,L16+d67,L14+d47,L16+d68) =min(0+8,2+4,5+2,5+4,4+12,5+8)=6,故给四个点中对应最小值的点p2标号（6，3），L12=6； （6）对已标号点p1,p2,p3,p4,p6，与其相邻的末标号点有p5,p7,p8三点，min(L12+d25, L16+ d65,L16+d67,L14+d47,L16+d68) =min(6+9,5+2,5+4,4+12,5+8)=7,故给三个点中对应最小值的点p5标号（7，6），L15=7； （7）对已标号点p1,p2,p3,p4,p5,p6，与其相邻的末标号点有p7,p8两点，min(L16