A polynomial-time algorithm to find shortest paths with recourse

《A polynomial-time algorithm to find shortest paths with recourse》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、APolynomial-TimeAlgorithmtoFindShortestPathswithRecourseJ.ScottProvanDepartmentofOperationsResearchUniversityofNorthCarolinaChapelHill,NC27599-3180December2,2002AbstractTheShortestPathwithRecourseProbleminvolvesfindingtheshortestexpected-lengthpathsinadirectedn

2、etworkeachofwhosearcshavestochastictraversallengths(ordelays)thatbecomeknownonlyuponarrivalatthetailofthatarc.Thetravelerstartsatagivensourcenode,andmakesroutingdecisionsateachnodeinsuchawaythattheexpecteddistancetoagivensinknodeisminimized.Wedevelopanextensio

3、nofDijkstra’salgorithmtosolvetheversionoftheproblemwherearclengthsarenonnegativeandresetaftereacharctraversal.Allknownno-resetversionsoftheproblemareNP-hard.Wemakeapartialextensiontothecasewherenegativearclengthsarepresent.Keywords:stochasticnetwork;shortestpa

4、th;recourse;Dijkstra11IntroductionThestochasticshortestpathproblemhasasinputadirectednetworkG=(N;A)withnodesetNandarcsetAofcardinalitiesnandm,respectively.Eacharc(i;j)ofGhaslengthLijwhichisarandomvariabletakingonrijfinitevaluesl1<:::

5、urcenodes,andijijisinterestedinreachingadestinationnodetusingapathhavingminimumexpectedlength.Therearetwopopularversionsofthestochasticshortestpathproblemthatdifferintheamountofinformationthatatravelerhasaboutthearc-lengthsasthenetworkistraversed.Intheexpecteds

6、hortestpathproblem,thetravelerknowsallarclengthsinthenetworkbeforestartingthetraversal,andhencealwayschoosesthedeterministicshortest(s;t)-pathforthatpar-ticularrealizationofthenetwork.Thisproblemissurveyedin[4],Section6.Althoughdeterminationofthepathknowingeac

7、hparticularrealizationisasimpleshortestpathcomputation,actuallycomputingtheexpectedpath-lengthsoverallrealizationsisNP-hardeveninthecasewherethearcstakeononly0-1values.Intheshortestexpectedpathproblem,thetravelerisawareofnoarclengthswhiletraversingthenetwork,a

8、ndthusmusttakethepredetermined(s;t)-paththathasshortestexpectedlength.Thisprobleminvolvessimplyfindingtheshortest(s;t)-pathinGusingexpectedarclengthsforeacharc,andtheexpectedvaluehe