第5章-物流配送路线与物流中心的选址

物流运筹学教学课件第5章物流配送路线与物流中心的选址物流配送路线1配送中心的送货规划2物流最大通过能力3物流中心的选址4货物集散中心场地的设置55.1物流配送路线5.15.1.1起点与终点不同的路线的选择只考虑产品配送的运输路线而忽略产品运输车辆的回程，适用于需求点单一的问题。首先要明确配送中心到产品需求点之间的所有可能的路径，了解路线各连接点的具体位置以及两个相邻连结点之间的运输时间、距离或成本，然后从配送中心开始计算各条可能路径的累计运行时间、距离或成本，选择数值最小的点作为确定点。重复上述步骤，直到把所有的产品需求点都包括在确定的路线里为止。狄克斯屈拉（Dijkstra）算法；求从某一点至其他各点之间的最短距离。5.1.1起点与终点不同的路线的选择【例5.1

】

某配送公司要将客户急需的商品从配送中心P运送到商场Q，图5-1表示由起点P到终点Q的路线图，各条弧所对应的数字表示通过该段路线所需时间。试求所需时间最短的路线。5.1.1起点与终点不同的路线的选择解：我们分四个阶段来考虑问题。

第一阶段是由P到B1，B2，B3；

第二阶段是分别由B1，B2，B3到C1，C2，C3；

第三阶段是分别由C1，C2，C3到D1，D2；

第四阶段是分别由D1，D2到Q。5.1.1起点与终点不同的路线的选择n表示由某点到终点之间的阶段数。S表示状态，即在任意阶段所处的状态。S可以取P，B1，B2，B3

，C1，C2，C3

，D1，D2和Qxn（

S

）表示决策变量，它表示当处于状态S处还有n个阶段要走时，下一步所选取的点

fn（

S

）表示现在处于状态S，还有n个阶段要走时，由S到终点Q的最短距离。dn（

S，

xn（

S

））表示从点S到下一部所选的点xn（

S

）的距离。5.1.1起点与终点不同的路线的选择由P到B1，B2，B3的第一阶段共有三种走法：

此时处于状态B1，还有三个阶段要走。由B1至Q的最短距离为

，所以，选这个走法，最短距离为

此时处于状态B2，还有三个阶段要走。由B2至Q的最短距离为

，所以，选这个走法，最短距离为

此时处于状态B3，还有三个阶段要走。由B3至Q的最短距离为

，所以，选这个走法，最短距离为5.1.1起点与终点不同的路线的选择5.1.1起点与终点不同的路线的选择5.1.1起点与终点不同的路线的选择求f4（

P

）的过程是由最后一个阶段开始向前面各阶段计算的过程，也称为逆推n=1时，有：f1（

D1）=1，由D1至Q的最短距离为1，其路线为D1Q

f1（

D2）=12，由D2至Q的最短距离为2，其路线为D2Q

5.1.1起点与终点不同的路线的选择n=2时，有：

由C1至Q的最短距离为4，其路线为C1D2Q

由C2至Q的最短距离为7，其路线为C2D1

Q

由C3至Q的最短距离为7，其路线为C3D2

Q

5.1.1起点与终点不同的路线的选择n=3时，有：

由B1至Q的最短距离为5，其路线为B1C1D2

Q

由B2至Q的最短距离为11，其路线为B2C2D1

Q

由B3至Q的最短距离为8，其路线为B3C1D2

Q

5.1.1起点与终点不同的路线的选择n=4时，有：

由P至Q的最短距离为8，其路线为PB1C1D2

Q

5.1.2起点与终点相同时的路线选择从配送中心出发的产品配送车辆按照一定的路线把所有需求点的货物送达后，返回配送中心。需求点多，分布广首先要确定配送中心与各产品需求点之间的运输距离、时间及成本，然后按照选择标准选定离配送中心最近的一个需求点，再以此确定的点作为另一个起点来确定下一个产品配送的需求点，如此重复操作，直到所有的需求点都在所确定的路线中为止。5.1.2起点与终点相同时的路线选择【例5.2

】某配送公司由配送中心A向全市四个商店B、C、D、E进行药品供应，各需求点相对位置见图5-2，运输距离见表5-1，试选择最佳配送路线。

