Hi, I’m try to do this exercise:
Let there be an undirected graph with arcs all having travel time equal to 1. n agents move on this graph. Each agent i has origin node oi and a destination node di. Define a mathematical model to minimize the sum of the minimum paths of all agents, taking into account that agents cannot be at the same instant at a node or along an arc and considering the time component.
SETS
set NODES; #set of nodes set EDGES within (NODES cross NODES); #set of edges set AGENTS; #set of agents
PARAMETERS
param Source{AGENTS} symbolic in NODES; #starting node for each agent param Destination{k in AGENTS} symbolic in NODES, != Source[k]; #destination node for each agent param b{AGENTS} >= 0 default 1; #flow of each agent param c{EDGES} >=0, default 1; #cost of each edge param d{EDGES} >= 0, default 1; #capacity of each edge
VARIABLES
var x{EDGES,AGENTS} binary; #binary variable indicating whether agent k is on edge (i,j) var y{NODES,AGENTS} binary; #binary variable indicating whether agent k is on node I
CONSTRAINTS
#two agents cannot have the same starting node subject to no_same_source{k1 in AGENTS, k2 in AGENTS: k1 < k2 and Source[k1] = Source[k2]}: sum{i in NODES} y[i,k1] + sum{i in NODES} y[i,k2] <= 1;
#two agents cannot have the same destination node subject to no_same_dest{k1 in AGENTS, k2 in AGENTS: k1 < k2 and Destination[k1] = Destination[k2]}: sum{i in NODES} y[i,k1] + sum{i in NODES} y[i,k2] <= 1;
#flow balance on nodes
subject to flow_balance{j in NODES, k in AGENTS : j != Source[k] and j != Destination[k] } : sum{h in NODES : (j,h) in EDGES} x[j,h,k] - sum{h in NODES : (h,j) in EDGES} x[h,j,k] = 0;
Each agent must start from its source node
subject to source_balance{k in AGENTS}: sum{h in NODES : (Source[k], h) in ARCS} x[Source[k], h, k] - sum{h in NODES : (h, Source[k]) in ARCS} x[h, Source[k], k] = b[k];
Each agent must reach its destination node
subject to destination_balance{k in AGENTS}: sum{h in NODES : (Destination[k], h) in ARCS} x[Destination[k], h, k] - sum{h in NODES : (h, Destination[k]) in ARCS} x[h, Destination[k], k] = -b[k];
Each arc must respect its capacity
subject to maximum_capacity{(i, j) in ARCS}: sum{k in AGENTS} x[i, j, k] + sum{k in AGENTS} x[j, i, k] <= d[i, j];
No agent overlap on nodes
subject to no_node_overlap{k in AGENTS, i in NODES}: sum{j in NODES : (i, j) in ARCS} x[i, j, k] <= y[i, k];
No agent overlap on arcs
subject to no_arc_overlap{k in AGENTS, (i, j) in ARCS}: x[i, j, k] + x[j, i, k] <= y[i, k] + y[j, k] - 1;
OBJECTIVE
minimize total_cost : sum{(i, j) in ARCS} c[i, j] * (sum{k in AGENTS} x[i, j, k])
Can help me? Undestanding why this not work.
in case you would be able to write the mathematical model so then I translate it into ampl