The issue isn't about approximating a TSP instance, but ensuring that points aren't too far apart from each other, even at the cost of increasing total length.
I can't immediately think of a reduction that would factor this in so the best thing may be to just reduce this to the appropriate ILP instance and use a mixed ILP approximator like GLPK (or Gurobi is free for students too).
Incidentally, achieving a polynomially-sized ILP formulation for TSP isn't quite obvious. Wikipedia has a good explanation of how to do this: https://en.wikipedia.org/wiki/Travelling_salesman_problem#In.... I'm not sure if the metric TSP has a simpler formulation.
Edit: Now that I think about it, it may be difficult to express the constraint that edges should be balanced out in a linear way. I happened to write about a similar problem a while ago (https://modalduality.org/posts/optimizing-color-coding/), I ended up giving up on finding a linear formulation and went for sequential least squares instead.
If you want to minimize the long distance walks add an exponential weight for distance then solve. There are many ways to go about this stuff, but the goal is to map your preferences to the weight function.
Right, but then the problem is no longer linear and approximating is more difficult. I'm not exactly sure what you mean by "exponential weight" in a linear program, do you have an example?
I am not sure what your asking? Your just assigning constants for weights on each trip a>b = K1, a>c = K2.
I am saying you may map K1 as √((x1-x2)^2+(y1-y2)^2) to find least distance, but TSP allows for arbitrary constants. So remove the √ and long trips will be strongly avoided.
PS: As far as I know you can use any arbitrary set of constants then use a linear solver. Or am I forgetting about something?
I can't immediately think of a reduction that would factor this in so the best thing may be to just reduce this to the appropriate ILP instance and use a mixed ILP approximator like GLPK (or Gurobi is free for students too).
Incidentally, achieving a polynomially-sized ILP formulation for TSP isn't quite obvious. Wikipedia has a good explanation of how to do this: https://en.wikipedia.org/wiki/Travelling_salesman_problem#In.... I'm not sure if the metric TSP has a simpler formulation.
Edit: Now that I think about it, it may be difficult to express the constraint that edges should be balanced out in a linear way. I happened to write about a similar problem a while ago (https://modalduality.org/posts/optimizing-color-coding/), I ended up giving up on finding a linear formulation and went for sequential least squares instead.