ABCDEA034484767B340171934C481703431D471934026E6734312605.1.2起点与终点相同时的路线选择配送路线的起点是A，由表5-1第一行看，非零的最小数为34，即A到B点距离最短，为34；再以B点为起点，可以看到表5-1第二行的非零最小数为17，即C点应该在配送路线上，其前一站是B点；再以C点为起点，由表5-1知其第三行中除A，B两点外的距离中31最小，即E距C最近；再以E为起点，由表5-1知第四行以26为最小，即D离E最近。得最短配送路线为：A→B→C→E→D→A总运输距离为：34+17+31+26+47=1555.1.3选择配送路线的节约法到两个站点的配送方法从配送中心P用两辆车分别向站点A1

和

A2

送货，再返回，这时总的行程为：

D1=2d1+2d2若用一辆车，从配送中心P出发，先送货到站点A1，再从站点A1送货到站点A2，然后从站点A2返回配送中心P，即P→A1→A2→P，进行一次巡回送货。这时总的行程为D2=d1+c+d25.1.3选择配送路线的节约法到两个站点的配送方法节约里程：△D=D1-D2=（2d1+2d2）

-（d1+c+d2）=d1+d2

-c

5.1.3选择配送路线的节约法到多个站点的配送方法从配送中心P到多个站点送货时，将其中能够取得最大节约里程的两个站点合并在统一条路线上，进行巡回送货，这样能够获得最大的节约里程，同时在不超过运输车辆载货容量的条件下，设法使这条选定的巡回路线尽可能把其他站点按其所能节约里程的大小纳入到这条路线之中，就可以获得更大的节约里程，这时节约里程法的基本思想。5.1.3选择配送路线的节约法步骤第一步：将各个分店的需求量列成表格，并计算配送中心P至各个站点的最短距离和各个站点之间的最短距离，将这些数据列成表格。第二步：由上述最短距离表，用节约里程法（△D=d1+d2-c）算出各站点之间的节约里程，并将其列成表格。注意：计算节约里程时，可能得出0或负数，这种情况一律写成0。第三步：根据上述节约里程表中节约里程的数据，按由大到小的顺序把它们排列起来。并把它们列成表格，称之为节约里程次序表，以便尽量使节约里程最多的点组合装车配送。第四步：根据节约里程次序表和配送车的载重量、有效容积及可行驶的里程等约束条件，给出配送的近似最佳路线。5.1.3选择配送路线的节约法【例5.3】

有6个站点A1，A2，A3，A4，A5，A6的货运任务，各任务的货运量qi。这些任务由配送中心O发出的载重量4t和2.5t的车辆来完成，中心O到各站点以及各站点之间的最短距离（单位:km）由表5-3给出。试制定合理的车辆行驶路线，以完成上述送货任务。站点A1A2A3A4A5A6qi0.80.71.01.751.101.15OA1A2A3A4A5A6O091212202421A1

0919293330A2

010322933A3

0251925A4

061A5

06A6

05.1.3选择配送路线的节约法解:根据表5-2，利用公式，计算各站点之间的节约里程，得到节约里程表如表5-4所示。A1A2A3A4A5A6A10122000A2

014070A3

07178A4

03840A5

039A6

05.1.3选择配送路线的节约法由表5-4可得节约里程次序表，如表5-5所示。序号(Ai，Aj)△dij序号(Ai，Aj)△dij序号(Ai，Aj)△dij1(A4，A6)406(A1，A2)1211(A1，A4)02(A5，A6)397(A3，A6)812(A1，A5)03(A4，A5)388(A2，A5)713(A1，A6)04(A3，A5)179(A3，A4)714(A2，A4)05(A2，A3)1410(A1，A3)215(A2，A6)05.1.3选择配送路线的节约法根据表5-5逐项考察对应的一对站点Ai和Aj，进行点对之间的连接(Ai，Aj)两点的位置Q=∑qi（t）连接与否A4—A6非线路上点Q=2.9<4A4→A6A6—A5非线路上点，外点Q=4A4→A6→A5A5—A3非线路上点，外点Q=5>4×A2—A3非线路上点Q=1.7<4A2→A3A1—A2非线路上点，外点Q=2.5<4A1→A2→A3A3—A4一点为内点

×A2—A5一点为内点

×A3—A4不同线路上的点，一终点，一起点（除O点）

×5.1.3选择配送路线的节约法载重量为4t的货车：O→A4→A6→A5→O，

