ֻ20ज ֻ4௹ ୡѯն࿐࿐Бč۽ϱĎ 2007୍12ᄅ JOURNAL OF NINGBO UNIVERSITY ( NSEE ) Dec. 2007 ໓ᅣщݼ:1001-5132č2007Ď04-0503-04 ૫ཟᇏཬఒြࠢಕ֥٤ડᄛӚਇט؇໙ี࣮1212༱໓ૼđݓڶđᇫචתđွ٦وč1.ୡѯն࿐ ྐ༏॓࿐ა۽ӱ࿐ჽđᆄࡾ ୡѯ 315211Ġ2.ୡѯն࿐ ۽࿐ჽđᆄࡾ ୡѯ 315211Ď ᅋေğࠎႿᇏཬఒြࠢಕ֥หׄđ۳ԛቋഒෂӚਇඔ֥࠹ෘଆđՖቋഒෂӚਇඔaቋ؋एa۲ਫ਼ཌӱޙބൈࡗԳ֩ٚ૫ؓࠢෂ၂ุ߄Ӛਇט؇໙ีࡹ৫ଆđႨڿࣉ֥ଆࠅෘمࢳھט؇ଆ. ๙ݖٟᆇൌ২ဒᆣਔھෘم֥ॖྛྟđژކൌൈྟ֥ေ. ܱՍğӚਇט؇Ġ٤ડᄛĠൈࡗԳĠෂӚਇඔ ᇏٳোݼğTP183 ໓ངѓ്ğA གྷᄝఒြᆭࡗ֥ੀෂหљ൞ᇏཬఒြࠢॖ૭ඍູğଖӚӆႚႵ၂קඔਈᄛᇗਈनູQ֥Ӛಕᆭࡗ֥ੀෂ၂Ϯ൞ཬٓຶa࣍एaཬਈaਇđགྷႵnཛࠊᄎൻༀေປӮđૄ۱ༀႵ؟Ցaູ؟Ⴈڛༀ֥ࣜ࠶ࠃđᆃൈૄ۱ༀሱ֥࠭ࠢࠊׄބෂࠊׄđေӚਇᄝ၂ק֥ࠢࠊ֥ׄׄࠊਈཬႿӚਇಸਈđႨ၂ਇӚࠧॖᆳྛༀ. ልࠊުᄎᇀ၂ק֥ෂࠊཱྀׄࠊđၘᆩૄ۱ༀ֥ࠊЧ໓ࡼࠎႿᆃུหׄđࡹ৫ቋഒෂӚਇඔ֥࠹ෘᄎਈGડቀG<Qđ1/2Q<G<Qđᆃൈ҂iiiଆđՖቋഒෂӚਇඔaቋ؋एa۲ਫ਼ཌӱ֥ༀၛႨ၂ਇӚটປӮ. ေૄཛༀᄝܿޙބൈࡗԳ֩ٚ૫ؓࠢෂ၂ุ߄Ӛਇט؇໙ีק֥ൈࡗٓຶଽປӮđડቀࠊᄎླ֥ٮႨቋཬࡹ৫ଆ. ଢభđ၂ུ࣮Ӛਇט؇໙ี֥໓ང֥ਫ਼ཌט؇ٚσđေھٚσି۲Ӛਇ֥۽ቔ[1-3]ીႵ۳ԛປӮༀ෮ླေ֥ቋഒӚਇඔđط൞ਈбࢠनޙđࠧ҂ିԛགྷႵ֥ӚਇޓॹࣼປӮਔ۳ყ༵۳קӚਇඔđᄝᆃ۱ࠎԤഈႪ߄ט؇ਫ਼ཌ. ކק֥ༀđطႵ֥ӚਇླေޓӉൈࡗҌିປӮ۳ק֥ෂӚਇඔႋھ۴ऌऎุༀބჿඏ่ࡱಒༀ֥ሑঃ. ູ҂ᄯӮூসࡐđေૄ۱ඳࠏ֥קđط҂ႋყ༵۳ק. طᆃུ໓ངᇶေՖቋ؋एᄎൻӱ҂ӑݖ۳ק֥ᆴ. đቋ؋ൈࡗটႪ߄ט؇ਫ਼ཌđીႵॉ੮ඳࠏ֥ூসࡐđЧ໓ᄝᆃུٚ૫ࡼჍၛປ. 2 ଆࡹ৫ 1 ໙ี૭ඍ ቋഒӚਇඔܙ࠹ ૄ۱ༀஊ၂ਇӚԛಀܥಖॖၛປӮༀđႵӱބൈࡗԳჿඏ֥٤ડᄛӚਇט؇໙ีೂݔଖӚਇᄝປӮଖཛༀުିܔᄝ҂ິّჿ ൬۠ರ௹ğ2007-06-06. ୡѯն࿐࿐Бč۽ϱĎຩᆶğ ࠎࣁཛଢğݓࡅሱಖ॓࿐ࠎࣁč70540023ĎĠᆄࡾസሱಖ॓࿐ࠎࣁčM703100đZ604342ĎĠ࢝ტ҆॓࿐ඌ࣮ᇗׄཛଢč205066ĎĠୡѯն࿐࢝൱ࠎࣁčXJ0709004Ď. ቔᆀࡥࢺğ༱໓ૼč1982ĒĎđଳđК༹ୡದđᄝණൖ࣮ളđᇶေ࣮ٚཟğӚਇט؇აႪ߄ቆކ. E-mail: xwmzip2006@
504 ୡѯն࿐࿐Бč۽ϱĎ 2007 ඏ่֥ࡱ༯đᆰࢤᄜಀປӮਸ਼၂ཛༀđ၂Ϯটඪđ(3) ൈࡗԳ१ჿඏ. ൈࡗԳ१൞ෛሢਬ९թᆃбૄ۱ༀՖӚӆஊ၂ਇӚԛಀ֥ӮЧေ֮(Just In Time, JIT)֥ิԛطӁള֥đေਬࡱᆺ֤؟đၹՎປӮଖུༀஊԛಀ֥ӚਇඔᄀഒӮЧᄝᆞݺླေ֥ൈࡗٓຶଽෂղളӁཌđၛࡨഒ९ᄀ֮. ູࡨഒӮЧđ൮༵ܙ࠹ປӮ෮Ⴕༀ෮ླေթđࢆ֮ӮЧ. ࡌഡSіൕӚਇ֞ղࠊᅜi֥ൈख़đi֥ቋഒӚਇඔm. DіൕӚਇᄝࠊᅜi֩ր֥ൈࡗđDіൕӚਇႮiijഡႵnཛᄎൻༀđܿקֻjཛༀT(j=1đ ࠊᅜiྛ֞ࠊᅜj֥ൈࡗđࡌഡࠊᅜi֥ልཱྀj2đ⋅⋅⋅đn)षᆳྛ֥ൈࡗԳູ[EđL]đༀTປӮࠊ؇ູVđᄵႵğ jjii֥ൈख़ູOđᄍྸଖᄎൻӚਇᆳྛປༀTުᄜS=0đi=0іൕӚਇՖӚӆԛؿĠ ii0ሇ߭টᆳྛༀTđᆺေھӚਇ֥ሇ၍ൈࡗT(ՖX=1đᄵႵS+D+D+G/V=Sđi≠jĠ jijijiiijiijༀi֥ປӮֹׄ֞ༀjԛؿֹׄ෮Ⴈ֥ൈࡗ)D=max{E−Sđ0}đࠧӚਇᄝEᆭభ֞ղiiiiᄝༀT֥षᆳྛൈࡗԳଽđࠧğ ࠊᅜjđᄵӚਇླᄝՎ֩րĠӚਇᄝLᆭު֞ղjiEO+TL. ཁಖđປӮnཛᄎൻༀࠊᅜiđᄵေࣉྛཌྷႋ֥ԩـ. jiijjቋ؟ླေnਇӚ. קၬYູğ ᆃൈࡗԳ֥ଢѓݦඔZູğ ij3nn1đ⎧ປӮༀTުᄜሇಀປӮༀTđijZ=Cmax(S−Lđ0)+Cmax(E− Y= ⎨3∑2∑ii3iij0đڎᄵ(iđj=1đ2đ⋅đn)đ i=1=1⎩Sđ0)đ (4) iᄵླေஊԛ֥ቋഒӚਇඔmູğ nnఃᇏಃᆴCđC֥౼ᆴࠏᇅაCཌྷ. 231m=n−Y. (1) ∑∑iji=1j=1(4) ༀनޙჿඏ. ሹӮЧቋཬ֥ਫ਼ཌ҂၂ק ჿඏ่ࡱ ି۲Ӛਇ֥۽ቔਈनޙđఃᇏଖུӚਇ۽ቔਈູьႿࡹ৫ႵൈࡗԳa٤ડᄛٿоӚਇט؇໙ࢠնđॖି߶ඳࠏூসࡐ֝ᇁؿള൙ܣđሇطี֥ඔ࿐ଆđקၬэਈXೂ༯ğ ijӮЧᄹࡆđܣླؓनޙิԛ၂ק֥ေđࠧ۲Ӛ1đ⎧ӚਇႮࠊᅜiཟࠊᅜjđX= ⎨ਇࡗᄎൻਫ਼ཌ֥Ӊ؇ҵ҂նႿଖ۳קᆴLđࠧij0đڎᄵ. ⎩(f−f)<LđఃᇏfູmਇӚᇏቋӉ֥ᄎൻmaxminmaxࡌഡࠊᅜi֥ࠢކູNđWіൕӚਇႮࠊᅜiijਫ਼ӱđfູmਇӚᇏቋ؋֥ᄎൻਫ਼ӱđᄵनޙჿmin֞ࠊᅜj֥ٮႨđᄵႵ༯૫֥ჿඏ่ࡱ. ඏ֥ଢѓݦඔॖіൕູğ (1) ᄎൻٮႨZቋཬ. 1nnZ=Cmax(f−f−Lđ0)đ (5) 44maxminminZ=WX.(2) 1∑∑ijijఃᇏCູӲـၹሰđაಃᆴC֥౼ᆴࠏᇅཌྷ. i=0j=141(2) ಸਈჿඏđࠧૄਇӚ෮ປӮ֥ༀ֥ࠊູ҂ᄯӮூসࡐđߎܿקૄਇӚ֥ྛਫ਼ӱ҂ӑਈ҂ିӑݖӚ֥ᄛᇗਈ. ݖ၂۱۳ק֥ᆴRđࠧfR. ଢѓݦඔॖіൕmaxnູğ GYQđi∈Nđ∀k=1đ2đ⋅⋅đm. ∑iiki=1Z=Cmax(f−Rđ0)đ (6) 55maxႨಸਈჿඏ֥ଢѓݦඔູğ ఃᇏCູӲـၹሰđაಃᆴC֥౼ᆴࠏᇅཌྷ. n51ZCmax(GY−Qđ0).(3) 2∑1iikሸഈđॖ֤ႵӱބൈࡗԳჿඏ֥٤ડᄛӚਇi=1ט؇໙ี֥ିਈݦඔğ ಃᆴC൪ؓಸਈჿඏ֥ᇗ൪ӱ؇طקđູਔ1۬ડቀಸਈჿඏđႋႵC=+∞đॉ੮֞࠹ෘE=CZ+Z+Z+Z+Zđ(7) 1012345ࠏԩ֥҂ьđCॖ౼၂۱ൡ֒ն֥ᆞඔ. ఃᇏCູZ֥ಃᆴđ൪Zᄝᆜ۱ݦඔEᇏ֥бᇗ0111
ֻ4௹ ༱໓ૼđ֩ğ૫ཟᇏཬఒြࠢಕ֥٤ડᄛӚਇט؇໙ี࣮ 505 طקđх૧ᄝ൬৻ݖӱᇏZФшჸ߄. ᆸđڎᄵᆳྛ(3). 1Ֆෘمੀӱഈुđᄝھෘمᇏđਣࢳ֥Ӂളٚ3 ଆࢳ مބਣთࢲܒ֥ܒᄯᄝޓնӱ؇ഈ߶႕ཙෘمི֥ݔ. Ч໓რႨၛ༯ෘمᅳਣࢳ. ູࣚಒࢳđЧ໓რႨڿࣉ֥ଆࠅෘمႪ(1) Ԛ߄S'đS'={Ԣ൮ແ2۱ਬຓđ၇00߄ݦඔE. ູਔٝᆸෘمՖಆअቋႪ๋߭अ҆ቋՑࡼSᇏ֥ਬಀו}đࠧປӮଖཛༀު҂߭Ӛ0ႪđЧෘمഡᇂਔ၂۱࠺ၫၹሰpđ࠺ᇾ෮ႵӆđᆰࢤಀປӮ༯1۱ༀĠ ෆ෬֥֞अ҆ቋႪᇏ֥ቋཬᆴđᆃဢࣼෘႻ๋߭अ(2) ೂݔΔE0đᄵS=S'đڎᄵࡼਬҀഈđ00҆ቋႪđ္ॖၛ๙ݖ࠺ၫၹሰpᇗേࣜݖ֥ಆअቋࠧᄜࢤሢಀປӮਸ਼၂ࡱༀࣼ߶ິّჿඏđᄵླႪ. ေᄜՖӚӆஊ1ਇӚԛಀĠ ᇶေᆳྛ҄ᇧ (3) ᆜඔi=1đj=i+1Ġ ࡌഡༀTູࡼࠊՖࠊᅜiᄎൻ֞iđᄵ(4) ؎j൞ڎཬႿn(nູༀඔ)đೂݔ൞ᄵi12T={iđi}ູ၂่Ⴕཟш. ᆜ۱ෘم֥ॿࡏೂ༯ğ ࢌߐS'ᇏiđj໊ᇂԩ֥ჭ֤֞S''đೂݔ҂൞ᄵi1200(1) ܒᄯ၂۱ԚॖྛࢳS={0đTđ0đTđ0đ⋅đ ෘمࢲඏĠ 0120đTđ0}đ0іൕӚӆđࠧSіൕૄཛༀஊ၂(5) ࠹ෘΔE=E(S')−E(S')đ ೂݔΔE>0đ n000ਇӚԛಀᆳྛđᆳྛປުْ߭ӚӆĠ ᄵS'=S''Ġ 00(2) ۳ק၂۱ࢠն֥ఏ໑؇T=Tđ໑؇T(6) i=i+1đj=j+1đᆳྛ(3). 0֥༯ࢆੱσđቋ֮໑؇minTބ၂۱ڜׄඔpđఃᇏڜׄඔp൞Ⴈট࠺ᇾቋཬ֥अ҆ቋႪׄđॖٝᆸ4 ଆٟᆇ ӱ๋ݖಆअቋႪׄު๋҂߭টਔĠ (3) ᄝSਣთଽӁള၂۱ྍࢳS'Ġ ഡႵ8۱ࠊᅜđщݼٳљູ1đ2đ⋅⋅⋅đ8đႮӚ00(4) ΔE=E(S')−E(S)đ࠹ෘିਈݦඔҵᆴĠ ӆ0ஊԛӚਇᆳྛༀđӚਇ֥ಸਈູ10tđܿ00(5) ೂݔΔE0đS=S'đp=Sđᆳྛ(7)Ġ קt=2đC=100đC'=1000đC=10đC'=100.ࡌഡ0002233-1(6) ೂݔΔE>0đ࠹ෘࢤ൳ਫ਼ཌטᆜ֥ۀੱૄਇӚ֥ྛ؇ູ50km·hđᄎٮູૄ܄-1exp(−ΔE/T)>0đೂݔ ჭđልࠊཱྀࠊ؇ֆູ໊ t·h. ေ۲Ӛਇࡗᄎൻmin[1đexp(−ΔE/T)]random(0đ1)đ ਫ਼ཌ֥Ӊ؇ҵ҂նႿ8h֥ӚӱđӚӆࠣ۲ࠊᅜ֥ࠧਫ਼ཌטᆜࢤ൳ݦඔᄝ0֞1ᆭࡗđᄵS=S'đቕѓ(XđY)ႮCეݦඔ९ᇏ֥random () ݦඔᄝ00iiڎᄵЌھᆴĠ [0đ100]×[0đ100]֥თଽෛࠏӁളđ۲ࠊᅜ֥ࠊ(7) ໑؇༯ࢆđT=σTđσնູႿ0ཬႿ1֥ᄎਈGᄝ(50đ100)ଽෛࠏӁളđֆູ໊ؕđཌྷܱඔiҕඔđӫູ໑؇־ࡨੱđσᄀնၩሢෆ෬ݖӱᄀऌі1đఃᇏб২ູ1:10. ༀٳљູğ1→8đ ત. ၂Ϯ౼σ= 9đT<minTᄵෘمᇔ2→5đ4→6đ7→6đ8→3đ൫ಒקژކჿඏ֥ቋႪі1 Ӛӆa۲ࠊᅜ֥ቕѓ(X, Y)a۲ࠊᅜ֥ༀਈGaཱྀࠊ؇Vࠣࠊᅜ֥ൈࡗԳ iiiiӚӆ 0 1 2 3 4 5 6 7 8 ቕѓ 42, 34 11, 38 68, 77 33, 58 23, 8 62, 61 4, 12 8, 9 17, 56 ༀਈ/t 0 55 65 0 52 0 0 56 90 -1ཱྀࠊ؇/(t·h) Ē 45 50 50 62 53 61 60 62 ൈࡗ/h 0, 100 3, 10 0, 11 12, 25 10, 20 10, 20 5, 30 6, 23 5, 15
506 ୡѯն࿐࿐Бč۽ϱĎ 2007 ྛӚਫ਼ཌ. නམ൞҂ࣇေӱቋ؋đطေᄝఞ֥֒ൈࡗ֞ղࣜݖٟᆇॖᆩປӮᆃ5۱ༀᇀഒླေ3ਇᆷקֹׄ. ቋުႨڿࣉ֥ଆࠅෘمؓھଆӚđӚਇ1đ2đ3֥ྛӚਫ਼ཌٳљູğ0→1→8→ ࣉྛࢳđՖٟᆇൌဒॖၛुԛھෘمऎႵࢠॹ֥3→00→7→6→4→6→0đ0→2→5→0. ൬৻؇đᄝ؋ൈࡗଽିࠆ֤ࢠۚᇉਈ֥ಆअቋႪՖ1ॖुԛھຩࣜݖ؟Ցםսղ֞໗קđࢳ. ఒြࠢಕ๙ݖھٚمࣉྛӚਇט؇ॖၛॹॖड़ק1ᇏିਈݦඔᆴ֥ቋ֮ׄ൞ಆअડၩࢳ. ႵֹིࣉྛༀஊෂđՖطࢆ֮ఒြ֥ᄎႏӮЧđิࣩۚᆚ৯đၹՎЧෘمऎႵ၂ק֥ൌ࠽ၩၬ. ҕॉ໓ངğ [1] K C Tan, Y H Chew, L H Lee. A hybrid multi-objective evolutionary algorithm for solving vehicle routing prob- lem with time windows[J]. Computational Optimization and Applications, 2006, 34(1):115-151. [2] ੍ቑ, ൎᇑ॓. ႵཋӚਇט؇໙ี֥ଆބڿࣉ၌1 ିਈݦඔ൬৻ Ԯෘم[J]. ࠹ෘࠏႋႨ࣮, 2006(4):60-62. [3] Li Haibing, Lim Andrew. Evolutionary computing and optimization: local search with annealing-like restarts to 5 ࢲე solve the vehicle routing problem with time windows[C]. Proceedings of the 2002 ACM Symposium on Applied ؓགྷսఒြหљ൞ఒြࠢಕሧჷט؇ᇏ֥ᇗComputing, 2002. ေߌࢫ—–Ӛਇט؇໙ีࣉྛਔࡹଆđࡹଆ֥ࠎЧ Study on Vehicle Scheduling Problems of Non-full Loads for Small and Medium Enterprises Clusters 1212XIA Wen-ming, LI Guo-fu, ZHU Shuang-dong, YE Fei-fan( of Information Science and Technology, Ningbo University, Ningbo 315211, China; of Engineering, Ningbo University, Ningbo 315211, China ) Abstract: The algorithm presented in this paper establishes the model of minimal vehicle dispatch based on characteristics of the small and medium enterprises clusters. The model takes into consideration the minimum number of vehicle used, shortest distance, distance balance of each routing, time window constraints, etc. The analytical solution to the problem is given in the simulated annealing algorithm. The simulation results demonstrate the algorithm’s feasibility and satisfaction to real-time requirements. Key words: vehicle scheduling problem; non-full loads; time windows; number of vehicle used CLC number: TP183 Document code: A čᄳщࠠ ൎཬৡĎ
