Maxplus Function
Last update : 18/05/2014

Wardrop - Wardrop equilibrium ( Newton hybrid method )

Calling Sequence

[v,f,err]=Wardrop(H,d,l,r,a,eps,niter)

Parameters

Description

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.

Examples

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() 

 

See Also

costo,  howard,  fluide,