论文部分内容阅读
黑龙江省教育厅科学技术项目资助 项目号:12521545
【文章摘要】
本文对货物配送企业的选址问题作了分析,对国内外相关问题的研究做了归纳,提出了一种基于遗传算法的货物配送企业的选址问题方案,阐述了方法的具体思想和实施方法。方案考虑了货物配送企业的选址问题过程中存在的各种参数。
【关键词】
课表;遗传算法;计算机
0 引言
货物配送企业的选址的问题最终归结为如何使得各种费用合成的总运营成本达到最小化的问题。为明确表达种费用以及在运算中使用费用值,可将各种费用转化为相应的决定参数的函数。运输费用的相关参数包括运输距离、运输方式和运输量。当然运输费用实际函数并非线性值,为了计算简便,方便判断,可简化为线性函数,这种替代只要处理得当,不影响结果的准确性。运营费用的参数包括劳动力、公用事业费用和其他开支等等。物流中心选址的固定费用则由土地使用、设备和建筑费用组成。重新选址费用由将设备移到新物流中心地址的费用、新物流中心初建费用和关闭旧址处的设施费用等参数来决定。当然还有其它一些相关参数。
多年来,选址问题的解决方法经过了不断的改进和发展,种类繁多,发展很快。特别是随着先进的计算工具的不断出现和应用,一些新的方案变得可行,这成了选址问题得以有效解决折基础。由于遗传算法的先进性和可行性,其在不同行业中应用越来越广,在企业选址问题上可以有效地应用,使问题可以有效收敛,最终解可以达到令人满意的效果,这对于改进易腐物流系统布局,提高易腐物流系统的科学决策水平具有极大的意义。
1 国内外研究现状
早期的选址问题中主要是基于运输成本的,该问题的早期理论的主要研究专家是土地经济学家和区域地理学家。1909年Weber最早提出选址问题,该问题的目标是找到一个使仓库与各处客户之间的总运输距离最短的仓库位置。1929年Holelling提出了另一个选址问题,研究一条直线上两个竞争供应商的选址。1964年,Hakimi的研究打破了以前研究的局限性,使问题更具一般性,形成了统一的理论,这一进步为后来的选址理论的进一步发展打下了坚实的基础,同时更具实用性,可以扩大实际应用。选址问题的研究有进一步深入的必要,因为选址问题和NP-完全问题经常有千丝万缕的联系,可以被更广更深的研究。
2 遗传算法的研究现状
遗传算法(Genetic Algorithm, GA)是一种全新的算法,近年来得以快速发展和广泛应用。它是基于生物体的进化的思想,主要来源于达尔文的进化论和Mendel的遗传学说。1975年Holland及其学生于密执安大学研究创建了遗传算法。由于优化效率和实用性,各国学者开始关注和研究遗传算法,对该算法进行了深入研究和改进。现在每年都有遗传算法的学术会议召开,影响范围越来越广。较为重要的会议包括国际遗传算法学会组织召开的ICGA(International Conference on Genetic Algorithms) 和FOGA( Workshop on Foundation of GeneticAlgorithms)会议,这些会议成了相关研究人员获取信息和相互交流的平台。
进入90年代,遗传算法的发展速度得以大大提高,在理论研究和应用研究都取得了很多成果,现在遗传算法在各行各业的应用都成为可能,应用领域在不断扩大,遗传算法的效率也在不断提高。研究的过程中也出现了一些一些新的理论和方法。
国内的研究人员也对遗传算法进行了不断地研究,做了许多改进。为了解决局部收敛问题,2002年,戴晓明等应用多种群遗传并行进化的思想,对不同种群基于不同的遗传策略。2004年,赵宏立等提出了并行遗传算法(Building-block Coded Parallel GA,BCPGA),对简单遗传算法进行改进。2005年,江雷等使用弹性策略来维持群体的多样性,很好地解决了TSP问题。
3 遗传算法的编码
编码负责连接实际目标问题的遗传算法的染色体位串,在企业选址问题中也要依据不同的实际问题特点进行编码的确定。
对于一般性的企业选址问题,可以采用二进制编码形式。编码选择和确定会直接影响后面的遗传算子的选择,这一点设计交叉算子和变异算法时要重要考虑。
编码要具完备性、健全性、非冗余性。
4 重心法
重心法是用来求解物流企业选址问题的一个有效的方法,首先,要有相关的地图,图中包含物流企业的各个服务对象,图中相关比例要正确; 其次,构建坐标系,为个服务对象确定坐标,获得数据; 最后,建立重心模型,求解;
【参考文献】
[1]李敏强,寇纪淞,林丹,等.遗传算法的基本理论与应用[M].北京:科学出版社,2002年3月第一版.
[2]姜大立,杨西龙.易腐物品配送中心连续选址模型及其遗传算法.2003.2(2):63-65.
[3]高竟成. 基于遗传算法的紧急物品配送中心选址问题的研究[J],2009, 6:3-9.
[4]吴江,李太勇,姜玥,等 基于多样化进化策略的基因表达式编程算法[J].吉林大学学报:信息科学版,2010,28(4):396-403
[5]李敬花.遗传蚁群融合算法求解多项目资源能力平衡问题[J].计算机集成制造系统, 2010,16(3):643-649.
[6]陈皓,崔杜武,崔颖安,等族群进化算法[J].软件学报,2010, 21(5) :978-990.
[7]慕彩红,焦李成,刘逸.求解约束优化问题 M-精英协同进化算法[J].西安电子科技大学学报:自然科学版,2010,37(5) :852-861
【作者简介】
马传志(1970.11-)男,黑龙江佳木斯人,佳木斯大学信息电子技术学院,副教授,研究方向:软件工程、数据库。
【文章摘要】
本文对货物配送企业的选址问题作了分析,对国内外相关问题的研究做了归纳,提出了一种基于遗传算法的货物配送企业的选址问题方案,阐述了方法的具体思想和实施方法。方案考虑了货物配送企业的选址问题过程中存在的各种参数。
【关键词】
课表;遗传算法;计算机
0 引言
货物配送企业的选址的问题最终归结为如何使得各种费用合成的总运营成本达到最小化的问题。为明确表达种费用以及在运算中使用费用值,可将各种费用转化为相应的决定参数的函数。运输费用的相关参数包括运输距离、运输方式和运输量。当然运输费用实际函数并非线性值,为了计算简便,方便判断,可简化为线性函数,这种替代只要处理得当,不影响结果的准确性。运营费用的参数包括劳动力、公用事业费用和其他开支等等。物流中心选址的固定费用则由土地使用、设备和建筑费用组成。重新选址费用由将设备移到新物流中心地址的费用、新物流中心初建费用和关闭旧址处的设施费用等参数来决定。当然还有其它一些相关参数。
多年来,选址问题的解决方法经过了不断的改进和发展,种类繁多,发展很快。特别是随着先进的计算工具的不断出现和应用,一些新的方案变得可行,这成了选址问题得以有效解决折基础。由于遗传算法的先进性和可行性,其在不同行业中应用越来越广,在企业选址问题上可以有效地应用,使问题可以有效收敛,最终解可以达到令人满意的效果,这对于改进易腐物流系统布局,提高易腐物流系统的科学决策水平具有极大的意义。
1 国内外研究现状
早期的选址问题中主要是基于运输成本的,该问题的早期理论的主要研究专家是土地经济学家和区域地理学家。1909年Weber最早提出选址问题,该问题的目标是找到一个使仓库与各处客户之间的总运输距离最短的仓库位置。1929年Holelling提出了另一个选址问题,研究一条直线上两个竞争供应商的选址。1964年,Hakimi的研究打破了以前研究的局限性,使问题更具一般性,形成了统一的理论,这一进步为后来的选址理论的进一步发展打下了坚实的基础,同时更具实用性,可以扩大实际应用。选址问题的研究有进一步深入的必要,因为选址问题和NP-完全问题经常有千丝万缕的联系,可以被更广更深的研究。
2 遗传算法的研究现状
遗传算法(Genetic Algorithm, GA)是一种全新的算法,近年来得以快速发展和广泛应用。它是基于生物体的进化的思想,主要来源于达尔文的进化论和Mendel的遗传学说。1975年Holland及其学生于密执安大学研究创建了遗传算法。由于优化效率和实用性,各国学者开始关注和研究遗传算法,对该算法进行了深入研究和改进。现在每年都有遗传算法的学术会议召开,影响范围越来越广。较为重要的会议包括国际遗传算法学会组织召开的ICGA(International Conference on Genetic Algorithms) 和FOGA( Workshop on Foundation of GeneticAlgorithms)会议,这些会议成了相关研究人员获取信息和相互交流的平台。
进入90年代,遗传算法的发展速度得以大大提高,在理论研究和应用研究都取得了很多成果,现在遗传算法在各行各业的应用都成为可能,应用领域在不断扩大,遗传算法的效率也在不断提高。研究的过程中也出现了一些一些新的理论和方法。
国内的研究人员也对遗传算法进行了不断地研究,做了许多改进。为了解决局部收敛问题,2002年,戴晓明等应用多种群遗传并行进化的思想,对不同种群基于不同的遗传策略。2004年,赵宏立等提出了并行遗传算法(Building-block Coded Parallel GA,BCPGA),对简单遗传算法进行改进。2005年,江雷等使用弹性策略来维持群体的多样性,很好地解决了TSP问题。
3 遗传算法的编码
编码负责连接实际目标问题的遗传算法的染色体位串,在企业选址问题中也要依据不同的实际问题特点进行编码的确定。
对于一般性的企业选址问题,可以采用二进制编码形式。编码选择和确定会直接影响后面的遗传算子的选择,这一点设计交叉算子和变异算法时要重要考虑。
编码要具完备性、健全性、非冗余性。
4 重心法
重心法是用来求解物流企业选址问题的一个有效的方法,首先,要有相关的地图,图中包含物流企业的各个服务对象,图中相关比例要正确; 其次,构建坐标系,为个服务对象确定坐标,获得数据; 最后,建立重心模型,求解;
【参考文献】
[1]李敏强,寇纪淞,林丹,等.遗传算法的基本理论与应用[M].北京:科学出版社,2002年3月第一版.
[2]姜大立,杨西龙.易腐物品配送中心连续选址模型及其遗传算法.2003.2(2):63-65.
[3]高竟成. 基于遗传算法的紧急物品配送中心选址问题的研究[J],2009, 6:3-9.
[4]吴江,李太勇,姜玥,等 基于多样化进化策略的基因表达式编程算法[J].吉林大学学报:信息科学版,2010,28(4):396-403
[5]李敬花.遗传蚁群融合算法求解多项目资源能力平衡问题[J].计算机集成制造系统, 2010,16(3):643-649.
[6]陈皓,崔杜武,崔颖安,等族群进化算法[J].软件学报,2010, 21(5) :978-990.
[7]慕彩红,焦李成,刘逸.求解约束优化问题 M-精英协同进化算法[J].西安电子科技大学学报:自然科学版,2010,37(5) :852-861
【作者简介】
马传志(1970.11-)男,黑龙江佳木斯人,佳木斯大学信息电子技术学院,副教授,研究方向:软件工程、数据库。