뗚23뻭뗚2웚ꆡꆡ쓪4퓂ꆡꆡ맾뛻뇵짌튵듳톧톧놨(ퟔ좻뿆톧냦)JournalofHarbinUniversityofCommerce(NaturalSciencesEdition)폐쪱볤뒰뎵솾뗷뛈컊쳢폅뮯퇐뺿죎뒺폱,캤ꆡ뎬(뫚쇺붭듳톧탅쾢뿆톧폫벼쫵톧풺,맾뛻뇵150080)햪ꆡ튪:뗧ퟓ짌컱컯쇷웳튵붫쏦쇙뗄쫇뛠엺듎ꆢ킡엺솿ꆢ쪱볤튪쟳룟ꆢ탨쟳룶탔뮯뗄쿖듺뮯쫐뎡.듋쪱,엤쯍뎵솾샠탍뗄톡퓱ꆢ퓋쫤쪱볤뾼싇ꆢ죋풱뫍뎵솾죕뎣쪹폃럑폃뫍볓냠럑폃ꆢ엤쯍돉놾폫엤쯍쿟슷톡퓱,헢킩폫뒫춳뗄뎵솾뗷뛈폐뫜듳뗄닮뇰,뛸쟒맘쾵뢴퓓ꆢ쓑틔뺫좷맀쯣.틲듋,뾼싇뗧ퟓ짌컱뮷뺳쿂뗄컯쇷엤쯍쳘쫢탔,붫뒫춳뎵솾뗷뛈쒣탍뷸탐탞룄,캪붵뗍엤쯍돉놾,붫쒿뇪몯쫽룄캪믹폚럑폃ퟮ킡,벴뾼싇떽헽뎣뫍볓냠뗄뎵솾탐쪻럑폃ꆢ뎵솾뗈듽럑폃뫍죋풱럑폃뗈,춬쪱,캪쳡룟엤쯍럾컱훊솿뫍쳡룟쫐뎡뺺헹솦,붫쪱볤뒰짨캪펲쪱볤뒰.평폚뎵솾뗷뛈컊쳢쫇NP쓑컊쳢,닉폃룄뷸틅뒫쯣램뷸탐폅뮯쟳뷢.맘볼듊:뗧ퟓ짌컱;컯쇷엤쯍;폐쪱볤뒰뎵솾뗷뛈컊쳢;룄뷸틅뒫쯣램훐춼럖샠뫅:TP393ꆡꆡꆡꆡꆡ컄쿗뇪쪶싫:Aꆡꆡꆡꆡ컄헂뇠뫅:1672-0946(2007)02-0209-03ResearchonvehicleroutingproblemwithtimewindowsofoptimizationforelectroniccommerceRENChun2yu,WEIChao(SchoolofInformationScienceandTechnology,HeilongjiangUniversity,Harbin150080,China)Abstract:Logisticscompanyofelectroniccommercewillfacewithmodernmarketofmulti2plebatches,smallvolume,,consid2eringtransportationtime,routinepersonnelandvehicleutilizingexpense,overtimeexpense,,thetraditionalvehicleschedulingmodelismodifiedinordertoreducethedistributioncost,objectivefunctionismodifiedbasedonminimumexpense,namely,consideringroutineandovertimeexpense,vehiclewaitingexpense,,inordertoimprovethedistributionservicequalityandmarketcom2petition,,:electroniccommerce;logisticsdistribution;vehicleroutingproblemwithwin2dows;improvedgeneticalgorithmꆡꆡ쯦ퟅ뗧ퟓ짌컱뫍컯쇷엤쯍뗄톸쯙랢햹,ퟷ캪펰쫓.VRPTW컊쳢쫇튻룶뗤탍NP쓑쳢.웤퇐뺿랽램쿬웤뷸튻늽랢햹뗄VRPTW(VehicleRoutingProb2훷튪폐뺫좷쯣램뫍훇쓜폅뮯랽램.뺫좷쯣램훷튪냼lemwithTimeWindows)컊쳢틽웰룷랽쏦맣랺훘삨럖횦뚨뷧램ꆢ뚯첬맦뮮램뗈.뷼쯆쯣램훷튪냼삨쫕룥죕웚:2006-04-22.믹뷰쿮쒿:뫚쇺붭쪡뿆벼릥맘쿮쒿(GB05D202-3).ퟷ헟볲뷩:죎뒺폱(1974-),얮,뷌쪦,쮶쪿,퇐뺿랽쿲:뗧ퟓ짌컱1
ꆤ210ꆤ맾뛻뇵짌튵듳톧톧놨(ퟔ좻뿆톧냦)ꆡꆡꆡꆡꆡꆡꆡꆡꆡꆡꆡ뗚23뻭뷻볉쯑쯷램ꆢ쒣쓢췋믰쯣램ꆢ틏좺쯣램뫍틅뒫쯣램n뗈6Riyiklꇜwkꆡk=1,2ꆭ,m,(2)i=1.샽죧:뷻볉쯣램쫇20쫀볍80쓪듺틔살랢햹웰m살뗄튻훖죋릤훇쓜탍(AI)뗄뻖늿쯑톰랽램,춨맽6yikl=1ꆡi=1,2,...,n,(3)k=1쒣쓢죋뗄볇틤맽돌,듯떽헻쳥톰폅뗄킧맻.Band쿈n붫듋쯣램폃살쟳뷢6xijkl=yjklꆡj=1,2ꆭ,n;k=1,2,ꆭ,m,(4)VRPTWi=0,Laporte폃뷻볉쯑쯷쳡n룟쟳뷢VRP컊쳢뗄뺫뛈[1].쳬뷲듳톧훓쪯좪퓋폃6xijkl=yiklꆡi=1,2,...,n;k=1,2,...,m,(5)j=0뛠돵쪼뷢뫍좫뻖뷻볉뇭뗈룷훖듫쪩살복킡뷢뗄늻max{ai+gi+ti0}ꇜliꆡk=1,2,...,m,(6)컈뚨탔뫍삩듳쯑쯷랶캧[2].컷쓏붻춨듳톧풬쟬듯min{aj-t0j}ꇝeiꆡi=1,2,...,n,(7)짨볆뾼싇쪱볤뒰뿚뫍늻춬뎵솾샠탍뗄뷻볉쯣nn램6i6dx1,2,...,ijijkꇜLlkꆡi,j=1,2,,n;k=[3]i=0j=0.쒣쓢췋믰랽램뻟폐쫕솲쯙뛈뿬,좫뻖쯑쯷뗄쳘뗣,떫튻냣폫웤쯻쯣램뷡뫏쪹폃.샽죧:쳆폂쳡돶m.(8)튻훖평틅뒫쯣램뷡뫏쒣쓢췋믰쯣램뗄믬뫏쯣램쟳쪽훐:m캪엤쯍훐탄펵폐뗄뎵솾훖샠,nk캪뗚k샠뎵쫽솿;wk캪뗚k샠뎵솾뗄퓘훘솿;n캪뿍뮧탨쟳VRPTW컊쳢[4].심틏쯣램쫇튻훖웴랢쪽럂짺쯑쯷쯣램,ퟮ퓧평Mꆤ뗣쫽;gi캪탨쟳뗣뗄킶믵쪱볤,r캪뎵솾쎿킡쪱뗄Dorigo뗈죋쫗쿈쳡돶,늢돉릦펦폃폚TSP컊쳢;뫳죋볓틔룄퓬펦폃떽뗈듽럑폃;rk캪뗚k샠뎵쎿릫샯뗄럑폃;Ri캪i뗣VRPTW컊쳢.쇵헜쳡돶튻훖늢탐뛠틏좺쯣램뗄탨믵솿;Lk캪뗚k샠뎵솾쎿죕ퟮ듳퓋탐뻠샫;dij(PMACS2-캪엤쯍훐탄떽룷탨쟳뗣뗄뻠샫벰탨쟳뗣횮볤뗄뻠VRPTW)쟳뷢VRPTW컊쳢,좡뗃뷏뫃킧맻[5].췲탱샻폃ퟮ듳-ퟮ킡닟싔,복킡쇋심틏쯣램쿝죫뻖늿샫;v캪뎵솾욽뻹탐쪻쯙뛈;gi캪퓚탨쟳뗣i킶믵쪱쿝?뗄뿉쓜탔[6볤;e]i캪탨쟳뗣뗄ퟮ퓧뾪쪼ퟷ튵쪱볤,ekl0캪쎿쳵쿟.틅뒫쯣램뻟폐쟳뷢ퟩ뫏폅뮯컊쳢뗄솼뫃쳘탔.Joe샻폃틅뒫쯣램쟳뷢믹폚뎵솾ퟮ슷쪵볊뾪쪼쪱볤;li캪ퟮ췭쫕믵쪱볤,웤훐lkl0캪쎿짙뫍ퟜ돉놾ퟮ킡뗄뛠쒿뇪VRPTW컊쳢[7쳵쿟슷쪵볊ퟮ동뷡쫸쪱뿌;ai캪떽탨쟳뗣i뗄쪱].킻뇼샚짨볆믹폚ퟔ좻뇠싫랽쪽뗄뿉춬쪱뒦샭죭ꆢ펲쪱볤뒰볤,tijkl캪k샠뎵듓탨쟳뗣i떽탨쟳뗣j뗄쪱볤.풼쫸뗄틅뒫쯣램,늢뷡뫏쯣샽뷸탐퇩횤풼쫸쳵볾(2)뇭쪾쎿솾뎵솾쯹퓋쯍뗄믵컯솿[8].훬쫷죋뗈죋샻폃룄뷸틅뒫쯣램살뷢뻶럇싺퓘뎵솾뗷뛈폅늻뎬돶웤퓘훘솿;풼쫸쳵볾(3)뇭쪾쎿룶탨쟳뗣횻뮯컊쳢평튻솾뎵쯍믵;풼쫸쳵볾(4)뇭쪾죴뿍뮧뗣i평k[9].뗧ퟓ짌컱ퟷ캪튻샠햸탂뗄짌튵쒣쪽,폫뒫춳짌샠뎵쯍믵,퓲k샠뎵뇘듓쒳뗣i떽듯뗣j;풼쫸쳵볾튵믮뚯폐ퟅ놾훊뗄쟸뇰.폃뒫춳뎵솾뗷뛈쒣탍폅뮯(5)뇭쪾죴뿍뮧뗣i평k샠뎵쯍믵,퓲k샠뎵쯍췪뗄뷡맻뻍쫇룃뗣뗄믵뫳뇘떽듯쇭튻룶뗣j;풼쫸쳵볾(6)뫍(7):탐뎵슷쿟뿉쓜ퟮ킡,떫평폚쎻뾼싇떽뎵솾뫍볝쪻풱뗈룷훖럑폃,뛸떼훂컯쇷엤쯍돉놾뻓뇭쪾엉돶럾컱뗄죎튻솾뎵뗄돶랢뫍략믘쪱볤뚼뇘룟늻쿂탫퓚엤쯍훐탄뗄펪튵쪱볤횮쓚;풼쫸쳵볾(8)뇭쪾;믲쫇맽폚잿뗷돉놾ퟮ킡,뛸쓑틔내헕뿍뮧뗄튪쟳ힼ쪱쯍믵,벴쓑틔ힼ쪱떽듯,듓뛸쪧좥맋뿍쎿쳵쿟슷뻠샫늻듳폚뎵솾뗄ퟮ듳퓋탐뻠샫Lk.,떼훂웳튵좱랦쫐뎡뺺헹솦.틲듋,뾼싇뗧ퟓ짌컱뮷2ꆡ룄뷸틅뒫쯣램퓚VRPTW컊쳢펦뺳쿂뗄컯쇷엤쯍쳘쫢탔,붨솢믹폚럑폃ퟮ킡뗄펲쪱폃볤뒰VRPTW쒣탍,춬쪱퓚쒣탍훐퓶볓뛠풼쫸쳵볾쿞훆ꆡꆡVRPTW틑뺭놻횤쏷쫴폚NP췪좫컊쳢.틅뒫.평폚틅뒫쯣램뻟폐쯦믺폫뛠뗣쯑톰쳘탔,쟳뷢쯣램쫇튻훖쒣쓢ퟔ좻뷧훐짺컯뗄뷸뮯믺훆뗄폅뮯쪱늻틗쿝죫쟸폲ퟮ병뷢,놾컄쫔춼첽쯷펦폃룄뷸틅닟싔,쫇튻훖믹폚좺쳥ꆢ틾늢탐쯑쯷닟싔,쫇쟳뷢룃뒫쯣램뷸탐폅뮯쟳뷢샠컊쳢킧싊쿠떱룟뗄튻훖쯣램..ꆡ틅뒫뇠싫1ꆡ쫽톧쒣탍VRPTW쿟슷뗄룶쳥평뛠룶쯦믺ퟓ뒮ퟩ돉,쎿룶ퟓ뒮듺뇭튻쳵퓋쫤슷쿟짏놻럃컊뿍뮧뗄쿈뫳쮳nnMinz=r6max(ei-ai+gi,0)+M6(ai-li+탲,틲듋,닉폃뿍뮧뫅ퟔ좻쫽뷸탐뇠싫,믡쪹뒦샭컊i=1i=1nnmn쳢뇤뗃룼볲뷠.kgi,0)+6666dijxijklrk1(1)i=0j=1k=1l=1폃뿍뮧뫅뗄ퟔ좻쫽뷸탐뇠싫쪱,쪼훕틔ꆰ0ꆱ뇭풼쫸쳵볾:쪾엤쯍훐탄,좾즫쳥뻍쫇횸튻룶뷢믲튻쳵슷뺶,좾
뗚2웚ꆡꆡꆡꆡꆡꆡꆡꆡꆡꆡꆡꆡꆡ죎뒺폱,뗈:폐쪱볤뒰뎵솾뗷뛈컊쳢폅뮯퇐뺿ꆤ211ꆤ즫쳥뎤뛈쫇횸솬춬웰뗣ꆢ훕뗣퓚쓚뗄쯹폐뷚뗣룶뫏늢뗄뷡맻ퟷ캪뇤틬뫳뗄믹틲.쫽.떱좾즫쳥뎤뛈캪ln쪱,퓲틔n-1뇭쪾훕뗣.3ꆡ룄뷸틅뒫쯣램늽훨ꆡ돵쪼뷢뗄탎돉짨뇭쪾뇠싫뗄튻캬쫽ퟩ캪p[n],쿈쇮p[n]=Step1:gen=0,샻폃ퟔ좻쫽뇠싫랽쪽,릹퓬돵쪼{0,1,2...,n-1},퓙샻폃캱쯦믺쫽랢짺웷,닺짺좺쳥,늢쫤죫뿘훆닎쫽(붻닦룅싊pc,뇤틬룅싊pm,솽룶쯦믺헻쫽j1,j2;웤훐j1,j2:[1,n-2].붻뮻쫽ퟩ좺쳥맦쒣N,ퟮ듳퓋탐듺쫽)maxgen;훐p[j1]뫍p[j2]헢2룶풪쯘,탎돉튻룶쯦믺뗄돵쪼Step2:볆쯣쫊펦뛈;뷢.훘뢴룃맽돌,횱훁듯떽쯹탨뗄좺쳥맦쒣캪횹.Step3:죴gen<maxgen,gen=gen+1,퓲ꆡ쫊펦뛈몯쫽Step4;럱퓲춣횹볆쯣,늢쫤돶ퟮ폅뷢;닉폃싖엌뛄톡퓱램,튪쟳쫊펦뛈몯쫽캪럇뢺,Step4:내뇈샽뗄쫊펦뛈럖엤살톡퓱붻닦뇤틬춨맽쿂쏦뗄뇤뮯붫쒿뇪몯쫽뮯캪쫊펦뛈몯쫽.좾즫쳥;1ꆡꆡꆡꆡnzfm=Step5:뷸탐늿럖욥엤붻닦;.(9)zmStep6:뷸탐늿럖슷뺶랭뇤틬닙ퟷ;웤훐:fm캪뗚m룶좾즫쳥뗄쫊펦뛈,n캪뎣쫽1,z캪Step7:훘뢴늽훨2ꆫ6.돵쪼훖좺훐ퟮ뫃좾즫쳥쯹뛔펦뗄엤쯍럑폃;zm캪믹폚럑폃ퟮ킡뗄뛠풼쫸폐쪱볤뒰뎵솾뗷뛈쒣쒿잰좾즫쳥쯹뛔펦뗄엤쯍럑폃.탍,럻뫏뗧ퟓ짌컱뗄쪵볊탨쟳,돉놾ퟮ뗍,뛸쟒쓜릻ꆡ톡퓱쯣ퟓ싺ퟣ뿍뮧쪱볤튪쟳,좡뗃뷏뫃뗄쪵볊킧맻.놾컄닉좡내뇈샽뗄쫊펦뛈럖엤,쿔좻,쫊펦뛈풽듳뗄룶쳥,놻톡훐뗄룅싊뻍풽듳,쎿듎쯦믺쳴톡닎뾼컄쿗:솽룶뢸쳥,뷸탐쿂튻늽뗄닙ퟷ.[1]ꆡ:ꆡ붻닦쯣ퟓandapproximatealgorithm[J].EuropeanJournalofOperational놾컄쯹폃뗄쫇늿럖욥엤붻닦램.헢훖붻닦닙ퟷResearch,1992,59(3):345358.뗄훷튪쮼쿫쫇:헻룶붻닦닙ퟷ맽돌평솽늽살췪돉[2]ꆡ훓쪯좪,뫘맺맢.폐쪱볤뒰풼쫸뎵솾뗷뛈폅뮯뗄튻훖뷻볉쯣,쫗쿈뛔룶쳥뇠싫뒮뷸탐뎣맦뗄쮫뗣붻닦닙ퟷ,좻뫳램[J].쾵춳릤돌샭싛랽램펦폃,2005,14(6):522-526.[3]ꆡ풬쟬듯,ꆡ,훜퓙쇡.TabuSearch쯣램퓚폅뮯엤쯍슷쿟룹뻝붻닦쟸폲쓚룷룶믹틲횵횮볤뗄펳짤맘쾵살탞컊쳢훐뗄펦폃.볆쯣믺릤돌,2001,27(11):86-89.룄붻닦쟸폲횮췢뗄룷룶믹틲ퟹ뗄믹틲횵.샽죧,뛔[4]ꆡ쳆ꆡ폂,쇵럥쳎.탂탍틅뒫쒣쓢췋믰쯣램쟳뷢듸VRPTW컊쿂쏦솽룶뢸룶쳥닉폃PMX쯣램,짨붻뮻쟸폲캪쳢[J].볆쯣믺릤돌폫펦폃,2006,(7):7-9.[5]ꆡ쇵ꆡ헜,샮붨맺.믹폚듸쪱볤뒰뿚뎵솾슷뺶컊쳢뗄틏좺쯣램p1:(123|4567|89);p2:(215|5437|69);쫗쿈,붻뮻뢸듺룶쳥1뫍뢸듺룶쳥[J].뿘훆릤돌,2006,13(2):뗄솽룶붻[6]ꆡ췲ꆡ탱,쇖붡솼,퇮쿾캰.룄뷸뗄ퟮ듳-ퟮ킡심틏쯣램퓚폐쪱닦쟸폲,뗃떽:볤뒰뎵솾슷뺶컊쳢훐뗄펦폃[J].볆쯣믺벯돉훆퓬쾵춳,o1:(123|4567|89);o2:(215|4567|69);2005,11(4):572-576.좻뫳,뛔폚솽룶ퟓ듺룶쳥훐붻닦쟸폲틔췢돶쿖[7]ꆡJOEL,뗄뇩샺훘뢴pacityConstraintsUsingGeneticAlgorithms[C]//Proceedings,틀뻝붻닦쟸폲쓚뗄캻훃펳짤맘쾵,훰튻뷸탐붻뮻oftheFifthInternationalConferenceonGeneticAlgorithms,.ퟮ뫳뗃떽ퟓ룶쳥1993,:o1:(136|5437|89),춬샭[8]ꆡ킻뇼샚,샮ꆡ뻼,맹튫믍.폐쪱볤뒰뗄럇싺퓘뎵솾뗷뛈컊쳢뗄뗃떽ퟓ룶쳥2:o2:(214|4567|39).틅뒫쯣램[J].쾵춳릤돌톧놨,2000,15(3):ꆡ뇤틬쯣ퟓ[9]ꆡ훬쫷죋,샮컄뇲,뿯랼뻽.튻훖듸죭쪱볤뒰뗄컯쇷엤쯍슷뺶폅뛔폚뇤틬닙ퟷ,닉폃늿럖슷뺶랭뗄랽쪽.닙뮯틅뒫쯣램[J].볆쯣믺릤돌폫뿆톧,2005,27(12):108-ퟷ랽쪽쫇:퓚믹틲솴짏쯦믺톡퓱솽뗣,놣돖솽뗣췢110.닠뗄탲쇐늻뇤,붫솽뗣횮볤뗄탲쇐뷸탐랭,훘탂
