Hello, dear experts,

I have a partial solution of TSP which is 0-1-2-4-6-0. Node 0 is the depot or starting node, while other nodes represent cities or customers that need to visit in this single route.

Now we have two new cities 3 and 5, originating from dynamic request or the ruin step of large neighborhood search. These two nodes need to insert into the existed route, respecting their sequence. That is, node 1 should be visited before node 2. But node 3 can be inserted between node 1 and node 2.

I want to formulate a mathematical model to exactly solve this problem via CPLEX or Gurobi. But I have no idea how to formulate it. A simple method is to model a standard TSP formulation and then add the sequence constraint, e.g., node 1 before node 2. But this will make the problem more difficult than the standard TSP, which is not the instinct idea of large neighborhood search.

Do you have some ideas how to formulate the repair problem? thank you very much.


asked 26 Jul '17, 04:17

LinYuan's gravatar image

accept rate: 0%

Adding sequence constraints to a standard TSP formulation (using all seven nodes) will make the MIP model larger. I'm not at all sure that it will make it more difficult (meaning longer solution time).

I think the following formulation is technically correct, but I'm not sure it is any better than the expanded TSP formulation, and it may be harder for someone to read. Let \(d_{ij}\) be the distance from node \(i\) to node \(j\), and let \(\delta_i\) be the distance from any node \(i\notin\left\{ 3,5\right\}\) to the node that currently follows it. (For instance, \(\delta_6=d_{60}\).) Define binary variables \(x_{ij}\) for \((i,j)\in\left\{ 3,5\right\} \times\left\{ 0,\dots,6\right\}\) and for \((i,j)\in\left\{ 0,\dots,6\right\} \times\left\{ 3,5\right\}\). Each \(x_{ij}\) indicates, as usual, whether \(j\) immediately follows \(i\) in the new sequence. Finally, create continuous variables \(z_0,\dots,z_6\) with \(z_j\) representing the distance traveled in the new sequence from node \(j\) to the node following \(j\).

The objective is to minimize \(\sum_{j=0}^6 z_j\). Constraints defining a valid insertion of the two new nodes are as follows:

  • \(\sum_{j=0}^6 x_{ij}=1\) for \(i=3,5\) (new nodes are exited once each);
  • \(\sum_{j=0}^6 x_{ji}=1\) for \(i=3,5\) (new nodes are entered once each);
  • \(x_{33}=x_{55}=0\) (you can't go from a new node to itself);
  • \(x_{35}+x_{53}\le 1\) (the new nodes cannot form a subtour).

The distance variables are defined by the following constraints:

  • \(z_{i}=\sum_{j=0}^6 d_{ij} x_{ij}\) for \(i=3,5\);
  • \(z_{i}=\delta_i +(d_{i3}-\delta_i)x_{i3} + (d_{i5}-\delta_i)x_{i5}\) for \(i=0,1,2,4,6\).

answered 26 Jul '17, 15:48

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

edited 26 Jul '17, 15:51

Thank you very much, Prof. Rubin. This formulation really works well in TSP. Now we want to extend this idea to VRP. It is more difficult, since multiple routes are available to be inserted, and each route may have capacity constraint and time window constraint.

For the possibility, we can define (x_{ijk}) where (j\ only define in the nodes on route (k). The capacity constraint is easy. But the TW constraint is a little tricky. My idea is to also define (x_{ijk}) for all (i) and (j), where some have definite value. Then represent the TW as stand VRPTW. How do you think @Paul Rubin

(27 Jul '17, 05:33) LinYuan

Fixing some of the \(x_{ijk}\) means that you will be limiting a priori where the new stops can be inserted. So the optimal solution to the modified problem may not actually be optimal overall.

(27 Jul '17, 14:50) Paul Rubin ♦♦

@Paul Rubin, Thanks, regarding your instructions, I have an idea on VRP recreation. Define y_i as the time to serve node i. Define x_ijk as usual, s_i is the service time of node i, and z_i defined above. Then the time window constraint can be imposed by y_i + s_i + z_i <= y_j + M(1-x_ijk), without fixing some of x. How do you like this? Thank you, Prof. Rubin.

(27 Jul '17, 22:13) LinYuan

Dear Prof. Rubin, I want to give the whole formulation when inserting some nodes to a partial VRP solution. But the words exceed the limit if it is adding as comment, so I post it here.

We are about to insert nodes 3 and 6 into the following routes, respecting the sequence:

\(0 \rightarrow 1 \rightarrow 2 \rightarrow 4 \rightarrow 6 \rightarrow 0\)

\(0 \rightarrow 8 \rightarrow 7 \rightarrow 9 \rightarrow 0\)

Define \(d_{ij}\) as the distance between nodes \(i\) and \(j\), \(s_i\) as the service time of node \(i\), \(\delta_i\) as the distance between node \(i\) and the node following \(i\) in the given sequence (thus, \(\delta_1 = d_{12}\), but how about \(\delta_0\)? Since two different nodes follow node 0). Alternatively, the second route can be changed to \(10 \rightarrow 8 \rightarrow 7 \rightarrow 9 \rightarrow 10\)

Define decision variable \(x_{ijk}\) as standard VRPTW in the new sequence, continuous variable \(z_i\) defined as above, \(y_i\) as the time to start serve node \(i\).

\(\min \sum\limits_{i=0}^9{z_i}\)

\(\sum\limits_{k=0}^1{\sum\limits_{j=0}^9{x_{ijk}}} = 1\), for \(i \in {3,5}\)

\(\sum\limits_{k=0}^1{\sum\limits_{j=0}^9{x_{jik}}} = 1\), for \(i \in {3,5}\)

\(x_{33k} = x_{55k} = 0\), for \(k \in {0,1}\)

\(\sum\limits_{j=0}^9{x_{ijk}q_i} \leq Q_k\), for \(k \in {0, 1}, i\in{3, 5}\), where \(q_i\) is the demand of node \(i\), and \(Q_k\) is the remaining capacity of route \(k\).

\(y_i + s_i + z_i \leq y_j + M(1-x_{ijk})\), for \(\forall i,j,k\)

When define \(x_{ijk}\), \(i \in {3, 5}, k \in {0,1}\), \(j\) should only define one the nodes on route \(k\) in the given sequence plus \(3, 5\).

\(x_{35k} + x_{53k} \leq 1\), for \(k \in {0, 1}\) to avoid subtour

@Paul Rubin, How do you think this formulation? Do you have some ideas to improve the time window constraints?

(27 Jul '17, 22:38) LinYuan

I agree that you should use a dummy node 10 as the origin/destination of the second route. The rest looks fine to me, assuming that the "distances" \(z_i\) are actually travel times. However, this looks as if you are treating all the \(x_{ijk}\) as variables, which would seem to solve a complete model from scratch. I suspect you can reformulate so that the only binary variables are where new nodes 3 and 5 are inserted.

(05 Aug '17, 11:46) Paul Rubin ♦♦
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 26 Jul '17, 04:17

Seen: 407 times

Last updated: 05 Aug '17, 11:46

OR-Exchange! Your site for questions, answers, and announcements about operations research.