Could anyone please suggest a nice fast way to find a set of nodes and edges that are accesible from some source node within a predifined threshold in GAMS? I'm trying to solve this as follow but Is there any way? Like to run this as a model? or is there any better way to compute everything in one loop?
The following code is from GAMS website with slight modification. It calculate all the shortest path from a node to every other nodes. I'd like to calculate something similar, and was wondering what is the best practice in this situation.
I have a netwok with some sellers (like s1,s2,s3). Each seller is located in a city. And all sellers have some time limits that determines their presence time in the network. For example, for seller `s1` the earlist arrival time is 190 and lates exit time is 294 (the shown times are minutes of the day). With that, we can calculate a presence time of each seller in the netwok which is 294-190=104 for this seller.
Assuming that the parameters `Arrival(s)` and `exit(s)` represting this arrival and exit times. How can I find:
1- A set of all nodes in the network that a shortest path from the seller's start point to those node are less than the seller's presence time (i.e . shortest < `exit(s)-arrival(s)`)
2- once having all the nodes that are whithin time limits, how to check if they have edge in network? I mean, among all nodes that are within the time limits, how to build/find a set nodes that form an edge in the network? (i.e. set of edges that are passable within the treshold)
Here is my try:
Code: Select all
Set i 'cities' / boston , chicago , dallas
kansas-cty, losangeles, memphis
portland , salt-lake , wash-dc /;
#set sub(i) 'the start location of each seller' / dallas, memphis, portland/;
set s 'sellers' /s1*s3/;
Alias (i,j,k);
Parameter a(i,j) 'arcs and cost'
/ boston .chicago 58, kansas-cty .memphis 27
boston .wash-dc 25, kansas-cty .salt-lake 66
chicago .kansas-cty 29, kansas-cty .wash-dc 62
chicago .memphis 32, losangeles .portland 58
chicago .portland 130, losangeles .salt-lake 43
chicago .salt-lake 85, memphis .wash-dc 53
dallas .kansas-cty 29, portland .salt-lake 48
dallas .losangeles 85, dallas .memphis 28
dallas .salt-lake 75 /;
Parameter f(i,j) 'shortest route between two cities';
option a:0, f:0;
Scalar
old 'old total distance'
new 'new total distance';
a(i,j) = max(a(i,j),a(j,i));
* let's assum this is already imported
Parameter Arrival(s), exit(s);
display a;
f(i,j) = inf;
f(i,i) = 0;
f(i,j) $= a(i,j);
* to find the shortest path from the start point of each seller to every other nodes in the netwrok
loop(i$sub(i),
new = na;
repeat(
f(i,j)$(not sameas(i,j)) = smin(k$a(k,j), f(i,k) + a(k,j));
old = new;
new = sum(j$(f(i,j) < inf), f(i,j));
until old = new);
);
display f;
* defining other parameters/sets to calculate set of passable nodes and edges within time limits
set
passable_nodes(i,j,s)
passable_arcs(i,j,r)
;
*this will calculate the set of nodes that are reachable from start point of the seller s to every other node in the network within their time limit
passable_nodes(i,j,s)$(f(i,j)<= exit(s) - arrival(s) ) = yes;
* could this give me a corretc set od links?
passable_links(i,j,s)$(a(i,j) and passable_nodes(i,j,s))=yes;
Any advice is of great value and I thank you and appriciate it.