货运总重量为4t，总路程为20+1+6+24=51（km）。载重量为2.5t的货车：O→A1→A2→A3→O，

总路程为：9+9+10+12=40（km）。由上可知，此行驶路线的总里程为51+40=91（km）。5.2配送中心的送货规划5.2

5.2.1按最短路径送货如果配送物资属于大件或重载物品，运送距离比较远，属于区域性配送，一般按最短路径送货.区域内的配送点和运送路线一般呈网络结构.最短路径的确定方法可以仿照前面介绍的方法，在各回路中去掉一条线段，使各点到起点的距离小于回路总长度的一半

5.2.1按最短路径送货在安排整零配车时，从树型结构的端点（树叶）开始，逐站向起点站（树根）反向搜索。为了降低成本，配车的原则是先一站配车，后多站配车。因此每条线路进行两次搜索，首先搜索具备一站配车的站点，即送货量达到整车的站点，然后再进行多站配车。如果是计算机自动配车，可建立的数据库。数据库包括各站点的序号、站名、链号、辖区、路程和待送货物的数量。

5.2.1按最短路径送货序号站点名链号路程标志送货量（件）1A128182A210202123A32121204A45101105A5713386A68121137A7883258A810122159

10A0——0—各点的编号，与数据库记录号一致前一点的序号该点与前一点的距离起点端点分叉点

5.2.1按最短路径送货树型结构有4个端点，即A1，A3，A4，A6，因此可在4条路线上进行搜索

5.2.1按最短路径送货假定每车容量是装20件货物，那么各次搜索配车结果为：A3的货物装一车，20件；A7的货物（20件）装一车，余货5件；A1与A2的货物组装一车，共20件；A7（余货）与A8的货物组装一车，共20件；A5和A4的货物组装一车，共18件；A6的货物装一车，13件。

5.2.2环路送货序号站点名链号路程标志送货了量（件）1A11，281182A22，10，320，122123A33，2，4，712，15，72324A42，3，515，102285A53，4，6，710，10，132156A62，5，810，122137A73，3，5，817，13，82158A83，10，6，712，12，82459

10A02，2，820，1200与该站相连的数目相连的站点序号对应的距离起点2点其他站点

5.2.2环路送货主要考虑“汽车装载率高”的目标，其次考虑“路径短”和“单个用户的货物批次少”等目标.汽车空载时，可以按树型结构确定返回配送中心的路线，这便可实现空车路径最短的目标.

5.2.2环路送货以表3-10中的数据为例，假定每车满载可以装30件货物，首先按最短路径配装“满载车”，这种配装结果能达到“装载率最高”，又满足“最短路线”条件.具体结果如下：A1与A2的货物组装一个整车，无余货；A8的30件货物组装一个整车，还剩余15件；A8的15件余A7的15件货物组装一个整车，无余货；A3的30件货物组装一个整车，余货两件.然后进行环路配车和非满载配车，配装结果如下：A3的余货和A4的货物组装一车，28件；A6和A5的货物组装一车，28件.5.3物流最大通过能力5.3

5.3物流最大通过能力主要介绍在不考虑运输里程最小这一条件的情况下，两个供需点或城镇之间车辆的最大通过能力问题。甲、乙两个点之间有很多道路相连接，相互交织成网任务：从相互交错、最大通过能力各不相同的路线中，较快地计算出甲城到乙城的最大通过能力。由外及里以此计算各条从甲城到乙城的路线的最大通过能力，这样才能得出答案。该路段的最大通过能力

5.3物流最大通过能力【例5.4】

求图5-6所示的交通图中从甲城到乙城的最大通过能力。

5.3物流最大通过能力解:由甲城到乙城最外边的路线有两条。（1）甲—A—D—乙；（2）甲—B—乙。在（1）中，A—D这一段最大通过能力为10，而甲—A这一段最大通过能力是40，D—乙这一段最大通过能力为40，均大于10，因此路线（1）的最大通过能力为10。在（2）中，B—乙这一段最大通过能力为10，而甲—B这一段最大通过能力为60，超过了10，因此路线甲—B—乙的最大通过能力也只能是10。于是（1）和（2）这两条从甲到乙最外边的路线的通过能力总共为20。

