仓库的选址关系到物流网络中的运营成本以及资源的优化配置, 因此一直是各行业十分关心的问题[1,8]。文献[2, 3]给出层次分析的方式, 但此方式只考虑选址中的初始成本, 而仓库在运营中的实际成本并未进行重点分析, 从长远来看, 此成本显得更为重要。仓库的选址问题由于节点多, 运算量非常大, 采用传统的算法无法在有效时间内获得最优值, 而遗传算法恰好能很好地解决此类问题[9,10]。文献[4, 5]使用遗传算法来实现一个仓库内部货位的优化, 文献[5, 6]分析了企业内部某一地点的仓库选址优化问题。但这些文献都无法解决物流中的仓库选址优化问题。

遗传算法是一种典型的智能进化算法, 用以模拟生物在自然界中的生存繁衍, 逐渐适应其生存环境的方式来获得问题的近似最优值。遗传算法中会根据问题的目标函数构成一个适应度函数, 而问题解的各个可能取值称之为染色体, 一系列的染色体构成一个种群。这一种群中的各个染色体经过若干代的交叉、变异与选择, 逐渐趋向问题的最优解。其描述, 如图1所示。

由图1可以看出, 用遗传算法解决问题时, 需要设计的工作包括:生成初始种群, 即完成问题的编码;设计一个适合问题的适应度函数, 以作为染色体选择及进化的标准;需要设计一个交叉算子实现每对染色体的交叉运算;为防止问题陷入局部最优解, 需要设计一个变异算子, 从而能找到全局最优解。

图1 遗传算法流程图  下载原图

图2 仓库选址示意图  下载原图

物流的仓库选址问题可以描述为:在全国或者某个区域预建立若干个仓库, 在选择仓库地址时, 通过遗传算法来计算得到其中某个最优的地址组合, 使得仓库在运营过程中, 产生的费用最低。如图2所示, 其数学描述如下。

设共有m个候选仓库地址, n个货物需求地, 则C{C1, C2, , Cm}为候选的仓库地址, D{D1, D2, , Dn}为货物需求地的集合。用xi表示Ci选定为货物供应仓库, 所以xi的取值为:

定义物流量矩阵, 其中fij表示仓库i到需求地j之间的物流量。

定义距离矩阵, 其中rij表示仓库i到需求地j之间的距离。

则仓库的选址问题其数学模型如下:

若令, 适应度函数可以采用动态线性标定方式:

在仓库选址中, 若要从m个候选仓库地址中选择出k个最终地址, 从1…m中随机选择k个数, 这样可以构成编码为:

X={a1, a2, L, ai, …ak}, 其中ai∈{1, 2, L, m}, 且当i≠j时ai≠aj

选择算子使用的是轮盘赌算法。假定种群规模为NP, 则个体被选择的概率可以表示为:

交叉算子使用的是部分映射交叉[10], 其步骤为:

1) 在父代上选择两个交叉点, 这两个交叉点之间的子串称为映射段。

2) 交换两个映射段。

3) 根据映射段获得部分基因码之间的映射关系。

4) 子代继承父本中不存在映射关系的基因码。

5) 交换存在映射关系的基因码。

其示例如下。

假设存在父本:

父本1:1, 2, 3, 4, 5, 6, 7, 8

父本2:10, 3, 7, 8, 9, 1, 4, 6假定交叉点为4~6位, 即:

父本1:1, 2, 3, |4, 5, 6|, 7, 8

父本2:10, 3, 7, |8, 9, 1|, 4, 6交换映射段:

子代1:*, *, *, |8, 9, 1|, *, *

子代2:*, *, *, |4, 5, 6|, *, *获得的映射关系:

父本1中的4←→父本2中的8;

父本1中的5←→父本2中的9;

父本1中的6←→父本2中的1;最终得到的基于码为:

子代1:6, 2, 3, 8, 9, 1, 7, 4

子代2:10, 3, 7, 4, 5, 6, 8, 1

变异算子选择的是对换变异[10]:随机选择个体编码中的连个基因, 然后交叉它们的位置, 其示例如下。

交换基因3和基于7之间的位置, 变异之后的个体为:1, 2, , 4, 5, 6, , 8

对于仓库选址问题, 若要从m个候选仓库地址中选择出k个最终地址, 其所有可能的组合数为:Cmk。当m较大时, 可选择的总和数将急剧增加。如果用每秒可以计算10亿个取值的计算机来解从30个候选地址中选择15个最终地址的问题, 则大约花费的时间为4.92年。解从40个候选地址中选择20个最终地址的问题, 则大约花费的时间为4371.08年。

仿真实例:设有20个货物需求地, 20个候选仓库地址, 从中选择10个最终地址。根据上面的分析可知, 其组合数为C2010, 即184756。仓库到货物需求地的物流量设定为0~100之间的随机取值, 仓库到货物需求地之间的距离为0~100之间的随机取值。用Matlab软件编程, 初始种群大小设定为2000, 交叉概率为0.9, 变异概率为0.15, 其运算结果如图3所示。从此图可以看出当进化到第60代时, 算法已经收敛于近似最优解。

图3 仓库选址的遗传算法优化结果  下载原图

仓库的选址是物流业中的一个十分重要的问题, 其问题复杂, 且计算量大, 当问题规模较大时, 采用贪心算法在有效时间内几乎不可能得到最优解。而智能计算中的遗传算法恰恰能很好地解决此类问题。本文设计了仓库选址遗传算法的数学模型, 通过仿真实验证明此模型有效。