基于遗传算法的第四方物流的一类路径优化问题

       第四方物流是一个通过拥有的信息技术、整合能力以及其他资源提供一套完整的供应链解决方案，以此获取一定的利润的集成商。路径优化问题是第四方物流中的关键问题。根据现代物流服务的需要，本文提出了一类第四方物流的带时间窗的路径问题。综合路径优化和供应商选择两方面的问题，从多重图的角度出发，建立了多属性单目标的数学模型，并采用遗传算法对其进行了求解。针对这类特殊的路径优化问题，本文提出了一种新的染色体编码和交叉变异方式，使得在遗传算法运行过程中出现不可行解的概率大大降低，这点在具体的算法实现中取得了很好的效果。此外，本文基于Matlab进行了路径优化问题遗传算法的编码，利用Matlab强大的数值计算能力较好地解决了问题并进行了实例验证，对第四方物流企业实现科学快捷的调度和路径的优化有实际意义。

从第四方物流的简介可以看出，优化决策是其得以盈利的关键环节。而优化决策的关键问题在于路径、运输载体、3PL供应商的选择上。　而由于路径选择、运输载体选择、3PL供应商选择并非顺序进行的，而是综合的、并行的一个过程,给问题的求解增加了复杂性。我们将路径及3PL供应商的选择作为优化决策的主要关键因素，从第四方物流中抽象出了一类路径优化问题。

问题的叙述如下：首先我们取定供应链节点s为货物的发送点，节点e为接收地点。这两节点之间还有N个节点也需要物流服务，即该业务需要历遍这N个节点。这些供应链节点可能是组成这个供应链的城市、加工中心、仓库等。在每两个节点之间都存在不同的3PL供应商，每个供应商的费用、时间、承载能力、信誉度作为它的选择参数。为了使问题简化明了，我们设定每两个地点之间最多有4个不同的3PL供应商，不足4个的可以扩充为4个，那些实际不存在的供应商可以把费用和时间的参数设定为无穷大。我们要求从发送地点出发，历遍所有的中转站，最终到达接收地点结束。在以上的约束条件之下，我们要对历遍中转站的顺序及供应商进行选择，以达到费用最少、时间尽量短的目标。另外，为了进一步简化问题，我们在结合实际后利用时间窗的概念把时间参数统一到费用计算中。即假定任务存在最大允许时间，再按超出允许时间的长短来计算惩罚金额，把它纳入到总费用中去。

现有某第四方物流公司承接了某一地区的供应链物流业务，需要执行一项从供应链节点s到供应链节点e的任务，已知两节点之间还有5个节点也需要物流服务，即该业务需要历遍这5个节点。这些供应链节点可能是组成这个供应链的城市、加工中心、仓库等。根据实际问题考虑，在实例多重图中，每条边的费用、时间、承载能力、信誉指标都可以通过信息采集得到，作为已知条件信息。任务预期时间为85单位时间，每超过单位时间后罚款5元。假设经过了

图表2各节点之间的所需时间

承载能力和信誉指标的筛选之后，有如下可选数据：

 

图表3各节点之间的费用

将上面表格数据以矩阵形式在Matlab中输入，将遗传算法的种群大小设置为120，重组概率设置为0.75，这里只对路径的选择进行变异，变异率为0.08（详见附录）。

 

最后计算所得到的结果为

opt_rte         =   s    4     5     3     1     2    e          （历遍节点的顺序）

opt_slc         =         3   1    3     2     2     1       （供应商的选择）

min_cost      =   70  （最小费用）

functionvarargout =ga(n,C,T,t0,a,pop_size,num_iter)

 

%初始化遗传算法的参数

 

nargs = 7;

for k = nargin:nargs-1

switch k

case 0

            n=5;

case 1

pop_size = 120;

case 2

num_iter = 5e3;

case 3

            C=[ 11  12  13  14  16  17  11  14  12  11  infinf 22  13  7   inf 13  21  19  inf 30  12  17  24;

                0   0   0   0   4   9   7   inf 3   10  7   12  15  13  21  inf 15  17  27  inf 10  11  11  17;

               13   21  19  17  0   0   0   0   12  21  17  infinfinfinfinf 14  25  16  inf 17  15  19  14;

               13   12  17  inf 17  19  14  22  0   0   0   0   28  26  20  17  19  17  infinf 12  18  14  inf;

               19   20  21  22  16  13  19  inf 11  13  17  12  0   0   0   0   12  15  19  13  16  17  infinf;

               32   18  23  inf 15  13  23  inf 10  11  13  17  17  infinfinf 0   0   0   0   23  26  20  17

               ];

