I have a TSP modeled as a integer program with euclidean distance in the objective function. Often, the optimal solution will take a zig zagged path, which my customer finds less than ideal. In every case, there exists a very-near optimal solution which takes a more smooth and predictable path.

Example

Does anyone have any suggestions for encouraging such a path? What I have tried so far is changing the objective function from euclidean to a sum of the distance in each dimension: SUM( Abs(x2-x1) ) + SUM( Abs(y2-y1) ) + SUM( Abs(z2-z1) )

This does indeed discourage zig zagging, but it is not 100% reliable on all problem sets, and I really wish there was a more reliable way to do this that would not sacrifice the euclidean distance consideration, which I would prefer to keep as a driver.

asked 31 Jan, 12:17

gtg489p's gravatar image

gtg489p
3113
accept rate: 0%


I think this depends to some extent on what precisely you mean by "zig-zag". Let's assume solution time is fast enough that you can do it in two stages: (1) find the shortest distance solution without regard to "quality"; (2) constraint distance to not more than some multiple of the shortest distance, switch the objective to minimizing "nonlinearity", and solve again. To handle nonlinearity (zig-zagging), I might be tempted to look at each pair of edges incident on a common node and assign a penalty to using them consecutively based on the angle they form (in some representative map). Other ways to view zig-zagging might include counting the number of times the latitude,longitude or distance from the source node decreases and then immediately increases again. So the phase 2 objective looks like some linear function of pairs of consecutive edges, which can be modeled by adding a bunch of auxiliary variables.

link

answered 31 Jan, 16:04

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.5k412
accept rate: 19%

Paul thanks for your expert input. While this is an interesting solution, I am so reluctant to go down any path that will add a bunch of auxiliary vars just because of how hard we worked to keep the number of variables and constraints as low as possible using various optimization tricks. I would hate to lose all of that performance if at all avoidable.

(01 Feb, 11:29) gtg489p

Understandable. The auxiliary variables would be continuous, rather than integer, and continuous variables are relatively cheap given modern MIP solvers' capabilities. On the other hand, there would also be a bunch of constraints to define them, which would add drag.

(01 Feb, 11:42) Paul Rubin ♦♦

If your TSP solver accepts sparse input, you could try omitting "long" edges. But if you omit too many, you'll make the problem infeasible.

link

answered 31 Jan, 13:29

Rob%20Pratt's gravatar image

Rob Pratt
1.2k26
accept rate: 28%

Thanks Rob, to clarify - the illustration I provided does not have the same scale on each dimension. The y axis, which is where the bad zig zagging happens, is actually a very short distance if you look at the scale. Which is why the TSP found it to be shortest path. So omitting long legs won't help here.

(31 Jan, 13:33) gtg489p

One way I could think of is adding a few binary variables to detect chosen direction of movement in each leg of the journey and minimize the deviation from previous directions as much as possible.

i.e

if \(y_{ij}\) is the binary variable that says journey from point i to point j is in the tour or not, then using the following binary variables for directions: \(b_x,b_y,b_z\)

constraints

\(abs(X_i-X_j)*y_{ij} <= d_{ij}\)

\(abs(Y_i-Y_j)*y_{ij} <= d_{ij}\)

\(abs(Z_i-Z_j)*y_{ij} <= d_{ij}\)

\(b_x+b_y+b_z = y_{ij}\)

\(abs(X_i-X_j)b_x+abs(Y_i-Y_j)b_y +abs(Z_i-Z_j)*b_z = d_{ij}\)

additional components in objective

\(\sum_{ij,ij'}(abs(b_x_{ij}-b_x_{ij}')+abs(b_y_{ij}-b_y_{ij}')+abs(b_z_{ij}-b_z_{ij}')+d_{ij})\)

I have'nt tried it out. Maybe this is a dumb answer. This approach might be my first approach.

link

answered 31 Jan, 15:14

Naveen%20Divakaran's gravatar image

Naveen Divak...
7418
accept rate: 25%

edited 31 Jan, 15:29

You could possibly take a look at the so called pyramidal TSP. One possible way of implementing this is to sort the points in non-decreasing distance to a seed customer, and then limit the number of points which are allowed to be incident to two points having a higher index than it self. If you allow no customers being connected to two nodes of higher index, you will get a nice route that goes "out and then home".

link

answered 01 Feb, 10:51

Sune's gravatar image

Sune
913412
accept rate: 19%

edited 01 Feb, 14:46

Your answer
toggle preview

Follow this question

By Email:

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

By RSS:

Answers

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

Tags:

×228
×190
×11

Asked: 31 Jan, 12:17

Seen: 187 times

Last updated: 01 Feb, 14:46

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