Modelling a time-space-network with cplex OPL

Question

I would like to model a time-space network in the context of a carsharing provider that is defined by S (stations) x (0,... t,..., Tmax) with different arcs that connect a node i at time t to a node j at time t' with t'>t. Each arc is associated with different values (for example profit).

Do you have any ideas on how to implement these arcs?

So far my idea was to define different tuples but I had problems integrating the time-component. Do you know if it's possible to solve such a problem with tuples at all?

Answer 1

I guess what you have is a graph that defines how the stations are connected:

{int} nodes = { 1, 2, 3, 4 };
tuple Arc {
  int origin;
  int destination;
}
{Arc} arcs = { <1,2>, <1,3>, <1,4>, <2,3> };

If I understand correctly then this graph needs to be duplicated for every period in a time interval which is defined as

int Tmax = 5;
range T = 0..Tmax;

You can define a new tuple that defines an arc with origin and destination as well as starting and end time:

tuple TArc {
  int origin;
  int destination;
  int starttime;
  int endtime;
}
{TArc} tarcs = { <o, d, s, e> | <o,d> in arcs, s in T, e in T : e > s };

In case you also need the nodes of the duplicated graphs then first define the nodes:

tuple TNode {
  int node;
  int time;
}
{TNode} tnodes = { <n,t> | n in nodes, t in T };

and then the arcs:

tuple TArc {
  TNode origin;
  TNode destination;
}
{TArc} tarcs = { <<o,s>,<d,e>> | <o,d> in arcs, s in T, e in T : e > s };

The cost/profit for an arc a probably depends either on the distance of the nodes (which would be distance(a.origin.node, a.destination.node)) or the time delta (which would be a.destination.time - a.origin.time).