Wardrop - Wardrop equilibrium ( Newton hybrid method )
Compute the Wardrop equilibrium of a transport assignment problem by solving the following optimization problem:
Min_q 1/2 f'If+l'f
f=Sum_i q_i
I=diag(r)^(-1)
Hq_i=d_i
O<=q_i
i=1,...,p
The method used is a decomposed newton method in the space (q_i,v_i) i=1,p, where the v_i denote the dual variables associated to the constraints Hq_i=d_i .
v=Sum_i v_i.
a must be taken small. It regularizes the matrices giving the potentials.
It exists a Scilab toolbox (called CiudadSim) dedicated to this problem. See Scilab Contributions.
m=25; n=100; p=100; // generates a random admittance matrix r=max(rand(n,1),0.1);l=rand(n,1); // generates a random incidence matrix H=spzeros(m,n); for j=1:n ij=ceil(m*rand(2,1)); H(ij(1),j)=1; H(ij(2),j)=-1; end // generates random inputs-outputs d=spzeros(m,p); for j=1:p ij=ceil(m*rand(2,1)); d(ij(1),j)=1; d(ij(2),j)=-1; end // computes the wardrop equilibrium and gives // the computation time. timer();[V,f,pre]=Wardrop(H,d,l,r,0.01,1.e-7,20);timer()