How to implement all or nothing assignment in a graph / network ?

1 次查看(过去 30 天)
Hi,
I have a transport network of n nodes represented by a ( nxn ) matrix A . This matrix contains zeros for non existing links between nodes and positive numbers for existing links. These numbers reflect the weight/cost of the link. I have applied graphshortestpath to A , in a loop, in order to find the shortest paths, with corresponding node sequencies and predecessors, from each node to every other node.
I also have a transport Origin-Destination ( OD ) demand matrix which indicates how many people want o travel between two nodes i and j .
What I want to do now is to find the traffic flows on each edge, according to the shortest path between each OD pair, performing all-or-nothing assignment. This means that the total demand between two nodes i and j will be transferred only through the edges which belong to the shortest path between i and j .
As example I use the following A and OD matrices:
A=[0 3 5 0 0;
0 0 2 6 0;
0 1 0 4 6;
0 0 0 0 4;
3 0 0 7 0];
OD=[0 2 7 3 1;
2 0 2 6 8;
1 4 0 4 6;
4 10 9 0 4;
5 6 3 6 0];
and the following loop to produce the matrix with the Shortest Paths, node sequencies and predecessors
for jj=1:size(A,1)
[SP,path,pred] = graphshortestpath(sparse(A),jj);
SPmat(jj,:)=SP;
pathMat(jj,:)=path;
predMat(jj,:)=pred;
end
Can anyone suggest what is the easiest way to do implement the above with these inputs?
Thanks,
Iro
  2 个评论
Iro
Iro 2014-3-27
编辑:Iro 2014-4-3
I have written the following code which seems to work.
sparse(A);
[i,j,s]=find(sparse(A));
SPRS_Mat=[i,j,s];
Links=SPRS_Mat(:,1:2);
link_sum_flow=[];
for ll=1:size(Links,1)
this_link=Links(ll,:);
Link_flow=[];
linkFlow=[];
for spr=1:size(pathMat,1)
for spcol=1:size(pathMat,2)
this_path=pathMat{spr,spcol}; % for every path of pathMat:
path_or=this_path(1); % find the Origin
path_dest=this_path(end); % find the Destination
path_OD=OD(path_or,path_dest); % find the corresponding OD
% Check if this link belongs to this path
[tf,loc] = ismember(this_link,this_path);
if (tf(1)==1 && tf(2)==1 && abs(loc(1)-loc(2))==1)
% Add the OD flow on this link
linkFlow(spcol)=path_OD;
else
linkFlow(spcol)=0;
end
end
Link_flow(spr,:)=linkFlow; % matrix with all flows of thislink
end
Link_flow;
link_sum_flow(ll)=sum(sum(Link_flow,1));
end
link_sum_flow; % The vector with the flows for each link
LinkFlowMat=[SPRS_Mat,link_sum_flow'];
But I would appreciate any tips for more efficient implementation since my real networks are much bigger than this example.
Thanks,
Iro

请先登录,再进行评论。

回答(0 个)

类别

Help CenterFile Exchange 中查找有关 Graph and Network Algorithms 的更多信息

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by