Umlegungsalgorithmus

Nachstehend folgt der Pseudo-Code des Verfahrens im Rahmen eines Umlegungsalgorithmus.

function LUCE

            f = 0          initialize the solution flows to zero

for k = 1 to n          perform n iterations

   for each d∈Z          for each destination d

     for each ij∈A          compute arc costs and their derivatives

             cij = cij( fij)

       gij = max{∂cij( fij)/∂fij, ε}

       if fid > 0 then yijd = fijd / fid else yijd = 0

     B(d) =B(B(d), c, f)          initialize or modify the current bush

     Cdd = 0           the average cost of the destination is zero

     Gdd = 0          so its derivative

     for each i:∃ij∈B(d) in reverse topological order  for each node i ≠ d in the bush

       if fid > 0 then

         Cid = ∑j∈FSB(i, d)yijd • (cij + Cjd)        compute the node average cost to d

         Gid = ∑j∈FSB(i, d)yijd2 (gij + Gjd)        and its derivative

      else

         Cid = min{cij + Cjd: j∈FSB(i, d)}

         Gid= ∑j∈FSB(i, d) [Cid = cij + Cjd] • (gij + Gjd) / ∑j∈FSB(i, d) [Cid = cij + Cjd],

  ed = 0          reset the arc and node flows to d

  for each o∈Z          load on the origins the demand to d

      eod = Dod

  for each i:∃ij∈B(d) in topological order  for each node i ≠ d in the bush

     J = FSB(i, d)          initialize the set of arcs with positive flow

     λ = 0

      until λ = 1 do

       λ = 1

       Vid = [eid + ∑j∈J (cij + Cjd) / (gij + Gjd) - eid•yijd] / ∑j∈J 1/(gij + Gjd)

       for each j∈J

                  eijd = Vid / (gij + Gjd) - (cij + Cjd) / (gij + Gjd) + eidyijd

         if eijd < 0 then

            eijd = 0

            J = J \ {j}         remove ij from the set of arcs with positive flow

            λ = 0          then repeat the procedure

     for each j∈J

        ejd = ejd + eijd          propagate the arc flows to the head node flows

  α = 1

  if k > 1 then

    until ∑ij∈A cij( fij + a • (eijd - fijd)) • (eijd - fijd) < 0 do α = 0.5 •α  armijo step

  for each ij∈A          update arc flows

    fij = fij + α • (eijd - fijd)

    fijd = fijd + α • (eijd - fijd)

Der Busch zu jedem Ziel d∈Z wird mit der Menge der effizienten Kanten initialisiert, die näher an das Ziel heranführen, wobei die minimalen Kosten bei unbelastetem Netz ausgewertet werden. Bei jeder Iteration werden alle nicht-effizienten Kanten, über die keine Zielbelastungen fließen, aus dem Busch entfernt, während alle Kanten, die Kurzwege auf dem Busch verbessern würden, hinzugefügt werden, wenn die entgegengesetzte Kante keine Belastung trägt. Ist der resultierende Teilgraph azyklisch, ersetzt er den aktuellen Busch dieses Ziels. Da der LUCE-Algorithmus auf ein Gleichgewicht auf dem Busch abzielt, wird die Belastung auf den nicht-effizienten Wegen schließlich abgebaut und der Busch kann passend umgebaut werden.

Bemerkenswerterweise erfordert der LUCE-Algorithmus nach der Initialisierung der Büsche keine weiteren Kurzwegberechnungen, sondern lediglich einfaches Durchlaufen der Büsche.