5.3物流最大通过能力把已经满负荷的道路抹去，并将道路其他没抹去的各段的最大通过能力的数值减去抹去的道路的最大通过能力的数值，然后把差数添在该段道路旁边。于是得到的剩下的由甲地到乙地的交通图如图5-7所示。

5.3物流最大通过能力图5-7中由甲城到乙城最外边的道路为：（3）甲—A—C—D—乙；（4）甲—B—C—乙。仿上述可知：路线（3）的最大通过能力为10，而路线（4）的最大通过能力为20。抹去满负荷的路段，得图5-8。

5.3物流最大通过能力路线（3）与（4）的通过能力总和为30。如图5-8所示，由甲城到乙城已无路可通了，从而可知甲城到乙城的最大通过能力为20+30=50。5.3物流最大通过能力用由外及里的原则，凡是运输能力用完的路段均抹掉，剩下的路段将原运输能力减去已抹去的运输能力的差数写在该段路旁，继续用由外及里的原则，直至图断开成两片，且起点与终点分别各在一片中。5.4物流中心的选址5.4

5.4.1用实验的方法计算质量中心的坐标1.

在一块水平放置的板上有四个质点，按质点所在位置打四个小洞，每个小洞分别挂上与对应质点的质量成比例的砝码，其质量分别为m1，m2，m3，m4（单位：g），然后把栓砝码的线的另一端连接在一起，让它们自由地处于平衡状态，这时，那个线的结点的位置就是四个质点质量中心所在的位置。

5.4.1用实验的方法计算质量中心的坐标C点是当四个悬挂的砝码处于平衡位置时结点的位置，C点的位置就是质量中心的位置。此时，从C到A1，A2，A3，A4四个点的距离分别乘以m1，m2，m3，m4，再求和，得

5.4.1用实验的方法计算质量中心的坐标2.一线段AB，端点坐标分别为A（x1），B（x2），【引例1】设在A处有质量m1，B处有质量m2，求其质量中心的坐标。

5.4.1用实验的方法计算质量中心的坐标设C点是质量中心，坐标为C（xm），则当得最小值

5.4.1用实验的方法计算质量中心的坐标【引例2】设△ABC三个顶点的坐标分别为A（x1，y1），质量为m1；

B（x2，y2），质量为m2；

C（x3，y3），质量为m3；

求△ABC的质量中心的坐标。

5.4.1用实验的方法计算质量中心的坐标设质量中心为M（xm，ym

），先求BC的质量中心P（xp，yp

）

5.4.1用实验的方法计算质量中心的坐标连接AP，求A（质量为m1），P（质量为m2+m3）的质量中心M（xm，ym

），那么

M（xm，ym

）就是△ABC的质量中心。

5.4.1用实验的方法计算质量中心的坐标可以看出：xm是x1

，x2

，x3的加权平均值，权数分别为ym是y1

，y2

，y3的加权平均值，权数分别为

5.4.1用实验的方法计算质量中心的坐标【例5.5】质点A(1，3)的质量为10g，B(2，-5)的质量为13g，C(-2，1)的质量为7g，求质量中心M的坐标。质量中心M的坐标为（）

5.4.1用实验的方法计算质量中心的坐标3.设平面上有n个质点Ai（xi，yi

），其质量为m1（i=1，2，…，n）。则质量中心坐标为：若质量中心为M（xm，ym），

P（x，y）为平面上任意一点，则

5.4.2物流中心位置的设置如果在一个地域范围内有n个用户，且它们的位置已确定，各个用户的平均需求量也是已知的。那么，选择物流中心时，就应该选使总运费最小的位置。设用户Ai的坐标为（xi，yi

），需求量为Wi

（i=1，2，…，n），那么物流中心的坐标应该是：5.5货物集散中心场地的设置5.5

5.5货物集散中心场地的设置出发点固定，收点不确定的物资调运问题。我们希望能确定一个收点，使得各个发点的物资运到这个收点时所花费的吨公里数最小，这种点称为最优设场点。

5.5.1寻求最优设场点的逐点计算法最优设场点一定能够在发点或者在路线的交叉点上找到。通过直接计算所有的物资运到各个发点或路线的交叉点处分别要花费的吨公里数。然后，我们从中找出花费吨公里数最小的那个发点货路线交叉点，这个点就是最优设场点。

5.5.1寻求最优设场点的逐点计算法【例5.6】

