基于MATLAB遗传算法的物流中心选址问题研究

第10卷第7期中国水运Vol.10No.72010年7月ChinaWaterTransportJuly2010收稿日期：2010-04-25作者简介：胡莹（1988-），女，贵州铜仁人，北京交通大学交通运输学院在读本科生，研究方向为交通运输类。摘要：为了更好的提高物流中心选址的准确性，体现MATLAB的遗传算法在带有时效性的物流中心选址的问题中的计算优势。文中去掉了原有模型中对区域连续性要求的限制条件。利用简单算例，给出运用MATLAB的遗传算法求解的具体步骤，验证模型和算法的可行性。表明基于MATLAB遗传算法的优化算法是一种较其他算法更为有效的求解带有时效性约束的物流中心选址问题的算法。关键词：物流管理；物流中心；时效性选址模型；遗传算法；MATLAB中图分类号：F259.22文献标识码：A文章编号：1006-7973（2010）07-0072-03物流中心是物流网络的节点，是物流系统中的基础设施。它的规划、筹建、运行与完善，涉及交通、物资、商业、外贸、工业、建筑、农业、金融等多个部门、多个行业的企业。同时，物流中心在整个物流网络中，起到枢纽点的作用。现阶段，由于物流中心的选址其很大程度上决定着物流网络结构，影响物流效率、成本和客户服务水平，而受到了社会上的很大关注，已经成为当前物流领域研究的热点之一。在原有的选址模型的建立中，为了满足算法所需条件，而常常假设整个区域为连续区域，如文献[5]中所研究的，这一点与实际情况有一定的冲突。因此，针对该问题，本文利用遗传算法来解决以对时效性的要求较高的物流中心选址模型，去掉区域连续这一约束条件。利用简单算例，运用matlab工具箱，给出具体的计算步骤，说明模型和算法的可行性。一、遗传算法的简介遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的。在出版了颇有影响的专著《AdaptationinNaturalandArtificialSystems》之后，GA这个名称才逐渐为人所知[1]。算法的整个运算过程就是从任一初始的群体出发，通过随机选择、交叉和变异等遗传算子，使群体一代一代地进行到空间中最好的区域，直至达到最优点。（1）确定编码方案GA在进行搜索前，先要将解空间的数据表示成为遗传空间的基因型串接数据，这些数据的不同组合就构成了不同的点，现阶段编码方式主要有：二进制编码、格雷码和浮点数编码[1]。（2）确定适应度函数遗传算法在进化搜索中基本不利用外部信息，仅以种群中每个个体的适应度函数值（fitnessfunction）为依据进行搜索，因此适应度函数的选取至关重要。适应度函数将表明个体或解的优劣性，对于不同的问题，适应度函数的定义方式也不同。在GA的算法中，适应度函数的确定常常运用两种方法：①将目标函数直接作为适应度函数②将待求解的的目标函数做适当处理后再转化为适应度函数。（3）确定遗传算子在GA中，遗传算子主要包括：选择、交叉、变异三类算子。①选择算子选择的目的是为了从当前种群中，选出优良的个体，使它们有机会作为父带的下一代繁衍子孙。常用的选择算子的方案有：比例选择、轮盘式选择、确定式采样选择、无放回随机选择、无放回余数随机选择、排序选择、随机联赛选择等[1]。②交叉算子交叉算子用于组合产生新的个体，它要求对个体编码串中的优良模式不能有太多的破坏并且能有效的产生出一些较好的新个体模式，以便在解空间中能进行有效搜索，且保证对有效模式的破坏概率较小。最常用的交叉方案有：单点交叉、双点交叉、多点交叉、均匀交叉和算术交叉[1]等。③变异算子在生物的遗传和进化过程中，生物的某些基因偶尔会发生变异，从而产生出新的个体，虽然其概率比较小，但对新物种的产生也是一个不可忽视的因素。模仿生物遗传和进化过程中的这种变异现象，在遗传算法中引入了变异算子来产生新的个体。变异算子的主要方式有：基本位变异、均匀变异、边界变异、非均匀变异、高斯变异[1]等。（4）确定遗传算法运行参数在遗传算法的运行中，有几个参数对遗传算法的运行有很大影响。它们分别是：个体编码串长度L、群体大小M、交叉概率PC、变异概率Pm、以及终止代数T。遗传算法解决问题的具体步骤如下：Step1确定编码，编码是遗传算法中的主要步骤，是用恰当的遗传形式来表示问题的可行解；Step2确定适应度函数，根据实际问题选择适应函数；第7期胡莹：基于MATLAB遗传算法的物流中心选址问题研究73Step3选择控制参数：控制参数主要包括种群规模，算法执行的最大迭代次数，执行不同遗传操作的概率及其他一些辅助性控制参数；Step4遗传算子的设计：主要包括选择、交叉和变异以及其他高等遗传操作；Step5确定算法的终止准则；Step6确定解码方式，根据该为问题最终所需导出的结果形式，确定解码方案；Step7统计整体结果，导出最终所求结果；Step8上机编程，完成上述步骤，并通过多次迭代得到可靠的最优解。具体算法运算流程图如图所示。二、物流中心选址优化模型为了验证算法的可行性，本文将强调时效性物流中心选址问题，抽象改进如下的数学定义：在某一区域内有n个客户，拟建一个物流中心，已知客户j地址坐标为（xi，yi），需求量为wi，最大允许配送距离为Di。确定物流中心的地址坐标（X，Y），使得在满足客户最大允许配送距离的前提下，总运输周转量最低。假设如下：（1）简单的用两点之间的距离代替运输距离；（2）时效性约束用最大允许配送距离表示。目标函数为[5]：n22iiii1minwxy=×+∑（X,Y）=（X-）（Y-）（1）约束条件为：22iiiiiiixy0minxmaxxminymaxyiDXY⎧+−≤⎪⎪≤≤⎨≤≤⎪⎪∀∈⎩（X-）（Y-）（）（）（）（）N（2）三、遗传算法的模型求解模型求解的运算步骤如下操作：Step1初始化。利用随机选择的方法选择M个染色体x1，x2，...，xM作为初始种群，即种群规模为M，P（t）={x1，x2，...，xM}其中xi，包含决策变量X与Y的相关信息，t=0。同时确定交叉概率为Pc，变异概率为Pm，终止代数为T；Step2若t＞T，则终止搜索，否则，转向Step3Step3将产生的M个染色体带入适应度函数，计算其适应度，保留最好的个体；Step4令t=t+1，按给定的概率进行交叉、变异运算，得到中间种群，转入Step2。四、基于MATLAB工具箱的遗传算法算例分析假设某一区域内有6个客户，其位置坐标与日需求量如下表1所示，假设最大允许运送范围Di不得大于50km。利用MATLAB强大的运算能力和编写能力，进行如下的操作：Step1：根据目标函数（1），编写M文件my_fun，将目标函数作为适应度函数。Step2：根据约束条件（2），编写非线性约束条的M文件constraint。同时根据确定X、Y的取值范围。Step3：因此，利用matlab工具箱中遗传算法的参数设置要求，进行相关参数的设置，具体的如下：适应度函数@my_fun非线性约束函数@constraint变量个数：2最大迭代次数：60交叉概率为（PC）：0.7变异概率（Pm）0.001边界设定：Lower：[42，9]TUpper：[93，86]T个体选择参数函数@selectionroulette（轮盘赌选择法）个体变异参数函数@mutationuniform（均匀变异法）个体交叉函数@crossoversinglepoin（单点交叉法）其他参数按照MATLAB遗传工具箱默认给出的值设定。表1客户坐标及相关需求量经过计算得到点的得到物流中心的选址位置为X=71.95km，Y=48.94km，总周转量为Z=34102.56t•km。而每个客户到物流中心的有时效约束的客运周转距离和周转量的计算表格如表2所示。表2时效约束的客户周转距离和周转量文中给出的算例较为简单，没有涉及到过多的变量，仅为一个物流中心的选址问题，运用遗传算法求解的优势并不是十分明显。但若是将该算法，运用到实际问题中，涉及多个变量考虑时，遗传算法的优势将为比较明显。它将快速有效的达到最优目标的同时，提高原有算法的精确度。（下转第75页）实际问题参数集编码成位串种群1计算适应度选择与遗传种群2改善或解决实际问题随机算子1.位串解释参数2.计算目标函数3.函数值像适值映射4适值调整三种基本算子：1.选择算子2.交叉算子3.变异算子种群2代替种群1统计结果经过优化的一个或多个参数集第7期刘雁翎：关于海船船员技术档案管理在运行中的思考75还对船员服务机构，航运企业的规范管理都有重要的意义。真实的船员档案能够反映船员成长过程以及船员目前的状况为实施船员跟踪管理，信息管理，网络化管理提供依据。笔者认为：海事机构应建立电子信息档案平台，除有关不涉及保密的电子信息档案之外，将电子档案应向社会公开、以便产生社会效益。船员的培训、考试和发证记录，考试报名、成绩查询等基本资料的公开，建立统一的船员信息平台。还将为船员跟踪管理过程中及船员服务机构和船员用人单位提供参考依据。船员档案是船员考试发证机关在船员注册、培训、考试、评估和发证管理等工作过程中形成的具有查考、利用价值的各种文字、图表、声像、光盘等不同形式和载体的文字资料。是船员考试、评估和发证的历史依据和原始凭证，而且还真实记载了水上运输活动中完整的水上资历、业务技术水平、教育培训情况等。为船员用人单位聘用船员时，若对船员不甚了解、手上也没有可参考的船员资料，那么就可以登录船员电子档案系统，对船员以往的就职情况，安全记录、违章信息等安全信用度进行查询，掌握对屡次违章造成重大水上交通事故的船员慎重考虑聘用，从而择优录用，保证本单位船员队伍的整体素质，从而保障船舶的安全营运和单位的经济效益。《中华人民共和国船员条例》规定“船员服务机构应建立船员档案加强船舶配员管理，掌握船员的培训、任职资历，安全记录、健康状况，并将上述情况定期报海事管理机构备案。船员用人单位直接招用船员的，应当遵守前款的规定”。然而，在现实中，船员服务机构和用人单位档案管理工作不被重视，没有意识到船员档案管理中隐藏很多他们所利用的专业技术、信息资源工作经验等有用信息，认为并没有为他们创造任何经济价值。尽管有些单位建立了船员电子信息档案但受到利益的驱使也不会将违章记录，记录在档案中。因而，应在每年船员管理责任检查中，船员管理资质的认证中，重点检查有关船员管理系统的电子档案的建立以及真实记载的检查。从而，建立一个面向社会的船员信息系统，加大海事管理对船员监督管理的力度和效能，能够给船公司等用人单位选择高素质船员提供参考和借鉴。从而，提高社会的船员管理的整体水平，更有利于提高航运企业，海事管理机构共同创新和发展。四、提高档案管理人员素质确保档案及时归档船员考试、评估和发证的各种材料的归档，是档案形成的最后一个环节，也是档案材料转化为船员档案的一个重要步骤。档案材料是船员档案的前身和源泉，考试、评估和发证各部门只有把办理完毕的、具有查考、保存价值的档案材料交递给档案管理人员进行集中、整理、立卷，完成之后，才能使档案材料转化为船员档案。因此，文书立卷归档和档案工作是同一事物所处的两个不同阶段，相互之间的联系是密不可分的。档案材料立卷质量的好坏，是否及时立卷归档等，关系到档案的质量，档案是否齐全完整，在一定程度上，则取决于档案立卷制度是否健全。如果没有健全的归档制度，办理完毕的文件材料不及时归卷，就难以保证案卷质量。然而完善档案归档，人员是基础，制度是保障。船员档案管理的好坏很大程度上取决于档案工作人员。作为档案管理工作人员应该努力提高自身素质，加强责任感，注重自身专业水平的提高，减少工作中的失误和差错，严格按照船员档案管理工作中的各项规章制度来办事。要建立健全船员档案管理工作的各项规章制度，使档案工作有规可循，有章可依。重质量，抓管理，船员档案管理人员要以制度来维护档案的管理，以管理来保证归档质量，切切实实做好管理工作，让