毕业设计（论文）：基于遗传算法的货物配送公司选址的求解.doc

目 录 第一章 绪论 1 1.1货物配送的研究意义 1 1.2 国内外研究现状 1 1.2.1 配送中心选址问题的国内外研究现状 1 1.2.2 遗传算法的国内外研究现状 2 1.3 本文研究的主要内容和组织结构 4 第二章 基本理论 4 2.1 遗传编码 4 2.2 二进制编码 5 2.3 改进重心法 5 2.4 并行算法 6 2.4.1 并行计算的三个基本条件 6 2.4.2 采用并行计算技术的主要目的 6 2.5遗传算法的基本原理 6 2.6 并行编程环境MPI 7 第三章 设计思想与实现 8 3.1串行算法 8 3.1.1. 串行算法设计思想 8 3.1.2. 串行程序的具体实现 10 3.1.3. 程序实现 15 3.2并行算法 15 3.2.1 并行算法思路 15 3.2.2 并行方案设计 16 参考文献 20 第一章 绪论 1.1货物配送的研究意义 确定货物配送中心选址的主要目标是使总运营成本最小，其中考虑的主要成本有运输费用、运营费用、选址固定费用和重新选址费用等。运输费用取决于运输距离、运输方式和运输量。大多数模型都假设运输费用为线性函数，但实际中正常的运输费用函数却是非线性的或指数型的，所以为计算上的简便起见，也可将非线性费用函数用线性函数来近似代替。运营费用取决于可重复使用的资源费用，如劳动力、公用事业费用和其他开支。物流中心选址的固定费用一般是最初投资的年费用，包括土地使用、设备和建筑费用。重新选址费用包括将设备移到新物流中心地址的费用、新物流中心初建费用和关闭旧址处的设施费用。新物流中心选址还包括其他限制因素，如所选位置的数量及可得性、供应源(工厂或仓库)能力、消费点(仓库或顾客)的需求、建新物流中心的总资金等。 近30 年来，选址理论发展迅速，各种不同的选址方法也越来越多，特别是电子计算机的广泛应用，促进了物流系统选址问题的研究，为不同方案的可行性分析提供了强有力的手段。由于并行遗传算法[1]将种群规模的扩大和各个子种群的隔离，使种群的多样性得以丰富和保持，并减少了未成熟收敛的可能性，大幅度地提高了求解质量。运用遗传算法解决配送中心的选址问题对于改进易腐物流系统布局，提高易腐物流系统的科学决策水平具有一定的意义。 1.2 国内外研究现状 1.2.1 配送中心选址问题的国内外研究现状 许多选址问题的早期理论是由土地经济学家和区域地理学家提出的。运输成本在选址决策中的重要作用是贯穿所有这些早期研究的共同主题。最早的选址问题是由Weber在1909年提出的。他所考虑的选址问题是确定一个仓库位置.从而使仓库与各处客户之间的总运输距离最短。对于这一问题，Isard于1958年结合了工业选址、土地使用和相关问题进行了重新研究。另一个较早的选址问题是由Holelling于1929年提出的，指在一条直线上两个竞争供应商的选址。 随后Smithies和Stevens对这一问题进行了扩展在19世纪50年代和60年代初，许多人在研究设施布置和设计问题，Losch和Moses认为经济因素与生产中心选址是有关系的。Miehle则研究使网络内的连接长度最小化的问题。在19世纪60年代中期以前，选址理论的研究工作是在各个不相关的领域内展开的，因此并没有形成统一的理论。直到1964年，Hakimi对选址问题进行了更加理论化的研究，他考虑了带有一般性的问题，就是在一个网络中选顶一个或多个设施的位置，使得总距离或设施与点之间的最大距离最小。至此，选址理论已有了很大发展，并扩展到很多实际应用中。选址研究中的典型问题，如Weber问题、中值问题、覆盖问题、中心问题多目标选址、竞争选址、不受欢迎的设施选址、选址-分配、选址-路线等，都是引起广泛关注和深入研究的热点课题，研究的也较为成熟。由于很多选址问题都是NP-完全问题，所以算法的研究有很大的余地，现在的研究也大多集中在算法的设计与改进上。目前，用于支持选址的方法主要有以下几种： 解析方法。它通常只考虑运输成本对配送中心选址的影响，而运输成本一般是运输需求 量、距离以及时间的函数，所以解析方法根据距离、需求量、时间或者三者的结合通过在坐标上显示，以配送中心位置为因变量，用代数方法来求解配送中心的坐标[2]。总之，数学规划方法模型简单，主要适用于单个配送中心选址问题。对于复杂的选址问题，解析方法常常感到困难，通常需要借助其他更为综合的分析技术。 模拟方法。它将实际问题用数学方法和逻辑关系表示出来，然后通过模拟计算机逻辑推理确定最佳布局方案，这种方法的优点是比较简单，缺点是采用这种方法选址时，分析者必须提供预定的各种网点组合方案以供分析评价，从中找出最佳组合，因此，决策的效果依赖于分析者预定的组合方案是否接近最佳方案[3]。 启发式方法。它是一种逐次逼近最优解的方法,大部分在2