数学建模55295

TeamControlNumberForofficeuseonlyForofficeuseonlyT155295F1T2F2T3ProblemChosenF3T4DF42017MathematicalContestinModeling(MCM/ICM)SummarySheetBreezingThroughSecurityCheckpoints:anIntelligentAirportwithSmartSchedulingSummaryInordertoimprovetheperformanceofairportsecuritycheckwhilepreservingthesamesecuritystandards,wemodelandrefinethisprocess.Werunextensivesimulationstoanalyzeperformanceofourmodel.Specifically,Fortask(a),wemodeltheairportsecurityprocesswithaqueueingnetwork.Wegettheparametersofthequeueingnetworkmodelbyfittingthedataintheprovideddatasheettodifferentdistributions.Wevalidateourmodelbysimulatingitwiththerealworldparametercombinationandcomparingitsoutputagainstdatacollectedfromairportpassengers.Weidentifythreebottlenecksinourmodel:lackofsufficientIDcheckpoints;exclusiveassignmentofscreeningcheckpointstopassengers;thepresenceofsuspiciouspassengers.Fortask(b),weproposethreeroutingalgorithmstooptimizethethroughputandvarianceoftheairport:greedyalgorithm,backpressurealgorithm,anddrift-plus-penaltyalgorithm.Thebestoneofthesealgorithmsachieveshighthroughputthatisclosetooptimalandrelativelylowvarianceinwaitingtime.Besides,ourproposedroutingal-gorithmmanagestoretainpassengersatisfactionwhilescheduling.Wealsoexploretheoptimalratioofdifferentkindsofcheckpointsandtesttherobustnessofmodifiedmod-els.Fortask(c),weanalyzetheimpactofdifferentculturesandtravelertypesandrunsimulationtoseethereactionofourmodel.Theculturesweanalyzearecollectivistcul-tures,individualistcultures.Thetypesoftravelersweanalyzearefamily-basedtravelersandtech-basedtravelers.Wealsoproposeaccommodationstothesespecialsituations.Fortask(d),weproposebothgloballyapplicableandlocallyapplicablepoliciestoairportsecuritymanagers.Ourpoliciesarebasedonouranalysisofdifferentculturesandtypesoftravelersaswellasouranalysisofourroutingalgorithms.Keywords:QueueingNetworks;RoutingAlgorithms;LyapunovOptimizationBreezingThroughSecurityCheckpoints:anIntelligentAirportwithSmartSchedulingTeam#55295SummaryInordertoimprovetheperformanceofairportsecuritycheckwhilepreservingthesamesecuritystandards,wemodelandrefinethisprocess.Werunextensivesimulationstoanalyzeperformanceofourmodel.Specifically,Fortask(a),wemodeltheairportsecurityprocesswithaqueueingnetwork.Wegettheparametersofthequeueingnetworkmodelbyfittingthedataintheprovideddatasheettodifferentdistributions.Wevalidateourmodelbysimulatingitwiththerealworldparametercombinationandcomparingitsoutputagainstdatacollectedfromairportpassengers.Weidentifythreebottlenecksinourmodel:lackofsufficientIDcheckpoints;exclusiveassignmentofscreeningcheckpointstopassengers;thepresenceofsuspiciouspassengers.Fortask(b),weproposethreeroutingalgorithmstooptimizethethroughputandvarianceoftheairport:greedyalgorithm,backpressurealgorithm,anddrift-plus-penaltyalgorithm.Thebestoneofthesealgorithmsachieveshighthroughputthatisclosetooptimalandrelativelylowvarianceinwaitingtime.Besides,ourproposedroutingal-gorithmmanagestoretainpassengersatisfactionwhilescheduling.Wealsoexploretheoptimalratioofdifferentkindsofcheckpointsandtesttherobustnessofmodifiedmod-els.Fortask(c),weanalyzetheimpactofdifferentculturesandtravelertypesandrunsimulationtoseethereactionofourmodel.Theculturesweanalyzearecollectivistcul-tures,individualistcultures.Thetypesoftravelersweanalyzearefamily-basedtravelersandtech-basedtravelers.Wealsoproposeaccommodationstothesespecialsituations.Fortask(d),weproposebothgloballyapplicableandlocallyapplicablepoliciestoairportsecuritymanagers.Ourpoliciesarebasedonouranalysisofdifferentculturesandtypesoftravelersaswellasouranalysisofourroutingalgorithms.Keywords:QueueingNetworks;RoutingAlgorithms;LyapunovOptimizationTeam#55295Contents1Introduction12BasicAnalysisoftheproblem12.1SingleQueueingNodes.............................12.2ParameterSettings................................22.3RateStability....................................32.4MeasuresofPerformance............................33Models43.1TandemM/G/cQueueingModel........................43.2QueueingNetworkModel............................54SimulationsandBottleneckDetection64.1SimulationSetup.................................64.2ValidatingOurModel..............................64.3SimulationEvaluation..............................75ModificationstotheProcess95.1GreedyRoutingBasedonBacklogs.......................95.2LyapunovDriftandBackpressure-BasedRouting..............105.2.1LyapunovOptimizationforQueueingNetworks...........105.2.2ThePerformanceofBackpressureRouting..............115.3Drift-Plus-PenaltyAlgorithm..........................135.3.1Drift-Plus-Penalty............................135.3.2ThePerformanceofDrift-Plus-PenaltyAlgorithm..........146SensitivityAnalysis146.1ModelingDifferentSituations..........................156.1.1CollectivistCulturalNorms.......................156.1.2IndividualistCulturalNorms......................156.1.3Family-basedTravelers.........................166.1.4Tech-basedTravelers...........................166.2ImpactofVariousSituations...........................16Team#552956.2.1CollectivistCulturalNorms.......................166.2.2IndividualistCulturalNorms......................176.2.3Family-basedTravelers.........................176.2.4Tech-basedTravelers...........................186.3AccommodationforSituations.........................187Conclusion197.1ConclusionoftheProblem............................197.2PolicyProposal..................................197.3StrengthandWeaknessofOurModel.....................197.4FutureApplicationofModels..........................20Team#55295Page1of201IntroductionSecurityhasbeenoffirstpriorityintransportationactivitiesthatinvolvepeoplesincethebeginningofthecentury.Aseriesoftime-consumingsecuritycheckprocessesarenecessarytoensurethesecurityofallpassengersaboard.Butpassengersarecomplain-ingaboutwaitingforsecuritycheckinextremelylongqueues.Itisquitechallengingtoimprovetheperformanceofairportsecuritychecksystemswhilepreservingthecurrentsecuritystandards.Inthispaper,wetrytomodelthissecuritycheckprocessandrefinethemodel.Ourmaincontributionsareasfollows:1.Wemodelthesecuritycheckprocesswithaqueueingnetwork.Wevalidateourmodelbysimulatingitwithreal-worldparametercombinationsandcomparingitsresultwithrealworlddata.WeidentifylackofsufficientIDcheckpoints,exclusiveassignmentofscreeningcheckpoints,presenceofsuspiciouspassengersasthreebottlenecksinthemodel.2.Weproposeandimplementthreeroutingalgorithmstooptimizeourbasicmod-el.Wesimulateourmodelwiththesealgorithmsandanalyzetheirperformance.Wefindthattheproposedbackpressurealgorithmachievesthroughputclosetooptimalandarelativelylowvarianceinwaitingtime.3.Weanalyzethesensitivityofourmodelbyconsideringtheimpactsofculturalnormsandpassengertypes.Weanalyzehowtheoutputofourmodelchangeswithrespecttodifferentnormsandpassengers,andproposeaccommodationstothesesituations.2BasicAnalysisoftheproblem2.1SingleQueueingNodesM/G/1Queue:WeadoptM/G/1queue[1](showninFigure1(a))inourmodel.•M:thearrivaltimesofthepassengersfollowaPoissondistribution•G:theservicetimesfollowanarbitraryprobabilitydistribution•1:thereisonlyonecheckpointavailableThearrivalsaredeterminedbyaPoissonprocesswithrateparameterµ.Jobservicetimehasanormaldistributionwithparameterµandσ.M/G/cQueue:WealsoadoptM/G/cqueue(showninFigure1(b))inourmodel,whichisageneralizationoftheM/G/1queue.crepresentsthenumberofcheckpoints.ThearrivaltimeofpassengersfollowsaPoissondistributionwithrateparameterλ.Jobservicetimefollowsanormaldistributionwithparameterµandσ.FIFO:Thequeueobeysafirst-come,first-serveddiscipline.Asinglecheckpointservescustomersoneatatimefromthefrontofthequeue.Whentheserviceiscomplete,Team#55295Page2of2012λλ3PoissonμPoissonarrivalsarrivalsExponentiallydistributedservicetimecExponentiallydistributedμservicetime(a)M/G/1(b)M/G/cFigure1:SingleQueueingNodesthecustomerleavesthequeueandthenumberofcustomersinthesystemreducesbyone.2.2ParameterSettingsBeforethesimulation,wesetbasicparametersoftheprobabilitydistributioninqueue-ingnodebasedonthedatainthedatasheet.WeusetheEstimatedDistributionfunctionofMathematicatodetermineprobabilitydistributionsandestimateparame-ters.Theaverageintervalforthearrivaltimeofregularandpre-checkpassengersfol-11lowsexponentialdistributionwithparameterλ1andλ2respectively.AndtheaveragerateofIDcheckserviceinzoneAandbaggageandbodyscreeningfollownormaldis-tributionwithparameters(µ1,σ1)and(µ2,σ2).Besides,weassumethetimeforregularpassengerstoremoveshoes,belts,lightjacketsandcomputersfromtheirbagsfollowsanormaldistributionwiththeparameters(µ4,σ4).Thustheaveragerateofbaggageandbodyscreeningforregularcustomerfollowsnormaldistributionwithparametersp22(µ3,σ3),whereµ3=µ2+µ4andσ3=σ2+σ4.Thenormaldistribution(µ3,σ3)andthenormaldistribution(µ4,σ4)areindependenttoeachother.ThespecificnumbersareinTable1.SymbolDefinitionvalueλ1Rateofregularpassengerarrivals4.63476λ2Rateofpre-checkpassengerarrivals6.52921(µ1,σ1)MeanandvarianceofIDcheckservicetime(0.186875,0.0612029)Meanandvarianceofscreeningservicetime(µ,σ)(0.507639,0.158551)22forpre-checkpassengersMeanandvarianceofscreeningservicetime(µ,σ)(2.507639,0.524536)33forregularpassengersTable1:TheParametersintheProblemsTimesTimesTimesTimes2.53.0662.02.5552.0441.51.5331.01.0220.50.5110.0Arrvingtimeinterval(min)0Arrvingtimeinterval(min)0Servicetime(min)0.0Servicetime(min)0.20.40.60.81.01.21.40.10.20.30.40.50.60.10.20.30.40.40.60.81.0Figure2:TheFittingResultsfromMathematicaThedistributionofservicetimeindifferentcheckpointssnotidenticalinreallife.InTeam#55295Page3of20ordertosimulatethedifferencesamongcheckpoints,wekeepthevarianceofnormaldistributionσkunchanged(k=1,2,3),anduniformlygenerateµkiofnormaldistribu-tionbetweenµk−σkandµk+σk.2.3RateStabilityDuetothecostofhiringemployeesandmaintainingthemachine,itisimpossibleforairporttosetupinfinitecheckpoints.Buttheairportmakessurethatthenumberofcheckpointssatisfiestheneedofpassengersandthenumberofpassengerswaitinginqueuewillnotgrowlargerovertime.LetQ(t)representthecontentsofasinglequeueingnodedefinedattimeslotst∈{0,1,2,...}.Q(t)isastochasticprocessaccordingtoprobabilitylaw.AqueueingnodeE{|Q(t)|}isratestable[2]iflimt→∞t=0.Ratestabilityensuresthequeuewillnotkeepgrowingovertime.a(t)representsthenumberofnewpassengersthatarriveonslottandb(t)representsthenumberofpassengersthecheckpointofthequeuecanserveonslott.Q(t)isratestableift−11Xlimsup[a(τ)−b(τ)]≤0.t→∞tτ=0Westipulatethatthenumberofcheckpointssatisfiesratestabilitywhiletheratioofcheckpointsbetweentheregularandpre-checkpassengersis3:1.ThereforewesetthenumberofcheckpointsasshowninTable2.zoneregularpre-checkIDcheck(zoneA)31Screening(zoneB)124Table2:TheNumberofServiceCounters2.4MeasuresofPerformanceThroughputandvarianceofaveragewaitingtimearetwomainmeasuresinthese-curitychecksystem.Theyaredefinedasfollows.Throughput:Theaveragenumberofpassengersthatpassthesecuritychecksysteminperunittime.Theperunittimehereissetasminute.Variance:SupposethewaitingtimeforregularpassengerisX1andthewaitingtimeforpre-checkpassengerisX2.Thepercentageofregularpassengersisp.Thevarianceofsystemisdefinedash2ih2ipE(X1−E(X1))+(1−p)E(X2−E(X2))Throughputmeasuresthesecuritychecksystem’scapacityonacollectivelevelwhilevarianceofwaitingtimemeasuresthefairnessonanindividuallevel.Team#55295Page4of203ModelsInthissection,wefirstpresentourmodelsindetails.Thefirstmodelisanoptimalbutunpracticalmodel,whichservesasacomparisonandaimstoprovidemodificationinsights.Thesecondonemodelsthequeueingnetworksofrealsecuritycheckingsysteminanairport.SymbolDefinitionλTherateparameterfortheexponentialdistributionµThemeanvalueparameterforthenormaldistributionσTherateparameter(squaredscale)forthenormaldistributionNThenumberofcheckpoints(c)Qa(t)ThebacklogsatqueueingnodeaforpassengercattimetThetransmittingratefromqueueingnodeaandqueueingnodebforµ(c)(t)abpassengercattimetL(t)TheLyanpnovfunctionattimet∆(t)TheLyanpnovdriftattimetVThecontrolparameterindrift-plus-penaltyalgorithmTable3:Notations3.1TandemM/G/cQueueingModelWefirstpresentanidealmodel,thetandemM/G/cmodel.Thismodelrealizesthemaximumthroughputbutisnotfeasibleinthereallife.Wewilllatercomparetheper-formanceofthisidealmodelwiththatofpracticalmodeltoevaluatethelatterandmakemodification.AsFigure3demonstrates,twoM/G/cqueuesareinatandemarray.ThefirstM/G/cqueueingnodedenotesthequeuesofIDcheck(ZoneA)andthereareNAcheckpoints.Similarly,thesecondM/G/cqueuedenotesthequeuesofbaggageandbodyscreen-ing(ZoneB)andthereareNBcheckpoints.Allcheckpointsareaccessibletobothreg-ularpassengersandpre-checkpassengersandtheonlydifferenceisthatthepre-checkpassengersarelikelytospendlesstimeatZoneB.IDCheckScreeningCheckλ1+λ2Poissonarrivalsμ2，σ2RegularPaxμ1，σ1μ3，σ3Pre-checkPaxNormaldistributedservicetimeFigure3:TandemM/G/cQueueingModelTeam#55295Page5of20TandemM/G/cqueueingmodelachievestheoptimalperformance.Allcheckpointsinthesamezonearebusyaslongastherearepassengerswaitinginqueue.Asforothermodels,acheckpointinonequeueingnodeisidlewhenpassengersarewaitingbeforethelineinanotherqueueingnodewhenazonehavemorethanonequeueingnode.Inthisway,tandemM/G/cmodelavoidsunnecessarywaitingtimeandattainthemaximumthroughput.However,tandemM/G/cmodelisunpractical.Foronething,thesinglequeueatev-eryzonecanbeextremelylong,whichishardtokeeporder.Foranother,accesstoeverycheckpointsforbothregularpassengersandpre-checkcustomersisfeasible.Particular-ly,screeningcheckpointsatzoneBhavedifferentcheckprocessforthesetwokindsofpassengersandit’simpossibletomixtwoprocesstogether.Therefore,tandemM/G/cmodelhasachievedmaximumthroughputbutisunprac-ticalinreallife.Thismodelisusedforcomparisonwithreal-lifemodelandprovideinsightsformodificationslater.3.2QueueingNetworkModelNowweintroducequeueingnetworkmodelwhichmodelsthesecuritycheckinreal-lifeairports.Queueingnetworksaresystemsinwhichanumberofqueuesareconnectedbycustomerrouting.SimilartoBCMPnetworks[3],ourqueueingnetworkmodelsareopennetworkswithverygeneralservicetimewhichfollowsthenormaldistribution.Thequeueingnetworkinreal-lifeairportisillustratedinFigure4.EveryqueueingnodeisanM/G/1queueing,forthereisonequeueforeverycheckpoint.Regularpas-sengersandpre-checkpassengersareseparatefromeachotherintheentireprocessofsecuritycheck.EveryqueueingnodeatzoneAdirectstoitscorrespondingqueueingnodesatzoneB.WeuseNA1andNA2todenotesthenumberofqueueingnodeinZoneAforregularpassengersandpre-checkpassengersrespectivelyanduseNB1andNB2todenotesthenumberofqueueingnodeinZoneBforregularpassengersandpre-checkpassengersrespectively.IDCheckScreeningCheckRegularPaxNA1NB1NA2NB2Pre-checkPaxFigure4:QueueingNetworkModelWewilllatermodifythetopologyofqueueingnetworksandapplydifferentroutingalgorithmsinqueueingnetworkstoachievelargerthroughputandsmallervarianceinthequeueingsystem.Team#55295Page6of204SimulationsandBottleneckDetection4.1SimulationSetupWerunmassivesimulationsonthequeueingnetworkmodelusingthedatafromtherealairportstovalidatethequeueingnetworkmodel.WesimulateboththetandemM/G/cnetworkandqueueingnetworksmodel.Thesimulationdataisgeneratedbasedontheprobabilitydistributionthatweobtainfromthedatasheet.Weset1000peopletopassthesystemineverysimulationandcollectstatisticsoflengthofthequeue,throughput,average,andvarianceofwaitingtime.Wealsoconsiderthepresenceofsuspiciouspassengersinthesecuritychecksystem1insimulation.Everysuspiciouspassengerappearswithaprobabilityof1000andthequeuewillbestuckfor10min.Wetesttherobustnessofqueueingsystembyaddingthepresenceofsuspiciouspassengers.4.2ValidatingOurModelTovalidateourmodel,wesimulatethemodelusingreal-worldparametercombina-tionsandcomparetheresultwithreal-worlddataprovidedbyairportpassengers.Specifically,wegetthenumberofdailypassengersof5biggestairportsintheUSfromtheirofficialwebsite[4][5][6][7][8].Wethenassumethatthearrivaltimeofpas-sengersfollowthePoissondistribution,andthereforewecancalculatethemeanarrivalrateofpassengersbydividingthetotalnumberofpassengerswiththetimelengthofaday.Besides,wegetthemeanwaitingtimeofpassengersfrom[9].OtherparametersaresetaftertheBangkokInternationalAirport,whichisshowninFigure5.Afterthat,wesimulateourmodelusingthecorrespondingarrivaltimedistribution.TheresultofoursimulationisshowninTable4.Figure5:BangkokInternationalAirportSecurityCheckSystemTeam#55295Page7of20averagewaitingdailyaveragewaitingtimecalculatedAirportarrivaltimefrombypassengerswebsites(minute)model(minute)ChicagoO’Hare2,000,00040−6079.0155International(ORD)Hartsfield-JacksonAtlanta260,00010−2042.9196International(ATL)LosAngeles205,00020−3032.5824International(LAX)JohnF.Kennedy156,00010−2016.8958International(JFK)SanFrancisco137,0001−109.4987International(SFO)Table4:ResultofValidationProcessWecanseefromTable4thattheresultingaveragewaitingtimeofourmodelisgen-erallyclosetotherealaveragewaitingtimeandthusourmodelisvalidinreallife.Thediscrepancybetweenthemodeloutputandthegroundtruthcanbeexplainedasfol-lows.Thenumberofcheckpointsofourmodelisfarlessthanthatoftherealcase.Sincetherealnumberofcheckpointsisunavailableonline,sowehavetoestimatethenum-berfromthefactthatthewaitingqueueofclientsisatleastratestable(asisdiscussedinsection2.3).Thatis,λ≤c·µ,whereλisthearrivaltime,µistheservicerate(estimatedfromExceldata),andcisthenumberofcheckpoints.cobtainedinthiswayisverylike-lytobefarsmallerthantherealnumberofcheckpointssincerealairportsdeploymorecheckpointstodealwithlargenumberofpassengers.Inall,theinaccurateestimationofnumberofcheckpointscontributestothediscrepancy.4.3SimulationEvaluationWenowevaluatethesimulationresultsgiventheparametersinourproblemandanalyzethebottleneckincurrentsecuritychecksystem.ThelackofsufficientIDcheckpointsforpre-checkpassengersisabottleneckinthequeueingnetworkmodel.Fromsection3.2,weseethatthelengthofIDcheckqueueforpre-checkpassengersgrowsquickly.However,thehighspeedofscreeningcheckpointforpre-checkpassengerskeepstheaveragewaitingtimeforpre-checkpassengersmuchsmallerthanthatofregularpassengers.Theimbalancedallocationofresourceincurscongestioninthesecuritysystemforpre-checkusers.DeployingonemoreIDcheckpointforpre-checkpassengers,whichisaneffectivebutluxurioussolutiontothelimitofIDcheckpoint,maynotmeettheapprovalduetotheheavycost.Theexclusiveassignmentofscreeningcheckpointstosomespecificgroupofpas-sengersisanotherbottleneck.Inthismodel,everyIDcheckpointonlyconnectsto4screeningcheckpointsfortheconvenienceofmanagingpassengersandthese4checkpointsareexclusivelyusedbypassengersfromthepreviousIDcheckpoint.Insection3.2,4screeningqueuesfromthesameIDcheckpointsforregularpassengerssufferfromlongqueuewhilescreeningqueuesfromotherIDcheckpointshavemuchshorterqueue.Team#55295Page8of20Sincetheservicetimeisnotidenticalforeverycheckpoint,apassengerfromfastIDcheckpointsispossibletobedirectedtoslowscreeningcheckpoints.Inconsequence,theremightbecertainscreeningcheckpointssufferingfromlongwaitingqueuesandtheseparationofscreeningcheckpointsforregularcustomersresultsinthewasteofresource.80PreIDQ0RegScreenQ02RegIDQ0RegScreenQ0360RegIDQ1RegScreenQ10RegIDQ2RegScreenQ1140PreScreenQ00RegScreenQ12PreScreenQ01RegScreenQ1320PreScreenQ02RegScreenQ20NumberofPAXinqueuePreScreenQ03RegScreenQ210RegScreenQ00RegScreenQ22050100150RegScreenQ01RegScreenQ23Time/minFigure6:TheNumberofPAXinQueueinQueueingNetworkModel802060queue15in40PAX10IDCheckQueueofrScreeningCheckQueue205NumbeMaxnumberofPAXinaqueue00050100150200020406080100120Time/minTime/minFigure7:TheLongestQueuewithFigure8:TheNumberofPAXinQueueinTandemSuspiciousPassengerM/G/cQueueingModelThepresenceofsuspiciouspassengersisthethirdbottleneckofthismodel.AfteranalyzingFigure6and7,theoutlineof6isthemaximumnumberofpassengersinaqueuewithoutthepresenceofsuspiciouspeople.ContrastingtheFigure7withtheoutlineofFigure6,thereisasuspiciouspassengershowingupat88minutes,whichresultsintherisingslopeincreasesfor15minutes,andthemaximumvalueislarger.At152minutes,anothersuspiciouspassengerarrives,whichresultsinthemaximumnumberofaqueuekeepingfor10minutesinsteadofdecreasingasinFigure6.Bycomparingthefigures,wefindthatthepresenceofsuspiciouspassengerswillinfluencethestabilityofthesystem.Intheairport,thesuspiciouspassengersaremorelikelytobedetectedwhenthesecuritycheckisstrictespeciallyinfestivalsoraftercertainevents.Sotheinfluenceofsuspiciouspassengersshouldbeconsideredasoneofthebottlenecksofqueueingnetworkmodel.Thesebott