Answers to: Method to encourage straight/smooth paths for TSPhttp://www.or-exchange.com/questions/15348/method-to-encourage-straightsmooth-paths-for-tsp<p>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.</p>
<p><a href="https://imgur.com/a/Gif72">Example</a></p>
<p>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) )</p>
<p>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.</p>enThu, 01 Feb 2018 11:42:18 -0500Comment by Paul Rubin on Paul Rubin's answerhttp://www.or-exchange.com/questions/15348/method-to-encourage-straightsmooth-paths-for-tsp#15362<p>Understandable. The auxiliary variables would be continuous, rather than integer, and continuous variables are <em>relatively</em> 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.</p>Paul RubinThu, 01 Feb 2018 11:42:18 -0500http://www.or-exchange.com/questions/15348/method-to-encourage-straightsmooth-paths-for-tsp#15362Comment by gtg489p on Paul Rubin's answerhttp://www.or-exchange.com/questions/15348/method-to-encourage-straightsmooth-paths-for-tsp#15361<p>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.</p>gtg489pThu, 01 Feb 2018 11:29:30 -0500http://www.or-exchange.com/questions/15348/method-to-encourage-straightsmooth-paths-for-tsp#15361Answer by Sunehttp://www.or-exchange.com/questions/15348/method-to-encourage-straightsmooth-paths-for-tsp/15359<p>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".</p>SuneThu, 01 Feb 2018 10:51:48 -0500http://www.or-exchange.com/questions/15348/method-to-encourage-straightsmooth-paths-for-tsp/15359Answer by Paul Rubinhttp://www.or-exchange.com/questions/15348/method-to-encourage-straightsmooth-paths-for-tsp/15353<p>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.</p>Paul RubinWed, 31 Jan 2018 16:04:45 -0500http://www.or-exchange.com/questions/15348/method-to-encourage-straightsmooth-paths-for-tsp/15353Answer by Naveen Divakaranhttp://www.or-exchange.com/questions/15348/method-to-encourage-straightsmooth-paths-for-tsp/15351<p>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.</p>
<p>i.e</p>
<p>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\) </p>
<p><strong>constraints</strong></p>
<p>\(abs(X_i-X_j)*y_{ij} <= d_{ij}\)</p>
<p>\(abs(Y_i-Y_j)*y_{ij} <= d_{ij}\)</p>
<p>\(abs(Z_i-Z_j)*y_{ij} <= d_{ij}\)</p>
<p>\(b_x+b_y+b_z = y_{ij}\)</p>
<p>\(abs(X_i-X_j)<em>b_x+abs(Y_i-Y_j)</em>b_y +abs(Z_i-Z_j)*b_z = d_{ij}\)</p>
<p><strong>additional components in objective</strong></p>
<p>\(\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})\)</p>
<p>I have'nt tried it out. Maybe this is a dumb answer. This approach might be my first approach.</p>Naveen DivakaranWed, 31 Jan 2018 15:14:29 -0500http://www.or-exchange.com/questions/15348/method-to-encourage-straightsmooth-paths-for-tsp/15351Comment by gtg489p on Rob Pratt's answerhttp://www.or-exchange.com/questions/15348/method-to-encourage-straightsmooth-paths-for-tsp#15350<p>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.</p>gtg489pWed, 31 Jan 2018 13:33:11 -0500http://www.or-exchange.com/questions/15348/method-to-encourage-straightsmooth-paths-for-tsp#15350Answer by Rob Pratthttp://www.or-exchange.com/questions/15348/method-to-encourage-straightsmooth-paths-for-tsp/15349<p>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.</p>Rob PrattWed, 31 Jan 2018 13:29:33 -0500http://www.or-exchange.com/questions/15348/method-to-encourage-straightsmooth-paths-for-tsp/15349