Robustoptimizationforroutingproblemsontrees
SabineBüttner1·SvenO.Krumke1
Received:13December2014/Accepted:14May2015/Publishedonline:10June2015
?SociedaddeEstadísticaeInvestigaciónOperativa2015
AbstractTheprize-collectingtravellingsalesmanproblem(pc-tsp)isaknownvari-antoftheclassicaltravellingsalesmanproblem.Inthepc-tsp,wearegivenaweightedgraphG=(V,E)withedgeweights??:E→R+,aspecialvertexr∈V,penaltiesπ:V→R+andthegoalisto?ndaclosedtourKsuchthatr∈V(K)andsuchthatthecost??(K)+π(V\V(K)),whichisthesumoftheweightsoftheedgesinthetourandthecostoftheverticesnotspannedbyK,isminimized.Inthispaper,westudythepc-tspfromaviewpointofrobustoptimization.Inoursetting,anoperatormust?ndaclosedtourina(known)edge-weightedtreeT=(V,E)startingandendinginthedepotrwhilesomeoftheedgesmaybeblockedby“avalanches”de?ningthescenarioξ.Thecostf(K,ξ)ofatourKinscenarioξisthecostresultingfrom“shortcutting”K,i.e.fromrestrictingKtothenodeswhicharereachablefromrinscenarioξ,i.e.inthegraphT\ξ=(V,E\ξ).Intheabsoluterobustversionoftheproblemonesearchesforatourwhichminimizestheworst-casecostoverallscenarios,whileinthedevi-ationrobustcounterpart,theregret,thatis,thedeviationfromanoptimumsolutionforaparticularscenario,issoughttobeminimized.Weshowthatbothversionsoftheproblemcanbesolvedinpolynomialtimeontrees.
KeywordsRobustoptimization·Routingproblem·Dynamicprogramming·Uncertainty·Prizecollectingtravelingsalesmanproblem
MathematicsSubjectClassi?cationPrimary90C35(Programminginvolvinggraphs);Secondary90C39(DynamicProgramming)
B
1SabineBüttnerbuettner@mathematik.uni-kl.deUniversityofKaiserslautern,Kaiserslautern,Germany
123
Robustoptimizationforroutingproblemsontrees3391Introduction
ProblemswithinRobustoptimizationfeatureaninitiallackofpreciseinstancedata.Thepossiblespeci?cationsofalldatagivethescenariosξintheuncertaintysetU.Usually,theuncertaintysetitself,i.e.thepossiblescenariosareknownbutdifferproblem-speci?cally.Solutionsneedtoberobustinsomesenseandthetaskistosolvetherobustcounterpartofaproblem.
Thetravellingsalesmanproblem(tsp)isaclassicalproblemofcombinatorialoptimization(Lawleretal.1985;GareyandJohnson1979).OneisgivenanundirectedgraphG=(V,E)withedgeweights??:E→R+andthegoalisto?ndashortesttourvisitingeachvertexatleastonce.
Inthispaper,westudyarobustversionofthewell-knownprize-collectingtravellingsalesmanproblem(pc-tsp),awell-knownvariantofthetsp.Inthepc-tsp,oneisgivenanundirectedgraphG=(V,E)withedgeweights??:E→R+togetherwithaspecialvertexr∈V(the“depot”),andpenaltiesπ:V→R+.Thegoalisto?ndaclosedtourKsuchthatr∈V(K)andsuchthatthecost??(K)+π(V\V(K)),whichisthesumoftheedgeweightsinthetourandthecostoftheverticesnotvisitedbyK,isminimized.1Asthetsp,thepc-tspiswellknowntobeNP-hardtosolve(Balas1989).Thepc-tsphasalsobeenstudiedextensivelyintheliterature,seee.g.Bienstocketal.(1993),Archeretal.(2011),Awerbuchetal.(1995),Reinelt(1994).Intherobustversiontreerob-pctspofthepc-tspatouroperatormust?ndaclosedtourina(known)edge-weightedtreeT=(V,E)startingandendinginthedepotrwhilesomeoftheedgesmaybeblockedby“avalanches”.Givenaparameterk∈N,eachsubsetofatmostk-blockededgesde?nesapotentialscenarioξwherethenominalscenarioξnom=?correspondstothesituationwherealledgesareavailable.LetUk={ξ?E:|ξ|≤k}denotethesetofallallowedscenarios,alsocalledtheuncertaintyset.Thecostf(K,ξ)ofatourKinscenarioξ∈Ukisthecostresultingfrom“shortcutting”K,i.e.fromrestrictingKtothenodeswhicharereachablefromrinscenarioξ,i.e.inthegraphT\ξ=(V,E\ξ).Wedenotebyopt(T,ξ)theoptimum(aposteriori)tourintreeTforξ∈Uk.
Intheabsoluterobustversionofthetreerob-pctspwithuncertaintysetUkoneseekstosolve
(1)minmaxf(K,ξ)KtourinTξ∈Uk
andthedeviationrobustversionconsistsofsolving
min????maxf(K,ξ)?fopt(T,ξ),ξ.(2)KtourinTξ∈Uk
Themainresultofthispaperisthatbothproblemscanbesolvedoptimallyinpolynomialtimeontreesbydynamicprogramming.
1Here,weadopttheusualnotationthatforafunctionf:S→RandasubsetU?Swewritef(U):=??u∈Uf(u).
123
340S.Büttner,S.O.Krumke
1.1Relatedwork
PapadimitriouandYannakakis(1989)introducedtheproblemof?ndingashortestpathinagraphinwhichsomeedgesmaybediscoveredtobeblocked.Ablockageofanedgeisdiscoveredonlywhenoneofitsendpointsisreached.Subsequently,Bar-NoyandSchieber(1991)studiedthek-CanadianTravelerProblem,whichisthevariant,whereatmostkedgesmaybeblocked.Theyprovedthat?ndinganoptimumstrategywhichminimizestheworst-casecostisPSPACE-complete.Thisproblemisrelatedtotheconceptofrecoveryrobustness(Liebchenetal.2009)orrecoverytofeasibility(GoerigkandSch?bel2011),whereaprecomputedsolutionmayberepairedwhenmoreinformationaboutthescenarioisavailable.
Thereisawiderangeofexactspeci?cationsoftherobustcounterpartandtheprecisemeaningof“robust”solutionintheliterature(moredetailedoverviewsareofferedforexampleinBeyerandSendhoff2007;Ben-Taletal.2009;GoerigkandSch?bel2010;Bertsimasetal.2011;Gabrieletal.2014).Onepossibilityistheconsiderationofstrictorabsoluterobustness,whereasolutioniscalledstrictrobustifitisfeasibleforallscenariosandminimizestheworst-casecost(cf.Ben-TalandNemirovski1998).Theabsoluterequirementoffeasibilityinallpossiblescenariosisoftentoorestrictive(notethatintheproblemtreatedinthispaperfeasibilitywillberesolvedautomaticallybyshortcuttingatour,seedetailsbelow).OtherconceptsextendtherobustnessapproachinvariouswaysBen-Taletal.(2004),Ben-TalandNemirovski(2000),BertsimasandSim(2004),FischettiandMonaci(2009),GoerigkandSch?bel(2011),Liebchenetal.(2009),Sch?bel(2014),YuandYang(1998).
1.1.1Relationtoonlineoptimization
Anotherapproachtodealwithuncertaintyaboutblockededgesinroutingproblemsistouseonlineoptimizationandcompetitiveanalysis.Anonlinealgorithmiscalledc-competitiveifitscostonanyinstanceisatmostctimestheoptimumcost.Papadim-itriouandYannakakis(1989)showedthatitisPSPACE-completeto?ndanonlinealgorithmwithaboundedcompetitiveratio.Westphal(2008)gaveanalgorithmwhichachievesacompetitiveratioof2k+1forthecasewhenatmostkedgesmaybeblocked.Anonlineversionpc-tspcalledtheCanadianTourOperatorProblemwasstudiedinBüttner(2012,2014),BüttnerandKrumke(2012),whereupperandlowerboundsonthecompetitiveratioweregiven.
Incompetitiveanalysis,oneseekstominimizethevalue
minmaxf(K,ξ).f(opt(T,ξ),ξ)(3)KtourinTξ∈UTl
Equations(3)forcompetitivenessand(2)relatetherealizationcostf(K,ξ)ofsomesolutionKinascenarioξtothe(scenario-dependent)bestpossiblecostf(opt(T,ξ),ξ)andtakethemaximumregardingtheratioorthedifference,respec-tively.
Nevertheless,thefollowingexampleshowsthatsolutionsmeetingtheminimumratioorabsolutedifferencedonotcoincideingeneral.
123
Robustoptimizationforroutingproblemsontrees
341
Fig.1InstancewithdifferingbestcompetitiveanddeviationrobustsolutionTable1Realizationcostofshortcuttoursinvariousscenarios
ξnom
K?K1K2
11.60.6
ξ111
ξ111.61.6
Considerthenetworkwiththreenodes{r,v1,v2}onasimplepath(seeFig.1).Thenumbersnexttotheedgesandnodesinthe?gureindicatethelengthsandpenalties,respectively.
Therearethreescenarioswhichentailinfactinequivalentrealizations:eitherthe?rstedgeisblocked(denotedbyξ0),orthesecondedgeisblocked(scenarioξ1)ornoneoftheedgeswhichistheso-callednominalscenarioξnom.Thepossibletoursareeithernottouseanyedgeatall(K?),totravelonlythe?rstedgeandreturntorimmediately(K1),ortotravelthewholeline(K2).Table1givestherealizationcostofthe(shortcut)toursintherespectivescenarios.
CheckingandcomparingtherespectiverealizationcostandtheoptimumforallscenariosshowsthatK2isthetourwiththebestcompetitiveratioof1.6,whileK?solvesthedeviationrobustproblem(buthascompetitiveratio1/0.6=5/3>1.6).
2Solvingtheabsoluterobustproblem
We?rstnotebrie?ythatanoptimalsolutiontothepc-tspontrees,i.e.totree-pctsp,canbedeterminedeasilybydynamicprogramminginlineartime.ForanodevwedenotebyTvthesubtreeofTrootedatv,inparticularTr=T.Wecallavertexuachildofvertexv,ifvisthedirectpredecessorontheuniquepathfromtherootrtov.Leto(v)=f(opt(Tv,ξnom),ξnom))bede?nedastheminimumcostofanysolutioninthesubtreeTvwhenthedepotistherootvofthesubtree.IfvisaleafofT,theno(v)=0.Otherwise,letwi,i=1,...,p,bethechildrenofv.Then,wehavetherecursion:
??
o(v)=min{2??(v,wi)+o(wi),π(Twi)}.(4)
wichildofv
Thecorrectnessof(4)canbeseenasfollows:foreachchildnodewiofvweeither
traversetheedge(v,wi)andthenprocessTwioptimallybeforereturningbacktov,orweleaveoutthewholesubtreeTwi.Thetourresultingfromcomputingthevaluesin(4)bottom-upfromtheleavesgivesanoptimumsolutiontothenominalproblem,i.e.wecandetermineopt(Tv,ξnom)inlineartime.Sincefork=0theabsolutetreerob-pctspreducestothepc-tsp,wehave:
123
342S.Büttner,S.O.KrumkeObservation1Ifnoblockageisallowed(k=0)theoptimalpc-tsptourisalsotheoptimalsolutionfortheabsoluterobustcounterpart.Theoptimumsolutioncanbefoundinlineartime.
2.1Binarytrees
Wenowproceedtoinvestigatetheabsolutetreerob-pctspwithnontrivialuncer-taintysetsUk,k≥1.Ina?rststep,weassumeadditionallythatthetreeTisafullbinarytree,thus,eachinteriornodehasexactlytwochildren.Weshowlaterhowthisassumptioncanberemoved.
Theorem2ThetourK?,whichdoesnottravelanyedgeindependentlyofanyblock-age,isanoptimalsolutionfor(1)onabinarytreeifk≥2.
ProofFork≥2,thesetofpossiblescenariosUkincludesthescenarioξ0inwhichbothedgesincident??withtherootnoderareblocked.Thus,thecostforanytourin0scenarioξis??=v∈V\{r}π(v).Consequently,foranytourK??wehave
ξ∈Ukmaxf(K??,ξ)≥f(K??,ξ0)=??.
Ontheotherhand,thetourK?hascost??inanyscenario,andthus
KtourinTξ∈Ukminmaxf(K,ξ)≤maxf(K?,ξ)=??.ξ∈Uk
Thiscompletestheproof.????Wehaveseenthatinbinarytreesthecasesk=0andk≥2essentiallyleadtotrivialresults.Incasek=1,thesituationismoreinvolvedand,thus,moreinteresting.Letv∈VbeaninternalnodeofthetreeT.Thetwochildrenofvaredenotedbyw1andw2withattachedsubtreesabbreviatedbyT1:=Tw1andT2:=Tw2,andedgee1oflength??1connectingvandw1and??2withc(e2)=:??2betweenvandw2,respectively(cf.Fig.2).Furthermore,UlTisthesubsetofscenariosintreeTwhereatmostledgesfail.Inthesequel,wewriteopt(ξ)insteadofopt(Tv,ξ)ifweareTvforacertainsubtreeTv.Thus,opt(ξ)alwaysdenotesconsideringscenariosξ∈Ukanoptimumtourwithinthesubtreeforwhichξde?nesascenario.
Wedenotebya(v,l)theoptimumsolutionvalueof(1)inthesubtreeTvwithuncertaintysetUlTv,thatis,
a(v,l)=KtourinTvξ∈UTvkminmaxf(K,ξ).
Then,the??valueof(1)isa(r,k)andwehavealreadyseenthata(v,0)=o(v)anda(v,l)=u∈Tv\{v}π(u)forl≥2.Thus,theonlynontrivialpartistodeterminethevaluea(v,1).
Supposethatthesalesmaniscurrentlylocatedinnodev.Therearefourtypesoftourscombiningthe(independent)behaviorsconcerningedgese1ande2:weusethe123
Robustoptimizationforroutingproblemsontrees
Fig.2Denotationsinthe
dynamicprogramforaninternal
nodev
a(v,1):=KtourinTvξ∈UTv1min??maxf(K,ξ)
maxf(K,ξ),minmaxf(K,ξ),
??
(5)=minK00-tourinTvξ∈UTv1minK10-tourinTvξ∈UTv1K01-tourinTvξ∈UTv1minmaxf(K,ξ),K11-tourinTvξ∈UTv1minmaxf(K,ξ).
Weconsiderthefourtourtypesseparately.
2.1.100-tours
IfonlytoursareconsideredwhichenterneitherT1norT2,theresultingcostisπ(T1)+π(T2)-independentofthescenario.
2.1.210-tours/01-tours
IfatourdoesnotenterT2,thecostforthissubtreeisπ(T2)andagainnotdependingonthescenario.ForthecostofsubtreeT1,afurtherdistinctionfortheinnermaximumandthescenarioξ??isnecessary:eitheredgee1isunavailable,forbiddingthetourtoenterT1,ortheedgee1isavailableinwhichcasethetourentersT1byde?nitionandmightfaceablockededgefurtherbelow.Inthe?rstcase,wehavecostofπ(T1)fortreeT1,whileinthesecond,thebestatourcanachieveis:
forgoingtow1????????2??1+KtourinT1ξ∈UT11minmaxf(K,ξ)=2??1+a(w1,1).
Whetherthe?rstorthesecondvalueisvalidinthecaseofascenarioinwhiche1isnotblockeddependsonthescenariowithinT1.Thiscannotbein?uencedbythe
123
344S.Büttner,S.O.Krumkechosentourbutwhencomputinga(v,1),themaximumofbothneedstobetakenintoconsideration.
Hence,theminimumoverall10-toursisgivenby:
K10-tourinTvξ∈UTv1minmaxf(K,ξ)=max{π(T1),2??1+a(w1,1)}+π(T2)
Analogoustothederivationofthetermfortoursoftype10,toursoftype01contributewithπ(T1)+max{π(T2),2??2+a(w2,1)}.
2.1.311-tours
Fortoursintendingtovisitbothw1andw2,theinnermaximumoverthescenarioscanalsobere?nedfurther:theblockageinoneofthesubtrees(eitheredgeeiitselforsomeedgewithintreeTi:max{π(Ti),2??i+a(wi,1)})necessarilyenablesthetourintheothersubtreeTj,j=itobeundisturbedwithinTj.Sinceweareonlyconsidering11-tourswhichbyde?nitionenterTjifpossible,thisentailsacostof2??i+o(wi)forTj.Thus,thecorrespondingcontributionis:
K11-tourξ∈UTv1inTvminmaxf(K,ξ)=max{π(T1)+2??2+o(w2),2??1+a(w1,1)
+2??2+o(w2),2??1+o(w1)+π(T2),2??1
+o(w1)+2??2+a(w2,1)}.
2.1.4Combiningeverything
Combiningtheresultsforthefourtypesoftours,weobtainthefollowingrecursionforaninternalnodev:
a(v,1)=min{π(T1)+π(T2),max{π(T1),2??1+a(w1,1)}+π(T2),π(T1)
+max{π(T2),2??2+a(w2,1)},max{π(T1)+2??2+o(w2),2??1
+a(w1,1)+2??2+o(w2),2??1+o(w1)
+π(T2),2??1+o(w1)+2??2+a(w2,1)}}.
Sinceforaleafnodevwehavea(v,1)=0foralllthisenablesustocomputethevaluesa(v,1)bottom-upinlineartime,giventhevaluesowhichwehavealreadyshowntobecomputableinlineartime.Thus,forbinarytreesweobtainalineartimealgorithmfortheabsolutetreerob-pctsp.
2.2Extensiontonon-binarytrees
TohandleageneraltreeT,wetransformTintoafullbinarytreebyinsertingnewedgesofzerolengthandnewnodeswithzeropenalty:anodevwithp≥2childrenw1,...,wpisreplacedbyapathofp?2dummynodeseachwithzeropenalty.ThisprocedureisillustratedinFig.3.LetT??betheresultingbinarytree.
123
Robustoptimizationforroutingproblemsontrees345
Fig.3Transformationintoabinarytree,dashededgesandverticeshavecost0
AnytourinT??canbetransformedintoatourinTwiththesamecostandvice
TandUT??arenotequivalent:blockingoneoftheversa.However,thescenariosetsUkk
??newedgesinTmaycorrespondtoblockingmorethanoneedgeintheoriginaltree
T.Toovercomethisissue,weneedtoconsiderandsolveamoregeneralproblemon
T??(F)thescenariosinwhichatmostkT??:forasubsetFoftheedgeswedenotebyUk
edgesinT??areblockedbutnoneoftheedgesinFis.Thus,ifFdenotesthesetofall
T??(F)dummyedges,thereisaone-to-onecorrespondencebetweenthescenariosinUk
T.Letusde?ne:andUk
a??(v,k)=
KtourinTvξ∈UTv(F)
k
min
maxf(K,ξ).
Thecomputationofthevaluesa??(·,1)canbedonecompletelyanalogouslytothecomputationofa(·,1)withtheonlymodi?cationthatintheinnermaximasomeofthescenariosareeliminatedbecausetheywouldblockanunblockableedge.Forinstance,incaseof11-tourswheretheedgee1iscontainedinF,therecursionbecomes
K
11-tourξ∈UTv(F)
1inTv
minmax
f(K,ξ)=max{2??1+a??(w1,1)+2??2+o(w2),
2??1+o(w1)+π(T2),2??1+o(w1)+2??2+a??(w2,1)}.
However,forthegeneralizedproblemitisnolongertruethata??(v,l)=π(T1)+
π(T2)forl≥2,becausethescenarioξ0inwhichbothedgesincidentwiththerootnoderareblockedmightnotbecontainedinUlTv(F).Nevertheless,thedynamicprogramcanbeextendedtocomputea??(·,l)forl≥2inastraightforwardmanner.
/F,weobtainthevaluefor11-tours:Forinstance,taking(v,w1)∈F,(v,w2)∈a??(v,l)=
K11-tourinTvξ∈UTv(F)
l
min??
maxf(K,ξ)
e2blockede2notblocked
=max2??1+a??(w1,l?1)+π(T2),
l1+l2=l
??
max{2??1+a??(w1,l1)+2??2+a??(w2,l2)}.
123
346S.Büttner,S.O.KrumkeThetermsareexplainedasfollows:inscenarioswheree2isblocked,l?1blockededgesarepossiblewithinT1.However,ife2isnotblockedandthetourtypeindicatesthate1ande2areinfacttravelled,anydistributionofthelblockagesoverthetreesT1andT2,i.e.l1oftheminT1,andl2oftheminT2wherel1+l2=l,mightyieldthemaximumvalue.
Theaboveconsiderationsyieldadynamicprogrammingalgorithmtocompute??a(v,l)forallv∈Vandl=0,...,kintimeO(n??k2),wheren??=|V(T??)|.SincethesizeofT??islinearinthesizeofT,wegetthefollowingresult:
Theorem3Theabsolutetreerob-pctspcanbesolvedintimeO(nk2).Iftheunder-lyingtreeisbinary,therunningtimeimprovestoO(n).
3Solvingthedeviationrobustproblem
Onasimplepathwithnodeset{1,2,...,n},r=1,thedeviationtreerob-pctspcanbesolvedoptimallyinpolynomialtimebysimpleenumeration:thereareonlynpossibletoursandonlyndistinguishablescenarios(anysubsetofedgeswhichtheoreticallyde?nesasinglescenarioeachcanbeclassi?edbytheedgewhichhastheleastdistancetor.Atravellerstartinginrcanneverovercomethisunavailableedgeandhence,laterblockagesdonotfallintoaccount).Thus,forsolvingtheproblemoneneedstoevaluateonlyO(n2)values(solutioncostminusoptimumcostforthisscenario)whichcanbeaccomplishedeasilyinpolynomialtime.
Incaseoftrees,however,thesetofpossibletoursmaybeofexponentialsize.Thus,simpleenumerationdoesnotleadtoapolynomialtimealgorithm.Asintheprevioussection,we?rstgiveadynamicprogrammingalgorithmonbinarytreesandthenarguehowtoextendthisapproachtogeneraltrees.
3.1Binarytrees
Usingthenotationintroducedinthebeginning,weaimatdeterminingatoursolvingthedeviationtreerob-pctsponatree:
KtourinTξ∈UTkmin????maxf(K,ξ)?fopt(ξ),ξ.(6)
Here,wehaveomittedagainthereferencetothetreeTwithinopt(ξ)=opt(T,ξ)toavoidclutteringinnotation.
ForsomenodevinTwhereTvisthesubtreerootedinv,letagain
o(v):=o(Tv):=f(opt(ξnom),ξnom)
betheoptimumcostforthenominalproblem(withoutblockages)intreeTvwhenstartingandendingattherootnodevofthesubtreeTv.Moreover,let
s(v,l):=max
ξ∈UlTvKtourinTvminf(K,ξ)=maxf(opt(Tv,ξ),ξ).ξ∈UlTv
123
Robustoptimizationforroutingproblemsontrees347denotetheworst-casecostintreeTvwhichcanbeenforcedbyblockinguptolarbitraryedgesinTv,i.e.thecostwhichcannotbecircumventedbyanytourwhichstartsandendsinv.Finally,let:
c(v,l):=KtourinTvξ∈UTvlminmaxf(K,ξ)?f(opt(ξ),ξ).(7)
Thisistheobjectivevalueofthedeviationtreerob-pctspon(sub-)treeTvwithuptolblockededges,i.e.theworst-casedifferencebetweenthebestalgorithmandtheoptimumscenariocostforascenariowithuptolfailures.Thesolutionvalueof
(6)isthengivenbyc(r,k).??Weabbreviateπ(Tv)=w∈Tvπ(w)asusual.WealsousethenotationoftheprevioussectionillustratedinFig.2.
3.2Computings(v,l)
Thesubtreerootedinaleafvonlycontainstheleafitself,andnotraveldecisionshavetobetaken.Thecostiss(v,l)=0forallleavesvandalll.Wenowproceedtocomputethevaluess(v,l)foraninteriornodev.
Byde?nition,thevalues(v,l)representsthecostwhichanysolutioninTvsuffersatleastifuptoledgesmightbeimpassable.
Ifnoblockageisallowed,i.e.l=0,theguaranteedcostofanysolutioncannotbehigherthanthecostoftheoptimalhandlingofTv,andhence,
s(v,0)=o(v)forallv∈V.(8)
For2≤l≤k,thescenarioswhereeitheredgee1oredgee2isblocked,orbothornoneofthem(whiletheremainingblockagesareonedgeswithinT1andT2)arepossible.ThetourwhichdoesnotenterneitherT1norT2isavalidtourinallofthosecasesandhascostofπ(T1)+π(T2).Hence,theminimuminanyofthecasescanbeatmostthisamount,whilethiscostisindeedenforceableinthescenariowherebothedgesareblocked.Themaximumamongtheconsideredvaluesalsoequalsthetotalpenaltyofallchildrenofv:
s(v,l)=π(T1)+π(T2)where2≤l≤k.(9)
Asinthecaseoftheabsolutetreerob-pctsp,theleasttrivialpartistocomputes(v,1).Here,notonlytheminimumtourcostforscenarioswheree1failsandwheree2failshavetobeconsidered,butalsoablockagefurtherbelowinoneofthesubtreesmightdeterminethemaximumvalueweaimfor.
(i)Ifedgee1isunavailable,thenthecostinsubtreeT1is?xedtobeπ(T1).Atthesametime,asl=1,therecannotbeablockageinsubtreeT2,andthispartofthe
graphcanbetreatedoptimallyafterreachingw2.Thevalues,therefore,equalsπ(T1)+min{π(T2),2??2+o(w2)}inthiscase.
123
348S.Büttner,S.O.Krumke(ii)Analogoustoablockageofe1,afailureofe2?xesthecostwithrespecttoT2
andprovidesintotalavalueofmin{π(T1),2??1+o(w1)}+π(T2).(iii)Theminimumvalueofanysolution,ifsomeedgeinsideT1orinsideT2isblocked,isfoundamongthetermsrepresentingthetourwhichdoesnottraveltoanyofthechildnodes(a),discardingthesubtreeT1unenforcedly,buttravelalonge2and,asthecasemaybe,experiencingoneblockededgeinsideT2(b),fortravellingonlytov1accordingly(c)andtravellingbothe1ande2(d).NotethatinthelastcaseatleastoneofthesubtreescanbetreatedoptimallyasthereisatmostoneblockageinTvintotal.Thecostwhichcannotbeavoidedbyanysolution,hence,isinthiscase
(a)(b)(c)????????????????????minπ(T1)+π(T2),π(T1)+(2??2+s(w2,1)),(2??1+s(w1,1))+π(T2)
??
2??+2??2+max{o(T1)+s(w2,1),s(w1,1)+o(T2)}.??1??(d)
Combiningthepreviousresultswecansetuparecurrencerelationforl=1by
??s(v,1)=maxπ(T1)+min{π(T2),2??2+o(w2)},min{π(T1),2??1+o(w1)}??+π(T2),minπ(T1)+π(T2),π(T1)
+(2??2+s(w2,1)),(2??1+s(w1,1))+π(T2),2??1????(10)+2??2+max{o(w1)+s(w2,1),s(w1,1)+o(w2)}.
Togetherwith(8)and(9)thevaluess(v,·)canbecomputedbottom-up,providedthevalueso(v)arealreadyknown.TherunningtimeoftheresultingdynamicprogramisO(nk).
3.3Computingc(v,l)
Forthedynamicprogramtoobtainthevaluesc(v,l)forallvandalll=0,1,...,k,westartbyconsideringsomeinternalnodev∈V.WeagainrelyonthefamiliardenotationsdepictedinFig.2.At?rst,letl=0,i.e.weonlyconsiderscenarioswithoutanyblockage(orinotherwords:thenominalscenario).Weget:
c(v,0)=
=KtourinTvξ∈UTv0
KtourinTv
nomminmaxf(K,ξ)?f(opt(ξ),ξ)minf(K,ξnom)?f(opt(ξnom),ξnom)),ξnom)?o(Tv)=0.(11)=f(opt(ξ
So,let1≤l<k.Wedistinguishthedifferentcasesregardingthedifferenttoursandscenarios.Theouterminimumin(7)ischosenoutofthe(inner)maximumvalues123
第11 / 22页
Robustoptimizationforroutingproblemsontrees349attainedforthescenario-dependentcostoftheoptimumtours.Theedgese1ande2areeithertravelledorskipped,iftheyareavailableatall.
WeuseagainthedistinctionintothefourdifferenttourtypesintroducedinSect.2andrewrite:
c(v,l)=min{c00(v,l),c10(v,l),c01(v,l),c11(v,l)}
where
cij(v,l):=minmaxf(K,ξ)?f(opt(ξ),ξ)(12)(13)Kisij-tourξ∈UTvl
andconsiderthecasesindividually.
3.3.100-tours
IftoursarerestrictedtoneitherenterT1norT2,therelatedcostisindependentofthescenarioandgivenbyπ(T1)+π(T2).Hence,weget:
c00(v,l)=Kis00-tourξ∈UTvlminmaxf(K,ξ)?f(opt(ξ),ξ)
ξ∈UlTv=π(T1)+π(T2)?minf(opt(ξ),ξ)=π(T1)+π(T2)?o(v).(14)
Forthelastequalitynotethatξnom∈UlTv.
3.3.210-toursand01-tours
Anytouroftype10doesnotenterT2independentofthescenarioandhaspredeter-minedcostofπ(T2)forthispart.ForT1,wefurthermoredistinguishforthepossiblescenarios:eitherascenariohasablockageatedgee1oritindeedallowsforusingedgee1.Therefore,wecanfurtherre?nethecorrespondingterm:
c10(v,l)=
=Kis10-tourξ∈UTvlminmaxf(K,ξ)?f(opt(ξ),ξ)max{(a)
(b)maxwithe1blocked??Kis10-tourminξ∈UlTvf(K,ξ)?f(opt(ξ),ξ),??(15)f(K,ξ)?f(opt(ξ),ξ)}.ξ∈UlTvmaxwithe1open
Ifatourintendingtousee1facesablockage(term(a)),thenthecorrespondingvalueforT1isindependentfromtheactualintendedbehaviorwithinT1andequalsπ(T1).Atthesametime,ascenariowiththisblockageforbidsalsoanyothersolutiontoenterT1,inparticularthisholdsfortheoptimalopt(ξ).Analogouscomputationsasinthecaseofa00-tourshowthatthecompetingsolutiongivingthemaximumdifferenceinthispartisonewithbesttreatmentofthesubtreeT2.Suchasolution
123
350S.Büttner,S.O.KrumkeeitherentersthetreeT2yieldinganoptimalcosto(w2)plustravellingtwicelength??2orthetreemightbediscardedforanamountofπ(T2).Khasa?xedcostofπ(T2)withrespecttoT2,andwehave
ξ∈UlTvmaxwithe1blockedf(K,ξ)?f(opt(ξ),ξ)
=π(T1)?π(T1)+π(T2)?min{2??2+o(T2),π(T2)}????????forcedbyblockage
forKandopt(ξ)
=π(T2)?min{2??2+o(T2),π(T2)}.(16)
IfthetourincludesenteringT1ande1isactuallytraversable(term(b)),theoptimaltreatmentofT1canbeeithertoenterthesubtreeortodiscardit(dependingonthescenario).We,therefore,subdividefurtherforany10-tourKandget
max
withe1openξ∈UlTvf(K,ξ)?f(opt(ξ),ξ)????=maxTv???ξ∈Ulmaxf(K,ξ)?f(opt(ξ),ξ),
????
???withe1openandopt(ξ)entersT1ξ∈UlTvmaxf(K,ξ)?f(opt(ξ),ξ)(17)withe1openand
opt(ξ)doesnotenterT1
andexamineseparately.Itholds
maxf(K,ξ)?f(opt(ξ),ξ)
withe1open
andopt(ξ)entersT1ξ∈UlTv
????????2??1?2??1+performanceofKinT1foruptolblockages=
+π(T2)?min{2??2+o(T2),π(T2)}??maximumdifferencew.r.t.T2Kandopt(ξ)enterT1=maxf(K|T1,ξ)?f(opt(ξ),ξ)ξ∈UlT1
+π(T2)?min{2??2+o(T2),π(T2)}.(18)
Here,by“performanceofKinT1foruptolblockages”wedenotethemaximum(takenoverallscenariosξinT1)deviationoftherestrictionK|T1ofthetourKtoT1fromthecostf(opt(T1,ξ),ξ)ofanoptimumsolutionwithinT1.ThenotationK|T1emphasizesthatthisrestrictionisavalidtourinT1.Weusesimilarformulationsof123
Robustoptimizationforroutingproblemsontrees351restrictionsoftourstosubtreesinthefollowinginsteadofintroducingamnemonictoimprovereadability.
Toevaluatethelastterm,i.e.theperformanceofKinT1,theoverall(outer)minimumhastoberegarded.Wepostponethishereandreturntothesubjectfurtherbelow.
Forthemaximumoverthescenariosinwhichopt(ξ)doesnotusee1,thebehav-iorinT2isagainpredeterminedanddoesnotallowforanysmallervaluethanπ(T2)?min{2??2+o(T2),π(T2)}.Additionally,weareinthecasethatopt(ξ)inevitablyequalsπ(T1)ase1isnottravelled.Hence,themaximumisattainedinpreciselythescenariowhichcausesthemaximumexpenseinT1thatisenforceablebytheremainingblockages.Thisworst-casevalueisexactlywhatweintroducedass(v,l).TherecanbeuptolfailededgesinT1andweget:
maxf(K,ξ)?f(opt(ξ),ξ),
f(opt(ξ),ξ)ξ∈UlTv(19)withe1openandopt(ξ)doesnotenterT1maximumcostforKinT1=??????2??1+s(w1,l)???π(T1)+π(T2)?min{2??2+o(T2),π(T2)}.????maximumdifferencew.r.t.T2
Inserting(18),(19)and(16)intoEq.(15)includingtheminimumoverall10-toursyields:
c10(v,l)=min????maxπ(T2)?min{2??2+o(T2),π(T2)},by(16)Kis10-tour
2??1+s(w1,l)?π(T1)+π(T2)?min{2??2+o(T2),π(T2)},by(19)????maxf(K|T1,ξ)?f(opt(ξ),ξ)+π(T2)?min{2??2+o(T2),π(T2)}by(18)
ξ∈UlT1
=Kis10-tourmin??????max0,2??1+s(w1,l)?π(T1),maxf(K|T1,ξ)?f(opt(ξ),ξ)??ξ∈UlT1
+π(T2)?min{2??2+o(T2),π(T2)}????????(?)max2??1+s(w1,l)?π(T1),maxf(K|T1,ξ)?f(opt(ξ),ξ)=minKis10-tourξ∈UlT1
+π(T2)?min{2??2+o(T2),π(T2)}
(??)=max{2??1+s(w1,l)?π(T1),c(w1,l)}
+π(T2)?min{2??2+o(T2),π(T2)}.(20)
For(?)notethatalltermsinthemaximumarenon-negative;atourwhichisoptimalfortherespectivescenariocanatleastimitateK.Thezero-termwithinthemaximumcan,therefore,beomitted.ThecorrespondingvaluestemsfromEq.(16)forthesce-nariosinwhichtheedgee1isblocked.
123
352S.Büttner,S.O.KrumkeThelastreformulation(??)in(20)?nallyevaluatesthe“performanceofKinT1”.Recallthatbyde?nition
c(w1,l)=KtourinT1ξ∈UT1lminmaxf(K,ξ)?f(opt(ξ),ξ).
LetK?representthetourwheretheminimumofthetermisattained,i.e.inparticular?inT1itholds:foralltoursK
ξ∈Ul?,ξ)?f(opt(ξ),ξ)≥maxf(K?,ξ)?f(opt(ξ),ξ)=c(w1,l).maxf(KT1ξ∈UlT1
+oftype10inT:asthetypeindicates,edgeeisWeextendK?togetatourK?v2
de?nitelynottravelledwhileedgee1incontrastis,andthebehaviorinT1isdetermined+:bytourK?.Wegetfortheevaluationofthemaximumvaluein(20)fortourK?
????+max2??1+s(w1,l)?π(T1),maxf(K|T1,ξ)?f(opt(ξ),ξ)|K?
???????=max2??1+s(w1,l)?π(T1),2??1?2??1+maxf(K?,ξ)?f(opt(ξ),ξ)??????T????ξ∈Ul1????opt(ξ)doesnotenterT1????????opt(ξ)doesenterT1???????ξ∈UlT1
=max{2??1+s(w1,l)?π(T1),c(w1,l)}.
+isonevalid10-tourinT,thisyieldsintotalSinceK?v
??????minmax2??1+s(w1,l)?π(T1),maxf(K|T1,ξ)?f(opt(ξ),ξ)T?Kis10-tour?ξ∈Ul1
≥max{2??1+s(w1,l)?π(T1),c(w1,l)}????
+=max2??1+s(w1,l)?π(T1),maxf(K|T1,ξ)?f(opt(ξ),ξ)|K?T1??ξ∈Ul????≥minmax2??1+s(w1,l)?π(T1),maxf(K|T1,ξ)?f(opt(ξ),ξ).T??Kis10-tourξ∈U1l???≥c(w1,l)forallKThus,equalityhastoholdeverywhereandthevalidityofthelastreformulationin
(20)isshown.Thecomputationofc10(v,l)inparticularonlyincludesknownvalues.Toursoftype01contributeanalogouslytothe10-tourswiththeterm
c01(v,l)=π(T1)?min{2??1+o(T1),π(T1)}
+max{2??2+s(w2,l)?π(T2),c(w2,l)}.(21)
123
第15 / 22页
久久建筑网m.kkreddy.com提供大量：建筑图纸、施工方案、工程书籍、建筑论文、合同表格、标准规范、CAD图纸等内容。