基于遗传算法的污水处理厂选址-配送问题集成研究-论文 6页

技术与方法物流技术2015午第34~6)q刊(上半月)doi：l0．3969／j．issn．1005—152X．2015．06．044基于遗传算法的污水处理厂选址-iE送问题集成研究赵崤含’，李冰毅’，石咏’，郭海湘，周欣然’，潘雯雯(1冲国地质大学经济管理学院，湖北武汉430074；2．中国地质大学数字化商务与智能管理研究中心，湖北武汉430074)[摘要】从选址一路径问题(Location—RoutingProblem，LRP)集成化的角度研究了华北石油局大牛地气田污水处理厂的扩张选址问题。综合考虑车辆容量、设施容量等约束，使得之前的污水处理厂和新建造的污水处理厂共同作业，产生的运输费用、建厂费用和车辆使用固定费用的总和最小，即建立了多设施多车型的有容量限制的LRP模型，并合理地设计遗传算法求解模型，同时优化选址问题和路径问题，最终得到了最优解。该模型和算法对于进一步补充和完善选址和配送模型具有一定的意义，对油田、煤矿等工业物流领域的决策具有重要的指导意义。【关键词】遗传算法；污水处理厂；选址一路径；油田物流；扩张选址【中图分类号1x505；F224【文献标识码lA【文章编号】1005—152x(2ms)o6-Ol36—06StudyonIntegratedLocation—-routingProblemofSewageDisposalPlantsBasedonGeneticAlgorithmZhanXianhan‘，LiBin~'i‘，ShiYong，GuoHaixiang，ZhouXinran，PanWenwen’(1．SchoolofEcnnnmics＆Management，ChinaUniversityofGeoseiences，Wuhan430074；2．DigitalizedCommerce＆SmartManagementResearchCenter，ChinaUniversitynfGeosciences，Wuhan430074，China)Abstract：Inthispaper，inviewoftheintegratedlocation—routingproblem，westudiedthelocationproblemintheextensionandrelocationoftheDaniudiGasFieldSewageDisposalPlant，thenafterconsideringtherelevantcnnstraints，builttheLRPmodelformuhiplefacilitiesandheterogeneousvehicleswithcapacityconstraint，thendesignedthegeneticalgorithmtnsolveit，optimizedthelocationandmutingproblematthesametime，andattheend，obtainedtheoptimalsolution．Keywords：geneticalgorithm；sewagedisposalplant；location-routing；gasfieldlogistics；extensionandrelocation选址是企业的中长期决策，对企业物流发展具有重要的战略1引言意义；而车辆路径问题是企业的中短期决策，对企业的物流配送具有重要的战术参考价值。早期的研究都是将二者分开单在物流系统解决方案中，运输与配送问题占有很重要的独研究，从物流实践中发现，选址问题和车辆路径问题在决策地位，主要原因是运输和配送过程的成本占物流总成本的比过程中具有很多的内在关联性，即二者一般都要考虑物资集重很大，根据现有的研究成果，大约在70％一90％之间⋯。因此散中心和客户的分配关系、运输成本的最小化，因此将二者集研究物资运输配送优化问题对于降低物流配送费用、提高企成研究，即选址一路径问题-61对于设计最优的物流布局与布置业的运作效率和利润具有重要的意义。在目前供应链与物流配送路线具有重要的意义。研究中，最基本的两个问题是选址问题和车辆路径问题1。选址一路径问题在近五年得到了迅速的发展，主要研究方f收稿日期12015一O1—12[基金项目】国家自然科学基金资助(71473232，71173202，71103163，71103164，71301l53)；教育部新世纪优秀人才支持计划(NCET一13—1012)；教育部人文社会科学研究青年基金资助(10YJC790071)；中央高校基本科研业务费专项资金资助(CUG110411，CUGl20111，G20l2n02A，CUG140604)[作者简介】赵崤含(1986一)，多‘，河南汝州人，博士研究生，研究方向：数量经济、能源系统工程；李冰毅，男，河南郑州人，博士，研究方向：物流管理；石咏(1989一)，通讯作者，硕士，研究方向为：物流系统建模与优化仿真；郭海湘(1978一)，男，湖南湘乡人，教授，博十，博士生导师，主要研究方向：软计算、复杂系统模拟与决策。．．136——\n\n技术与方法物流技术2015年第34卷6月刊(上半月)i点装的)，否则为O；c表示车辆从i点到j点的运输费用数约束。(Vij∈N)。3算法的设计决策变量：一』11如果车辆从节点到节J√，Vi,j~N．IRP是NP难问题，当需求点和设施数量的规模稍大时，0否则传统的精确算法(如线性规划、分枝定界法、割平面法和动态一J1如果建设此污水处理厂，Vn．规划法等)显得无能为力。启发式算法是一种能获得满意解hl0否则的最常用算法许多学者在研究LRP时习惯于将其分解成选一J1如果集气站i被分配到污水处理厂n．Vi∈，Vn∈，v。U0址问题和路径问题两个子问题进行研究，把选址问题的输出10否则结果作为路径优化问题的输入进行求解。尽管这种分阶段的min∑∑∑c+∑FD⋯Y+∑∑∑F(1)⋯KV，E⋯VnE，UEK启发式算法大大简化了问题的复杂性，并且在一些研究中已S．t．经被证实可以有效解决LRP，但这种方法很容易使问题陷入∑∑=1，V(2)局部最优。很明显这种求解方法没有体现LRP将选址和路径E^，EN集成化研究的本质。本文在研究LRP模型时通过适当的编码∑，=∑，V∈Ⅳ．VK(3)和解码，将选址问题和路径优化问题视为一体，同时优化，并』EvJ∈结合遗传算法。通过合理的选择、交叉、变异等算子，求得最优∑一∑=ViEM(4)』E-rjel解I”1o≤CVkxVijcN，≠，EK(5)本文之所以选择遗传算法，主要是基于遗传算法整数编∑=∑p，，Vn~OLJN。(6)码简单、全局搜索能力强、扩展性强等特点的考虑”。J∈M，E3．1染色体的编码∑=o，Vn∈DuⅣ。(7)，￡M染色体的编码一般应满足个原则：非冗余性、健全性及≤(c—pj)x，Vi∈N，EM．Vk∈K(8)完备性。考虑到LRP的特殊性，其解必须同时包含配送中心v≥p—x_k，Vi∈M，j∈N，k∈Kt9)选址和车辆路径信息，根据这一特性设计一种自然数编码方∑Zin=1，V∈M(1o)法。同时解决了，车辆路径问题和服务次序问题。每个染色体"E0U分为三段，一个染色体就是问题的一个可行解．、考虑到本研∑≤⋯Y，Vn~OUN。(11)究中模型的特殊性：即0点必须被选中，并且至少要有一辆车和一个客厂1被该污水处理厂服务，本文设计了合理的染色体∑≤，V∈，VneOUNo(12)结构。现在假设：有m个集气站(编号依次为：1，2，3，⋯，60)，∑≤zV∈．VnEOUN。(13)1个已经确定的污水处理厂(编号为1)，n一1个备选污水处理+∑≤2，VJ∈~，VnEOUN，VK(14)厂(A、B、c、D分别编号为2,3，4，5)，k表示车辆的数量(依次编，H∈0Uwnm≠号为23，⋯，28)。则染色体表示结构见表1。Y=1(15)表l染色体的编码设计¨∈{0，l}，V√∈Ⅳ，V∈K(16)m位1m位Ik位∈{0，1}，V∈M，Vn∈0UNo(17)车辆编号I集气站编号I污水处理』编号Y∈{0，1}，Vn∈N，(18)表1中，染色体子段1有m位，随机生成1到k的自然数，≥0，Vij∈N(19)每个客户对应一辆车的编号完成顾客点与车辆的指派；染色体子段2有m位，是1到m的随机数排列，表示了每条服务路其中，式(1)最小化总的系统费用，包括运输费用、处理厂线上对客户的服务次序；染色体子段3有k位．产生1到n的随建设费用和车辆使用固定费用；式(2)确保每个集气站被服务机数，表示了每辆车由哪个配送中心派出．由此完成了配送中一次；式(3)确保每个节点进出平衡；式(4)车辆在i集气站装心与服务车辆间的指派。特别地，本研究中约束(15)表示O载流程约束；式(5)确保车辆在任何路径上的装载量低于车的点必须被选中，因此在生产初始种群时必须要建议予段3中必装载容量；式(6)确保污水厂的所有车辆污水装载量等于分须包含基因1，否则要重新生产。配到此处理厂的集气站的污水量；式(7)表示从处理厂出发时为了更详细地描述解码过程，给一个具体的例子(因为车辆装载污水量为0；式(8)一式(9)表示车辆在路径上时的污本文的实际背景集气站个数过多，不方便书写，举一个集气站水装载量边界约束；式(1o)确保每个集气站必须被分配到一个数较少的例子)。假设m=15；n=3；k=4，mat|ah随机生成的一个污水处理厂；式(11)表示污水处理厂处理量约束；式(12)一个染色体表示如图2所示。式(14)确保车辆起止于同一个污水处理厂；式(15)表示原有的污水处理厂0一定被启用；式(16)一式(19)表示决策变量整．．138．．\n赵崤含，等：基于遗传算法的污水处理，一选址一配送问题集成研究技术与方法子段2约束(19)的处理则可以通过不断的检验每条染色体的子段3中的基冈是否有1。约束(11)和(19)分别表示车辆容量约束}?【Ilz4_l38j4{和污水处理厂的处理能力约束。本文采用惩罚函数来处理。图2染色体基因位编码示意图当仟何一条染色体违反了(11)和(19)中的任何一个约束条件其中子段1有15个基因位置，表示集气站和服务车辆的时，目标函数加上一个足够大的值M；否则目标函数保持不指派。具体见表2、表3。变。通过降低适应度函数值来大大降低其遗传到下一代的概率。表2车辆与集气站编号对应3．3适应度函数．集气站编号车辆编号集气站编号车辆编号集气站编号车辆编号l162111本文的模型是求最小值，因此在设计遗传算法时，适应度22731243182134函数取目标函数的倒数。当染色体违反模型中任何一个约束4494143条件时，目标函数加上一一个足够大的值M；否则目标函数保持541O4l53不变。这样在不断迭代的过程中，通过降低适应度函数的值表3车辆与集气站的指派关系来大大降低违反约束条件的个体，及其遗传到下一代的概率，车辆编号由该车辆服务的集气站编号从而不断提高种群中可行解的个数。l。1、3、1l22、6、83．4遗传算子的设计37、14、15(1)选择。本文的选择操作将使用到两种方法：即精英保44、5、9、1O、l2、13留策略和轮盘赌方法，适应度最高的若干个个体不参与交叉由于确定了集气站与车辆的对应关系，还得确定每辆车变异等操作，直接保留到下一代；而其他个体则通过轮盘赌的对集气站的服务次序。染色体子段2有15位，每位对应一位方法被选出。适应度最高的个体很可能不是全局最优解，但集气站编号，数字序列代表了对应客户的服务顺序，对上述服极有可能暗含着全局最优解的信息，因此精英保留策略有利务顺序作涮整即得到行车路线表示如下：于算法的快速收敛。(2)交叉。交叉是产生新个体的主要方式，在表1的编码表4车辆与行车路线安排方式中，子段1和子段3的编码较为类似；子段2与其它两个的车辆编号该车辆的行车路线编码结构有差异。因此，本文的交叉操作也使用了两种操作1l1一-+3—1方式，分别是：两点交叉和部分映射交叉，具体如下；22一}8—}6315一+14_+74l0—l2—4—9叶l3～巧染色体Bl10l5I4I6I31817l2l1l9染色体的子段3车辆对应的开放中心见表5。①针对染色体子段1和子段3采用两点交叉。例如下面表5车辆与污水处理厂指派关系有两个染色体在第4和第7位之问两点交叉。交叉后变为：污水处理厂编号J3I1l1l3染色体的子段3表示了所派车辆与开放的配送中心问的对染色体BI10I514I3I7I4f2I211I9应关系。由表5可知：车辆l：由污水处理厂3派出；车辆2：由污②针对表l中的子段2，该子段内不允许不同基因位取相水处理厂1派出；车辆3：由污水处理厂1派出；午辆4：由污水处同的值，使用部分映射的方法进行交叉。如染色体A和B进行理厂3派出。本次配送只有中心1、3被选中，因此完成选中配交叉时分成两部。送中心与配送车辆的对应，而1是原：有的污水处理厂，因此在该(1)如rl=4，r，=7，先进行两点交叉．变为：染色体中被选中的是3号污水处理厂即B污水处理厂。因此上述i个子段完成了选址、配送路线的安排问题。染色体B书聿J10}5Jf3J7I4I2JI1I93．2模型中约束条件的处理(2)交叉后不重复个体保留，有冲突的个体选择部分映射的方法消除冲突：即利用中问段的映射关系进行调整，如下：在使用遗传算法求解带约束的规划问题时，一定要对解决的约束条件进行适当的处理，到目前为止，常用的处理约束染色体B料l10l518I3I714I2l6I1l9条件方法有：拉格朗tq松弛分解法、惩罚函数法和可行解变换(3)变异。变异是产生个体多样性的辅助手段，针对表1法等。通过分析在第二部分建立的模型的约束条件，结合3．1中染色体子段的特点。对子段1和子段3采用两点变异；对子的编码设计，发现除(5)、(11)、(19)之外的约束均能够被3．1段2采用倒序变异法。下面以染色体A为例子进行说明。的编码设计来实现”一。例如：表1的染色体编码保证了每个集气站只能被服务一次，任何两个污水处理厂不能被连接，任墨鱼堡垒I!l1II!l!IIl!l何被选中的污水处理厂至少被一辆车来服务等约束。而对于①两点变异，指在同一染色体选择两个变异位置，将两个—．139．．\n技术与方法物流技术2015年第34卷6月刊(上半月)变异位置设为r1=4，r2=7，则染色体A变异后为表7集气站的位置坐标和产水量鱼堡垒：l!I【!II!I!lll!I产水量产水量序号y序号y②倒序变异，是指对两个变异位置之间的基因位进行倒(单位：方)(单位：方)l8．57717473007O．958．96序。本部分对表2中的子段2进行倒序变异。22．8761．15319313．36鱼竺：：I!II!lI!l!III!l131．63．66O3328．41．25．8840．16．74．953369．814．473．5算法的操作流程50．87．91887347．5212．82Step1：设置遗传操作参数，种群大小popsize，最大迭代次61726O．33357．94l2．29725721870366．17．711．55数maxgen，精英保留策略中进行交叉、变异的个体数与种群个8O．9545．79379_322．04体总量的比率GGAP，交叉操作概率Pc，变异操作概率Pm。9O．64．2l9．23388．44．216O61O0851O18．79399名119．51Step2：初始化种群。随机生成一条染色体，判断是否满足11O．61．6483406．21041945所有约束条件；如果满足则保留染色体。否则重新生成个体，12241．56344175．912．O0直至所有的染色体均满足约束条件，将此时的染色体记为：l34．2ll14O842lO．5ll51．79l4l757．79l5438．9l1．81026Oldehrom。15O69．34_3044{037．67．72Step3：计算目标函数和适应度函数，并记录最优的个体。160．43741379459．5l7-3l591716318l244468舟1362．25Step4：对于Oldchrom，采用精英保留策略和轮盘赌法选出1815．8178．0747851521275需要直接保留的个体subpopl，需要进行交叉变异的个体sub—19l2．7140．01481031428．24203656．8l6．2649787．53．40pop2。2185．31．53505．813．28．97Step5：对于subpop2，以进行交叉。对于每一个个体，223．65．78．5l515．513．715．】1子段1和子段3采用两点交叉，子段2使用部分映射的方法进2318113．77525．2l4．214．69241．26．49．455313．19．15．49行交叉。交叉后记为subpop3。25O8l14．575415512．514．70Step6：对于subpop3，按照Pm进行变异。对于每一个个263．5O．8l88755l5．674l2．8627O653．117．8256l1．55．412．31体，对子段1和子段3采用两点变异，子段2进行倒序变异。最28O．152．61340571522．917O6终得到的染色体记为subplot4。29723．819．905812．9255．98Step7：将subplotl和subplot4组成新的染色体，记为New—chrom，用Newchrom来替换Oldchrom。Step8：判断是否达到收敛条件，若满足则输出最优解并退出计算；否则转向Step3。4算例仿真目前关于LRP的研究多种多样，没有统一的测试集来测试算法的有效性。为了说明本文算法的有效性，先取m=15；n=5；k=4，分别采用Cplex以及本文提到的启发式算法求解。发现二者得出的最优解非常接近，这说明了算法是有效的。结合问题背景进行了大量的调研工作，收集到相关数据。为了精确描述选址位置，对图1进行了坐标量化(图1中单位1代表2．5kin)。表6给出了污水处理厂(含待建和已建)图3最优目标函数的收敛情况的位置坐标，表7给出了各个集气站的位置坐标和平均的每日表8为选址一路径安排优化结果，原有污水处理厂0继续使污水产生量。用，在备选点D建立一个新污水处理厂，备选点A、B、c都未启表6待建和已经存在的污水处理厂的坐标位置用。28辆车中有4辆40方的和2辆50方的未启用，有3辆3O方呈JI垒l璺lI旦的、4辆40方的和6辆50方的被原有污水处理厂0启用，其余的位置坐标I(2．90，7．21)l(9．33，11．79)l(9．77，14．06)l(9．58，13．88)l(9．50，629)都被新建污水处理厂D启用。路径安排见表8最后一列，如第车辆有28辆，依次编号为1—28，其中30方的有5辆，40方二行0—45—51—0表示一辆容量为30立方的车从原有污水的有l3辆，50方的有10辆。处理厂0出发，依次到集气站45、集气站51，最后返回污水处理优化时，车辆的固定费用分别为80、100、120(单位为元)，厂0。配送方案中的两个污水处理厂服务的集气站数目的差异仓库开放的固定费用1000(元)。算法的参数为：popsize=性，与集气站位置、污水处理厂位置和产水量有关。500，maxgen=3000，sizepop=40，Pc=0．8，Pm=0．09，GGAP=0．9。为了说明选址较其他位置的优越性，编码时将字段1固算法迭代过程中的目标函数收敛情况如图3所示。——140—-\n赵崤含，等：基于遗传算法的污水处理厂选址一配送问题集成研究技术与方法表8最优解所对应的选址与配送方案search，2009，l96(2)：401—4l2．污水处理启用车辆的[3]EksiogluB，VuralAV，ReismanA．Thevehicleroutingproblem：Ataxo—厂编号车辆编号容量(方)配送路线nomicreview[J]．Computers＆IndustrialEngineering，2009，57(4)：1472一130O—珥5—}5l—}Ol483．230ol—}O530O—39—37—+O[4]MinH，JayaramanV，SrivastavaR．Combinedlocation—routingproblems：740O一15—13一Ol14004l_1_÷oAsynthesisandfutureresearchdirections[J]．EuropeanJournalofOp—原有1440O—_+24—27—OerationalResearch，1998，108(1)：1-15：的污水处理1440o—24—+27—O／和启用的O1540o—7—}16—}O[5]NagyG，SalhiS．Location-routing：Issues，modelsandmethods[J]．Euro—车辆1750o22—1o_一56—o2050O—43—5—斗OpeanJoin'halofOperationalResearch，2007，177(2)：649-672．2l50o—}36—}52—48—}o【6JProdhonC，PrinsC．Asurveyofrecentresearchonlocation—routing2450o—}54—}38—O2650O—20—3O—8—Oproblems[J]．EuropeanJournalofOperationalResearch，2014，238(1)：l—275004332_14_÷Ol7．330D—34—}D430D—42—}57—+D『7]-~b华丽，周战杰，薛耀锋．考虑路径风险的不确定需求应急物流定位一启用940D—35—28—+23—D路径问题[上海交通大学学报，2013，47(6)：962—966．的污水处理1340D—}6—}18—44—}9—Dr和D1650D—}47—}26—D[8】吕新福，蔡临宁，曲志伟废弃物回收物流中的选址一路径问题阴．系统车辆1850D—55—40—}D1950D—21—斗17—}5o．叶D工程理论与实践，2005，(5)：89—94．2250D—49—32—3—29—_+D【9]AlumurS，KaraBY．Anewmodelforthehazardouswastelocatiqn—routing2350D—19—_+46—58—Dproblem[J]．Computers＆OperationsResearch，2007，34(5)：1406-1423．6、8、10、12、30方：0辆未启用A、B、C2540方：4辆[1O】张宁宁，李清方，郑峰，等．大牛地气田管网系统仿真模拟及优化[J]．、2850方：2辆油气储运，2014，33(3)：264—268．定，即可模拟出在其它位置的选址，路径最优化时的运输费[11]ZareMehrjerdiY，NadizadehA．Usinggrebdyclusteringmethodto用见表9。solvecapacitatedlocation-routingproblemwithfuzzydemands[J]．Eu—表9污水处理厂方案及其最优配送最优费用ropeanJournalofOperationalResearch，2013，229(1)：75—84．【12]TingCJ,ChenCH．Amultipleantcolonyoptimizationalgorithmfor污水处理厂布局方案该方案下的配送的最优费用(元)o和A50023×104thecapacitatedlocationroutingproblem[J]．InternationalJournalofO和B3．9980x1OProductionEconomics，2013，141(1)：34—4_4．O和C3I3l97x10[13]DerbelH，JarbouiB，HanafiS，eta1．Geneticalgorithmwithiteratedlo—O和D2．0605×lOcalsearchforsolvingalocation—routingproblem[J]．ExpertSystems通过表9，发现只选择O和D点时最优运输费用最小，这withApplications，2012，39(3)：2865—2871．也印证了O和D点是最优的选址方案。[14]罗耀波延明，刘小龙．多约束选址一路径问题的改进混合遗传算法研究叫．计算机应用研究，2013，30(8)：2283—2287．5结论[15]TasanAS，GenM．Ageneticalgorithmbasedapproachtovehicleroutingproblemwithsinmhaneouspick—upanddeliveries[J]．Comput—在之前的油田物流系统研究中，大多数是把设施选址问题ers＆IndustrialEngineering．2012．62(3)：755—761．与车辆路径问题分开来研究。本文从选址一路径集成化的角度[16]EscobarJW．Heuristicalgorithmsforthecapacitatedlocation—rout—研究了华北石油局大牛地气田污水处理厂的扩张选址问题。ingproblemandthemulti—depotvehicleroutingproblem[J]．4or综合考虑车辆容量、设施容量等约束，使得之前的污水处理厂QuarterlyJournaloftheBelgianFrench＆ItalianOperationsRe—和新建造的污水处理厂共同作业，产生的运输费用、建厂费用searchSocieties，2014；12(1)：99-100．和车辆使用固定费用的总和最小，即建立了多设施多车型的有[17]EscobarJW，LinfatiR，BaldoquinMG，eta1．AGranularVariableTabu容量限制的LRP模型，通过遗传算法得到了最优的建厂位置、NeighborhoodSearchforthecapacitatedlocation-routingproblem[J]．污水处理厂与集气站的分配关系和车辆的访问顺序。本文的TransportationResearchPartB：Methodological，2014，67：344—356．模型和算法对于进一步补充和完善选址和配送模型具有一定[18]BaldaeciR,MingozziA，WolflerCalvoR．Anexactmethodfortheca—的意义，对油田、煤矿等工业物流领域的决策具有重要的指导pacitatedlocation-routingproblem[J]．OperationsResearch，2011，59(5)：l284—1296．意义。本文的不足之处在于，模型中并没有考虑时间窗、需求[19]EscobarJW，LinfatiR，TothP．Atwo-phasehybridheuristicalgo—的动态变化等特征，这也是今后研究的主要工作-川。rithmforthecapacitatedlocation-routingproblem[J]．Computers＆[参考文献】OperationsResearch．2013,40(1)：70—79．[1]张潜．物流配送路径优化调度建模与实务[M]．北京：中国物资出版社，[20JKaraoglan],AhiparmakKaraI,eta1．Abranchandcutalgorithmfor2006．thelocation-routingproblemwithsimultaneouspickupanddelivery[J]．[2]MeloMT，NickelS,Saldanha—da—GamaF．FacilitylocationandsupplyEuropeanJournalofOperationalResearch，2011,211(2)：318-332．chainmanagementAreview[J]．EuropeanJournalofOperationalRe—141