理论教育 直接运输:解决最短线路问题的位势法

直接运输:解决最短线路问题的位势法

时间:2023-05-25 理论教育 版权反馈
【摘要】:直送式运输,是指由一个供应点对一个客户的专门送货。现以位势法为例,介绍如何解决物流网络中的最短线路问题。第一步,选择货物供应点为初始结点,并取其位势值为“零”,即Vi=0。图7-1 物流网络图图7-2 最优线路图依照上述方法,将物流网络中的每一结点当作初始结点,并使其位势值为“零”,然后进行计算,可得所有结点之间的最短距离,如表7-4。

直接运输:解决最短线路问题的位势法

直送式运输,是指由一个供应点对一个客户的专门送货。

从物流优化的角度看,直送式客户的基本条件是其需求量接近于或大于可用车辆的额定载质量,需专门派一辆或多辆车一次或多次送货。因此,直送情况下的运送追求的是多装快跑,选择最短运送线路,以节约时间、费用,提高运送效率。即直送问题的物流优化,主要是寻找物流网络中的最短线路问题。

目前解决最短线路问题的方法有很多,如位势法、“帚”型法、动态法等。现以位势法为例,介绍如何解决物流网络中的最短线路问题。已知物流网络如图7-1,各结点分别表示为ABCDEFGHIJK,各结点之间的距离如图7-1所示,试确定各结点间的最短线路。

寻找最短线路的方法步骤如下。

第一步,选择货物供应点为初始结点,并取其位势值为“零”,即Vi=0。

第二步,考虑与I点直接相连的所有线路结点。其初始结点的位势值为Vi,则其终止结点J的位势值Vj可按下式确定

Vj=Vi+Lij (7-1)

式中Lij——i点与j点之间的距离。

第三步,从所得到的所有位势值中选出最小者,此值即为从初始结点到该点的最短距离,将其标在该结点旁的方框内,并用箭头标出该连线ij,以此表示从i点到j点的最短线路的走法。

第四步,重复以上步骤,直到物流网络中所有结点的位势值均达到最小为止。

最终,各结点的位势值表示从初始结点到该点的最短距离。带箭头的各条连线则组成了从初始结点到其余结点的最短线路。分别以各点为初始结点,重复上述步骤,即可得各结点之间的最短距离。

例7-1在物流网络图7-1中,试寻找从供应点A到客户K的最短线路。

解:根据以上步骤计算如下。

(1)选择货物供应点A为初始结点,并取其位势值为“零”,即取VA=0。

(2)由公式(7-1)确定与A点直接相连的所有线路结点的位势值。

VB=VA+LAB=0+6=6

VE=VA+LAE=0+5=5

VF=VA+LAF=0+11=11

VH=VA+LAH=0+8=8

(3)从所得的所有位势值中选择最小值VE=5,此值即为从初始结点到该点的最短距离。同时,将其标注在对应结点E旁边的方框内,并用箭头标出连线A-E,此即为从A点到E点的最短线路走法。即

978-7-111-51595-1-Part02-44.jpg

(4)重复以上三步。选择E为初始结点。(www.daowen.com)

(5)计算与E直接相连的DGF点的位势值(如果同一结点有多个位势值,则只保留最小者)。

VD=VE+LED=5+2=7

VG=VE+LEG=5+14=19

VF=VE+LEF=5+4=9

(6)从所得的所有剩余位势值中选出最小者VB=6,此值即为除VE外的最小值,将其标注在对应的结点B旁边的方框内,并同时用箭头标出联线A-B,此即为从A点到B点的最短线路走法。即

978-7-111-51595-1-Part02-45.jpg

(7)同理,重复(1)~(3)步。选择B点为初始结点。

(8)计算与B直接相连的DC结点的位势值。它们的位势值分别为16和17。

(9)从所得所有剩余位势值中选出最小者VD=7,此值即为除VEVB外的最小值,即

min{8,7,19,9,17}=VD=7

将其标注在对应的结点D旁边的方框内,并同时用箭头标出联线E-D,那么从A点到D点的最短线路走法即为A-E-D

继续计算,即可得最优路线如图7-2所示,由供应点A到客户K的最短距离为24。

978-7-111-51595-1-Part02-46.jpg

图7-1 物流网络图

978-7-111-51595-1-Part02-47.jpg

图7-2 最优线路图

依照上述方法,将物流网络中的每一结点当作初始结点,并使其位势值为“零”,然后进行计算,可得所有结点之间的最短距离,如表7-4。

表7-4 结点之间的最短距离

978-7-111-51595-1-Part02-48.jpg

(续)

978-7-111-51595-1-Part02-49.jpg

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