首页分享物流中配送区域与配送路线的网络优化法

物流中配送区域与配送路线的网络优化法

来源：花匠小妙招时间：2025-07-13 10:20

物流中配送区域与配送路线的网络优化法

个配送中心的配送能力,以可承担多少个居民区(接货点)来确定,bj(j=1,2,3,…,k)表示第j个配送中心可承担bj个居民区(接货点)的配任务,每个接货点与配送中心之间都有道路连通。

假如每个配送中心的配送范围的划分,以运输距离最短为目标,可将问题(1)转化为网络中的优化问题。

设G=(V,E,W)是以V为顶点集,以E为边集,以W为赋权集的连通图[3]。其中:

(1)V={v0,v1,v2,v3,…,vn}表示图的点集

(2)Vk={vi1,vi2,vi3,…,vik}为配送中心构成的点集,VkΑV;

(3)VVk表示n-k个接货点:

(4)E={eij=(vi,vj):vi,vi∈V},eij表示vi与vj之间直接有道路相连;

(5)W={w(vi,vj)=wij:(vi,vj)∈E},wij表示vi与vj之间直接道路的长度设图G的支撑子图T=(V,E(T),W(T)),若:对任何vi∈:dj)|j:ij)∈E(T)}|(表示vi在图T中的次),如果要使图G的支撑子图T,就必须满足以下条件:

(a):vi∈VVk,存在vj∈Vk,使vi与vj在E(T)中有路连通;

(b),即:对任意vj∈Vk,dt(j)=|vi:vi与vj在图T中有路连通,且vik,dt()≤bj。

设H(a)图G中所有支撑图组成的集合

(1)W(T)=min　w(i,j)

(i,j)∈E(T):T∈H6

(b)图G中所有支撑图组成的集合,对引言中提出的问题2可下列问题的优化:当H是满足条件(a)、

W(T)=min

(i,j)∈E(T);T∈H6w(i,j)(2)

112将问题转化为最小支撑树问题

首先对图G进行扩充,在图G的结点外再增加一个结点vn+1,在结点vn+1与Vk之间分别增加一条

0边,得到图G0=(V0,E0,W0),其中:V0=V∪{vn+1};E=E∪{vn+1,vj):vj∈Vk};

W=W∪{w(vn+1,vj)=0:vj∈Vk}。0

定理1　设T0是图G0的最小支撑树。构造如下T:V(T)=V0{vn+1}=V;E(T)=E0(T0)

0{(vn+1,vj):vj∈Vk}。则T为(1)的最优解且W(T)=W(T)。

证明　按照T的构造方法,T显然是(1)的可行解。

因为w(vn+1,vj)=0,vj∈V,所以W(T0)=W(T)。

如果T不是(1)的最优解,设T3是(1)的最优解,W(T3)<W(T)=W(T0)。构造如下T1:

113V(T)=V∪{vn+1};E(T)=E(T)∪{(vn+1,vj):vj∈Vk};w(vn+1,vj)=0,vj∈Vk。

T1是图G0的支撑图,在图T1中,对任意vj,vi∈Vk两点,通过点vn+1连通。按照条件(a),对任意vi∈VVk,存在vj∈Vk,使vi与vj在E(T3)中有路连通,E(T1)ΒE(T3),T1是图G0的连通支撑图,显然

31000W(T)=W(T)≥W(T),与设T是图G的最小支撑树矛盾。故T是(1)的最优解。

定理2　设T是图G中问题(1)的最优解。构造如下T0

V(T0)=V∪{vn+1};E0(T0)=E(T)∪{(vn+1,vj):vj∈Vk};w(vn+1,vj)=0,vj∈Vk。则T0是图G0的最小支撑树且W(T0)=W(T)。

证明　由定理1的证明过程可知:T0是图G0的连通支撑图,假设图T0不是树,则在图T0中存在圈C=(vi1,vi2,vi3,…,vim),且|V(C)|=m≥3;由图T0构造方法可得:E(C)∩E(T)≠ ,否则E(C)Α{(vn+1,vj):vj∈Vk},C=(vi1,vi2,vi3,…,vim)不是圈,因此存在(vi,vj)∈E(C),使w(vi,vj)=wij>0。取101010303T=T(vi,vj),T也是图G的连通支撑图,且W(T)<W(T),设T是图G的最小支撑树,W(T)≤W(T1),与定理1的结论矛盾。因此定理结论成立。

推论1　设T是图G中问题(1)的最优解,则在图G0中E(vn+1)∩E(T)= 。