用混合遗传算法求解物流配送路径优化问题

2018-07-11王世贵王丹丹

西昌学院学报（自然科学版） 2018年2期

傅　勉，王世贵，王丹丹

（1.安徽新华学院a.商学院；b.大学生素质教育研究中心，合肥 230088；2.陆军炮兵防空兵学院，合肥 230031）

0　引言

物流配送路径优化问题是物流配送业务中的优化决策问题之一，目前多采用遗传算法[1]、模拟退火算法[2]、蝙蝠算法[3]、智能水滴算法[4]、神经网络算法[5]、蚁群算法[6]等启发式算法求解，但上述算法单独使用均存在早熟收敛，求解质量不高。为此，文章尝试将全局求解质量高的遗传算法与局部求解质量高的模拟退火算法相结合，对遗传算法求出的解进行多次模拟退火寻优，构造一种混合遗传算法。

1　物流配送路径优化问题的数学模型

假设已知情况如下：从配送中心向若干个客户送货，假设K表示最大车辆数；Qk（k=1,2,…,K）表示汽车的载重量；Dk表示车辆的最大行驶距离；L表示顾客配送数；qi表示每个顾客的需求量；dij表示配送点i到j的运距；d0i表示配送中心到各配送点的距离；nk表示第k辆车服务的客户数量；Rk表示第k条行驶路线；rki表示服务点rki在第k条路线的次序是i。求最优的车辆配送路线，使配送路径最短。

要求：1）每条线路上的总配送量不得超过车辆最大载重量；2）每条线路的总距离不能超过车辆行驶距离的临界值；3）各个顾客的需求只能被一辆车服务。因此，建立配送模型如下：

2　混合遗传算法构造

混合遗传算法主要是将模拟退火引入到遗传算法的交叉操作中，使得遗传算法不仅能够接收优良解，还能接收劣质解，避免陷入“早熟”解中，以增强遗传算法的局部求解效率。

2.1　算法实现步骤

具体实现步骤如下∶

1）确定种群大小n，交叉概率Pc，变异概率Pm，初始温度T0；

2）对个体进行编码，用随机法产生L个个体，计算个体的适应度；

3）对个体进行选择操作；

4）对个体分别进行交叉操作和模拟退火操作；

5）变异操作；

6）降温，T=T0*θk，θ为一个[0,1]之间的常数，k为迭代次数；

7）判断个体是否达到进化代数G，若达到则终止运算，否则转步骤3。

2.2　混合遗传算法的构造

1）编码。采用0、1、2、3、4，…，N的自然数编码。

2）适应度函数。对于某个个体，设其对应的配送路径条数与车辆总台数之差为M，取适应度值为Z，α为对每条不可行路径的惩罚权重，则适应度F为：

3）选择算子。采用最佳个体保留方法。

4）交叉算子。采用类似OX法的交叉方法。

5）模拟退火算法。假设交叉前的父代是f1、f2，交叉后产生的子代c1、c2，计算父代和子代的适应度分别是F(fi),F(ci)，i=1,2，然后进行模拟退火操作，如果子代F(ci)大于父代F(fi)，则用子代ci代替父代 fi，否则，以概率 exp((F(ci)-F(fi)/T)接受子代 ci，其中T为当前温度；

6）变异算子。为了保持群体内个体的多样化，使个体在排列顺序上有较大变化，采用了连续多次对换的变异方法。