뗚3뻭ꆡ뗚4웚릤돌톧놨2006쓪8퓂ꆡꆡꆡꆡꆡꆡ쳺뗀뿆톧폫JOURNALOFRAILWAYSCIENCEANDENGINEERINGꆡꆡꆡꆡꆡꆡVol13ꆡ몬ힰ킶릤뗷엤뗄컯쇷뎵솾엤쯍슷뺶컊쳢뗄퇐뺿쇵ꆡ돏1,돂훎퇇2(1.훐쓏듳톧쫽톧뿆톧폫볆쯣벼쫵톧풺,뫾쓏뎤즳410075;2.훐쓏듳톧붻춨퓋쫤릤돌톧풺,뫾쓏뎤즳410075)햪ꆡ튪:뾼싇떽컯쇷엤쯍뎵솾슷뺶컊쳢훐튪짦벰믵컯뗄ힰ킶ퟷ튵,붫ힰ킶릤뗷엤컊쳢뫍뎵솾슷뺶컊쳢쿠뷡뫏쳡돶쇋몬ힰ킶릤뗷엤뗄컯쇷뎵솾엤쯍슷뺶컊쳢,룸돶쇋틔ퟜ퓋쫤럑폃ퟮ킡ꆢퟜힰ킶릤죋쫽ퟮ짙캪쒿뇪몯쫽뗄쮫쒿뇪0-1믬뫏헻쫽맦뮮컊쳢뗄쫽톧쒣탍.내쒿뇪몯쫽뗄훷듎럖2룶뷗뛎뛔룃컊쳢뷸탐쟳뷢;ퟮ뫳,붫ힰ킶릤죋쫽ퟮ짙뮯캪ힰ킶럑폃ퟮ킡붫룃쒣탍뷸탐쇋췆맣ꆣ맘볼듊:ힰ킶릤뗷엤;뎵솾슷뺶;믬뫏헻쫽맦뮮;NP-삧쓑훐춼럖샠뫅:+1ꆡꆡꆡ컄쿗뇪쪶싫:Aꆡꆡꆡ컄헂뇠뫅:1672-7029(2006)04-0079-05StudyonphysicaldistributionvehicleroutingproblemwithloaderschedulingLIUCheng1,2,CHENZhi-y2a(,CentralSouthUniversity,Changsha410075,China;,CentralSouthUniversity,Changsha410075,China)Abstract:Consideringthefactthatphysicaldistributionvehicleroutinginvolvetheprocessofloadingandunloadinggoods,thispapercombinedloaderschedulingproblemwithvehicleroutingproblem,,,:loaderscheduling;vehiclerouting;mixedintegerprogramming;NP-hardꆡꆡ뎵솾슷뺶컊쳢(VehicleRoutingProblem,VRP)컶,좡뗃쇋뫜듳뷸햹ꆣ쫇평TSP컊쳢퇜짺뛸돶뗄ꆣVRP뗄튻냣뚨틥캪:ힰ킶릤죋뗄뗷엤컊쳢퓧퓚20쫀볍60쓪듺훐뛔튻쾵쇐쯍믵뗣뫍(믲좡믵뗣),ퟩ횯쫊떱뗄탐뎵슷맺뿆톧풺쫽톧퇐뺿쯹퓚퇐뺿퓋쫤컊쳢뗄쪱뻍놻쳡쿟,쪹뎵솾폐탲뗘춨맽쯼쏇,퓚싺ퟣ튻뚨뗄풼쫸쳵돶살[2],횮뫳폐맘헢랽쏦뗄퇐뺿짵짙,횱떽뷼2쓪볾쿂(죧믵컯탨쟳솿ꆢ랢쯍솿ꆢ붻랢믵쪱볤ꆢ뎵솾죝쳆맺뒺뗈뛔웤뷸탐퇐뺿뫍췆맣[3,4]ꆣ붫쪹ힰ킶릤솿쿞훆ꆢ탐쪻샯돌쿞훆ꆢ쪱볤쿞훆뗈),듯떽튻뚨뗄죋쫽ퟮ킡뗄ힰ킶릤죋뗷엤컊쳢췆맣캪쪹ힰ킶럑폃쒿뇪(죧슷돌ퟮ뛌ꆢ럑폃ퟮ짙ꆢ쪹폃뎵솾쫽ퟮ짙뗈)ꆣퟮ짙뗄ힰ킶릤컊쳢,늢횸돶췆맣뫳뗄ힰ킶릤컊쳢쫇ퟔ1959쓪평Dantzig뫍Ramser쳡돶틔살,룃컊쳢뻍튻룶NP-삧쓑컊쳢ꆣ퓚뎵솾슷뺶컊쳢쳘뇰쫇ힰ킶돉캪ퟩ뫏폅뮯쇬폲퇐뺿뗄죈뗣횮튻ꆣ본폚룃컊쳢믬뫏뎵솾슷뺶컊쳢(Vehicleroutingproblemwith뻟폐훘튪뗄샭싛틢틥뫍쿖쪵틢틥,맺쓚췢톧헟듓늻backhauls,VRPB)뫍듸쪱볤뒰뗄뎵솾슷뺶컊춬뷇뛈뛔룃컊쳢뷸탐쇋듳솿뗄샭싛퇐뺿뫍쪵퇩럖쳢[1,5-10]훐짦벰믵컯뗄ힰ킶,ퟔ좻튲뻍짦벰ힰ킶ퟷ쫕룥죕웚:2006-06-10쁓ퟷ헟볲뷩:쇵ꆡ돏(1966-),얮,붭컷폀탂죋,뢱뷌쫚,듓쫂ퟩ뫏폅뮯,컯쇷릤돌퇐뺿
80쳺뗀뿆톧폫릤돌톧놨ꆡꆡꆡꆡꆡꆡꆡꆡꆡꆡꆡꆡꆡꆡꆡ2006쓪8퓂튵틔벰ힰ킶릤죋뗄뗷엤컊쳢ꆣ퓚틔췹뗄퇐뺿훐,룼킶릤죋쫽ꛂi,쪹ퟜ뗄퓋쫤돉놾ퟮ킡틔벰ퟜ뗄ힰ킶릤뛠뗄쫇뛔룷훖떥뒿뗄뎵솾슷뺶컊쳢뗄퇐뺿,뛸늢쎻죋쫽ퟮ짙ꆣ폐붫ힰ킶릤뗷엤컊쳢폫횮폐믺뷡뫏살뷸탐뾼싇ꆣ짨뎵솾떽듯뿍뮧j뗄쪱볤캪tj,뎵솾듓뿍뮧i떽퓚듋퓲붫ힰ킶릤뗷엤컊쳢뫍뎵솾슷뺶컊쳢쿠뷡뫏뿍뮧j뗄탐쪹쪱볤캪t(iji,j=0,1,ꆭ,l),뎵솾퓚뿍뷸탐쳖싛뫍퇐뺿ꆣ뮧i뒦뗄럾컱쪱볤캪S(ii=1,2,ꆭ,l),t0=0,S0m1ꆡ몬ힰ킶릤뗷엤뗄뎵솾슷뺶컊쳢뗄=0,퓲tj=ꇆlꇆXijk(ti+t)ij+Si,j=1,2ꆭ,쫽톧쒣탍i=1k=1l)ꆣꆡ룄뷸뗄ힰ킶릤뗷엤컊쳢뚨틥뇤솿:컄쿗[3]뾼싇뗄ힰ킶릤죋뗷엤컊쳢쫇:엤쯍훐1,뎵솾k듓뿍뮧i탐쪻떽뿍뮧j;탄폐Xijk=a솾믵뎵뚼튪쿲b룶뿍뮧ힰ킶믵컯ꆣ엤쯍훐탄0,럱퓲ꆣ뿉틔낲업ꛁ1,뿍뮧i뗄죎컱평뎵솾k췪돉;k캻ힰ킶릤룺ퟅ뎵솾k,튲뿉틔낲업ꛂi캻Yힰ킶릤만뚨퓚뿍뮧ik=0,럱퓲ꆣi(i=1,2,ꆭ,b)뒦ꆣ틑횪퓚뿍뮧i뒦탨튪뗄ힰ킶릤죋쫽쫇퓲평듋룸돶죧쿂쫽톧쒣탍(ꋲ):e(ii=1,2,ꆭ,b),엤쯍훐탄펦룃뾼싇죧뫎뗷엤ힰ킶릤,쪹ퟜ뗄ힰ킶릤죋min쫽ퟮ짙ꆣꇆlꇆlꇆmCijXijk+dꇆlmax(ai-ti,0)+i=0j=0k=0i=1뾼싇떽엤쯍뎵솾쫇틔쯍믵캪훷,틲듋,룺뎵뗄fꇆlmin(ti-b)i;(1)ힰ킶릤죋쫽펦쫇폐쿞뗄ꆣ캪듋i=1,퓚컄쿗[3]쯹룸뗄ힰ킶릤뗷엤컊쳢짏퓶볓풼쫸:뎵솾kퟮ뛠뿉틔룺뎵minꇆmlꛁk+ꇆꛂi;(2)뗄ힰ킶릤죋쫽쫇k=li=1vk(k=1,2,ꆭ,a),평듋뗃떽룄뷸뗄ힰ킶릤뗷엤컊쳢뗄쫽톧쒣탍캪(늻쪧튻냣탔,볙.ꆡꇆlQiYikꇜQk,(k=1,2,ꆭ,m);(3)짨i=1e1ꇝe2ꇝeb):쒣탍(ꋱ)ꆡꇆlYik=1,k=1,2,ꆭ,m;(4)mi=1inꇆaꛁk+minꇆbꛂiꆣk=1i=.ꆡmax{0,eꇆlXijk=Yjk,j=0,1,ꆭ,l;k=1,2,ꆭ,m;i-ꛁk}=ꛂi,ꆡ(i=1,2,ꆭ,b;i=0k=1,2,ꆭ,a)(5)ꛁkꇜvk,k=1,2,ꆭ,a;ꛁkꇊZ+,k=1,2,ꆭ,a;ꇆlXijk=Yik,j=0,1,ꆭ,l;k=1,2,ꆭ,m;j=0ꛂiꇊZ+,k=1,2,ꆭ,bꆣ(6)ꆡ몬ힰ킶릤뗷엤뗄뎵솾슷뺶컊쳢뗄쫽톧쒣탍뷡뫏룄뷸뗄ힰ킶릤뗷엤컊쳢,쳡돶죧쿂뗄뎵솾ꇆlXihk=1;k=1,2,ꆭ,m;(7)i=0슷뺶컊쳢:짨엤쯍훐탄튪쿲l룶뿍뮧쯍믵,뗚룶뿍뮧뗄탨쟳솿캪q(ii=1,2,ꆭꇆllXihk-ꇆXhjk=0,h=1,2,ꆭ,m,l;k=,l),늢쟒룃뿍뮧뒦탨i=0j=1튪e1,2,ꆭ,m(8)i룶ힰ킶릤ힰ킶믵컯;듓엤쯍훐탄떽뿍뮧믲뿍뮧떽뿍뮧뗄퓋쫤돉놾캪c(ij웤몬틥뿉틔쫇뻠샫ꆢ럑폃ꆢ쪱볤뗈;i,j=0,1,2,ꆭ,l,엤쯍훐탄뇠뫅캪ꇆlXi0k=1,k=1,2,ꆭ,m;(9)i=00);뿉폃m솾뎵뷸탐엤쯍,뎵솾뗄퓘훘솿캪Qk(ktj=ꇆlꇆmXijk(ti+tij+S),j=1,2,ꆭ,l;i=1i=1k=1,2,k,ꆭ,m)ꆣ뎵솾뇘탫퓚튻뚨뗄쪱볤랶캧[ai,bi]쓚떽듯,퓧폚ai떽듯붫닺짺뗈듽쯰쪧,틔d(10)뇭쪾뗈듽쯰쪧뗄떥캻믺믡돉놾a;동폚biꇜtiꇜbi,i=1,2,ꆭ,l;(11)i떽듯붫뒦틔튻뚨뗄돍랣,틔f뇭쪾떥캻돍랣럑폃ꆣ뿉틔낲업max{0,ei-ꛁk}=ꛂi,i=1,2,ꆭ,l;k=1,2,ꛁk캻ힰ킶릤퓚뎵솾k짏룺뎵ힰ킶믵컯,ퟮ뛠뿉틔룺ꆭ,m;(12)뎵뗄ힰ킶릤죋쫽쫇vꛁk;튲뿉틔퓚뿍뮧i뒦맍펶ꛂi캻kꇜvk,k=1,2,ꆭ,m;(13)ힰ킶릤살ힰ킶믵컯,퓲놾컊쳢뗄쒿뇪쫇좷뚨뎵솾뗄Xijk=0믲1,i,j=0,1,ꆭ,l;k=1,2,ꆭ,mꆣ엤쯍슷뺶틔벰쿠펦뗄룺뎵ힰ킶릤죋쫽ꛁk뫍맍펶ힰ(14)
뗚4웚ꆡꆡꆡꆡꆡꆡꆡꆡꆡꆡꆡ쇵ꆡ돏,뗈:몬ힰ킶릤뗷엤뗄컯쇷뎵솾엤쯍슷뺶컊쳢뗄퇐뺿81Yik=0믲1,i=0,1,ꆭ,l;k=1,2,ꆭ,m;퓚듋늻럁닉폃C-W뷚풼웴랢쪽쯣램살쟳뷢,뗃떽(15)룷뎵솾뗄엤쯍슷뺶ꆣꛁ뗚2뷗뛎:뛔뗚튻뷗뛎뗃떽뗄룷솾뎵뗄엤쯍슷kꇊZ+,k=1,2,ꆭ,m;(16)ꛂkꇊZ+뺶내쒣탍(ꋱ)뗄쟳뷢랽램살뗷엤ힰ킶릤,틲캪쯹,i=1,2,ꆭ,lꆣ(17)쪽뗃떽뗄쎿쳵슷뺶쫇쿠펦평쒳튻솾뎵살췪돉엤쯍죎(3)뇭쪾쎿솾뎵뗄쯍믵솿뻹늻뎬맽룃뎵뗄퓘훘솿;쪽(4)뇭쪾쎿룶뿍뮧뻹횻평1솾뎵살엤쯍컱,틲듋퓚뗚1뷗뛎쟳뗃벸쳵엤쯍슷뺶,퓚듋뻍쟳;쪽뷢벸듎쿠펦뗄쒣탍(ꋱ)(듋쪱뛔펦쯹폐슷뺶짏뗄쒣(5)뫍(6)뇭쪾2룶뇤솿횮볤뗄풼쫸맘쾵;쪽(7),(8)뫍(9)뇭쪾쎿솾뎵듓엤쯍훐탄돶랢,럃컊뿍뮧탍훐쿔좻폐a=1,aꇜbꆣퟮ뫳,붫룷쒣탍훐뗄룺뫳뎵ힰ킶릤뫍맍펶ힰ킶릤ퟛ뫏퓚튻웰벴뗃떽룷솾뎵,ퟮ뫳폖믘떽엤쯍훐탄;쪽(10)뫍(11)뇭쪾뎵솾떽듯뿍뮧뗄쪱볤틔벰웤쪱볤뒰풼쫸;쪽뗄룺뎵ힰ킶릤죋쫽뫍룷룶뿍뮧뒦뗄맍펶ힰ킶릤죋(12)놣횤쎿룶뿍뮧뒦ힰ킶믵컯뗄ힰ킶릤죋쫽늻짙폚룃뿍뮧쫽ꆣ뒦쯹튪쟳뗄ힰ킶릤죋쫽;쪽(13)뇭쪾쎿솾뎵짏ힰퟛ뫏뷗뛎1뫍뷗뛎2뗄뷢벴뿉뗃떽쒣탍(ꋲ)킶릤죋쫽뗄쿞훆ꆣ뗄뷢ꆣ뛔폚룃컊쳢뗄쟳뷢,튲뿉틔붫쪹ힰ킶릤죋쫽ퟮ2ꆡ컊쳢뗄쟳뷢짙뗄쒿뇪몯쫽(2)춨맽뢶룸쎿캻ힰ킶릤ힰ킶럑폃(늻춬뎵짏틔벰늻춬뿍뮧뒦뗄ힰ킶릤쯹뢶룸뗄ힰ킶ꆡ쒣탍(ꋱ)뗄쟳뷢컄쿗[3]룸돶쇋웤쒣탍퓚컞풼쫸쳵볾ꛁkꇜ럑폃펦늻춬)뛸뮯캪쪹ퟜ뗄ힰ킶럑폃ퟮ킡뗄쒿뇪몯쫽ꆣ헢퇹뻍붫쒿뇪몯쫽(1)뫍쒿뇪몯쫽(2)쒿vꆡ(k=1,2,ꆭ,a)쪱뗄ퟮ폅뷢,벴떱aꇜb쪱ퟮ폅뷢캪뇪몯쫽뫏돉캪1룶떥쒿뇪ꆣ,듓뛸붫쮫쒿뇪맦뮮쒣:ꛁ탍뮯돉떥쒿뇪맦뮮쒣탍ꆣ틲캪퓚쯹럖컶뗄컊쳢훐31=ꆭ=ꛁ3a=ea+1,ꛂ31=ea-ea+1,ꛂ3a+1=ꆭힰ킶럑폃ퟮ킡폫ힰ킶릤죋쫽ퟮ짙늢늻췪좫뗈볛,틲=ꛂ3듋,틔짏쟳뷢랽램듋쪱늻퓙쫊폃ꆣb=0(ퟮ폅횵캪ꇆa);뛸떱aꇝb쪱,ퟮ폅뷢e1캪:ꛁ31=ꆭ=ꛁ3a=0,ꛂ32=e2,ꆭ,ꛂ33ꆡ쒣탍췆맣b=eb(ퟮ폅횵캪ꇆb퓚쒣탍(ꋱ)훐,쒿뇪몯쫽쫇쪹ퟜힰ킶릤죋쫽e1)ꆣi=1ퟮ짙,쪵볊짏룼맘탄뗄쫇ퟜힰ킶럑폃ퟮ짙ꆣ죴뚨틥퓚컄쿗[3]뗄믹뒡짏룸돶틔짏쒣탍(ꋱ)쟳뷢횧뢶룸쎿캻룺뎵ힰ킶릤뗄럑폃쫇C(1)k,횧뢶룸쎿맽돌죧쿂:캻맍펶ힰ킶릤뗄럑폃쫇C(2)k;늢쟒뿍뮧i뒦맍펶1)내컄쿗[3]뗄랽램쟳돶틔짏쒣탍(ꋱ)훐컞릤죋뗄죋쫽늻쓜뎬맽u(ii=1,2,ꆭ,b)ꆣ쇭췢,캪풼쫸ꛁkꇜvk(1,2,ꆭ,a)쪱뗄ힰ킶릤폅뮯뗷뛈랽쇋놣횤믵컯퓚ힰ킶맽돌훐늻믡쫜쯰,뮹뿉튪쟳싺ퟣ낸ꆣ죧쿂풼쫸:2)뷡뫏풼쫸쳵볾ꛁkꇜv뛔(1)훐뗄랽낸뷸탐Skꛁk+tꛂiiꇝeki,k=1,2,ꆭ,bꆣ죧쿂뗷헻:떱aꇜb쪱:죴ϖjꇊ{1,2,ꆭ,a}쪹vj웤훐:Sk뇭쪾뎵솾k짏ힰ킶릤뗄릤ퟷ뮷뺳;tiꇜea+1,퓲쇮ꛁj=vj,뛸듋쪱쿠펦뗄ꛂj=ej-vjꆣ떱뇭쪾뿍뮧i뒦뗄맍펶ힰ킶릤죋쯘훊;eki뇭쪾뎵솾kaꇝb쪱,퓲늻뇤ꆣ퓚뿍뮧i뒦뗄ힰ킶튪쟳ꆣ퓲뗃떽죧쿂쫽톧쒣탍[4]:ꆡ쒣탍(ꋲ)뗄쟳뷢헢쫇튻룶쮫쒿뇪0-1믬뫏헻쫽맦뮮컊쳢,뛸쒣탍(ꋳ)ꆡminꆡꇆaC(1)kꛁk+ꇆbC(2)ꛂiik=1i=1쟒2룶쒿뇪뗄솿룙늻춬ꆣ캪쇋쟳뷢룃쒣탍,틔쒿뇪sꆤtꆡSkꛁk+tꛂiiꇝeei,k=1,2,ꆭ,a;i=1,몯쫽(1)캪쒣탍(ꋲ)뗄훷튪쒿뇪몯쫽,뛸쒿뇪몯쫽2,ꆭ,b;(2)캪쿠뛔듎튪뗄쒿뇪몯쫽ꆣ쿂쏦럖2룶뷗뛎뛔룃ꛂiꇜui,i=1,2,ꆭ,bꆣ쒣탍뷸탐쟳뷢ꆣ(웤폠풼쫸쳵볾춬쒣탍(ꋱ))뗚1뷗뛎:퓚쒣탍(ꋲ)훐좥뗴쒿뇪몯쫽(2)뫍평듋붫쒣탍(ꋲ)췆맣캪죧쿂쒣탍(ꋴ),퓚쒣풼쫸쳵볾(12),(13),(16)뫍(17)퓝쪱늻볓뾼싇,헢탍(ꋴ)훐쒿뇪몯쫽뮯캪냼삨퓋쫤럑폃뫍ힰ킶럑퇹쒣탍(ꋲ)뻍뇤돉떥뒿뗄듸죭쪱볤뒰뗄뎵솾슷뺶폃뗄ퟜ럑폃ퟮ킡뗄떥쒿뇪ꆣ컊쳢쒣탍,쟳뷢뎵솾슷뺶쒣탍뗄웴랢쪽쯣램뫜뛠ꆣ쒣탍(ꋴ):
82쳺뗀뿆톧폫릤돌톧놨ꆡꆡꆡꆡꆡꆡꆡꆡꆡꆡꆡꆡꆡꆡꆡ2006쓪8퓂dmij/50ꆣ냑뎵뎡폫룷뿍뮧틔벰룷뿍뮧횮볤뗄뻠샫ퟷinꆡꇆlꇆlꇆmCijXijk+dꇆlmax(ai-ti,0)i=0j=0k=1i=1캪럑폃,죧뫎낲업뎵솾뗄탐쪻슷쿟뫍ힰ킶릤죋쫽,+쪹ퟜ럑폃틔벰ퟜ뗄ힰ킶릤죋쫽ퟮ짙fꇆlmax(ti-bi,0)+ꇆmC(1)kꛁk+ꇆbC(2)ꛂꆣ쿂쏦럖2룶뷗ikꆣi=1k=1i=1sꆤtꆡ뛎살뛔룃컊쳢뷸탐쟳뷢:Skꛁk+tꛂiiꇝeki,(k=1,2,ꆭ,b)ꛂiꇜ뗚1뷗뛎:평CꆪW뷚풼웴랢쪽쯣램뿉쟳뗃늻ui,(i=1,2,ꆭ,b)뾼싇ힰ킶릤뗷엤쪱떥뒿뗄듸쪱볤뒰뗄뎵솾슷뺶컊(웤폠풼쫸쳵볾춬쒣탍(ꋲ))평폚쒣탍(ꋳ)쫇튻룶쳢뗄뷢,벴:엤쯍쯹탨뎵솾3솾,쿠펦뗄뎵솾슷뺶럖NP-삧쓑컊쳢[4],뛸떥뒿뗄뎵솾슷뺶컊쳢튲쫇튻룶NP-삧쓑컊쳢,틲듋뇰캪0-3-1-2-0,0-6-4-0뫍0-8-5-,뫁컞틉컊7-0ꆣ,쒣탍(ꋴ)쫇NP-삧쓑뗄ꆣ틲캪풽살풽뛠뗄쿖듺폅뮯샭싛뫍랽램뗄돶쿖뗚2뷗뛎:샻폃쒣탍(ꋱ)뗄쟳뷢쯣램럖뇰뛔폚(죧틏좺쯣램ꆢ틅뒫쯣램ꆢ짱뺭췸싧ꆢ쒣쓢췋믰쯣램ꆢ뷻볉쯑쯷쯣램뗈튻슷뺶0-3-1-2-0,0-6-4-0뫍0-8-5-쾵쇐웴랢쪽쯣램)캪쟳뷢NP-삧쓑쳡릩쇋탂뗄춾7-0뷸탐ힰ킶릤뗷엤,웤뷡맻쫇슷뺶0-3-1-2뺶ꆣ헢퇹,뫏샭샻폃헢킩쯣램좥쟳뷢쒣탍(ꋴ)쫇뿉-0짏뗄룺뎵ힰ킶릤뗄죋쫽캪3,뿍뮧1뫍3늻탨튪틔쪵쿖뗄ꆣ맍펶ힰ킶릤,뿍뮧2탨튪맍펶2쏻ힰ킶릤;슷뺶0-6-4-0짏뗄룺뎵ힰ킶릤뗄죋쫽캪4,뿍뮧4탨튪맍4ꆡ쯣샽퇐뺿펶1쏻ힰ킶릤,뿍뮧6탨튪맍펶2쏻ힰ킶릤;슷뺶0쿖폐룸-8-5-7-0짏뗄룺뎵ힰ킶릤뗄죋쫽캪4,뿍뮧58룶뿍뮧퓋쯍믵컯뗄죎컱(뇠뫅캪1,2,ꆭ,b),룷뿍뮧뗄믵퓋솿탨튪맍펶2쏻ힰ킶릤,뿍뮧7탨튪맍펶1쏻ힰ킶릤,q(i떥캻:t);럾컱쪱볤S(i떥캻:h);튪쟳쎿룶뿍뮧뾪쪼횴탐뗄쪱볤랶캧뿍뮧8늻탨튪맍펶ힰ킶릤ꆣ[ai,bi]틔벰쎿룶뿍뮧뒦탨튪뗄ힰ킶릤뗄죋쫽ei평5ꆡ뷡ꆡ폯뇭1룸돶ꆣ헢킩뿍뮧평뎵뎡0랢돶뗄죝솿캪8t뗄뎵붫ힰ킶릤죋뗷엤컊쳢뫍뎵솾슷뺶컊쳢쿠뷡뫏,솾살췪돉,쎿솾뎵짏ퟮ뛠뿉틔룺뎵뗄ힰ킶릤뗄죋쫽쳡돶쇋몬ힰ킶릤뗷엤뗄뎵솾슷뺶컊쳢,룸돶쇋쿠펦캪4죋ꆣ뎵뎡0폫룷뿍뮧횮볤뗄뻠샫(떥캻:km)평뗄쫽톧쒣탍뫍쟳뷢랽램ꆣ늢퓚듋믹뒡짏뛔쒣탍뷸탐뇭2룸돶ꆣ뇭1ꆡ룷뿍뮧뗣뗄쳘헷벰엤쯍튪쟳쇋췆맣ꆣ쇭췢,ힰ킶릤뗷엤컊쳢튲뿉틔뷡뫏떽믬뫏뎵뛓벰폐쪱볤뒰뗄뎵솾슷뺶컊쳢훐좥ꆣ쳘뇰뛔ힰ킶Table1ꆡThecharacterofeverycustomerdotandthereguirementofitsdistribution믬뫏뎵솾슷뺶컊쳢(VRPB)뾼싇ힰ킶ퟷ튵붫룼뻟뿍뮧쪵볊틢틥ꆣ닎뾼컄쿗:[a[1]샮ꆡ뻼,맹튫믍.컯쇷엤쯍뎵솾폅뮯뗷뛈샭싛폫랽램i,bi][1,4][4,6][1,2][4,7][3,][2,5][5,8][,4][M].놱뺩:훐맺컯돶냦짧,2001.뇭2ꆡ룷뗣뛔횮볤뗄뻠샫LIJun,ꆡThedistanceofeverycustomerdotroutingproblemoflogisticdistribution[M].Beijing:ChinaLo2igistiesPress,[2]훐맺뿆톧풺쫽톧퇐뺿쯹퓋돯쫒.퓋돯톧[M].놱뺩:뿆톧돶냦짧,,InstituteofMathematics,[M].Bei23754075010050909015049010010010001007575100jing:SciencePress,[3]쳆맺뒺.ힰ킶릤죋뗷엤컊쳢벰웤뷢램[J].짏몣뗚뛾릤61007575907570070100716011075907590700100튵듳톧톧놨,2005,22(1):[J].JournalofShanghaiSecondPolytechnicUniversity,헢샯짨뎵솾뗄탐쪻쪱볤폫뻠샫돊헽뇈,쎿솾뎵2005,22(1):1-5.뗄욽뻹탐쪻쯙뛈캪50km/h,퓲탐쪻쪱볤tij=[4]쳆맺뒺.쿖듺컯쇷벼쫵훐ힰ킶릤컊쳢뗄쓢뛠쿮쪽쪱볤
뗚4웚ꆡꆡꆡꆡꆡꆡꆡꆡꆡꆡꆡ쇵ꆡ돏,뗈:몬ힰ킶릤뗷엤뗄컯쇷뎵솾엤쯍슷뺶컊쳢뗄퇐뺿83뿉뷢쟩뿶[J].퓋돯폫맜샭,2005,14(4):,2005,2(4):[J].Opera2[7]ThangiahSR,Jean-Yves,,2005,14(4):15-hicleroutingwithbackhaulsandtimewindows[J].,1996,23(11):1043-1057.[5]색쎯쿩.ힰ킶믬뫏뎵솾슷뺶컊쳢뗄쒣쓢췋믰쯣램퇐뺿[8]WadeAC,[J].쾵춳릤돌톧놨,2005,20(5):[J].Omega,2002,30:[J].JournalofSys2[9]TanKC,LeelH,ZQL,,2005,20(5):[J].ArtificialIntelligentin[6]럢좫쾲,쇵ꆡ돏.컯쇷엤쯍뎵솾슷뺶컊쳢뗄늢탐틅뒫쯣Engineering,2000,29(7):281-295.램퇐뺿[J].쳺뗀뿆톧폫릤돌톧놨,2005,2(4):88-91.[10]BentR,-stagehybridlocalFENGQuan-xi,[J].[R].USA:BrowUniversity,2001.
