ֻ29जֻ3௹`````````````````ᇏଲቂն࿐࿐Б(ሱಖ॓࿐ϱ)`````````````````୍9ᄅ``````````JournalofSouth-CentralUniversityforNationalities()``````````ࠎႿ૧ၦ၌Ԯෘم֥Ӛਇਫ਼ࣥႪ߄໙ี程林辉,吴立锋,张 潇(ᇏଲቂն࿐࠹ෘࠏ॓࿐࿐ჽ,ݱ430074)ᅋ`ေ`ᄝ࣮૧ၦ၌ԮෘمࠎЧં֥ࠎԤഈ,ഡ࠹ਔ၂ᇕႨႿࢳӚਇਫ਼ࣥႪ߄໙ี֥૧ၦ၌Ԯෘم,ѩࣉྛਔൌဒҩ൫,ൌဒࢲݔіૼෘمऎႵਅݺ֥ಆअෆ෬ି৯,ѩିܔႵֹིक़ڛ၌Ԯෘمᄝࣉ߄ݖӱᇏႮႿᇕಕ؟ဢྟࢆ֮طԛགྷᄪඃ൬৻གྷའ֥ಌׄ.ܱՍ`၌Ԯෘم;૧ၦ၌Ԯෘم;Ӛਇਫ਼ࣥ໙ีᇏٳোݼ`TP301`໓ངѓ്`A`໓ᅣщݼ`1672-4321(2010)03-0089-04VehicleRoutingOptimizationProblemBasedonImmuneGeneticAlgorithmChengLinhui,WuLifeng,ZhangXiao(CollegeofComputerScience,South-CentralUniversityforNationalities,Wuhan430074,China)Abstract``geneticalgorithm;immunegeneticalgorithm;vehicleroutingproblemࣼႄఏਔ؟۱ਵთ֥ህࡅ࿐ᆀૌ֥ܱᇿ,ѩ༵ުႤ1`໙ีМࣟࠣӈႨෘمགྷԛ၂ႨႿࢳھ໙ี֥ٚم,ೂࣚಒෘمaԮఓؿൔෘمaᇆିႪ߄ෘم֩.ཁಖ,ࣚಒෘمაԮӚਇਫ਼ࣥ໙ี(VehicleRoutingProblem,ࡥӫఓؿൔෘمѩ҂ൡކࢳथگᄖ֥VRP໙,ีଢVRP)ቋᄪ൞Ⴎᇷ࿐ᆀDantzigބRamserႿ1959భ,धն؟ඔ࣮ᆀҐႨᇆିႪ߄ෘم,бೂ၌Ԯෘ୍ิԛ֥[1],၂Ϯॖ૭ඍ:ູؓႿ၂༢ਙ֥ෂࠊׄم[2]a૧ၦෘم[3]a૧ၦ၌Ԯෘم[4,5]aၖಕෘم[6]aބ(ࠇ)ཱྀࠊׄ,ࠊᇏྏቆᆮކ֥Ӛਇྛਫ਼ཌ,ଆࠅෘم[7].֩Ӛਇᄝડቀ၂ק֥ჿඏ่ࡱ(ೂࠊ֥ླਈaӚЧ໓ᄝٳ༅ਔ၌Ԯෘمࠣ૧ၦෘم۲ሱႪಌׄਇ֥ಸਈཋᇅaࠊ֥ෂղൈࡗaӚਇ֥ྛൈࡗ֥ࠎԤഈ,ഡ࠹ਔࢳVRP໙ี֥૧ၦ၌Ԯෘم,֩)༯,ିܔႵֹ๙ݖૌ,ѩղ֞၂ק֥ଢѓ(ೂѩࣉྛਔཌྷܱ֥ӱഡ࠹,๙ݖაఃෘم֥ൌဒٮႨቋഒaӱቋ؋aႨӚਇ࣐ਈഒ֩).ଢభ,ࢲݔࣉྛбࢠބٳ༅,ဒᆣෘم֥ႵིྟࠣႪ൝.VRP໙ีᄝದૌളࠃ֥ޓ؟ٚ૫ၘࣜႵਔܼ֥ٗႋႨ,ೂӑࠩ൧ӆ֥അ܂ႋa۽ြӁᄎൻaࢌ2`VRP໙ีࡹଆ๙ᄎൻਫ਼ཌνஆ֩,ѩ౼֤ਔࠞնི֥ၭ.VRP໙ี൞၂۱ׅ֥ቆކႪ߄ো໙,ีऎႵޓ֥ۚ࠹ෘVRP໙ีေޅ၂ਇӚᄝྛਫ਼ࣥഈ෮ልگᄖྟ,ၘФᆣૼඋႿNP໙ี,ၹՎሱิԛၛটᄛ֥ࠊሹਈ҂ିӑԛӚਇ֥ቋնڵᄛཋᇅ.ࡌק``൬۠ರ௹`2010-06-30``ቔᆀࡥࢺ`ӱਟߩ(1980-),୯,ණൖ,ࢃഽ,࣮ٚཟ:ဆ߄࠹ෘ,E-mail:clh333@``ࠎࣁཛଢ`ᇏଲቂն࿐ሱಖ॓࿐ࠎࣁሧᇹཛଢ(YZQ07016)
90``````````````````ᇏଲቂն࿐࿐Б(ሱಖ॓࿐ϱ)ֻ29ज෮ႵӚਇཌྷ,ѩᄛࠊି৯္ཌྷ,֩ࢳݖӱߎࢫۿିބಆअෆ෬ି৯,ॖႨႿࢳथگᄖ֥۽ӱ໙сྶൈડቀ:෮ႵӚਇनႮֆ၂ࠊᇏྏԛؿ,ቋี[8].ᄝ૧ၦෘمᇏ,ॆჰؓႋႿ෮ࢳ֥໙,ีॆުᄜ߭֞ჰԩ,ૄ۱ग़ׄᆺФ၂ਇӚ٠໙၂ՑุؓႋႿ໙ี֥ࢳ.۴ऌॆჰაॆุᆭࡗކ৯֥ླਈିФડቀ.֮ۚ,ؓॆุಕࣉྛࡎބ࿊ᄴ,ۚބ৯֥ॆุ൳ࡌഡၘᆩ၂۱ࠊᇏྏ(Ⴈ0іൕ)ބn۱ग़֞՜ࣉ,ۚ୩؇֥ॆุ൳֞ၝᇅ.๙ݖॆุᆭࡗ֥ཌྷׄ(1,2,l,n),ૄ۱ग़ׄླਈഡູqi(i=1,2,՜ࣉބၝᇅቔႨ,ิۚቋႪࢳڸ֥࣍ෆ෬ི,ੱϥl,n),ग़ׄi֞j֥ए൞Dij(i,j=1,2,l,n),ຂअ҆ቋႪ,ၛղ֞ቋᇔ൬৻֞ಆअቋႪࢳ֥ଢࠊᇏྏૄਇӚ֥ڵᄛି৯नཋᇅູQ,ࡌഡMູ֥[3].ൌ࠽෮Ⴈ֥Ӛਇඔ,ഡnkֻູk(k=1,2,l,M)ਇ૧ၦ၌Ԯෘم൞ࡼ၌Ԯෘمა૧ၦෘمࣉྛವӚ෮ࣜݖ֥ग़ׄሹඔ,ႨࠢކSk={vki 0ink}ކ֥ᇆିႪ߄ෘم,ა၌Ԯෘمཌྷб,ᄹࡆਔॆჰটіൕֻkਇӚ෮ࣜݖ֥۲ग़ׄ,ఃᇏ,vk്љaॆุ୩؇טࢫۿିބ࠺ၫۿ,ିᄝ၌ԮෘمᇏiіൕֻkਇӚࣜݖֻ֥i۱ग़ׄ,vk0іൕࠊᇏྏ.ູႄೆॆุཌྷර؇ބॆุ୩؇֥ۀၛࠣॆุ୩؇॥VRP໙ีࡹ৫ඔ࿐ଆೂ༯ᇅҠቔ,ᄝؓॆุಕࣉྛܙ֥ൈ,ީ҂ࣇ࠹ෘॆุ:Tn֥ൡႋ؇,ط࠹ෘॆุ֥୩؇,۴ऌॆุ୩؇لᆴminZ=
(
kDrk(i-1)rki+Drknrk0),k॥ᇅཌྷරॆุ֥ඔਈ,ՖطЌӻᇕಕ֥؟ဢྟ,ٝᆸk=1i=1nෘمݖᄪ൬৻Ⴟଖअ҆ቋႪࢳ,ၹՎ൞၂ᇕڿࣉ.
kqrQ,k=1,2,l,M,(1)ki֥ऎႵ૧ၦۿି֥၌Ԯෘم.ა૧ၦෘمཌྷб,ᄝྙi=11nknൔഈ,ु൞ᄝ૧ၦෘمᇏࡆೆਔ၌Ԯෘሰ.ᆃဢ,,k=1,2,l,M,(2)
૧ၦ၌Ԯෘم࠻Ќਔ၌Ԯෘم֥ෆ෬ห,ྟႻᄝnk=n,k=1,2,l,M,(3)ޓնӱ؇ഈх૧ਔoᄪඃpགྷའ,֤ෘمіགྷԛSk={vki vki{1,2,l,n},0ink},(4)ൈӑᄀ၌Ԯෘمބ૧ၦෘم֥Ⴊׄ[9].Ч໓෮ഡ࠹Sk1Sk2= , k1k2.(5)֥૧ၦ၌Ԯෘم֥ࠎЧ҄ᇧೂ1෮ൕ.ఃᇏ,ଢѓݦඔZ൞֤ቋ؋֥ሹਫ਼ࣥӉ؇.ჿඏ่ࡱ(1)ູӚਇڵᄛཋᇅ,Ќᆣૄ่ਫ਼ࣥഈ۲ग़֥ׄሹླਈсྶཬႿӚਇڵᄛཋᇅ,ჿඏ(2)ཋקૄ่ਫ਼ࣥഈ֥ग़ׄඔ҂ӑݖሹग़ׄඔਈ,ჿඏ(3)j(5)ᄵ܋Ќᆣૄ۱ग़ׄႵӚਇູఃڛༀ,ѩཋקਔૄ۱ग़ׄᆺିႮ၂ਇӚট٠໙,ᆺିФ٠໙၂Ց.3`ࠎႿ૧ၦ၌Ԯෘم֥VRP໙ีࢳ`૧ၦ၌Ԯෘم֥ࠎЧනམ၌Ԯෘم൞ࠎႿളࣉ߄ݖӱᇏ֥ሱಖ࿊ᄴބ၌Ԯэၳ֩ࠏᇅطؿᅚఏট֥၂ᇕᇆିႪ߄ෘم,൞၂ᇕۚ؇ѩྛ֥aෛࠏaሱൡႋ֥ಆअྟۀੱෆ෬ෘم,ॖႨႿࢳथቆކႪ߄aࠏఖ࿐༝֩ᇆି໙ี.ࠎЧ၌Ԯෘمಸၞԛགྷoᄪඃpགྷའ,҂ିЌᆣၛቋնۀੱ൬৻֞ಆअቋႪࢳ,ᇶေჰၹ൞ࠎႿൡႋᆴб২֥࿊ᄴҦ֤ෘمᄝࣉ߄ݖӱᇏᇕಕ؟ဢྟࢆ,֮ᇁ֤ᆜ۱ᇕಕࣉ߄๔ᇌ҂భ,ෘمࢲݔ1`૧ၦ၌Ԯෘمੀӱ`Immunegeneticalgorithmflowchart๔ᄝअ҆ቋႪࢳڸ࣍,م֞ղಆअቋႪ.`ෘمऎุഡ࠹૧ၦෘم൞൳ള૧ၦࠏᇅఓؿطิԛ֥၂ᇕྍᇆିႪ߄ෘم,ऎႵਅݺ࠺ၫۿିaሱט 初始抗体群产生
ֻ3௹````````````ӱਟߩ,֩:ࠎႿ૧ၦ၌Ԯෘم֥Ӛਇਫ਼ࣥႪ߄໙ี``````````````9`1`ෘمൌགྷᇏ,ࡼVRP໙ี֥ଢѓݦඔࠣჿඏ֥୩؇іൕაఃཌྷර֥ॆุᅝᆜ۱ॆุಕ֥б২.่ࡱؓႋႿॆჰ,໙ี֥ࢳؓႋႿॆ,ุοᅶყ༵ഡࡌഡᇕಕᇏ܋Ⴕmᇕ҂֥ބ৯,ᄵࡼ۲ॆק֥ಕุܿଆN,ෛࠏളӮ၂ቆॆุቔູԚॆุಕ.ᆌؓVRP໙ี,Ч໓ॆุҐႨሱಖඔщุ֥୩؇لᆴഡᇂູ:Mmaxdensity(pi)=N.ؓႿ,Ⴈ0іൕࠊᇏྏӑݖ୩؇لᆴཋק֥ॆุ,ࡆၛ୩؇ၝᇅ,ࠧෛࠏള,Ⴈ1,2,l,nіൕn۱ग़ׄ,ॆุ֥щູ၂۱Ⴎ1֞n֥҂֥ሱಖඔቆӮ֥Ӊ؇ູӮӑ୩؇ܿଆඔਈ֥ۄྍॆุูߐࣸॆุ.n֥ཌྟਙ.ॆุࢳݖӱ:ູؓॆุᇏοඨԛགྷ 交叉变异操作֥ग़щݼᇯ۱ࣉྛҰ,ࡼଖग़ࡆೆ֞֒భࢌҭҠቔҐႨ҆ٳࢌҭٚم,ࠧᄝߐॆሰਫ਼ࣥ߶ᄯӮӚਇӑᄛ,ᄵࡼՎग़ቔູ༯၂ሰਫ਼ุࢌҭ؍ࠎၹԱ֥ൈ,טᆜఃჅᇗگ֥ࠎၹֻ໊֥֥ࣥ၂۱ग़ٚم.ࡌഡրᆳྛࢌҭҠቔ֥ਆ۱ॆุٳљູ:1,4,.7,3,8,5,2,9,6ބ2,5,8,1,9,6,7,4,3,ෛࠏӁള֥ 抗体适应度与亲和力计算קၬॆุაॆჰᆭࡗ֥ބ৯ູࠎၹࢌҭׄ൞3ބ6,ࢌߐਆ۱ॆุ֥ࢌҭׄᆭࡗ֥:G=1/F,ఃᇏࠎၹԱ,֤֞ਆ۱ᇏࡗॆ:ุ1,4 8,1,9,6 2,9,6,Fູൡႋ؇ݦඔ,ၛଢѓݦඔminZ=nބ2,5 7,3,8,5 7,4,3,ٳљטᆜ۲ॆุ֥ఃჅᇗ
T(
kDrk(i-1)rki+Drknrk0)ቔູൡႋ؇ݦඔ.Ⴎگࠎၹ໊,֤֞ਆ۱ྍॆ:ุ7,4 8,1,9,6 2,3,5kk=1i=1ބ৯܄ൔॖ,ਫ਼ࣥӉ؇ᄀ؋֥ॆุ,აॆჰބ৯ބ2,1 7,3,8,5 9,4,6.ᄀնэၳҠቔҐႨэၳٚم,ࡼଖॆุᇏෛࠏ,іૼھॆุᄀႪ.࿊ᇏ֥၂؍ሰԱ൮ແ֚ᇂ,Ӂള၂۱ྍॆ.ุࡌഡэ 抗体促进与抑制ᄝॆุࣉ߄ݖӱᇏ,ؓބ৯ࢠۚط୩؇ࢠ֮ၳభ֥ॆุູ:5,1,9 7,10,2,8,6 4,11,3,ࡌഡ֥ॆุࣉྛ՜ࣉ,ॆุक़ੈ֥ࠏੱۚ,္ѩ٤ཋෛࠏ࿊ᇏ֥၂؍ሰԱ൞ॆุᇏՖࠎၹ໊4֞ࠎၹ໊ᇅक़ੈ8ᆭࡗ֥ሰԱ7,10,2,8,6,ᄵؓھሰԱᆳྛэ,֒ॆุ֥୩؇ղ֞၂ק֥لᆴൈ߶൳֞ၝᇅ,ಒЌॆุಕุ۷ྍ֥ॆุ֥؟ဢ,ྟх૧ໃӮඃၳ,ࡼሰԱ൮໊ᇂ,֤֞ྍॆุ:5,1,9 6,8,2,൬৻10,7 12,4,11,3..ࡌഡॆุܿଆູ 终止条件判断N,ॆุಕູP={p1,p2,l,֒భॆุಕ֥ࣉ߄սඔղ֞ਔყק֥ቋնࣉpN},ࡌഡॆุpi֥ބ৯ູG(pi)(i{1,2,l,߄սඔൈෘمᇔᆸ.N}),۴ऌVRP໙ี֥หׄၛࠣࢳ֥щٚൔ,Ч໓ࡼॆุ֥୩؇קၬູ:density(pi)=N4`ൌဒ1N
similarity(pi,pj),ఃᇏ,ਆॆุ֥ཌྷර؇קၬj=1ູҐႨ໓ང[10]ᇏ֥ൌ২2ࣉྛҩ൫.ၘᆩ1۱: pi,pj,similarity(pi,pj)=1ࠊᇏྏބ20۱ग़ׄ,Ӛਇಸਈູ8t.ࠊᇏྏބ,ifG(pi)=G(pj),i,j{1,2,l,N}ji.ॆุ۲ग़֥ׄቕѓࠣླਈೂі1෮ൕ.0,else,і1`ࠊᇏྏބ۲ग़֥ׄቕѓࠣླਈ`Coordinatesanddemandsofdistributioncenterandallcustomerpointsग़щݼ0123456ቕѓᆴ,,,,,,,ླਈࠊᇏྏग़щݼ78910111213ቕѓᆴ,,,,,,,ླਈग़щݼ14151617181920ቕѓᆴ,,,,,,,ླਈ``໓ང[10]൞ҐႨ၌Ԯෘمބمཌྷࢲކ֥ࠁܿଆ40,ࣉ߄սඔ200,໓ᇏѩໃ۳ԛቋႪਫ਼ࣥ,۳ކ၌Ԯෘمࢳھቆൌဒඔऌ,֥ҕඔഡᇂູᇕಕԛਔࢳھൌ২֥10Ցෛࠏᄎྛࢲݔބनᆴ,ູ
92``````````````````ᇏଲቂն࿐࿐Б(ሱಖ॓࿐ϱ)ֻ29जਔьႿбࢠ,གྷႨЧ໓ഡ࠹֥ෘمࢳھൌ২,౼ބनᆴა໓ང[10]ࣉྛбࢠ,бࢠࢲݔೂі2ཌྷ֥ᇕಕܿଆބࣉ߄սඔ,ࡼ10Ցෛࠏ࠹ෘࢲݔ෮ൕ.і2`10Ցෛࠏҩ൫ࢲݔ֥бࢠ`Comparisonof10randomtestresultsෘمбࢠཛݼ12345678910नᆴࠁކ၌Ԯਫ਼ࣥӉ؇ෘم[10]Ӛਇඔ૧ၦ၌Ԯਫ਼ࣥӉ؇ෘمӚਇඔ``Վຓ,໓ང[10]ߎิ܂ਔࣇҐႨمބҐႨم֥ࠎԤഈ,ᆌؓVRP໙ี֥ห,ׄഡ࠹ਔ၂ᇕ၌Ԯෘمٳљࢳھҩ২֥नᆴ:م:,ࢳھ໙ี֥૧ၦ၌Ԯෘم.ෘمᄝᆳྛݖӱᇏ,๙ݖ၌Ԯෘم:.໓ང[10]֥ࠁކ၌Ԯෘم:122,طॆุ՜ࣉބၝᇅҠቔ,ၛࠣࢌҭބэၳෘሰ۷ྍॆЧ໓10Ց࠹ෘࢲݔ֥नᆴ൞.ุಕ,Ќᆣਔෘمᄝࣉ߄ݖӱᇏࢳ֥؟ဢ,ྟх૧ఃႨЧ໓෮ഡ࠹֥ෘم֤֥ቋႪਫ਼ࣥӉ؇ູ൬৻Ⴟअ҆ቋႪࢳ.ൌဒіૼ૧ၦ၌Ԯෘم҂ࣇऎ,Ⴈ3ਇӚປӮༀ,ቋႪਫ਼ࣥٳљСࠎЧ၌Ԯෘمෛࠏಆअѩྛෆ෬֥Ⴊׄ,ط๙ູ:18¹17¹3¹4¹14;20¹8¹7¹9¹12¹2¹10¹ݖ૧ၦҠቔႵֹིक़ڛਔෘمᄝࢳݖӱᇏಸၞཊ1¹5;19¹15¹16¹13¹6¹11.෮֤֥ቋႪਫ਼ࣥೆअ҆ቋႪ֥ሑ,֤ෘمᄝಆअ൬৻ྟഈ֤֞ೂ2෮ൕ.ਔ၂ק֥ڿࣉ,ൌဒࢲݔဒᆣਔෘمॖၛ֤ቋႪࢳࠇડၩࢳ.ҕ`ॉ`໓`ང[1]`DantzigGB,[J].ManagementScience,1959(6):80-91.[2]`น`এ.Ӛਇਫ਼ࣥ໙ีᇏ֥၌Ԯෘمഡ࠹[J].תն࿐࿐Б:ሱಖ॓࿐ϱ,2002,28(1):66-70.[3]`ًࡹ,ྮڂ.ࠎႿ૧ၦෘم֥Ӛਇਫ਼ࣥႪ߄໙ี[J].࠹ෘࠏ۽ӱაႋႨ,2006(4):210-212,217.[4]`Ⴥᆒ.Ӛਇਫ਼ࣥ໙ี֥ሱൡႋເѩྛ૧ၦ၌Ԯෘم[J].࠹ෘࠏ۽ӱაႋႨ,2010,46(1):221-223,226.[5]`ౄഒࢭ.SIGA:၂ᇕྍ֥ሱൡႋ૧ၦ၌Ԯෘم[J].ᇏ2`ቋႪ֥Ӛਇਫ਼ࣥն࿐࿐Б:ሱಖ॓࿐ϱ,2008(3):`Thebestvehicleroutingmap[6]`ӱ`Ⴇ,भڂ,ൗః.ੀӚਇਫ਼ࣥ໙ี֥ࠁކॹൌဒࢲݔބٳ༅іૼ,Ч໓෮ഡ࠹֥૧ၦ၌Ԯઓၖෘم[J].۽ြ۽ӱაܵ,2007,23(4):15-19.ෘم҂ࣇିЌࠎЧ၌Ԯෘمෛࠏaಆअaѩྛෆ෬[7]`ޱն,ᇫᆽ఼,ޱ`Ⴇ.Ӛਇਫ਼ࣥ໙ี֥ଆࠅෘ֩Ⴊׄم[J].ᇏݓ܄ਫ਼࿐Б,2006,19(4):123-128.,طߎିႵིक़ڛࠎЧ၌Ԯෘمᇏԛགྷ֥ᄪඃ൬৻གྷའ,ဒᆣਔھෘمᄝࢳVRP໙ีഈ֥[8]`TimmisJ,NealM,ႵིྟބႪ൝systemfordataanalysis[J].Biosystem,2000,55.(1):143-150.[9]`ޡ.ದ۽૧ၦ༢ჰაႋႨ[M].ݗغў:ݗغ5`ࢲඏეў۽ြն࿐ԛϱഠ,2003:131-157.[10]`བ,ޱන.Ⴈࠁކ၌Ԯෘمࢳੀෂਫ਼ࣥЧ໓ᄝ࣮VRP໙ีၛࠣ၌Ԯෘمބ૧ၦෘႪ߄໙ี֥࣮[J].ᇏݓܵ॓࿐,2002,10(5):51-56.
