1. 问题描述
本文中,我们考虑的问题是货物独立路径配送的情况下,选择车辆配送路线,使得总运费成本最小。在现实生活中,从任意配送中心i到配送中心j的最大配送量一致,而且不同的两个配送中心i与j之间没有直接到达的配送路线这是可能的,但是我们需要从i配送货物到j,因此我们需要从i出发配送货物到达其他配送中心k,然后再从k出发配送货物到其他配送中心s,如此不断的交替,最后从某一配送中心t出发配送货物到达j。问题是如此交替循环的配送过程中,如何安排货车从不同的配送中心按照独立的车辆路线,使得按照该路线配送总成本最小。
货物的独立路径配送问题的数学描述:图
,这里权重函数
,表示通过该弧所需要的配送时间,c是定义在弧
上的容量,且
其中L为定值,以吨为单位。点
,s为源点,t为汇点,令F为从s点出发的总货物质量,F以吨为单位。目标是求满足条件的总配送时间最短的
路
,其中
。
2. 算法设计
算法1 [3]
Step0:取第一个可行流f为零流,取
。
Step1:求X增广链。
1.0给s标号
,把所有点规定为未检验点。
1.1若所有已经标号的顶点已经检验完毕,转Step3;否则,任意取一个已经标号却未获得检查的点i,检验与点i关联的弧。
,如果
并且j没有标号,则给j标号
;
,如果
并且j没有标号,那么就给j标号
。当点i的所有关联弧都已经检验完成,则令点i为已经检验,转1.2。
1.2:如果t获得标号,则找到一条增广链,转Step2。否则转1.1。
Step2:对X增广。
2.0:令
。
2.1:若j的前点标号
,即j是s,对X增广结束,消除D中所有顶点的标号,转Step1。否则转2.2。
2.2:如果
,则输出
,取
,用点i代替点j,转2.1;如果
,则输出
,取
,用点i代替点j,转2.1。
Step3:X的最大流就是有向图D的独立配送路径数,输出配送路径条数K。
算法2 [4]
Step0:令零流为初始可行流。
Step1:假如
,则X所经过的弧就是有向图D的配送总费用最小的R条独立路径,结束。否则,转Step2。
Step2:把X所经过的弧方向反向,并且令所经弧的权值
,新的图记为
。
Step3:用Frod算法在有向图
中求最短路P,转Step4。
Step4:使X沿P增广1,获得新的X,转Step1。
算法3
Step1:通过算法1求图D中s到t的弧独立路径数K,若
,转Step2。否则,输出问题无解。
Step2:通过算法2求图D中配送总费用最小的R条独立配送路径。
3. 算法可行性的分析
引理3.1 [3]:
上的K (K为正整数)条独立配送路径与流值为K的0~1整数流一一对应。
引理3.2 [4]:有向图
是一个带源点s与汇点t的容量–费用网络,f是D上流值为v的最小费用流,P是
中从s到t的最小费用路,
是P的容量,
,
是定义在
的路P上流值为
的一个可行流,
则
是D上流值为
的最小费用流。
定理3.1算法3是货物的独立路径配送问题的最优算法。
证明:由引理3.1,我们采用最大流的Ford-Fulkerson算法来解决独立配送路径问题,判断有向图D是否有解。由引理3.2,我们在有向图D上用算法2求配送总费用最小的R条独立配送路径。算法3的Step1所需要的时间上界是
。Step2的计算量为
,因此算法3的时间复杂度为
。定理得证。