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

Problems with syntax of GAMS
Post Reply
Posts: 9
Joined: 3 months ago

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

Post by GAMS_practitioner » 2 months ago


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;

   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

   new = na;
      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



*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.

Post Reply