obtainedwww.00271

TheReviewofSocionetworkStrategies(2019)13:209–225https://doi.
org/10.
1007/s12626-019-00037-1ARTICLEPartitioningVerticalEvacuationAreasinUmedaUndergroundMalltoMinimizetheEvacuationCompletionTimeRyoYamamoto1·AtsushiTakizawa2Received:23December2018/Accepted:9April2019/Publishedonline:23April2019SpringerJapanKK,partofSpringerNature2019AbstractWhenanundergroundmallisflooded,theshoppersshouldbeevacuatedtoabuild-ingconnectedtothemall.
However,thenumberofevacueesfromalarge-scaleundergroundmallwillexceedthecapacityoftheevacuationcenter.
Furthermore,theevacuationtimemaybedelayed.
Thispaperproposesamathematicalprogram-mingproblemthatminimizestheevacuationcompletiontimeonageneralplanargraphofapartitionedevacuationareawithaspecifiedsinkcapacity.
Wealsopro-poseaworkflowfortranslatingthegeneralgeometricspatialdatatographicaldata.
TheproblemisappliedtotherealspatialdataandevacuationsettingofUmedaundergroundmallinOsaka,Japan.
Theproblem'sperformanceiscomparedwiththatoftheconventionalproblemthatminimizesthetotalevacuationdistance,anditsaccuracyisconfirmedinamulti-agentsimulation.
Thevalidityoftheproposedmethodisalsodiscussed.
keywordsEvacuationplanning·Verticalevacuation·Umedaundergroundmall·Dynamictreenetwork·Mixedintegerprograming·Multi-agentsimulation1IntroductionInrecentyears,torrentialdownpoursandgigantictyphoonshavebecomemorefre-quentinmanycountries,includingJapan.
Accordingly,thenumberofsevereriverfloodingdisastersisalsoincreasing.
OnMarch11of2011,morethan14,000peo-plediedinthetsunamifollowingtheGreatEastJapanEarthquake.
BecauseJapanisamaritimecountryandsubjectedtofrequentearthquakes,hugetsunamishave*AtsushiTakizawatakizawa@osakacu.
ac.
jp1DepartmentofUrbanEngineering,GraduateSchoolofEngineering,OsakaCityUniversity,Sugimoto33138,Sumiyoshiku,Osaka5588585,Japan2DepartmentofHousingandEnvironmentalDesign,GraduateSchoolofHumanLifeScience,OsakaCityUniversity,Sugimoto33138,Sumiyoshiku,Osaka5588585,Japan210TheReviewofSocionetworkStrategies(2019)13:209–225repeatedthroughoutitshistory.
ManyJapanesecitiesarelocatednearlargeriv-ersandalongthecoast,wheretheflood-damageriskishigh.
Moreover,manyofthesecitiesareoutfittedwithundergroundmallsthatarealsopronetoflooding.
Asfloodedundergroundmallsaredifficulttoevacuate,varioussafetymeasuresarenecessitated.
Thepresentstudyproposesamathematicalmethodthatpartitionstheevacuationareaofanundergroundmallatthetimeofadisaster.
ThemethodisappliedtothehugeUmedaundergroundmallinthecenterofOsakaCity,Japan,withanestimatedfoottrafficofonemillionpeopleperday.
AccordingtothedamageestimatesofOsakaPrefecture[1],alargeearthquakeintheUmedadistrictcausedbytheNankaitroughwillbefollowedbyatsunamiapproximately1hand50minlater.
There-fore,anevacuationplanthatcanbeexecutedasquicklyaspossiblefromunder-groundmallsisrequired.
Floodingevacuationbehaviorscanbehorizontal(escapetotheexteriorofthefloodedarea)orvertical(escapetohigh-risebuildingswithinthefloodedarea).
Horizontalevacuationmovementisgenerallyeasierthanverticalevacuationmovement.
However,iftheevacueescannotbeaccommodatedneartheevacuationdestinationincertainseasonsandtimezones,theyarephysicallyandmentallyburdened.
Ontheotherhand,verticalevacuationtendstobecongestedbymanyevacuees,buttheevacuationsitesarealwaysavailableforacertainamountoftime.
DuringatsunamicausedbytheNankaitrough,alargenumberofevacu-eesandstrandedpersonsareexpectedintheUmedadistrict.
AstheneighboringdistrictslackthefacilitiestoadequatelyaccommodatenumerousevacueesfromtheUmedadistrict,horizontalevacuationaloneispoorevacuationplanning.
Asaspe-cialmemberoftheOsakaCityUndergroundSpaceFloodControlCouncilorgan-izedin2014,Takizawa[2]simulatedaverticalevacuationfromafloodedUmedaundergroundmallbyamulti-agentmodel.
Theagentswereevacuatedtothecon-nectedbuildings,andthecompletedevacuationtimeandcongestionhotspotsinthemallwereidentified[3].
Thissimulationwasbasedonthesimplebehavioralprinci-plebywhichevacueesmovefromtheiroriginallocation,takingtheshortestpathtotheevacuationstaircaseofthenearestconnectedbuilding.
Inthisevacuationplan,theevacueeswereconcentratedonacertainstaircase,theevacuationcompletiontimewasextended,andsomeevacueesgatheredbeyondthecapacityofthecon-nectedbuildings.
Tomitigatetheseproblems,thepresentstudypartitionstheevacuationareasothatevacueescanmoveverticallytotheconnectedbuildingfromtheundergroundmallintheshortestpossibletime.
Ourapproachadoptsthedynamictreenetwork(DTN)concept[4].
Theresultsareverifiedinamulti-agentsimulation(MAS)usingthedataandscenariooftheUmedaundergroundmall.
Theremainderofthispaperisstructuredasfollows.
Section2describestherelatedresearch,andSect.
3describesourmethodforestimatingtheevacuationcompletiontimeonaDTN.
Section4formulatestwomathematicalprogrammingproblems;onethatminimizesthetraveldistance,andonethatminimizestheevacu-ationcompletiontime.
Theproblemsaresolvedonaplanargraphimitatingagen-eralbuildingplane.
Section5createsthespatialdataoftheUmedaundergroundmall,onwhichweverifyourmethodandpreparetheoptimization.
Section6appliesthemathematicalprogrammingproblemsproposedinSect.
3tothedatacreatedin211TheReviewofSocionetworkStrategies(2019)13:209–225Sect.
5,andhencepartitionstheevacuationarea.
InSect.
7,basedonthesepartitionresults,anevacuationisperformedinaMAS,andtheaccuracyoftheevacuationcompletiontimeestimatedbythemathematicalprogramingisverified.
ThestudyconcludeswithSect.
8.
2RelatedStudiesMASevacuationstudieshavebeenreportedaroundtheworld.
Theauthorsof[5]basedtheirevacuationstudyonthesocialforcemodel.
Othermethodsseektomini-mizetheevacuationcompletiontime.
SinceFordandFulkersonproposedtheirquickestflowmodelbasedondynamicnetworks,minimizingtheevacuationtimehasbeenatopicoftheoreticalinterest,andmuchprogresshasbeenmade[6,7].
Theflowproblemcalleduniversalquickestflow[8],whichguaranteesthatthemaxi-mumpossiblenumberofevacueesleavewithinanarbitrarytimefromthestartoftheevacuationtoitscompletion,isespeciallysignificantfromanevacuationplan-ningviewpoint.
Takizawaetal.
[9]appliedtheuniversalquickestflowconcepttotheevacuationplanningofTokushimacityinJapan.
Inthegeneralquickestflowmodel,allevacueespassatthesamenodealongthesameevacuationroute,whichhinderstheevacuationguidance.
Aconfluentflowfromthesamenodetowardthesameevacuationsiteisdesired,butisdifficulttofind.
Inevacuationplanningbythequickestflowmodel,thedestinationsitesoftheevacueesateachnodeshouldbedeterminedbyaflowdecompositionontheobtainedtime-expandednetwork.
Thismodelisimpracticalinbuilding-scaleevacu-ationplanning,whichissupposedtoguidetheevacuationbypartitioningthespace.
Asanalternativetotheflowbasedmodel,thenetworkstructurecanbesimplifiedintotreesandgrids,andtheflowproblemcanbetreatedasapartitionproblem.
ThisapproachwasadoptedbyMamadaetal.
[4].
Inyetanotherapproach,Yangetal.
updatedtheroadnetworkpartitionforevacuationbyagreedyalgorithm,account-ingforthedistancetraveledwithinthecapacityconstraintsoftheevacuationsites.
TheirnetworkwasconstructedonanetworkVoronoidiagram[10].
Unlikethenet-workflowproblem,thepartitioningproblemissuitableforbuilding-scaleevacua-tionguidancebecauseitdirectlyobtainstheevacuationarea.
Thisresearchappliesthetheoreticalstudyoftheevacuationareapartitioningproblemtorealproblems.
Inthetheoreticalevacuationmodel,thespacemustbeexpressedbyagraph.
However,convertingthe(usually)geometricdataofthebuild-ingtographicaldataisadifficultandtime-consumingtask,andposesalargeprob-leminpracticaluse.
Inaddition,thegraphtopologyoftheactualbuildingspaceisaplanargrapheveninthesimplestcases,andtheedgecapacityislocation-dependent.
Therefore,theassumptionsoftheexistingefficientpartitioningalgorithms—thatthegraphtopologycanbereducedtoatreeorgridwithconstantedgecapacity—areinvalidinbuilding-scalecases.
Furthermore,whereasthemulti-agentmodelinputsthegeometricspatialdata,theflowmodelrequiresgraphicalinputdata,whichhaveahighdegreeofabstraction.
Nevertheless,thecomputationalaccuracyoftheflowmodelhashardlybeenverified.
Byapplyingtheactualspatialdatainarealscenario,212TheReviewofSocionetworkStrategies(2019)13:209–225weuniquelyverifytheaccuracyoftheflowmodelinaMAS,whichismorerepro-duciblethantheflowmodel.
3DynamicTreeNetworksandItsMinimumEvacuationCompletionTimeLetG=(V,E)beaundirectedtreewithavertexsetVandanedgesetE.
LetN=(T,l,p,c,)beadynamicnetworkwhoseunderlyinggraphisatreeT,wherelisafunctionthatassociateseachedgee∈Ewithapositiveintegrallength.
Similarly,pisafunctionthatassociateseachvertexv∈Vwithapositiveintegralsupplyp(v)rep-resentingthenumberofevacueesatvertexv.
cisapositiveintegralconstantrepresent-ingthecapacityofeachedge;thatis,theleastupperboundofthenumberofevacueesenteringanedgeperunittime.
Inthenextsection,wewillrelaxtheintegralandedgeuniformityconstraintofc.
Theconstantrepresentsthetimerequiredfortraversingtheunitdistanceofeachevacuee.
Werefertosuchtree-structurednetworksasDTNs.
Nowlet(v)denotethesetofverticesadjacenttovertexv∈V,andlet(s)denotetheminimumtimerequiredforallevacueesonT(s,v)toevacuatetosinklocationsonT.
Weassumethatanynumberofevacueescanstayatv,andifthesinkislocatedatv,allevacueesonvcaninstantlyfinishtheirevacuation.
Then,letT(p)bearootedtreemadefromTsuchthateachedgeisnaturallyorientedtowardtherootp,andforanyvertexv∈V,letT(p,v)bethesubtreeofT(p)rootedatv.
ThenwehaveHere,weneedonlyconsider(s,u)foru=argmax{(s,u)|u∈(s)}.
Supposethattherearen′verticesinT(s,u),namedv1(=u),v2,…,vnsuchthatds,v1≤ds,vi+1fori∈1,n1.
Hered(s,v)denotestheshortestdistancebetweensandv.
Kamiy-amaetal.
[11]observedthat(s,u)remainsconstantwhensandallviwithi∈1,narerelocatedtoaline(i.
e.
,apath)withthesameedgecapacities.
Inthiscase,ds,viwithi∈1,nisunchanged(seeFig.
1).
Fromtheaboveobservation,theevacuationcompletiontime(s,u)fromnodeuonT(s)tosinksisgivenbyIntheconvertedpath,theevacueesareassumedtohavemovedfromtheirdesig-natednodestowardtherootsduringunittime.
Atthistime,themaximumnumberofevacueesreachingsperunittimeisthecapacityrestrictioncoftheedge.
Trafficcongestionisagroupoftemporallycontinuousarrivalsofcevacuees,terminatedbyanarrivalwithfewerthancevacuees,asillustratedinFig.
2.
Eachgroupiscalledaclusterandtheleadingsetofevacueesineachclusteriscalledahead.
Letusconsidertheevacuationcompletiontimeofacluster.
Supposethattheevacueesintheheadofaclusterarelocatedatnodev∈V.
Letd(x,v)bethedis-tancebetweennodevandtheroots,V(s,v)Vbeasetofnodessuchthat(1)(s)=max{(s,u)|u∈(s)}.
(2)(s,u)=maxj∈[1,n]ds,vj+∑i∈[j,n]pvic1.
213TheReviewofSocionetworkStrategies(2019)13:209–225(a)(b)Fig.
1Exampleofarootedtreeanditsequivalentpath214TheReviewofSocionetworkStrategies(2019)13:209–225d(s,w)≥d(s,v)w∈V(s,v),and(s,v)betheevacuationcompletiontimeofaclus-terwhoseheadevacueesarrivefromv.
Then(s,v)isexpressedasAstheevacueesattheheadoftheclusterarenotcongested,theirevacuationcompletiontimeisdeterminedonlybythefirsttermofEq.
(3);thatis,theshort-estroutefromtheevacuationsitetotheinitialpositionoftheevacuees.
Thearrivaltimesoftheevacueesfollowingtheheadaredelayedbythecongestion.
Thedelaytimecanberepresentedbythewidthofthecluster(seeFig.
2),andisgivenbythesecondtermofEq.
(3).
Obviously,(s)isthemaximumoverall(s,v)andisgivenbyIfcluster3inFig.
2isthelastevacuatedcluster,thelastgroupofevacueesincluster3reachthesinkxatatimecorrespondingto(s).
4PartitioningProblemintheEvacuationAreaThissectionformulatesourmathematicalprogrammingproblemsforpartitioningtheevacuationareainrealisticproblemsettings.
First,thepassageofthebuildingspacemustbere-expressedasaconnectedgraph.
Asthetopologyofageneralbuild-ingspaceisnotatree,itmustberepresentedasaplanargraph,whichisincompat-iblewithDTNs.
LetG=(V,E)beaundirectedtreewithavertexsetVandanedgesetE,XVbethesetofevacuationsites(i.
e.
,sinks),p(v)bethenumberofevacu-eesatnodev∈V,VNbethesetofnodessuchthatp(v)≥1forallv∈VN,d(s,v)betheshortestdistancebetweens∈Sandv∈V,r(s)betheevacueecapacityofs∈S,andx(s,v)∈{0,1}beabinaryvariableequaling1and0ifv∈Visassignedtoandunassignedtos∈S,respectively.
Inthisproblem,thenodesarevariablesforassign-ingtheevacuationsites.
Theevacuationareapartitionisfinalizedbyconnectingtheedgesbetweentheadjacentnodes,whichareassignedtothesameevacuationsite.
(3)(s,v)=d(s,v)+∑w∈V(s,v)p(w)c1.
(4)(s)=maxv∈Vd(s,v)+∑w∈V(s,v)p(w)c1.
Fig.
2Examplesofevacueeclusters215TheReviewofSocionetworkStrategies(2019)13:209–2254.
1Problem1:PartitioningProblemMinimizingtheTotalEvacuationDistancewithSinkCapacityForcomparisonwiththeproposedmethoddescribedinthenextsection,wefirstfor-mulatetheproblemoffindingtheevacuationpartitionthatminimizesthetotalevacu-ationdistancewithinthesinkcapacity.
Thisproblemisformulatedasamixedintegerprogrammingproblem(Eq.
3),whereA(s,v)Vdenotesthesetofnodesadjacenttovwiththeshortestdistancefromvtos.
Undertheconstraintcondition(9),whenv∈Visassignedtos∈S,atleastoneofthenodesinA(s,v)isnecessarilyassignedtos.
Ifthenodestobeconnectedarelimitedtonodesontheshortestpath,thespatialdistributionoftheevacueesdependsonthecapacityconstraintofthesink,increasingthepossibilitythatapartitioncannotbecre-ated.
Therefore,werelaxtheshortestpathcondition,meaningthatthepathfromstovisnotnecessarilytheshortestpath.
Althoughtheobjectivefunctionassumestheshort-estpath(asmentionedabove),weallowadegreeoffreedomfortheconnectionrela-tionshipamongthenodes.
Onthelongestpath,thesumofthedistancealongtheactualpathfromstonodea∈A(s,v)adjacenttovandthedistancefromatovismaximized.
However,anextremelylongdetourfromthecurrentlocationispreventedundertheconstraintd(s,a)≤d(s,v),a∈A(s,v).
4.
2Problem2:PartitioningProblemMinimizingtheEvacuationCompletionTimewithSinkCapacityWenowexplainthemainformulationofthisstudy.
Problem2assignsnodestothesinksthatminimizetheevacuationcompletiontimedescribedinSect.
3.
Theproblemisformulatedasthefollowingmixedintegerprogrammingproblem:(5)P1∶minimize∑s∈S∑v∈Vx(s,v)d(s,v)p(v),(6)s.
t.
x(s,v)∈{0,1}v∈V,s∈S,(7)∑s∈Sx(s,v)=1v∈V,(8)r(s)≥∑v∈Vx(s,v)p(v)s∈S,(9)x(s,v)≤∑a∈A(s,v)x(s,a)v∈V,s∈S.
(10)P2∶minimizeMax,(11)s.
t.
x(s,v)∈{0,1}v∈V,s∈S,216TheReviewofSocionetworkStrategies(2019)13:209–225AsintheDTN,thewalkingspeedoftheevacuees1∕isassumeduniform.
Ontheotherhand,theedgecapacityvariesamongthesinks.
Thecapacityoftheedgesleadingtosinks∈Sisrepresentedasc(s).
Inpreliminarymulti-agentnumericalexperiments,auniformedgecapacityledtonon-negligibleerrorsintheevacuationcompletiontime,sovaryingtheedgecapacityisnecessary.
Ingeneral,thebottle-neckofaverticalevaluationistheentranceoftheevacuationstaircase.
Becausethewidthoftheentranceslightlyvariesfromthestaircasewidth,changingtheedgecapacityateachsinkisreasonable.
NotealsothatEq.
(16)correspondstoEq.
(3).
However,whereasthesecondtermontherighthandsideofEq.
(3)mustbeaninte-ger,thisconditionisrelaxedinEq.
(16)toeasetheoptimizationprocess.
Theotherconstraintsarethoseofproblem1.
Therefore,theactualevacuationcompletiontimemayexceedtheevacuationcompletiontimeestimatedbytheshortestrouteformula.
ThiseffectwillbeexperimentallyclarifiedinSect.
7.
5DataPreparationThissectionappliestheproblemsdescribedinSect.
4toverticalevacuationfromtheUmedaundergroundmall.
Thestudyspaceextendsapproximately1.
1kmintheeast,west,northandsouthdirections(seeFig.
3),andincludesthepassageoftheUmedaundergroundmall,theconnectingbuildings,andfivesubwaystations.
ThespatialdataoftheoriginalUmedaundergroundmallarethree-dimensionalcompu-tationalaideddesign(CAD)data,whichareincompatiblewiththemodel.
Accord-ingly,theywereconvertedtonetworkdatabythefollowingprocedure.
Tomeetthespecificationofthemulti-agentsimulator(SimTreadversion2.
5[12])usedinthelaterverification,theplanviewsofallfloorsmustbearrangedonthesameplane.
Therefore,wefirstpreparedtheCADdataoftheundergroundmall,theconnectingbuildingsusedforevacuation,andtheplatformsofthesubwaysta-tionswiththeirconnectingstairsonthesameplan,asshowninFig.
3.
Inthisfigure,(12)∑s∈Sx(s,v)=1v∈V,(13)r(s)≥∑v∈Vx(s,v)p(v)s∈S,(14)x(s,v)≤∑a∈A(s,v)x(s,a)v∈V,s∈S,(15)Max(s,v)≥0v∈V,s∈S,(16)(s,v)=x(s,v)d(s,v)+∑w∈V(s,v)p(w)c(s)1v∈V,s∈S.
217TheReviewofSocionetworkStrategies(2019)13:209–225Fig.
3OriginalCADdataoftheUmedaundergroundmallanddistributionofpedestriansat18:00Fig.
4RasterizeddataofthepassagepartsofFig.
3218TheReviewofSocionetworkStrategies(2019)13:209–225theevacueesaredisplayedassmalldots.
Thenumberofevacueeswillbedeter-minedlater.
Next,theCADdatawereimportedtoageographicinformationsystem(GIS).
ThepolygonscorrespondingtopassageswereextractedbytheGISandconvertedtobinarymonochromerasterdata,asillustratedinFig.
4.
Afterthinningtheblackpixelsoftheimage,thethinnedimagewasconvertedintovectordatabyaGISfunc-tion,andthenetworkdatacomposedofnodesandedgeswereconstructed.
Atthistime,somenodesofthesubwayplatformsandundergroundmall,whichwereorigi-nallyconnectedbutbecamedisconnectedafterarrangementonthesameplane,wereconnectedbyanedgewithzerolength.
Followingapreviousstudy[3],thewalkingspeed1∕oftheevacueewassetto1.
0ms1ontheplainand0.
45ms1onthestair-way.
Asthewalkingspeedneedstobeconstant,thisspeedchangewasimplementedbydividingthestaircasepartoftheedgeandmultiplyingitslengthby1.
0/0.
45timestheoriginallength.
Thisoperationmaintainsthesametraveltimeforwalkingacrosstheplaneandclimbingthestairs.
Next,wesettheevacuationsiteasthesinknode.
InthepreviousMAS[3],thesinkswereregardedaspartofthesafefloor(almostsecondorthirdfloor)onthestairsoftheconnectedbuildings,butinthisstudy,thesinksweretheentrancesoftheevacuationstaircasestosimplifythesimulation.
Therefore,thelengthoftheedgejustbeforetheevacuationstaircasewaschangedfromtheoriginallengthoftheevacuationstaircasetothesumofthelengthsextendedbythepreviouslymentionedmethod.
Fifteenconnectedbuildingsareavailableforevacuation,andseveralevac-uationstairsmayresideinonebuilding.
Theoptimizationproblemmustconsidertheevacuationstairsasseparateentities.
However,whentheevacuationstaircaseisbehindthebuilding,itsuseisprohibitedbytherestrictionoftheareapartitioning.
Fourofthe15buildingsinthedatafacethissituation.
Ineachofthesebuildings,theevacuationstaircasewasconnectedtothesupersinkwithanedgelengthofzero,whichwassetasthedestinationnode(seeFig.
5).
Thefinalnumberofsinkswas19.
Next,thelongedgesweredividedintoappropriatelengthswithapproximatelyequalintervals.
Wecreatedthreegraphswithedgesdividedinto10-,20-or30-mintervals,andoptimizedeachgraph.
Asallfloorswereexpressedonthesameplane,weconnectedthenodesoftheplatformandticketgateofthesubwaystationsbyFig.
5Addingasupersinktomultipleevacuationstaircases219TheReviewofSocionetworkStrategies(2019)13:209–225zerolengthedgesinthegraphconstruction.
Table1liststhesizesofthethreegraphsusedintheoptimization.
Thegraphdividedinto30-medgesisillustratedinFig.
6.
Followingthepreviousresearch[2],weassumedthedistributionofpedestrians(evacuees)at18:00onweekdays,whenthenumberofusersintheundergroundshop-pingmallishighest.
Thespatialdistributionsofthepeopleintheundergroundmallandthestationpremiseswereestimatedfromtheresultofasectionalpedestrian-trafficvol-umesurveyconductedinaround2014.
Accordingly,14,782evacueeswereplacedinthetargetspace(representedbysmallreddotsinFig.
3).
Toapplythenetworkmodel,theevacueesdistributedingeometricspacewereallocatedtothenearestnodes.
Forthatpurpose,wecreatedaVoronoidiagramonthegeometricspace,inwhicheachnodewasageneratingpointandthewallswererepresentedasobstacles(seeFig.
7).
TheevacueesineachVoronoiregionwereconsideredastheevacueesatthegeneratingpointinthatregion(Table2).
Table1SizesofthethreegraphsusedintheoptimizationEdgelengthdivision(m)Num.
ofedgesNum.
ofnodes104522351920382128183036772674Fig.
6GraphrepresentationofthepassagesintheUmedaundergroundmall.
Eachedgeis30mlong220TheReviewofSocionetworkStrategies(2019)13:209–225Equation(16)ofproblem2requiresaconstantedgecapacityc(s)oftheedgelead-ingtosinks.
However,giventhevariablewidthofthepassagesintheundergroundmall,theappropriateedgecapacityisnotself-evident.
Ingeneral,theedgecapacityisaneffectiveconstraintwhentheevacuationsitesarefloodedwithevacuees.
Therefore,theevacuationMASwasperformedintheoriginalgeometricspacewith600sofcon-tinuouscongestionateachevacuationsites∈S.
Theedgecapacityc(s)wascalculatedasfollows:6OptimizationandResultsUsingthedataoftheUmedaundergroundmall,problems1and2weresolvedbythemathematicalprogrammingsolverGurobiOptimizer7.
5.
1.
Bothproblemsaremixedintegerprogrammingproblems,whicharesolvedbythebranchandbound(17)c(s)=Totalnumberofevacueestosin600s600s.
Fig.
7Voronoidiagramofthegeometricspacewithobstacles(walls).
EachnodeisageneratingpointTable2EdgeandsinkcapacityofeachconnectedbuildingBuildingc(s)r(s)Buildingc(s)r(s)A1.
53109J-11.
076708B1.
4159J-21.
08C1.
33122K-11.
222115D1.
18707K-21.
23E1.
26797L-11.
322477F1.
22406L-21.
07G1.
38549M1.
06130H1.
38145N1.
33860I1.
833859O-11.
322537O-21.
32221TheReviewofSocionetworkStrategies(2019)13:209–225method.
ToensurethebestsolutionbyGurobiOptimizer,wefirstcreatedanLPfileoftheproblemdescription.
TheoptimizationresultofeachproblemwasvisualizedbytheGISinthefollowingcomputationalenvironment:aWindows10Professional64bitOS,anIntelCorei7-4790KCPU,and16GBmemory.
Weoptimizedproblems1and2onthreegraphswithdifferentedgelengths,asdescribedinSect.
4.
Inproblem1,whichoptimizesthetotalevacuationdistance,theevacuationcompletiontimewasestimatedbyEq.
(16).
Theoptimizationresultsofbothproblems,includingtheevacuationcompletiontimeineachgraphsetting,aresummarizedinTable3.
Inproblem1,theoptimizationonallgraphswascompletedTable3OptimizationresultsofeachproblemProblemEdgelength(m)ComputationaltimeDualitygap(%)EvacuationcompletiontimebyEq.
(16)(m:s)Problem11021s038:152011s038:223014s038:21Problem2105days19.
727:24205days17.
425:51305days11.
625:44Table4Numberofevacueesandcapacityratioineachbuilding,evaluatedonthegraphwith30-medgesBuildingProblem1Problem2Num.
ofevacueesCapacityratioNum.
ofevacueesCapacityratioA290.
266290.
266B500.
847500.
847C720.
5901110.
910D470.
066470.
066E7971.
0007971.
000F1280.
3152990.
736G00.
00000.
000H690.
476690.
476I38591.
00024730.
641J-16880.
32914730.
449J-21520–1540–K-113750.
7629471.
000K-2237–1168–L-122921.
00018150.
947L-2185–530–M370.
285370.
285N8601.
0008601.
000O-121851.
00015761.
000O-2352–961–222TheReviewofSocionetworkStrategies(2019)13:209–225within30s.
Ontheotherhand,theoptimizationresultsofproblem2hadnotcon-vergedaftertheallocatedtimelimitofthesimulation(5days),soweacceptedtheresultsattheendofday5.
Aslengtheningtheedgesreducesthesearchspace,thedualitygapshrinksunderthecurrentcondition,reaching11.
6%ontheoptimizedgraphwithanedgelengthof30m.
Hereafter,wecomparetheevacuationcompletiontimesofbothproblemsonthegraphdividedinto30-medges.
Theevacuationwascompletedafter38and26mininproblems1and2,respectively,indicatingthatproblem2shortenedtheevacua-tiontimeby12min.
Table4summarizesthenumberofevacueesandthecapacityratioonthegraphwith30-medges.
Inproblem1,nearly4000evacueeswerecon-centratedinBuildingI,butproblem2reducedthenumberofevacueesinBuildingIbymorethan1000.
Figure8illustratesthepartitionsoftheverticalevacuationareainproblems1and2.
Thepartitionswereverydifferentinthetwoproblems.
Forexample,intheresultofproblem2,thepassageinthecentralpartoftheundergroundmallwasdividedintodifferentevacuationareas(coloredblueandgreeninFig.
8).
7VerificationoftheEvacuationCompletionTimeinaMultiagentSimulationWhenestimatingtheevacuationcompletiontimebyEq.
(16),weconstructedthegraphdatabysimplifyingtheoriginalgeometricspatialdata,andassumedacon-stantedgecapacityateachevacuationsite.
Therefore,theevacuationcompletiontimeestimatedbythisapproachmustbeverifiedbyanalternativeapproach.
Thissectionpresentstheevacuationresultsofamulti-agentsimulator(SimTread;seeSect.
5)intheobtainedareapartitions.
SimTreadispopularlyusedforsimulat-ingactualbuildingevacuations,especiallyinJapan.
Theevacueeswereplacedasdescribedintheoptimizations,andtheirwalkingspeedwasalsounchanged.
Theevacueesmovedtotheirnearesttargetpoints(whichcanbeuser-selected)inthedefaultsettingofSimTread.
Theevacuationdestinationsoftheevacueeswereindi-viduallysetaccordingtothepartitionedevacuationareasinFig.
8.
Eachevacueeclimbedthestairsofitsassignedbuildinguptotheevacuationfloor.
Whentheevac-uationfloorwasreached,theevacuationwascompleted.
Table5summarizestheevacuationcompletiontimesineachbuildingonthegraphwith30-medges.
TheestimatesofEq.
(16)arecomparedwiththoseoftheMASforbothproblems.
Thetwosetsofresultsdifferby30sorless.
ThisresultconfirmsthesmalldifferencebetweentheestimationresultsofEq.
(16)andtheMASresult,therebyvalidatingtheestimationformulaonthegraph.
8ConcludingRemarksWeproposedamathematicalprogramingproblem(problem2)thatminimizestheevacuationcompletiontimeonageneralplanargraphwithpartitionedevacuationareasandasinkcapacity.
Wealsoproposedaworkflowfortranslatingthegeneral223TheReviewofSocionetworkStrategies(2019)13:209–225Fig.
8VerticalevacuationareapartitioningintheUmedaundergroundmall,evaluatedonthegraphwith30-medges(colorfigureonline)224TheReviewofSocionetworkStrategies(2019)13:209–225geometricspatialdatatographicaldata.
TheproposedproblemwasappliedtotherealspatialdataandevacuationsettingoftheUmedaundergroundmallinOsaka,Japan.
Theperformanceoftheproblemwascomparedwiththeresultofproblem1,whichminimizesthetotalevacuationdistance.
TheevacuationcompletiontimesoftheevacueestomultipleconnectedbuildingsweresimilartothoseofaMAS,con-firmingthevalidityoftheproposedformulation.
Theevacuationcompletiontimeintheproposedformulation(~25min)wasatleast12minshorterthaninproblem1.
However,thelongoptimizationtimeoftheproposedformulationmustberesolvedinlaterwork.
Inthefuture,sensorsandactuatorswillbeinstalledinbuildingsandstreets.
Undoubtedly,ourlivingspaceswillbecomesmarter.
Promptevacuationguidancecanbeconsideredasaleadingandimportantservice.
Accompaniedbyafastsolu-tionalgorithm,theproposedproblemmightprovideabasictechnologyforrealizingsuchservices.
AcknowledgementsThisstudyispartiallysupportedbyGrant-in-AidforScientificResearch(A)andJSTCRESTinnovativealgorithmfoundationforbigdata.
Table5ComparisonofevacuationcompletiontimesestimatedbyEq.
(6)andcomputedbytheMASineachproblemAllresultswerecalculatedonthegraphwith30-medges(minute:second)BuildingProblem1Problem2Equation(16)MASEquation(16)MASA02:5802:4502:5802:44B04:3504:1704:3504:17C04:5104:2105:0104:52D03:3003:1503:3003:17E13:0513:1013:0513:03F05:1405:1007:5907:36G––––H03:1403:0203:1402:60I38:2138:1625:4425:45J-113:3013:1925:4425:36J-225:2525:5025:4325:55K-121:5221:4516:0415:55K-205:1805:1317:5517:52L-131:4431:3225:4325:37L-205:3505:2310:5810:47M03:5203:2703:5203:26N14:1714:0215:2815:03O-129:5829:3722:1922:15O-206:3606:2014:1714:08225TheReviewofSocionetworkStrategies(2019)13:209–225References1.
OsakaPrefecture(2013).
Aboutthetsunamiinundationassumption(commentary).
http://www.
pref.
osaka.
lg.
jp/attach/31241/00271160/95kaisetu.
pdf.
Accessed1Dec2018.
2.
OsakaCityUndergroundSpaceInfiltrationCouncil(2016).
UndergroundspacefloodcontrolplanofOsakastationarea,ver.
1(reference,latterhalf).
http://www.
city.
osaka.
lg.
jp/kikikanrishitsu/cmsfiles/contents/0000259/259323/osakaekitiku-shinsuitaisakukeikaku3.
pdf.
Accessed1Dec2018.
3.
Takizawa,A.
,Takagi,N.
,&Taniguchi,Y.
(2015).
VerticalevaluationsimulationinUmedaunder-groundmallincaseofflooding.
AnnualJournalofUnbanDisasterReductionResearch,2,35–38.
4.
Mamada,S.
,Uno,T.
,Makino,K.
,&Fujishige,S.
(2005).
Atreepartitioningproblemarisingfromanevacuationproblemintreedynamicnetworks.
JournaloftheOperationsResearchSocietyofJapan,48(3),196–206.
5.
Helbing,D.
,Farkas,I.
,Molnar,P.
,&Vicsek,T.
(2001).
Simulatingofpedestriancrowdsinnormalandevacuationsituations.
InM.
Schreckenberg&S.
D.
Sharma(Eds.
),Pedestrianandevacuationdynamics(pp.
21–58).
Berlin:Springer.
6.
Ford,L.
R.
,&Fulkerson,D.
R.
(1958).
Constructingmaximaldynamicflowsfromstaticflows.
OperationsResearch,6,419–433.
7.
Ford,L.
R.
,&Fulkerson,D.
R.
(1962).
Flowsinnetworks.
Princeton:PrincetonUniversityPress.
8.
Minieka,E.
(1973).
Maximal,lexicographic,anddynamicnetworkflows.
OperationsResearch,21,517–527.
9.
Takizawa,A.
,Inoue,M.
,&Katoh,N.
(2012).
Anemergencyevacuationplanningmodelusingtheuniversallyquickestflow.
TheReviewofSocionetworkStrategies,6,15–28.
10.
Yang,K.
S.
,Shekhar,A.
H.
,Oliver,D.
,&Shekhar,S.
(2013).
Capacity-constrainednetwork-Voro-noidiagram:Asummaryofresults.
InAdvancesinSpatialandTemporalDatabases—13thInterna-tionalSymposium,pp.
56–73.
11.
Kamiyama,N.
,Katoh,N.
,&Takizawa,A.
(2006).
Anefficientalgorithmforevacuationproblemindynamicnetworkflowswithuniformarccapacity.
IEICETransactiononFundamentals,E89-D(8),2372–2379.
12.
Kimura,T.
,Sano,T.
,Hayashida,K.
,Takeichi,N.
,Minegishi,Y.
,Yoshida,Y.
,etal.
(2009).
Repre-sentationofcrowdinmulti-agentmodel—developmentofpedestriansimulationsystemSimtread.
JournalofArchitectureandPlanning(TransactionsofAIJ),74(636),371–377.
Publisher'sNoteSpringerNatureremainsneutralwithregardtojurisdictionalclaimsinpublishedmapsandinstitutionalaffiliations.