5
$\begingroup$

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$:

enter image description here

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
$\endgroup$
2
  • $\begingroup$ When you say $i$ or $j$ is "a source node", do you mean "the source node, or do you have multiple sources? $\endgroup$ – prubin Apr 29 at 16:36
  • $\begingroup$ I have only one source node in the network. $\endgroup$ – bsha Apr 30 at 2:14
5
$\begingroup$

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}}$
$\endgroup$
7
  • $\begingroup$ As per my understanding, in TSP, all the nodes to be visited are directly reachable from any other node in a network. And the objective for such problem is to minimize the total travel cost. My problem is a bit different. There are nodes in the network that are not directly reachable. So we try to reach the destination through intermediate nodes. Each node can be visited more than once including destination nodes. But when all the destination nodes are visited at least once in minimum travel time, the program should stop. $\endgroup$ – bsha Apr 29 at 12:28
  • $\begingroup$ It would be great if I could see a mathematical formulation for this problem. I am trying to do it using different constraints. But I couldn't be successful. I am trying to implement it in Docplex. $\endgroup$ – bsha Apr 29 at 12:30
  • 1
    $\begingroup$ @bsha The (directed) TSP Sune is suggesting is over a complete auxiliary network with only the source and destination nodes, not the original network. And the arc costs for the auxiliary network are obtained from the all-pairs shortest paths computation in the original network. $\endgroup$ – RobPratt Apr 29 at 16:42
  • $\begingroup$ I have implemented the suggested solution. There is still a problem. For example, we consider O as the source node and D, E, and T as destination nodes. After creating an auxiliary network with all-pairs shortest paths to destination nodes, I applied Miller-Tucker-Zemlin (MTZ) formulation for solving TSP. Considering the network, it requires visiting D node twice for minimum shortest path. But it provides the solution as O-D-T-E-O. $\endgroup$ – bsha May 4 at 5:15
  • 2
    $\begingroup$ The main idea is that once you know the sequence in which you visit the nodes in $S$, the problem becomes trivial: you start at $O$, then take the shortest path to the first node in the sequence, then the shortest path to the second node in the sequence, etcetera. The matrix of shortest path distances between all nodes in $S$ will adhere to the triangle inequality even if the distance matrix for your original network does not. Once you have an optimal sequence on $S$, you expand the sequence by inserting the shortest paths in the original network, which may then introduce repeated visits. $\endgroup$ – Paul Bouman May 6 at 5:54
4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Many thanks for your answer. The total number of nodes and the destination nodes varies depending upon the size of the network. For a network of 1000 nodes with 100 destinations, the proposed solution will not be efficient. I am trying to formulate the constraints in a way that will be general and efficient for increasing number of nodes and destination nodes. $\endgroup$ – bsha Apr 29 at 12:22
  • $\begingroup$ Setting $y_i=1$ does not enforce anything here. You need additional constraints to do that. $\endgroup$ – RobPratt Apr 29 at 12:48
  • $\begingroup$ Wooops ! my mistake. I added the missing constraint. Thanks a lot. $\endgroup$ – Kuifje Apr 29 at 12:52
3
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ You are right. For the destination nodes, either A, B, D, and E or A, B, C, and E, it gives again a discontinuous path. Can you please elaborate that what do you mean by the right set of arc transit times? $\endgroup$ – bsha Apr 30 at 2:16
  • $\begingroup$ I meant transit times that would make O-A-B D-E-D an attractive "route" in terms of objective value. Small enough times for those arcs and large enough times for the other arcs would lead the solver to pick that solution. $\endgroup$ – prubin May 1 at 16:26
  • $\begingroup$ Will I have to assign virtual times for those arcs? If I consider the network in question, what modification is required in the constraint formulation that it could provide an optimal solution for different destinations? $\endgroup$ – bsha May 4 at 5:58
  • $\begingroup$ Sorry, I don't understand what you are asking. $\endgroup$ – prubin May 4 at 23:18
  • 1
    $\begingroup$ That does not make sense. The arc transit times should be parameters, not settings to tweak. Driving time from point A to point B is whatever it is, not what you would like it to be. (As a former commuter, I can attest to this personally.) $\endgroup$ – prubin May 6 at 15:21
3
$\begingroup$

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

*/
$\endgroup$
2
  • $\begingroup$ I could not understand your solution. The reason is that I am not much familiar with OPL. Could you please elaborate in mathematical formulation or docplex? $\endgroup$ – bsha May 4 at 5:55
  • $\begingroup$ Hi. In linkedin.com/pulse/… you have the same scheduling example both in OPL and docplex. The main constraint in the model I shared with you : "noOverlap(seq,M,true);" which means that we use the distance matrix M for the sequence. See ibmdecisionoptimization.github.io/docplex-doc/cp/… for the syntax of noOverlap in docplex $\endgroup$ – Alex Fleischer May 4 at 7:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.