基于遗传算法的机场机位分配策略

Parking-positionAssignmentProblemPAP[1][2](Constraint-SatisfactionProblemoverfinitedomainCSPoverfinitedomain)CSP,[3][4][5][6]1V,D,C,V={v1,v2,vn}D=D1,D2,DnviDiC=c1,c2,cmCSPVVviDivi|V||Di|C=c1,c2,cmc1c2(VIP)c3c4()c52M},0|{ZiMibBi∈=ZN},0|{ZiNivVi∈=NM,[e-mail](100083)CSPAirportParking-positionAssignmentsStrategyBasedonGATIANChen,XIONGGuixi(SchoolofComputerScience&Engineering,BeijingUniversityofAeronautics&Astronautics,Beijing100083)AbstractAfteranalyzingtheconstraintsandobjectiveofgeneralairportparking-positionassignmentproblem,amodelisputforward.Usingthismodel,thepaperproposesandimplementsastrategybasedongeneticalgorithmtosolvetheproblem.Inordertoacceleratetheconvergingspeedofthisalgorithm,anideaofsimulatedannealingisintroducedtorevisefitnessfunctionvalue.Experimentalresultsshowthatthealgorithmhasadvantagesincludingcomputationtime,realtimeperformanceandoptimizationoverotherexistedalgorithms.Thisstrategyhasbeensuccessfullyappliedinaninternationalairport.KeywordsCSP;Geneticalgorithm(GA);Airportparking-positionassignment313Vol.313ComputerEngineering20052··TP31910003428(2005)03018603A186February2005NDDDDD,,,,321L=iDiv)min()(111,2∑∑=+==MjNijiijSxf(1)∑==Mjijx11(2)jiTBTV∈}1|),{(),(=∈∀ijxjiji(3)}10,1,0,|),,{(),,(0,,,,++∈∀≥−+MjNkiEEkjikjiETSLjkjijkji(4)NiVBDDiii,,2,1,,L=⊂Φ≠(5),,,,1,2,,,1,2,,ijijkjSELiNjM−===LL(6)1,,1,,max(),{|1}NjijNjkjSELkiiix++=−=∈=(7),0,0,,min(),{|1}ijjjkjSELkiiix=−=∈=(8),,,,,001,1ijijijSLEiNjM≥≤≤+≤≤(9)xijij10TSAiiGiiEi,jijLi,jijTBiiTViiVBiiSi,jjEN+1,jE0,j(1)(1)~(5)(2)(3)xij=1ijij(4)ikjik(5)DDi(6)(7)(8)(7)(8)(9)33.1M=2N=102A1A2101,2,3,1013471256891021013470256891013.2,,N{|0iVvi=,}NiZ∈1−iiAA()M},0|{ZiMibBi∈=;~viDiD=D1,D2,D3,,DnvipopsizeDiDiDi-12Di+1Di+1i=N+1i!=N+1popsize=popsizeDii=1,B,VVBiDiDibjbj,23.3(1)0(2),187∑∑=+==MjNijiijSxf111,2)('(10)nafefitness10*'−=(11)aa3.4(1)(2):,,(3)3123(b)C^D^C^79D^8C^D^893(c)10D^0C^00D^2C^10D^2203(d)157802346910257910013468157910013691025780234468457910013682ParentAParentB105780234169ChildC^ChildD^ChildC.ChildD.457910012368578100123469ChildCChildD(a)(b)(c)(d)3(4)4443692590.70.001a=0.02n=35656CPU50200056CPU53695915~28s[1]IBM3083,5,2914~172s,[2]Pentium180,32MBRAM145231109~6402s228188MutexLock333//Mutex//ghDataLock=::CreateMutex(NULL,TRUE,DataMutex);HANDLEhFileMapping;//HANDLE//hFileMapping=::CreateFileMapping((HANDLE)0xFFFFFFFF,//FilehandleNULL,//SecurityattributesPAGE_READWRITE,//Protection0,//Size-high32bitssizeof(CReceivedDataStruct)*60,//Size-low32bitsDataBlock);//NameDWORDdwMapErr=GetLastError();gpDataBlock=(CReceivedDataStruct*)::MapViewOfFile(hFileMapping,//FilemappingobjectFILE_MAP_ALL_ACCESS,//Read/Write0,//Offset-high32bits0,//Offset-low32bits0);//Mapthewholething::ReleaseMutex(ghDataLock);//::WaitForSingleObject(ghDataLock,INFINITE);//…//::ReleaseMutex(ghDataLock);3.3MessagePassingSystemWindowsWM_WindowsMessageWM_TRIGGERWM_PARAMETERCWnd*pDESTNWnd=CWnd::FindWindow(NULL,DESTINATIONWndTITLE);if(pDESTNWnd){::PostMessage(pDESTNWnd-m_hWnd,WM_TRIGGER,NULL,NULL);}4UserFile.iniVPN1.().:,1998-032OppenheimAV.DigitalSignalProcessing.Prentice-hall,Inc,Engle-woodCliffs,NewJersey19833,..:,1986-014.MFC.:,2002-105.()().2003-011881AhmetB.ProceduresforProvidingRobustGateAssignmentsforArrivingAircrafts.EuropeanJournalofOperationalResearch,2000,120(1):63-802YanShangyao,HuoCheunming.OptimizationofMultipleObjectiveGateAssignments.TransportationResearchPartA:PolicyandPractice,2001,35(5):413-4323DozierG,BowenJ,HomaifarAA.SolvingConstraintSatisfactionProblemsUsingHybridEvolutionarySearch.EvolutionaryCompu-tation,IEEETransactionsonEvolutionaryComputation,1998,2(1):234EibenAE,RauePE,RuttkayZ.SolvingConstraintSatisfactionProblemsUsingGeneticAlgorithms.EvolutionaryComputation,IEEEWorldCongressonComputationalIntelligence,ProceedingsoftheFirstIEEEConference,1994,2:542-5475WangCJ,TsangEPK.SolvingConstraintSatisfactionProblemsUsingNeuralNetworks.ArtificialNeuralNetworks,SecondInterna-tionalConference,1991:295-2996CraenenBGW,EibenAE,MarchioriE.SolvingConstraintSatisfactionProblemswithHeuristic-basedEvolutionaryAlgorithms.EvolutionaryComputation,Proceedingsofthe2000Congress,2000,2:1571-1577228