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 '18, 12:17

gtg489p's gravatar image

gtg489p
3314
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 '18, 16:04

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
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 '18, 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 '18, 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 '18, 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 '18, 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 '18, 15:14

Naveen%20Divakaran's gravatar image

Naveen Divak...
7418
accept rate: 25%

edited 31 Jan '18, 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 '18, 10:51

Sune's gravatar image

Sune
958413
accept rate: 20%

edited 01 Feb '18, 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:

×231
×190
×11

Asked: 31 Jan '18, 12:17

Seen: 235 times

Last updated: 01 Feb '18, 14:46

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