学校代码学号面向物流配送系统中定位路径优化的聚类进化算法研究专业控制科学与工程姓名柴宏建指导老师高尚策日期年月日万方数据东华大学学位论文原创性声明本人郑重声明我恪守学术道德，崇尚严谨学风。所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已明确注明和引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品及成果的内容。论文为本人亲自撰写，我对所写的内容负责，并完全意识到本声明的法律结果由本人承担。学位论文作者签名日期年月日万方数据东华大学学位论文版权使用授权书学位论文作者完全了解学校有关保留使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅或借阅。本人授权东华大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印缩印或扫描等复制手段保存和汇编本学位论文。保密，在年解密后适用本版权书。本学位论文属于不保密。学位论文作者签名指导教师签名日期年月日日期年月日万方数据面向物流配送系统中定位路径优化的聚类进化算法研究面向物流配送系统中定位路径优化的聚类进化算法研究摘要随着经济全球化的快速发展，物流在经济活动中的地位与作用也日益明显。本文详细介绍了物流系统的相关理论，重点分析了物流决策模型中的中心选址与配送路径两个热点问题。本文在传统物流分析模型的基础研究之上，根据系统分析的思想，对配送中心选址问题及车辆运输路径规划问题的组合优化进行了研究。为了解决定位运输车辆路径安排这组合优化问题，人们提出了各种求解算法，进化算法是其中简单有效的智能算法。本研究针对传统进化算法求解问题的不足如二进制编码串过长，算法“早熟”现象等进行了系列的改进，通过对模拟数据的仿真分析，证明了其有可行性及有效性。本文的主要研究工作如下首先，对问题的常用模型进行了详细的分析，给出定位配给和运输路线规划问题的数学模型及其计算方法，在此基础上建立了个将两者进行整合的数学模型，并设计了种简单有效的两阶段求解算法。其次，针对传统进化算法实现过程中的不足提出了系列的改进措施。采用自然数编码方案与自适应交叉变异算子组合使得解空间搜索能力得到提高同时引入惩罚函数对约束进行处理，并对进化过程产生的非法个体采取相应措施，降低了过早收敛的可能性。最后，对本文的研究内容进行了总结，指出了本文模型和算法存在的不足，并结合实际情况中问题的复杂性，对该课题未来的研究方向进行了展望。关键词聚类路径优化中心选址进化算法万方数据面向物流配送系统中定位路径优化的聚类进化算法研究,.,.,.,.万方数据面向物流配送系统中定位路径优化的聚类进化算法研究目录摘要第章绪论.选题的研究背景及意义选题背景研究意义.国内外理论研究现状.本文的研究内容及技术路线研究内容技术路线第章定位运输路线安排问题研究.物流配送中心研究.配送中心选址概述配送中心选址原则及方法.问题的描述.问题.问题.问题.的研究方向.第章定位运输路线安排问题的算法研究.遗传算法.遗传算法概述遗传算法的特点遗传算法的基本原理遗传算法的基本流程遗传算法的改进.聚类算法.聚类算法概述聚类算法基本原理万方数据面向物流配送系统中定位路径优化的聚类进化算法研究聚类算法的步骤聚类算法的性能分析第章定位运输路径安排问题的数学模型.问题的分类.按内容分类按算法分类.模型分析.问题模型.问题模型.问题模型需要考虑的因素模型的建立.模型假设模型参数及决策变量数学模型第章算法设计.算法思路第阶段的聚类算法设计.值学习的遗传算法设计遗传聚类算法设计实验测试.第二阶段改进混合进化算法的路径安排设计算例分析.第章结束语.结论展望.参考文献攻读硕士学位期间发表的学术论文致谢万方数据面向物流配送系统中定位路径优化的聚类进化算法研究第章绪论.选题的研究背景及意义选题背景随着经济全球化的发展以及物质需求的日益提高，物流在经济活动中的作用越来大，被称作“第三利润源泉”，在流通行业中已经成为最重要的竞争领域，并且在未来日趋激烈的市场竞争必然起着至关重要的作用,。些发达国家已经具备了比较成熟的物流管理理念与完善的物流系统。在加入以后，为提高生产企业在经济全球化环境下的竞争力，我国也加快了发展现代物流业的步伐。企业经营者都希望能够物流系统中的每个环节都能更好的得到协调运作，以便能够为客户提供更高质量的服务，因此物流决策显得极为重要。在传统的物流模型中，最值得关注的两个问题分别是定位配给问题,和车辆运输路线安排问题，。问题更多的是对配送中心的选址和需求配给之间的关系进行考虑，从而对配送中心的个数与位置进行决策，使得整体物流成本最小。在中，般认为从配送中心到需求点的运输线路是呈放射线状的，在确定中心选址时，没有对车辆巡回路线进行充分的考虑，这就导致运输成本的较大浪费而问题是指在中心的位置选定的情况下，设计车辆在各需求点间的运输路线，在满足客户需求的前提下，确保总行程路线最短，也即运输成本最低。在问题中，车辆巡回路线安排被考虑到其中，运输效率得到提高，与实际情形比较吻合。但是在这个问题中，配送中心的选址问题没的得到很好的考虑，这就使得物流成本可能没有达到整体最低。由此，以及其他物流模型为基础，提出集成物流系统的概念，从而使物流系统的运作效率得到提高。这种概念认为根据配送中心的定位货物的配给与运输路线安排三者之间的相互影响的关系，对物流系统进行相应地优化与综合管理。从这种概念出发，国外学者对物流配送中心的选址及运输路线安排问题，进行了综合研究。在可选配送中心为多个的情形下，通过模型的建立，系统在确定最佳的中心的数量与位置的同时也要保证运输路线安排也趋向最优，使得物流系统整体成本最大限度地降低，从而使得产品的分销效率进步得到提高。万方数据面向物流配送系统中定位路径优化的聚类进化算法研究从世纪年代起，国外众多学者对问题展开了系列的研究，从实际问题中抽象出来了些优化的数学模型，并且也制定了相应的求解算法。但由于问题的属于难题，对它的研究进度就相对比较缓慢。从年代以来，国外的学者在物流系统优化问题中和模型的研究中取得了定的进展促进了问题研究进步的发展。随着物流系统的集成化概念的推广以及经济的全球化发展，针对问题的早已成为学术研究的热门课题。研究意义目前，在物流系统设计的过程中,决策者需要对下面的情况进行考虑.配送中心的数目与位置，即中心选址.将所有的需求点按区域进行划分，并由中心点服务.从配送中心到各个需求点的运输路线方案。在些情况下，这些因素对物流系统的总成本以及所提供的服务质量有着相当重要的影响。目前，许多用以确定中心选址问题的数学模型被建立。但是，在这些模型中，从中心出发的每辆车只为个客户提供服务后直接返回中心，整体呈放射线状，因此对于各个需求点之间的运输成本的估计是不准确的，而现实中，只要没有超出车辆的容量限制，同辆车在路线内可以对多个客户完成服务，这些模型对于中心选址与路线安排的相互影响并没有得到很好的考虑，而则是重点对这两个问题进行了综合的考虑。因此，模型与实际的物流系统更加符合，对的研究也就具有了十分重要的现实意义。物流系统优化设计中的关键环节在于配送中心的选址与运输线路安排的确定。物流配送中心的建设需要的投资非常大回收比较缓慢，并且旦选定后很难进行变动。因此，对中心选址进行优化就显得极其重要，它不仅直接关乎运作费用的高低，而且对系统的运营效率也有着较大的影响。对于运输路线的优化，是根据系统工程的思想，使得物品的运输距离短较快的到达以及较少的劳动消耗，最终实现系统整体效益的最大化。将运输仓储信息处理等环节有机的统起来，是现代物流和传统物流的最主要的区别，它以“系统性”作为核心指导思想。本文将定位配给问题和车辆路线优化问题作为个整体进行综合研究，考虑到两问题的不同因素之间的影响，根据已有的研究成果，提出了有效的解决该问题数学模型的方法。由于模型属于问题，目前，针对规模比较大的客户点求解最优解还是非常困难的。但是由于实际中配送中心的建设成本占据总成本比例相当大，因此对配送中心的选址进行优化显得至关重要同时对车辆运输线路的进行优化，可使得物流运营效益得到有效的提高。因此，对由和集万方数据面向物流配送系统中定位路径优化的聚类进化算法研究成得到的问题如图.所示进行系统的优化研究具有非常大的理论价值同时作为发展现代城市智能物流配送系统的理论基础，对于开发物流自动配送调度系统软件也同样具有相当重要的现实意义。综上所述，在物流系统的设计中，对选址问题和运输线路问题的优化研究有着重要的理论价值和现实意义。图.定位分配路线三者之间的关系.国内外理论研究现状问题可以描述为已知需求点的数量位置及其需求量，从给定的潜在中心点内选取定的数目，并确定出从中心到需求点的运输路线，以满足该问题的目标函数，其通常包括配送中心的建设成本经营成本以及车辆的运输成本等。表示设施结点表示客户结点表示运输路线表示未被选中的设施图.模型示意图年代初，自从集成化物流系统的概念提出之后，问题才开始慢慢的被重视。典型的代表应属年描述的问题的精确解法。除了问题自身的复杂性，配送中心与车辆的数目和容量等相关变量的变化也是问题求解过程需要加以考虑的因素，问题的求解也就变得越来越复杂。因此，在问题求解方法中相比精确解法，近似解法的应用更加的广泛。许多的研究，例如，与,和，万方数据面向物流配送系统中定位路径优化的聚类进化算法研究和，和，已经为带有如容量限制成本最低最大运输距离等约束条件的问题建立了相应的数学模型及其求解算法。对于问题的求解，我们可以将其看作三个问题的集成定位问题需求配给问题车辆路线问题。对这些子问题独立求得的最优解般并不是问题的最优解，然而，又不可能将这些子问题通过合并进行计算。在文献中介绍了种随机模型，该模型中初始阶段进行决策的时候不对需求点的需求量进行判断，需求点的需求量只有车辆到达时才能够被确定，当超出本路线上最大容量时，在第二阶段以增加定比例的罚金的方式对其进行补偿，文中抽象出了此问题的数学模型，同时也求出了它的最优解。但是由于精确解法的自身特性限制了中心和需求点在模型中的数量，因此这些数学模型只适用于规模较小的问题。文献中，介绍了种求解问题的优化方法，应用两个不同的估计值对路径的长度进行预测，从而预估该路径的运输成本。和提出了种迭代的方法，在遇到合适的停止准则前，将中心选址和路径优化两阶段不断的进行切换，该文介绍的问题模型与实际情况更加贴近。针对问题中涉及带有时间窗约束的多品种物品的物流配送问题利用禁忌搜索算法进行求解。近年来，定位路径规划问题也吸引了众多国内的学者的关注。张潜等介绍了优化算法评述，林岩等介绍了研究评述，章海峰等分析了类节点带有两重容量限制的问题，即在物流网络节点最大单批处理能力和中心吞吐能力的约束下，如何对物