Vi utvecklar en algoritm som beräknar för ett givet oriktat eller riktat nätverk med flödesberoende bitvis linjära edge-funktioner alla Wardrop equilibria som en funktion av flödesefterfrågan. Vår algoritm är baserad på Katzenelsons homotopy-metod för elnät. Algoritmen använder en bijection mellan vertex potentialer och flödesöverskott vektorer som är bitvis linjär i det potentiella utrymmet och där varje linjära segment kan tolkas som ett förstärkande flöde i ett restnät. Algoritmen iteratively ökar överskottet av en eller flera vertex par tills bijective når en punkt av icke-differentiability. Därefter, nästa linjära region väljs i en simplex-liknande pivot steg och algoritmen fortsätter. Vi visar först att denna algoritm korrekt beräknar alla Wardrop equilibria i oriktade single-commodity nätverk längs den valda vägen av överskott vektorer. Vi anpassar sedan vår algoritm för att även arbeta för okontinuerliga kostnadsfunktioner som gör det möjligt att modellera riktade kanter och/eller kantkapaciteter. Vår algoritm är output-polynomial i icke-degenererade fall där lösningskurvan aldrig träffar en punkt där kostnadsfunktionen av mer än en kant blir icke-differentiable. För degenererade fall vi fortfarande få en output-polynomalgoritm som beräknar linjära segment av bijective av ett konvext program. Den senare tekniken gör det också möjligt att hantera flera varor.
I tidigare arbete REF utvecklade vi en algoritm som beräknar alla Wardrop equilibria parametrized av flödesefterfrågan.
Computing all Wardrop Equilibria parametrized by the Flow Demand
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}