Single-source and multi-destination problem in CPLEX/Docplex?

Question

Can we use the CPLEX/Docplex for single-source and multi-destination problem in a network? For example, routing a vehicle from a source to visit multiple destinations in a single trip minimizing the overall travel time.

Answer 1

Same question at https://community.ibm.com/community/user/datascience/communities/community-home/digestviewer/viewthread?GroupId=5557&MessageKey=a7f94f07-bb8d-420a-b82e-6c45525f6949&CommunityKey=ab7de0fd-6f43-47a9-8261-33578a231bb7&tab=digestviewer&ReturnUrl=%2fcommunity%2fuser%2fdatascience%2fcommunities%2fcommunity-home%2fdigestviewer%3fcommunitykey%3dab7de0fd-6f43-47a9-8261-33578a231bb7%26tab%3ddigestviewer

Hi,

you could have a look at the tsp OPL example in

examples/opl/models/TravelingSalesmanProblem

If you want to do single source and multi destination you could change the objective from

minimize sum (<i,j> in Edges) dist[<i,j>]*x[<i,j>];​

to

minimize sum (<i,j> in Edges) dist[<i,j>]*x[<i,j>]-max(j in Cities:<1,j> in Edges) dist[<1,j>]*x[<1,j>];​

And you have the same example in python docplex in https://raw.githubusercontent.com/IBMDecisionOptimization/cplex_code_examples/master/docplex/tsp.py

For your specific instance:

using CP;

execute
{
  cp.param.timelimit=10;
}

{string} nodes={"O","A","B","C","D","E","T"};

tuple edge
{
  key string o;
  key string d;
  int time;
}

{edge} edges with o,d in nodes=
{
  <"O","A",40>,
  <"O","B",60>,
  <"O","C",50>,
  <"A","B",10>,
  <"C","B",20>,
  <"A","D",70>,
  <"B","D",55>,
  <"B","E",40>,
  <"D","E",10>,
  <"D","T",60>,
  <"E","T",80>
};

string origin="O";
{string} targets={"A","C"};
int bigvalue=1000;
int repeat=3;
range ranks=1..repeat;

{edge} edgeswithsym=edges union {<d,o,t> | <o,d,t> in edges};

{edge} transitions=edgeswithsym union {<o,d,bigvalue> | o,d in nodes: <o,d> not in edgeswithsym};

tuple triplet {int id1; int id2; int value;};
{triplet} M = {<ord(nodes,tr.o)+1,ord(nodes,tr.d)+1,tr.time> | tr in transitions};

assert card(transitions)==card(nodes)*(card(nodes));

// Interval for visiting a node
dvar interval itvs[nodes][ranks] optional;

// Sequence means visits
dvar sequence seq in all(n in nodes,r in ranks)itvs[n][r] types 
all(n in nodes,r in ranks)(ord(nodes,n)+1); 

// First we want to minimize the time for latest visit
// Second we want to minimize present intervals
minimize 
staticLex(max(t in targets) min(r in ranks) startOf(itvs[t,r],bigvalue),
sum(n in nodes,r in ranks) presenceOf(itvs[n][r]));
subject to
{
  // We visit origin at time 0
  startOf(itvs[origin,1])==0;
  
  // origin and destinations should be present
  presenceOf(itvs[origin,1])==1;
  forall(t in targets) presenceOf(itvs[t,1])==1;
  
  // noOverlap constraint will enforce time matrix
  noOverlap(seq,M,true);
  
  // break sym
  forall(n in nodes) forall(r in ranks:r!=1) 
    presenceOf(itvs[n,r-1])>=presenceOf(itvs[n,r]);
  
}

int nbActiveIntervals=sum(n in nodes,r in ranks) presenceOf(itvs[n][r]);
range R=1..nbActiveIntervals;

// Display solution
execute {
  

  writeln(origin);
  var s=seq.first(); 
  for(var i in R) 
  {
   if (i!=nbActiveIntervals)
      writeln(Opl.item(nodes,-1+Opl.typeOfNext(seq,s,bigvalue,0)));
   s=seq.next(s); 
   
  } 
   
}

/*

gives

O
A
B
C

*/