## How to find a set of edges that are reachable within some time limit?

Problems with syntax of GAMS
GAMS_practitioner
User
Posts: 9
Joined: 3 months ago

### How to find a set of edges that are reachable within some time limit?

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:

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?