How to visit a subset of network nodes in a single trip?

Question

I have a connected network where I want to visit a set of destinations which may require visiting intermediate nodes as well because there may be no direct edge between source and destination nodes. I want to visit all destinations including intermediate nodes (not all nodes, only those nodes which help in completing the tour in minimum time). As soon as the last destination is visited, it should give the minimum time to visit the destination, i.e., the source node will not be visited at the end. Each edge in the network is bidirectionally visitable. For example, a network in the following diagram, the source could be $O$ and destinations could be $A$ and $C$:

I have the following mathematical formulation for this purpose.

The objective function is to minimize the total travelling distance from source to all destination nodes which is defined as follows:

$$\min \sum_{(i, j)\in N} T_{ij} x_{ij}$$

The constraints include:

• $\sum\limits_{i,j\in\rm Edges} x_{ij} = 1$ where $i$ is a source node;

• $\sum\limits_{i,j\in\rm Edges} x_{ij} = 0$ where $j$ is a source node;

• $$\sum\limits_{j\in\rm Destinations}\sum\limits_{i,j \in\rm Edges} = \sum\limits_{j\in\rm Destinations}\sum\limits_{j, i\rm \in Edges} - 1$$ for all edges going into the destination nodes, it should be one greater than the last destination;

• $\sum\limits_{i,j\in\rm Edges} x_{ij} = \sum\limits_{j,l\in\rm Edges} x_{jl}$ for each intermediate nodes excluding source and destination nodes. It ensures path starts at origin and that each subsequent edge in the path is a continuation from the previous edge.

When I run these constraints in Docplex, it shows an infeasible solution. If I exclude the second $\sum\limits_{i,j\in\rm Edges} x_{ij} = 0$ constraint, it provides the solution as:

   O-A
   A-O
   C-O

The actual solution should be:

   O-A
   A-B
   B-C

Answer 1

To be clear, you have a set $S$ of nodes of a graph $G=(V,A)$, with $S\subseteq V$, which must be visited. There is a special node $O$, which must be the starting point of a tour. A tour visiting the nodes in $S$ starting from $O$ (but not returning to $O$) at minimum length must be found? If that is the case, I think the easiest way is to compute an all-pairs shortest path matrix on the set $O\cup S$ and then solve a TSP with the modification described in this answer.

---

Edit: As I can see from the comments that the answer was not entirely clear, I will try to elaborate a bit on the idea.

1. We can observe, that we will never take a route between two of the destination nodes, which is longer than the shortest path between the two destinations. This is because we can visit the nodes of the graph several times without problems per the OPs description.
2. If we knew the shortest paths between each pair of destinations nodes, say $i,j\in S$, and we knew the order in which the destination nodes should be visited, we can piece a correct solution together by traversing the shortest paths between the destination nodes in the order specified by the order of the destination nodes.
3. An optimal ordering of the destination nodes can be found by solving a TSP over the set $V= O\cup S$ with a distance matrix given by the shortest path distances between the nodes in $V$.
4. If we do not want to return to $O$ we can set the distances leading from destination nodes back to the origin to zero, and then solve a TSP over $V$ with the new distance matrix as per this answer.

From these observations you can solve you problem using the following approach

1. Compute an all pairs shortest path matrix on the set $V$ in the graph $G$. You can e.g. use the Floyd-Warshall algorithm. Let $(p_{ij})_{i,j\in V}$ be the matrix of shortest paths and let $d_{ij}$ be the corresponding distances..
2. For each $i,j\in V$ define a new matrix $\tilde{d}_{ij}$ as follows: if $i\in V$ and $j\in S$ then $\tilde{d}_{ij}=d_{ij}$ and otherwise $\tilde{d}_{ij}=0$ (that is, $\tilde{d}_{iO}=0$ for all $i\in V$).
3. Solve a TSP over the set $V$ with the matrix $\tilde{d}_{ij}$ as the distance matrix. From this you get an optimal "open TSP" of the set $V$. Let an optimal ordering of the destination nodes be given by $\{O,s_1,s_2,\dots,s_{\vert S\vert}\}$.
4. Find an optimal solution to your problem using the "tour" given by $p_{0s_1}\rightarrow p_{s_1 s_2}\rightarrow\dots\rightarrow p_{s_{\vert S\vert-1}s_{\vert S\vert}}$

Answer 2

If the set $S$ of nodes to be visited is not too large, you can solve $|S|$ shortest path problems with additional constraints imposing a visit to some nodes.

With your example, $|S|=|\{A,C \}|=2$ so it is not too bad. 1/ Find the shortest path from $O$ to $A$, while imposing a visit to node $C$. 2/ Then find the shortest path from $O$ to $C$, while imposing a visit to node $A$. 3/ Compare the two solutions and keep the best one.

The first case can be modeled as follows : $$\min \; \sum_{(i,j) \in E} T_{ij}x_{ij}$$ subject to \begin{align} \sum_{(i,j)\in E} x_{ij} &= \sum_{(j,i)\in E} x_{ji} \quad &\forall j \not \in \{O,A\} \tag{1}\\ \sum_{(O,j)\in E} x_{Oj} &= 1 \tag{2} \\ \sum_{(i,A)\in E} x_{iA} &= 1 \tag{3} \\ x_{ij} &\le y_j & \forall (i,j) \in E \tag{4}\\ y_j &\le \sum_{(i,j)\in E} x_{ij} \quad &\forall j \in V \tag{5}\\ y_{C} &= 1 \tag{6} \\ y_i & \in \{0,1\} \quad &\forall j \in V \\ 0 \le x_{ij} &\le 1 & \forall (i,j) \in E \end{align}

Constraints $(1)$ are flow conservation constraints. Constraints $(2)-(3)$ impose that the path starts at $O$ and ends at $A$. Constraints $(4)-(5)$ activates a binary variable that takes value $1$ when the associated node is visited, and constraints $(6)$ imposes a visit to node $C$.

Answer 3

I think your third constraint should be + 1, not - 1, on the right hand side. As stated, it says you enter destination nodes one time fewer than you exit them. You want to enter one time more.

Fixing that will make the optimal solution feasible, but it will not make the model correct. There still remains the possibility of a solution that is not a contiguous trip. For instance, in your sample network, suppose that A, B, D and E are destinations. O-A-B D-E-D satisfies your constraints: O is exited once and never entered; the number of entries to destinations (4) exits the number of exits (3) by 1; and entries and exits at non-destination nodes are equal (both 0). With the right set of arc transit times, that "solution" could be optimal.

Answer 4

you could try constraint programming / scheduling within CPLEX and use noOverlap to model the time matrix.

In OPL that gives

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

*/