如图5-12所示，某农业生产成包组有A，B，C，D，E，F，G共七块麦田，这些麦田较为分散，它们的位置和产量都在图5-12中标出。现在要设一个打麦场，使得所有麦田到该打麦场所花费的吨公里数最少。

5.5.1寻求最优设场点的逐点计算法解：用A（吨公里）表示发点B，C，D，E，F，G的小麦全运到A点所花费的吨公里数，其余类似。则有：A（吨公里）=5×4+4×6+4×5+7×3+11×7+12×6=234。B（吨公里）=4×9+9×4+7×6+4×3+7×7+8×6=223。C（吨公里）=5×9+9×5+5×6+8×3+15×7+16×6=345。D（吨公里）=5×4+4×9+7×5+3×3+10×7+11×6=236。E（吨公里）=3×6+7×9+8×4+4×5+7×7+8×6=230。F（吨公里）=7×3+5×6+7×5+11×9+10×6+15×4=305。G（吨公里）=5×7+8×5+8×3+12×9+16×4+11×6=337。H（吨公里）=3×4+2×9+2×6+6×5+5×3+13×6+12×7=249。I（吨公里）=5×7+6×6+2×5+2×3+6×9+5×6+10×4=211。J（吨公里）=2×7+3×6+5×5+5×3+9×9+8×6+13×4=253。以I点为设场点，其他各点的物资运到I点所花费的吨公里数为211，最小。所以I点是最优设场点。

5.5.2寻求最优设场点的“小半归邻站”法道路没有圈，检查各端点；小半归邻站，够半就设场。

5.5.2寻求最优设场点的“小半归邻站”法【例5.7】

如图5.13所示的交通图，其中发量单位为t，距离单位为km，求其最优设场点。

5.5.2寻求最优设场点的“小半归邻站”法解：这个交通图中无圈。检查端点A，B，E，H，I五个点，按“小半归邻站，够半就设场”来找最优设场点。本问题的总发量为：3+435+7+6+2+4+9=40（t）。总发量之半为20（t）。端点A的发量3<20，所以把A点的发量3t的物资归到其邻站C点，这样A点和弧AC就可以不考虑了，不妨把它们从图5-13中抹去，这样C点的发量由原来的5t变成8t，得到图5-14

5.5.2寻求最优设场点的“小半归邻站”法用B（新吨公里）表示B点为设场点时在这个新图中所花费的总的吨公里数，其余类似。我们有以下结果：B（吨公里）=B（新吨公里）+12，其中12=3×4是A点发量归到邻站C点在AC弧上所花费的吨公里数，C（吨公里）=C（新吨公里）+12，D（吨公里）=D（新吨公里）+12，E（吨公里）=E（新吨公里）+12，F（吨公里）=F（新吨公里）+12，G（吨公里）=G（新吨公里）+12，H（吨公里）=H（新吨公里）+12，I（吨公里）=I（新吨公里）+12。

5.5.2寻求最优设场点的“小半归邻站”法经过“小半归邻站”的方法而得到的新问题的交通图中，各点的吨公里数的大小顺序与原来问题的交通图中各点的吨公里数的大小顺序完全一致。用“小半归邻站”的方法，可以把无圈交通图的设置最优场点的问题变得越来越简单，而且不改变问题的最优设场点。到最优就剩下两个发点，这时，就可以求出最优设场点了。如果剩下的两发点的发量不同，则发量大的点为最优设场点。如果剩下的两发点发量相同，则这两点都是最优设场点。在用“小半归邻站”方法的过程中，只要发现一个发量“够半”的点，那么在以后继续用“小半归邻站”方法时，这个点就永远不会再动了，这个点必定是最后剩下的两点之一，而且发量已经“够半”了。因此，不必再往下做了，这一点就是最优设场点。

5.5.2寻求最优设场点的“小半归邻站”法图5-14，端点B的发量4<20，因此把B的物资归邻站C，这时，C的发量就变成12t了，抹去B点与BC弧，得图5-15

5.5.2寻求最优设场点的“小半归邻站”法图5-15，把C点的12t归到D点，抹去C点和弧CD；又把E点的6t归到D点，抹去E点和弧ED，这时D点的发量就变为25t了，而25>20，因此，D点是最优设场点。

5.5.2寻求最优设场点的“小半归邻站”法【例5.8】设有