Hi,
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:
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;
I doubt that passable_links(i,j,s)$(a(i,j) and passable_nodes(i,j,s))=yes; is the correct way to find links that are reachable/passable within the threshold.
Any advice is of great value and I thank you and appriciate it.