I've encountered a loopless positive sub-network from one origin to all destinations,I want to generate all the paths,but the flow of a path depends on path links and demand of that origin based ,we can't generate them with max flow algorithms.
I have been thinking about your question. If you simply want to enumerate all the paths, I do not see why "the flow of a path depends on path links" makes any important effect on the available paths. We can enumerate the feasible paths from Origin node to all the Destinations. If you want to have the "benefit" of that path depend on the flow that appears to be building up on that path, you have a kind of network equilibrium problem. The two approaches to that depend on your objective perspective: one is called system optimal, and the other is called user equilibrium. Both ideas are covered exhaustively in the literature: example Prof. Sheffi's text.
http://web.mit.edu/sheffi/www/selectedMedia/sheffi_urban_trans_networks.pdf
Yes indeed, your problem seems to be a rather classical static assignment problem. Among the available algorithms, the method of successive averages is easy to implement. See for instance, among numerous sources, page 324 of Sheffi's text pointed by Morton.
But I have another question : what do you mean by "... demand of that origin based,..." ? Are you working with Bar-Gera's origin based network assignment ?
- Badges
- Science topic