case 4

            T=[15   13  11  9   10  12  14  13  16  11  infinf 15  21  23  inf 18  15  14  inf 9   23  15  14;

               0    0   0   0   13  5   8   inf 12  5   9   9   11  13  12  inf 11  9   6   inf 10  11  11  7;

               13   11  15  13  0   0   0   0   16  13  15  infinfinfinfinf 19  17  16  inf 15  18  14  23;

               13   12  9   inf 15  22  14  13  0   0   0   0   16  14  18  27  13  17  infinf 18  12  14  inf;

               22   21  19  20  18  25  17  inf 18  13  17  21  0   0   0   0   17  15  9   13  16  13  infinf;

               5    14  17  inf 17  19  14  inf 20  17  13  12  15  infinfinf 0   0   0   0   21  17  20  19

               ];

case 5

            t0 = 85;

case 6

            a = 5;

otherwise

end

end

 

 

% 初始化种群

pop_rte = zeros(pop_size,n);    % 节点顺序

pop_slc = zeros(pop_size,n+1);     % 路径选择

for k = 1:pop_size

pop_rte(k,:) = randperm(n);

pop_slc(k,:) = round(3*rand(1,n+1));

 

end

pop_slc=pop_slc+1;

tmp_pop_rte = zeros(8,n);

tmp_pop_slc = zeros(8,n+1);

new_pop_rte = zeros(pop_size,n);

new_pop_slc = zeros(pop_size,n+1);

 

 

%执行遗传算法

global_min = Inf;

total_cost = zeros(1,pop_size);

cost_history = zeros(1,num_iter);

 

 

foriter = 1:num_iter

% 适应度计算

for p = 1:pop_size

        c = 0;

        t = 0;

p_rte = pop_rte(p,:);

p_slc = pop_slc(p,:);

        c = c + C(1,4*(p_rte(1)-1)+p_slc(1));

        t = t + T(1,4*(p_rte(1)-1)+p_slc(1));

for s = 1:n-1

           c = c + C ( p_rte ( s )+1 ,4 *( p_rte(s+1) -1)+ p_slc(s+1));

           t = t + T ( p_rte ( s )+1 ,4 *( p_rte(s+1) -1)+ p_slc(s+1));

end

        c = c + C ( p_rte ( n )+1 , 4*n + p_slc(n+1) );

        t = t + T ( p_rte ( n )+1 , 4*n + p_slc(n+1) );

if (t>t0)

           c = c + (t - t0)*a;

 

end

total_cost(p) = c;

end

 

%找到每代的最优解

    [min_cost,index] = min(total_cost);

cost_history(iter) = min_cost;

ifmin_cost<global_min

global_min = min_cost;

opt_rte = pop_rte(index,:);

opt_slc = pop_slc(index,:);

 

end

 

% 遗传交叉、变异与选择

rand_grouping = randperm(pop_size);

for p = 8:8:pop_size

rtes = pop_rte(rand_grouping(p-7:p),:);

slcs = pop_slc(rand_grouping(p-7:p),:);

costs = total_cost(rand_grouping(p-7:p));

        [ignore,idx] = min(costs);

        best_of_8_rte = rtes(idx,:);

        best_of_8_slc = slcs(idx,:);

rte_ins_pts = sort(ceil(n*rand(1,2)));

        I = rte_ins_pts(1);

        J = rte_ins_pts(2);

for k = 1:8 %产生新的子代

tmp_pop_rte(k,:) = best_of_8_rte;

tmp_pop_slc(k,:) = best_of_8_slc;

switch k

case 2

tmp_pop_rte(k,I:J) = fliplr(tmp_pop_rte(k,I:J));

case 3

tmp_pop_rte(k,[I J]) = tmp_pop_rte(k,[J I]);

case 4

tmp_pop_rte(k,I:J) = tmp_pop_rte(k,[I+1:J I]);

case 5

tmp_pop_slc(k,I:J) = fliplr(tmp_pop_slc(k,I:J));

case 6

tmp_pop_rte(k,I:J) = fliplr(tmp_pop_rte(k,I:J));

tmp_pop_slc(k,[I J]) = tmp_pop_slc(k,[J I]);

case 7

tmp_pop_rte(k,[I J]) = tmp_pop_rte(k,[J I]);

tmp_pop_slc(k,I:J) = fliplr(tmp_pop_slc(k,I:J));

case 8

tmp_pop_rte(k,I:J) = tmp_pop_rte(k,[I+1:J I]);

tmp_pop_slc(k,I:J) = tmp_pop_slc(k,[I+1:J I]);

otherwise

end% 交叉与变异

end

new_pop_rte(p-7:p,:) = tmp_pop_rte;

new_pop_slc(p-7:p,:) = tmp_pop_slc;

end%选择

pop_rte = new_pop_rte;

pop_slc = new_pop_slc;

end

 

 

% 返回结果

 

opt_rte

opt_slc

min_cost

 

 

 

 

end