论文部分内容阅读
[摘要]较佳的配送中心选址方案是使商品通过配送中心的汇集、中转、分发，直至输送到需求点的全过程的效益最好。遗传算法在求解配送中心地址模型时可以取得较好的效果，因此，本文采用遗传算法的思想对配送中心选址规划进行描述厦算法设计，为使用遗传算法求解配送中心地址模型提供一些参考。
[关键词]配送中心：选址；遗传算法；规划；算法设计
中图分类号：1775 文献标识码：A 文章编号：1009－283(2009)04-0124-01
1 配送中心选址规划及算法设计的遗传算法选择
配送中心的选址，是指在一个具有若干供应点及若干需求点的经济区域内，选一个地址设置配送中心的规划过程。较佳的配送中心选址方案是使商品通过配送中心的汇集、中转、分发，直至输送到需求点的全过程的效益最好。
在配送中心选址的定量方法中，主要有重心法及鲍摩一瓦尔夫模型的应用，但他们在求解时都存在缺点，如重心法中，因自由度过多，迭代计算非常复杂，最佳地点实际上很难找到；鲍摩一瓦尔夫模型因采用逐次逼近法，不能保证必然会得到最优解，并且在求出的解中，可能出现配送中心数目较多的情况，而且配送中心的固定费用没在所得的解中反映出来。
遗传算法(Genetic Algorithm)是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法的基本思想是建立在自然选择和群体遗传学机理基础上的随机、迭代、进化。具有广泛适用性的概率搜索方法，通过模拟生物进化中“优胜劣汰、适者生存”的规律，进行编码与进化寻优。
实践表明，遗传算法在求解配送中心地址模型时可以取得较好的效果，因此，本文采用遗传算法的思想对配送中心选址规划进行描述及算法设计，为使用遗传算法求解配送中心地址模型提供一些参考。
2 遗传算法下配送中心选址规划的一般描述
为了能够将遗传算法应用于配送中心选址问题，必须对其进行数学的抽象。可以将通常情况下的配送中心选址规划问题抽象为以下几个方面：
规划区域表示
将具体的规划区域抽象为一个矩形，根据实际需要的规划精度将矩形区域分割成为mxn的矩形单元格，每一个矩形单元格代表一个与实际物流情况近似的地理区域。用s(i，j)表示规划区域中的第i行、第j列的一个矩形单元格，配送中心可以设置在任一个矩形单元格内。
物流需求经济效益
用B(i，j)表示单元格s(i，j)在满足其物流需求的基础上所产生的经济效益，它是指单元格对物流活动结果进行生产消费和生活消费后产生的社会经济效益。 配送中心的修建成本
修建配送中心的成本与当地的地理情况和经济情况有很强的相关性，在不同区域修建配送中心代价是不相同的。在模型中用c(i，j)表示s(i，j)区域修建—个标准配送中心所需的费用
单元格物流需求量
在模型中，用Q(i，j)表示—个单元格s(i，j)的物流需求量。表示该区域在一定时期内对物流服务的需求量。单元格的物流需求量由该区域的人口密度、经济状况、产业结构等因素所决定。
单位物流成本
在模型中，用F(s(i，j)。s(k，1))表示从区域s(i，j)到区域s(k，1)的单位物流成本，并且只定义相邻区域之间的运输成本，非相邻区域的单位物流成本通过多个相邻区域的单位物流成本的叠加累计得出，在规划配送中心时应该使运输成本最小。
配送中心的配送范围
从经济角度和实际运输工具的运送范围来考虑，配送中心的覆盖范围不可能无限大。在时间情况中，考虑到配送中心之间的分工合作，每个配送中心都会有一定的覆盖范围。用A(i，j)表示设置在区域s(i，j)的配送中心的配送区域，其配送范围可以表示为：从点(i－k，j－k)到点(i+k，i+k)(k为自然数)的一个长方形区域，每个候选点的配送范围可以相同也可以不同，如果i－k<0或j－k<0，则说明其遇到了边界，无意义。
配送中心选址模型的规划目标
在规划区域内选取几个单元格作为配送中心的设置点，使规划区域内的物流需求经济效益减去物流成本达到最大。
3 配送中心选址模型的遗传算法设计
对配送中心选址模型的求解进行遗传算法设计是寻找出最优解的重要保证，遗传算法作为一种通过模拟自然进化过程搜索最优解的方法，在求解配送中心地址模型时可以取得较好的效果，本文对算法设计如下：
①前提假设
配送中心能够满足任意数量的物流服务需求；
在规划区域中处于相同划分区域的物流属性相同；
配送中心到物流需求点的配送时间可以忽略不计；
模型中不考虑库存。即在“零库存”的情况下进行的，并且物流需求产生时能够立即送货。
②配送中心规划方案的解表达方式
用一组长度为m×n的二进制数串来表示一种布局方案，第k个数表示s((k／n)+1，modle(k／n))的单元格为候选的配送中心。在模型中，用P(i，j)=l表示s(i，j)被设置为候选配送中心点，P(i，j)=0表示s(i，j)没被设置为候选配送中心点。
例如：{1，0，0，1，1……0，1，1}表示P(1，1)=l，P(1，2)=0，P(1，3)=0……
③依据配送目标确定配送中心规划方案的评价函数
④选择算子，采用比例选择算子，即每个个体以与适应度大小成正比的概率被选中遗传到下一代。
⑤交叉算子，采用单点交叉算子，即在个体编码字符串中随机设置一个交叉点，然后在该点相互交换两个配对个体的部分染色体。
⑥变异算子，采用编码字符串范围内的均匀随机变异，即分别用符合某一范围内均匀的随机数，以某一较小的概率来替换个体编码字符串中各个基因座上的原有基因值。
⑦设置终止循环条件，若满足收敛条件或固定迭代次数则终止，若不满足条件则重新进行进化过程。每一次进化过程就产生新一代的群体。群体内个体所表示的解通过进化最终达到最优解。
[关键词]配送中心：选址；遗传算法；规划；算法设计
中图分类号：1775 文献标识码：A 文章编号：1009－283(2009)04-0124-01
1 配送中心选址规划及算法设计的遗传算法选择
配送中心的选址，是指在一个具有若干供应点及若干需求点的经济区域内，选一个地址设置配送中心的规划过程。较佳的配送中心选址方案是使商品通过配送中心的汇集、中转、分发，直至输送到需求点的全过程的效益最好。
在配送中心选址的定量方法中，主要有重心法及鲍摩一瓦尔夫模型的应用，但他们在求解时都存在缺点，如重心法中，因自由度过多，迭代计算非常复杂，最佳地点实际上很难找到；鲍摩一瓦尔夫模型因采用逐次逼近法，不能保证必然会得到最优解，并且在求出的解中，可能出现配送中心数目较多的情况，而且配送中心的固定费用没在所得的解中反映出来。
遗传算法(Genetic Algorithm)是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法的基本思想是建立在自然选择和群体遗传学机理基础上的随机、迭代、进化。具有广泛适用性的概率搜索方法，通过模拟生物进化中“优胜劣汰、适者生存”的规律，进行编码与进化寻优。
实践表明，遗传算法在求解配送中心地址模型时可以取得较好的效果，因此，本文采用遗传算法的思想对配送中心选址规划进行描述及算法设计，为使用遗传算法求解配送中心地址模型提供一些参考。
2 遗传算法下配送中心选址规划的一般描述
为了能够将遗传算法应用于配送中心选址问题，必须对其进行数学的抽象。可以将通常情况下的配送中心选址规划问题抽象为以下几个方面：
规划区域表示
将具体的规划区域抽象为一个矩形，根据实际需要的规划精度将矩形区域分割成为mxn的矩形单元格，每一个矩形单元格代表一个与实际物流情况近似的地理区域。用s(i，j)表示规划区域中的第i行、第j列的一个矩形单元格，配送中心可以设置在任一个矩形单元格内。
物流需求经济效益
用B(i，j)表示单元格s(i，j)在满足其物流需求的基础上所产生的经济效益，它是指单元格对物流活动结果进行生产消费和生活消费后产生的社会经济效益。 配送中心的修建成本
修建配送中心的成本与当地的地理情况和经济情况有很强的相关性，在不同区域修建配送中心代价是不相同的。在模型中用c(i，j)表示s(i，j)区域修建—个标准配送中心所需的费用
单元格物流需求量
在模型中，用Q(i，j)表示—个单元格s(i，j)的物流需求量。表示该区域在一定时期内对物流服务的需求量。单元格的物流需求量由该区域的人口密度、经济状况、产业结构等因素所决定。
单位物流成本
在模型中，用F(s(i，j)。s(k，1))表示从区域s(i，j)到区域s(k，1)的单位物流成本，并且只定义相邻区域之间的运输成本，非相邻区域的单位物流成本通过多个相邻区域的单位物流成本的叠加累计得出，在规划配送中心时应该使运输成本最小。
配送中心的配送范围
从经济角度和实际运输工具的运送范围来考虑，配送中心的覆盖范围不可能无限大。在时间情况中，考虑到配送中心之间的分工合作，每个配送中心都会有一定的覆盖范围。用A(i，j)表示设置在区域s(i，j)的配送中心的配送区域，其配送范围可以表示为：从点(i－k，j－k)到点(i+k，i+k)(k为自然数)的一个长方形区域，每个候选点的配送范围可以相同也可以不同，如果i－k<0或j－k<0，则说明其遇到了边界，无意义。
配送中心选址模型的规划目标
在规划区域内选取几个单元格作为配送中心的设置点，使规划区域内的物流需求经济效益减去物流成本达到最大。
3 配送中心选址模型的遗传算法设计
对配送中心选址模型的求解进行遗传算法设计是寻找出最优解的重要保证，遗传算法作为一种通过模拟自然进化过程搜索最优解的方法，在求解配送中心地址模型时可以取得较好的效果，本文对算法设计如下：
①前提假设
配送中心能够满足任意数量的物流服务需求；
在规划区域中处于相同划分区域的物流属性相同；
配送中心到物流需求点的配送时间可以忽略不计；
模型中不考虑库存。即在“零库存”的情况下进行的，并且物流需求产生时能够立即送货。
②配送中心规划方案的解表达方式
用一组长度为m×n的二进制数串来表示一种布局方案，第k个数表示s((k／n)+1，modle(k／n))的单元格为候选的配送中心。在模型中，用P(i，j)=l表示s(i，j)被设置为候选配送中心点，P(i，j)=0表示s(i，j)没被设置为候选配送中心点。
例如：{1，0，0，1，1……0，1，1}表示P(1，1)=l，P(1，2)=0，P(1，3)=0……
③依据配送目标确定配送中心规划方案的评价函数
④选择算子，采用比例选择算子，即每个个体以与适应度大小成正比的概率被选中遗传到下一代。
⑤交叉算子，采用单点交叉算子，即在个体编码字符串中随机设置一个交叉点，然后在该点相互交换两个配对个体的部分染色体。
⑥变异算子，采用编码字符串范围内的均匀随机变异，即分别用符合某一范围内均匀的随机数，以某一较小的概率来替换个体编码字符串中各个基因座上的原有基因值。
⑦设置终止循环条件，若满足收敛条件或固定迭代次数则终止，若不满足条件则重新进行进化过程。每一次进化过程就产生新一代的群体。群体内个体所表示的解通过进化最终达到最优解。