基于遗传算法和层次分析法的物流配送中心选址问题研究---毕业论文

本本 科科 毕毕 业业 论论 文文 基于遗传算法和层次分析法的物流配送基于遗传算法和层次分析法的物流配送 中心选址问题研究中心选址问题研究 Research on Logistics Distribution Center Location Problem Based on Genetic Algorithm and AHP 姓 名： 学 号： 学 院：软件学院 系：软件工程 专 业：软件工程 年 级： 指导教师： 教授 年年 月月 摘摘 要要 物流配送中心是从事货物配备（集货、加工、分货、拣选、配货）和组织对 用户的送货，以高水平实现销售和供应服务的现代流通设施。近几年来，中国的 物流业得到了迅速发展，发展物流产业、建立稳定高效的物流系统已经成为中国 经济的一大热点。物流配送中心作为整个物流系统的关键环节，越来越明显地制 约着物流行业的发展。在物流配送体系中，配送中心已逐渐成为现代物流的标志， 并对整个物流配送体系的费用、效率和发展等产生影响。配送中心的选址是否合 理，对物流配送中心甚至整个物流体系的功能的发挥和综合效益的影响很大。 本文在前人研究成果的基础上，运用系统工程的理论思想为指导，结合运筹 学的一些方法研究物流配送中心的选址问题。 本文在综合考虑各种影响因素的基础上，建立了物流配送中心选址模型。在 此模型的基础上，针对经济性因素采用改进的遗传算法求解出指定个数个经济最 优解。改进的遗传算法在传统遗传算法三大遗传操作的基础上，又引入了存优操 作，进而提高了算法的收敛速度和解的优异性。此外，传统遗传算法以寻找到唯 一的一个最优解为目标，本文针对这一点对遗传算法也进行了改进，使得解的个 数可以由用户指定，从而更加满足实际的需求。 本文在考虑经济因素的基础上，兼顾环境性因素和服务性因素，使用层次分 析法对改进遗传算法选出的 N 个最优解进行综合评价，进一步选出配送中心选址 的最佳方案。 改进的遗传算法和层次分析法的结合，实现了从定量计算和定性分析两个角 度解决物流配送中心选址问题，使得所得结果更符合实际需求。 关键词：关键词：配送中心；遗传算法；层次分析法 Abstract Logistics center is a modern logistic facility which is engaged in allocating goods (goods collection, processing, distribution, electing and allocation), delivering goods and high standard service of marketing and supplying. During the few years, logistics is developing quickly in China. Logistics business and logistics system have already become the hot spots in Chinese economy. As a key point of the whole logistic system, logistics distribution seems more and more obviously restricting the development of electronic commerce. In logistics distribution system, distribution center is becoming the symbol of modern logistics, and effect the expense, efficiency and development of the entire logistics distribution system. Once the location of the distribution center confirms, it cannot be altered easily. Therefore, whether the location of the distribution center is rational will seriously influence the benefit of the logistic distribution center or even the whole logistic system. Based on research results done before, this paper uses the theory of system engineering and combines some methods of operations research to solve the location problem. To economic factors, several optimal solutions are found by improved genetic algorithm. Improved genetic algorithm adds keeping operator besides the three standard operators of traditional genetic algorithm, which improves the chance of finding optimal solution and convergence rate. Whats more, improved genetic algorithm allows users to get several solutions compared with only one in traditional genetic algorithm. Other factors such as environmental and service factors are then taken into account. In this process, solutions got from GA are evaluated by using AHP. The combination of both methods solves this problem both quantitatively and qualitatively, which makes final solution better in accordance with practical demands. Key words: distribution center; genetic algorithm; AHP. 目目 录录 第一章第一章 引言引言 1 1 1.11.1 问题的提出问题的提出 1 1 1.21.2 论文的研究内容与结构安排论文的研究内容与结构安排 1 1 第二章第二章 物流配送中心物流配送中心 3 3 2.12.1 物流配送物流配送 3 3 2.22.2 物流配送中心物流配送中心 3 3 2.32.3 物流配送中心规划物流配送中心规划 5 5 第三章第三章 常用物流配送中心选址模型与算法常用物流配送中心选址模型与算法 9 9 3.13.1 物流配送中心选址模型与算法概述物流配送中心选址模型与算法概述 1010 3.23.2 常用选址方法常用选址方法 1010 第四章第四章 物流配送中心选址模型的建立物流配送中心选址模型的建立 1414 4.14.1 概述概述 1414 4.24.2 配送中心选址模型的建立配送中心选址模型的建立 1414 第五章第五章 物流配送中心选址模型的求解物流配送中心选址模型的求解 1717 5.15.1 经济因素经济因素改进的遗传算法改进的遗传算法 1818 5.25.2 综合考虑非经济因素综合考虑非经济因素层次分析法层次分析法 2525 5.35.3 总体流程总体流程 3131 第六章第六章 系统实现系统实现 3232 6.16.1 初始界面初始界面 3232 6.26.2 中心选址界面中心选址界面 3333 6.36.3 方案评价界面方案评价界面 3535 第七章第七章 结束语结束语 3838 参考文献参考文献 4040 附录附录4242 相关研究成果相关研究成果 5151 致谢致谢5252 CONTENTS ChapterChapter 1 1 IntroductionIntroduction 1 1 1.11.1 PropositionProposition ofof thethe ProblemProblem1 1 1.21.2 TheThe ResearchResearch FrameFrame andand NewNew1 1 ChapterChapter 2 2 LogisticsLogistics DistributionDistribution CenterCenter 3 3 2.12.1 LogisticsLogistics DistributionDistribution3 3 2.22.2 LogisticsLogistics DistributionDistribution CenterCenter3 3 2.32.3 PlansPlans ofof DistributionDistribution CenterCenter5 5 ChapterChapter 3 3 StandardStandard LocationLocation ModelModel andand AlgorithmAlgorithm 9 9 3.13.1 IntroductionIntroduction ofof ModelModel andand AlgorithmAlgorithm1010 3.23.2 LocationLocation MethodsMethods DaililyDailily1010 ChapterChapter 4 4 Setting-upSetting-up LocationLocation ModelModel 1414 4.14.1 SummarySummary1414 4.24.2 Setting-upSetting-up thethe ModelModel1414 ChapterChapter 5 5 SolutionSolution ofof LocationLocation ModelModel 1717 5.15.1 EconomicEconomic FactorsFactorsImprovedImproved GAGA1818 5.25.2 ConsiderationConsideration ofof allall FactorsFactorsAHPAHP2525 5.35.3 TheThe WholeWhole ProcessProcess3131 ChapterChapter 6 6 SystemSystem ImplementsImplements 3232 6.16.1 InitialInitial InterfaceInterface3232 6.26.2 DestributionDestribution CenterCenter SelectionSelection InterfaceInterface3333 6.36.3 PlanPlan EvaluationEvaluation InterfaceInterface3535 ChapterChapter 7 7 ConclusionsConclusions 3838 ReferencesReferences 4040 AppendixAppendix 4242 RelatedRelated ResearchResearch ResultsResults 5151 AcknowlegementsAcknowlegements 5252 厦门大学软件学院毕业论文 基于遗传算法和层次分析法的物流配送中心选址问题研究 1 第一章第一章 引言引言 1.1 问题的提出问题的提出 在竞争日益激烈的今天，如何赢得更多的利润是企业家关注的焦点。越来越 多的企业开始关注被经济学家成为继劳动力、自然资源之后的“第三个利润源泉” 物流管理。在面临着金融危机的当今社会，物流业已作为我国十大振兴产业 之一提上了议程。物流科学作为提升物流业发展的动力，自产生以来便显示出它 强大的生命力，成为当代最活跃、最有影响力的新学科之一。 现代的物流是信息化的物流，它具备完善的信息系统和信息网络，无论是决 策、运作过程与管理都离不开信息系统的的支撑。在整个物流系统中，物流配送 中心通过有效地组织配货和送货，使资源的最终端配置得以完成，是提高整个系 统的运行水平的主要一环。配送中心已逐渐成为现代物流的标志，并对整个物流 配送体系乃至整个物流体系的费用、效率和发展等产生影响。 近几十年来，我国的配送中心发展迅速，但仍然存在着很多的问题，同美国、 日本等发达国家相比，还有很大的差距。目前，我国的物流水平还比较低，难以 满足时代的需求。因此，研究现代物流系统，特别是物流的核心配送中心及其 选址就尤其重要。 1.2论文的论文的研究内容与结构安排研究内容与结构安排 本文从系统的角度分析物流、物流配送中心，将系统工程的思想和运筹学的 方法结合起来，研究并求解物流配送中心选址模型，使配送中心的选址模型比传 统的模型和现阶段研究出的一般模型有更多的优点，并且在求解上可利用计算机 方便地实现。在建立选址模型之后，运用改进的遗传算法和层次分析法，综合考 虑经济因素和其他多种因素对模型进行求解，从而使得求解的结果更加符合实际 的需求。 本文首先介绍了项目的研究背景；在第二章中详细阐述了物流配送、物流配 送中心的相关概念及特点；在第三章中分析评价了针对该问题的当前主要建模方 法和模型求解算法；在第四章中运用改进的遗传算法和层次分析法对模型进行了 厦门大学软件学院毕业论文 基于遗传算法和层次分析法的物流配送中心选址问题研究 2 求解；最后，介绍了编码实现的可操作系统。 厦门大学软件学院毕业论文 基于遗传算法和层次分析法的物流配送中心选址问题研究 3 第二章第二章 物流配送中心物流配送中心 2.1 物流配送物流配送 配送是按照用户的订货要求，在物流据点进行分货、配货等工作，并将配好 的货物按时送达指定的地点和收货人的物流活动1。配送不仅仅是一种强化服务 的手段，更重要的在于它是一种先进的物流方式和物流体制。 配送作为物流中一种特殊的、综合的活动形式，是与商流的最终实现联系最 紧密的部分。特别是在当今零库存控制与快速反应的生产经营方式下，配送已成 为现代物流在经济合理区域范围内的一个缩影和全部活动的体现。物流配送有利 于促进物流运动的社会化、有利于实现物流资源的合理配置、有利于开发和应用 新技术、有利于创造社会整体效益。 配送的形式因产品、企业、流通环境的不同而不同，但无论何种形式，配送 的一般流程比较规范：配送中心根据客户要求进货，在配送中心进行加工处理， 然后经其他配送中心或直接送给客户2。配送流程图如图 2-1 所示。 图图 2-12-1：配送流程配送流程 由图可见，配送中心作为配送活动的中转站，是连接工厂与客户的中间 桥梁，是实现物流配送的重要载体。 2.2 物流配送中心物流配送中心 2.2.1 配送中心的定义配送中心的定义2 物流配送中心是以组织配送性销售或供应，执行实物配送为主要职能的流通 型结点；是一种新兴的经营管理设施，具有满足多量少样的市场需求及降低流通 厦门大学软件学院毕业论文 基于遗传算法和层次分析法的物流配送中心选址问题研究 4 成本的作用。配送中心的建立是基于物流合理化合发展市场两个需要而发展的。 所以配送中心可以定义为：配送中心是从事货物配备（集货、加工、分货、拣选、 配货）和组织对用户的送货，以高水平实现销售和供应服务的现代流通设施。 2.2.2 配送中心的分类配送中心的分类 由于建造配送中心的企业背景不同，配送中心的功能、构成凡是和运营方式 有很大的区别，因此在规划配送中心时要充分注意配送中心的类别及特点。 配送中心按照配送品种可分为专业化配送中心和综合性配送中心；按照服务 性质可分为供应型配送中心和销售型配送中心；按照地域范围可以分为城市配送 中心和区域配送中心；按照物流功能可分为储存型配送中心、流通型配送中心和 加工型配送中心；按照经营主体可分为制造商型配送中心、批发商型配送中心、 零售业型配送中心和仓储运输业型配送中心3。 2.2.3 配送中心的意义配送中心的意义 建立配送中心的意义可以从三个方面来考虑：其一，扩大市场占有率。出于 竞争的需要，企业除了提供品质优良的货品外，还必须提供适时适量的配送服务 以扩大市场占有率。其二，降低物流成本，这也是建立物流配送中心的根本目的。 一些连锁企业与生产企业的营业部门常常整合成立大型的配送中心，以提高作业 效率，降低库存和配送费用，如图 2-2 所示。其三，提高服务质量。良好的配送 中心能够快速反应处理订单及出货，实现多品种少批量的订货及多频率配送以满 足消费者需求。 图图 2-22-2：配送中心的作用：配送中心的作用 2.2.4 配送中心的系统结构配送中心的系统结构 配送中心是一个系统工程，其系统的构成如图 2-3 所示，包括物流系统、信 息系统和运营系统三个方面。物流系统包括物流设施、物流设备和作业方法；信 厦门大学软件学院毕业论文 基于遗传算法和层次分析法的物流配送中心选址问题研究 5 息系统包括配送中心作业管理、业务管理与决策支持系统；运营系统包括组织机 构、人员配备、作业标准和规范等。通过三个子系统的有机结合，实现配送中心 系统的高效运行。 图图 2-32-3：配送中心系统构成：配送中心系统构成 2.3物流配送中心规划物流配送中心规划 在电子商务时代，信息化、现代化、社会化的新型物流配送中心可归纳为以 下几个特征2:物流配送反应速度快、物流配送功能集成化、物流配送服务系列化、 物流配送作业规范化、物流配送目标系统化、物流配送手段现代化、物流配送组 织网络化、物流配送经营市场化、物流配送流程自动化、物流配送管理法制化。 配送中心的规划要素就是影响配送中心系统规划的基础数据和背景资料，主 要包括：配送的对象或客户、配送货品的种类、配送货品的数量或库存量、配送 的通路、物流服务水平、物流的交货时间、配送货品的价值或建造的预算。 2.3.12.3.1 规划目标规划目标 物流配送中心规划具有以下几个方面的目标4： 1、服务性目标。这是一个主要目标，指配送中心能向用户提供各种服务。 服务性目标主要包括：能向用户提供多种信息服务；能向企业的不同部门、不同 层次和不同环节提供各种信息服务；具有信息的及时反馈功能。 2、快捷性目标。配送中心要能够依据用户的要求，把货物准时送到用户指 厦门大学软件学院毕业论文 基于遗传算法和层次分析法的物流配送中心选址问题研究 6 定的地点，这需要企业在配送系统中建立快捷反应系统，以实现快捷目标。主要 包括：快捷灵活的配送、发货系统和运输系统；自动化的库存管理系统、分拣系 统和理货系统；快捷灵活的订货系统和收获系统；方便、灵活、及时的信息服务 系统。 3、降低成本目标。主要包括：有效利用配送面积和空间；科学合理选择运 输工具和路线；保持合理的库存规模和结构。 2.3.22.3.2 规划原则规划原则 物流配送中心在进行规划时应该遵循以下原则4： 1、定量分析与定性分析相结合的原则。物流配送中心系统分析总是遵循着 “定性-定量-定性”这样一个循环往复的过程，不了解物流配送中心各个方面的 性质，就不可能建立起来探讨物流配送中心定量关系的数学模型。同样通过数学 模型得出的结果也需要重新用于物流配送中心设计的过程中。只有将定性与定量 二者相结合起来综合分析才能达到物流配送中心整体优化的目的。 2、当前利益与长远利益相结合的原则。当前利益和长远利益这两方面在不 能兼顾时，需要通过全面分析论证，找到平衡点。 3、局部利益与整体利益相结合原则。在分析物流配送中心这一系统时，最 理想的状态是既可以保证系统的整体利益最大，也可以保证各个子系统的利益最 大。但是由于物流配送中心系统中各个物流环节是相互影响和相互制约的，所以 各个子系统的局部利益与整个系统的利益往往不一致。系统分析的准则则是整体 利益最大，在这一前提下，尽管某一子系统未获得最大利益，只要方案的整体利 益最优，这种方案仍然是可取的。 4、可持续发展原则。物流配送中心应该走可持续性发展的道理，为今后的 进一步发展提供硬件和软件上的升级空间。 2.3.32.3.3 规划步骤规划步骤 物流配送中心规划主要包括功能规划、选址规划、作业流程规划、信息系统 规划和设施设备规划，大体可以按照以下步骤进行，如图 2-4 所示。 厦门大学软件学院毕业论文 基于遗传算法和层次分析法的物流配送中心选址问题研究 7 图图 2-42-4：配送中心规划步骤：配送中心规划步骤 前期准备：为配送中心规划提供必要的基础资料，工作采用调研的方法，包 括网上调研、图书资料调研与现场调研。主要内容包括：收集配送中心建设的内 部条件、外部条件及潜在客户的信息；分析配送中心经营商品的品种、货源、流 量及流向；调查物流服务的供需情况，物流行业的发展状况等。 确定目标及准则：确认配送中心建设的目标是配送中心规划的第一步，主要 是依据前期准备工作的资料，确定配送中心建设的阶段性目标。配送中心建设的 原则一般是根据物流学远离及项目的实际情况确定的。 功能规划：是将配送中心作为一个整体的物流系统来考虑，依据确定的目标， 规划配送中心为完成业务而应该具备的物流功能。 选址规划：配送中心拥有众多建筑物、构筑物以及固定机械设备，一旦建成 很难搬迁，如果选址不当，将会付出长远代价，所以对于配送中心的选址规划要 给予高度的重视。选址规划主要包括：分析约束条件、确定评价标准、选择选址 方法、得出选址结果。 作业流程规划：是配送中心规划的重要步骤，决定了配送中心作业的详细要 求，对后续的建设有重要影响。不同类型的配送中心，其作业流程也不同，需要 根据实际情况来考虑。 信息系统规划：是配送中心规划的重要组成部分，要考虑满足配送中心内部 作业效率，还要获取和处理外部信息系统的各种营业信息。信息系统规划一般包 括配送中心管理信息系统分析设计和配送中心网络平台两部分。 设施设备规划:是保证配送中心正常运作的必要条件。设施设备规划涉及到 建筑模式、空间布局、设备安置等多方面的问题，需要运用系统分析的方法求得 厦门大学软件学院毕业论文 基于遗传算法和层次分析法的物流配送中心选址问题研究 8 整体优化，最大限度地减少物料搬运、简化流程。包括：原有设施设备分析、配 送中心的功能分区、设施的内部布局、功用设施及设备规划。 厦门大学软件学院毕业论文 基于遗传算法和层次分析法的物流配送中心选址问题研究 9 第三章第三章 常用物流配送中心选址模型与算法常用物流配送中心选址模型与算法 配送中心选址是指在一个具有若干供应点以及若干需求点的经济区域内确定 配送中心的数目以及各配送中心的具体坐落位置3。配送中心的选址方式往往决 定着物流的配送距离和配送模式，进而影响着物流系统的运作效率。因此，研究 物流配送中心的选址具有重要的理论和现实应用意义。这一课题也得到了很多国 内外学者的重视，适应于不同范围的选址模型及算法相继产生。配送中心选址的 一般程序如图3-1所示。 图图3-13-1：配送中心选址的一般程序：配送中心选址的一般程序 1、收集整理历史资料：包括对备选区域、低价、业务量、费用、配送路线、 设施现状的分析及需求预测。 2、选定备选地址：首先根据分析得出的各影响因素进行定性分析和审慎评 估，大致确定出几个备选的地址。 3、优化备选地址：确定了备选地址后，对这些具体的地点进行详细的考核。 在这一步建立数学模型，通过定量计算，得到优化坐落地点。 4、优化结果复查：在通过定量计算得出经济最优解后，考虑非经济因素对 配送中心坐落地点的影响，综合各种因素对优化结果进行复查。 5、确定最终方案：如果优化结果通过复查，即可将优化结果作为最终方案。 如果没有通过复查，重新返回第二步，进行备选地址筛选、优化备选地址、复查 厦门大学软件学院毕业论文 基于遗传算法和层次分析法的物流配送中心选址问题研究 10 等一系列步骤，直至得到最终结果。 3.1 物流配送中心选址模型与算法概述物流配送中心选址模型与算法概述 物流配送中心的选址方法主要有定性和定量两种方法。定性方法有专家打分 法、Delphi法等，定量方法有重心法、P中值法、数学规划方法、多准则决策方 法、解决NP hard 问题（多项式复杂程度的非确定性问题）的各种启发式算法、 仿真法以及这几种方法相结合的方法等5。 尼比和劳（Neebe ,.,2 , 1;,.,2 , 1( , 0, 0, 0njlkmiCYX iijik 模型中各字母说明如下： U-总费用； -工厂的个数；-备选物流配送中心的个数；-需求点的个数；lmn -从工厂到配送中心 的运输费率；-从工厂到配送中心 的运输量；- ki aki ki Xki ij b 从配送中心 到需求点的运输费率；-从配送中心 到需求点的运输量；ij ij Yij 配送中心 流转的单位管理费用；-标志位，标记配送中心是否选中，取值 0 i gi i f 或 1，0 代表配送中心 未选中，1 代表配送中心 被选中； -配送中心 的建设ii i Ci 费用;-工厂的最大供货量；-配送中心 的最大容量；-需求点的需求 k Ak i Mi j Rj 量。 其中， （4-2）式即配送中心的总费用；（4-3）式表示从工厂发往配送中心 的产品总量不超过它的供货能力；（4-4）式表示工厂的供货量不能超过配送中 心的最大容量；（4-5）式表示配送中心的供货量不能超过自身的最大容量； （4-6）式表示在实际中这些参数为非负值。 厦门大学软件学院毕业论文 基于遗传算法和层次分析法的物流配送中心选址问题研究 17 第五章第五章 物流配送中心选址模型的求解物流配送中心选址模型的求解 配送中心选址的布局如图5-1所示， E1、E2为两个供应工厂。有8 个需求点 Z1、Z2、Z8，各需求点的需求量分别为15、10、10、15、10、15、10、5，单 位为吨。物流配送中心备选地址共6 个，分别为S1、S2、S6，其固定建设费 用分别为40、90、85、20、30、65，单位为万元；容量限制分别为 15、45、30、20、20、30，单位为吨；流转单价分别为2、24、12、2、3、12， 单位为元/吨。 图图 5-15-1：工厂、备选配送中心和需求点网点位置示意图：工厂、备选配送中心和需求点网点位置示意图 工厂对各物流配送中心的单位运费见表5-1；各配送中心对各需求点的单位 运费见表5-2。 厦门大学软件学院毕业论文 基于遗传算法和层次分析法的物流配送中心选址问题研究 18 表表5-15-1：工厂对各物流配送中心的单位运费表：工厂对各物流配送中心的单位运费表 单位：元/吨 费率S1S2S3S4S5S6 E1871312119 E271188712 资料来源：宾厚，单圣涤：物流配送中心选址模型及其算法分析，2008年7月 表表5-25-2：物流配送中心对需求点的单位运费表：物流配送中心对需求点的单位运费表 单位：元/吨 费率Z1Z2Z3Z4Z5Z6Z7Z8 S1469861263 S28314931476 S349610121294 S47815531583 S58712551486 S6269137635 资料来源：宾厚，单圣涤：物流配送中心选址模型及其算法分析，2008年7月 作为赢利性企业，经济因素当然是建立物流配送中心所要考虑的首要目标， 因此本文中对模型的求解首先从经济因素加以考量，利用改进的遗传算法选择出 经济性较优的几个解，之后再结合其他影响因素，利用层次分析法对这几个解进 行综合评价，最终确定综合最优的选址方案。 5.1 经济因素经济因素改进的遗传算法改进的遗传算法 遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化 过程的计算模 型，是一种通过模拟自然进化过程搜索最优解的方法。它由美国 Michigan 大学 J.Holland 教授于 1975 年首先提出 。其运行步骤图 5-1 所示。 遗传算法的原理非常简单。以一群个体为例，它们都有自己的DNA。然 后衡量每一个个体的适应性（把它看做是适用于个体的DNA 的官能来衡量 ） ， 并且使那些更适应的个体更优可能繁衍。而最不适应的个体将会被灭绝。每个 幸存者都有机会繁衍（重要的是任何幸存者都可能会繁衍，如果不太适应的话， 厦门大学软件学院毕业论文 基于遗传算法和层次分析法的物流配送中心选址问题研究 19 仅仅是降低了可能性）。合并双亲的 DNA,对合并后的 DNA 应用随机变异以 模拟繁衍。理论上来说，新的个体和双亲是一样适应的，由于变异或增或减会 有些微小的变化。然后循环周而复始，直至满足退出条件而结束。 图图 5-15-1：遗传算法的运行步骤：遗传算法的运行步骤 在传统的遗传算法中，遗传操作一般都包括选择、交叉和变异三种基本形 式，它们构成了遗传算法具备强大搜索能力的核心。本文在此基础上又引入了存 优操作，用于保留每一代群体中的最优个体，使之直接进入下一代。这一操作能 够更好地改进遗传算法的收敛速度和提高找到全局最优解的概率。 此外，传统遗传算法的求解结果为唯一的最优解，但往往存在适应值相同但 基因不同的情况。在实际运用中，也常常需要针对经济因素选出多个较优方案， 再对这些方案进行其他非经济因素的评价，进而确定最终方案。改进的遗传算法 可以选出 N 个（N 由用户指定）较优的解，从而可以更方便地进行下一步的评价 工作。 改进遗传算法的运行步骤如图 5-2 所示。 厦门大学软件学院毕业论文 基于遗传算法和层次分析法的物流配送中心选址问题研究 20 图图 5-25-2：改进的遗传算法流程图：改进的遗传算法流程图 厦门大学软件学院毕业论文 基于遗传算法和层次分析法的物流配送中心选址问题研究 21 5 5. .1 1. .1 1 编编码码 在遗传算法中如何描述问题的可行解, 即把一个问题的可行解从其解空间转 换到遗传算法所能处理的搜索空间的转换方法就称为编码。要将实际问题转化为 数学模型，就必须将实际问题的解决方案（参数空间）一一映射为数学问题的编 码空间。因此，构造遗传算法的第一步是编码，每一组编码代表一组备选解。针 对已建立的数学模型，本文采用一维整数数组进行编码，编码策略如图5-3所示。 图图 5 5- -3 3：解解的的编编码码策策略略 图 5-3 中 m 表示需求点个数，n 表示配送中心个数。第 1m 位表示各需求 点由哪个配送中心供货，取值范围 1n。第 m+1 到 m+n 位表示各配送中心由哪 个工厂送货，取值范围 0k（k 为工厂个数） ，取值为 0 表示没有工厂为该配送中 心送货。这样的编码满足了编码空间到解空间的一一映射关系。 例如，针对本章开始提出的实际问题，图 5-4 所示的编码代表了此问题的一 个解。 图图 5 5- -4 4：解解的的编编码码实实例例 其中，编码长度为需求点个数（ 8 个）与备选配送中心个数（ 6 个）之 和（14） 。为方便说明，将编码编号为 114。第 1 位到第 8 位表示该编号的 需求点由哪个配送中心送货，取值范围16（备选配送中心个数）；第 9 位 到第 14 位表示第该编号减 8（需求点个数）个配送中心由哪个工厂送货，取 值范围 02（工厂个数） ，其中，0 表示没有工厂为该中心送货，即该配送中 心（中心 4）没有被选中。 该编码代表的配送方案如 表 5-1 和表 5-2 所示。 厦门大学软件学院毕业论文 基于遗传算法和层次分析法的物流配送中心选址问题研究 22 表表 5-15-1：各需求点配送方案：各需求点配送方案 需需求求点点12345678 供供货货中中心心26316251 表表 5-25-2：各工厂到配送中心的供货方案：各工厂到配送中心的供货方案 配配送送中中心心123456 供供货货工工厂厂21121 5 5. .1 1. .2 2 适适应应函函数数 适应值代表了生物个体适应环境的程度，直接决定了生物个体的存活概率。 由于适应值是群体中个体生存机会选择的唯一确定性指标,所以适应函数的形式 直接决定着群体的进化行为. 为了直接将适应函数与群体中的个体优劣度量相联 系, 在遗传算法中适应值规定为非负,并且在任何情况下总是越大越好.物流配送 中心选址问题所建立的目标函数是求总费用的最小化值, 针对该式建立如下适应 函数7。 maxmax )(),(CkfkfC若 g(k)= (5-1) 0,其他 式(5-1)中，f(k)为备选解k对应的系统总费用，是到当前所有代f(k)的最 max C 大值，会随着代数有所变化。 5 5. .1 1. .3 3 遗遗传传操操作作 在传统的遗传算法中， 遗传操作一般都包括选择、交叉和变异三种基本 形式，它们构成了遗传算法具备强大搜索能力的核心。本文在此基础上又引入了 存优操作，用于保留每一代群体中的最优个体，使之直接进入下一代。从而更好 地改进了遗传算法的收敛速度和提高找到全局最优解的概率。 各遗传操作详细阐述如下： 1、选择操作：采用最优方式实现选择操作,即首先保证父代种群中适应值最 大的染色体在子代中至少出现1次,然后按照标准的轮盘赌方式进行选择操作。 适应值大的个体被选中的概率就大，但适应度小的个体也有被选中的可能。这样 厦门大学软件学院毕业论文 基于遗传算法和层次分析法的物流配送中心选址问题研究 23 可以保证最优秀的染色体被保留到下一代。 2、交叉操作：遗传算法的交叉操作是模仿自然界有性繁殖的基因重组过程, 其作用在于将原有的优良基因遗传给下一代个体, 并生成包含更复杂基因结构的 新个体。 具体进行交叉操作时，首先利用随机函数产生任一小于1的概率，当此概率 小于预定义的交叉概率时进行交叉操作。其作用在于将原有的优良基因遗传给下 一代个体，并生成包含更复杂基因结构的新个体。本文采用两点交叉法进行交叉 操作。每次操作交换两个个体的随机长度个基因。 如本章开始所提出的实际问 题中，有8个需求点，6个备选配送中心，2个工厂。假设某个体1编码如图5-5所 示，个体2编码如图5-6所示。当这两个个体发生交叉时，随机挑选任意长度个基 因进行对应位置交叉，如交叉从第二位到第五位的4位基因，则交叉后个体1、个 体2的编码如图5-7、图5-8所示。交叉操作使运算包含更多的信息量，也有助于 算法收敛。 图图5-55-5：个体：个体1 1编码编码 图图5-65-6：个体：个体2 2编码编码 图图5-75-7：交叉后个体：交叉后个体1 1的编码的编码 图图5-85-8：交叉后个体：交叉后个体2 2的编码的编码 厦门大学软件学院毕业论文 基于遗传算法和层次分析法的物流配送中心选址问题研究 24 3、变异操作：变异操作对自然界中生物基因突变的模拟，它可以产生更多 种类的备选解，从而保证群体的多样性。进行变异操作时，用随机函数产生任一 小于1的概率，当此概率小于预定义的变异概率时进行变异操作。每发生一次变 异，随机产生一个符合条件的值，插入当前个体基因的任意位置。 4、存优操作：对第一代群体，先求出 N 个（N 由用户指定）最优个体并储 存起来。对此后的每一代群体，首先求出当代的最优个体，再将当代最优个体与 上一代的 N 个最优个体进行比较排序，从这 N+1 个个体中选出适应值最大的 N 个个体，生成新的 N 个最优个体进入下一代。 存优操作用于保存当前代具有最佳适应值的个体，使其直接进入下一代，从 而避免当前最优基因的丢失。当前最优基因被存储为新一代基因的末尾，并与新 一代基因进行比较。如果新一代基因中存在比最优基因适应度更大的个体，则最 优基因被替换。这就使得最优个体被保留且有机会变得更强大。 5 5. .1 1. .4 4 数数值值求求解解 以本章开头所述的问题为例 ，设置交叉概率为 0.2，变异概率为 0.2， 群体规模为 100，繁殖代数为 50，需要的方案数为 3。使用改进的遗传算法 求解该问题， 所得结果如表 5-3 所示。 使用传统遗传算法求解该问题的所得结果如表5-4 所示。 表表 5-35-3：改进遗传算法求解结果：改进遗传算法求解结果 总费用 1851521.90 编码 52656522010022 方案 1 选中的配送中心2、5、6 总费用 2451531.30 编码 66211445210221 方案 2 选中的配送中心1、2、4、5、6 总费用 3101689.47 编码 63326512111022 方案 3 选中的配送中心1、2、3、5、6 表表 5 5- -4 4：传传统统遗遗传传算算法法求求解解结结果果 厦门大学软件学院毕业论文 基于遗传算法和层次分析法的物流配送中心选址问题研究 25 总费用 3301569.03 编码 64632511122121 选中的配送中心1、2、3、4、5、6 由此可见，改进后的遗传算法无论在求解结果的质量还是数量上都要优于 传统的遗传算法。 5.2综合考虑非经济因素综合考虑非经济因素层次分析法层次分析法 遗传算法的求解以总费用最小为目标，但影响物流配送中心选址合理性的因 素不光有经济性因素，还包括环境性因素（如地理位置、交通条件、可持续发展 性等）和服务性因素（如配送的中转效率、自动化程度、人力素质等） 。因此， 合理的配送中心选址应当对这些因素进行综合考虑。层次分析法正是这样一种多 目标决策分析法。特别是将决策者的经验判断给予量化，对目标（因素）结构复 杂且缺乏必要数据的情况更为实用。 5 5. .2 2. .1 1 层层次次分分析析法法的的基基本本原原理理 层次分析法是系统评价的一种方法，是1937 年由美国学者 A.L.萨迪最 早提出的。层次分析法是一种定性分析和定量分析相结合的评价决策方法，它 将评价者对复杂系统的评价思维过程数学化。其基本思路是评价者通过将复杂 问题分解为若干层次和若干要素，并在同一层次的各要素之间简单地进行比较、 判断和计算，就可以得出不同替代方案的重要度，从而为选择最优方案提供决 策依据。 5 5. .2 2. .2 2 标标度度 为使各因素之间进行两两比较得到量化的判断矩阵，引入19 的标度。 根据心理学家的研究提出：人们区分信息等级的极限能力为72，特定制表 5-5。 厦门大学软件学院毕业论文 基于遗传算法和层次分析法的物流配送中心选址问题研究 26 表表 5 5- -5 5：标标度度方方法法 标 度 ij 定义 1 因素与因素相同重要ij 3 因素比因素略重要ij 5 因素比因素较重要ij 7 因素比因素非常重要ij 9 因素比因素绝对重要ij 2，4，6，8为以上两判断之间的偶数中间状态对应的标度值 倒数 若因素与 因素比较得到判断值为ji1/ jiij 5 5. .2 2. .3 3 运运行行步步骤骤 利用层次分析法进行方案要素权重的评价分析流程如图 6-9 所示： 图图 5-9：层次分析流程图：层次分析流程图 1、 系统描述。在充分考虑配送中心物流系统目标与功能的基础上，对选址问题 涵盖的范围加以界定； 2、 影响因素分析。可以利用专家经验等方法找出影响物流配送中心选址的要素 并进行归类分析； 厦门大学软件学院毕业论文 基于遗传算法和层次分析法的物流配送中心选址问题研究 27 3、 建立层次结构。将所有影响因素进行分类，一般分为目标层 A、准则层 C 和 措施层 P 三个层次； 4、 建立判断矩阵 A-C、C-P，计算每个影响因素的权重。矩阵中元素的值表 ij X 示该层中第 i 个因素相较第 j 个因素的重要程度，而各影响因素相对权重则 可以通过用近似法求解矩阵特征向量的方法求得，特征向量的值即各因素的 相对权重； 5、 进行一致性检验。分别求解判断矩阵 A-C、C-P 的最大特征值 1，2，并 通过 求得一致性指标。若 C.I.小于 0.1 则视为满足一致性条 1 max n n IC 件，否则重新进行判断矩阵的建立； 6、 确定各方案权重值。即进行 P 层各方案相对权重的计算：设 A-C 矩阵中目标 层 A 对准则层 C 的相对权重为,C-P 矩阵中准则层 C 对方案层),.,(a 321 aaa i P 的相对权重为,l=1,2,k.。则各方案的相对权重可通过),.,( 21nllll bbbb 权重组合而得到，P 层方案 n 的相对权重可表示为：),.2 , 1(klba l 、 ； k j njjn bav 1 7、 选择权重最大的方案为最佳方案。 5 5. .2 2. .3 3 数数值值计计算算 针对本章问题实例，运用层次分析法对改进遗传算法求出的三个方案进行 方案评价。具体步骤如下： 1、影响因素分析：影响配送中心物流系统的因素主要有三方面：一是经 济性因素，这一因素已经由遗传算法进行了择优处理，不需要再进行措施层的 具体评价；二是环境性因素，包含地理位置、交通便利性等；三是服务性因素， 包括配送效率、通信辅助设施等。 2、建立层次结构。将影响因素进行层次分类，分为总目标层、准则层和 措施层三个层次，如图 5-10 所示。 厦门大学软件学院毕业论文 基于遗传算法和层次分析法的物流配送中心选址问题研究 28 图图 5 5- -1 10 0：配配送送中中心心选选址址系系统统影影响响因因素素层层次次结结构构图图 3、建立判定矩阵，计算 各影响因素 相对权重，并检验一致性。 准则层 的影响因素判定矩阵、措施层的两个个影响因素判定矩阵分别如表5-6、5- 7、5-8 所示。 表表 5 5- -6 6：准准则则层层影影响响因因素素判判定定矩矩阵阵