# Linear Path Optimization with Two Dependent Variables

Alright, so this is a fairly interesting problem I have but also slightly difficult to explain so I will try my best.

There are two runners on a line that goes from $$x=0$$ to $$x=100$$. The two runners start at $$x=50$$. The runners are then given an array of coordinate pairs that they must visit. The catch is, the coordinate pair contains the $$x$$ value for locations runner 1 and runner 2 must be at the same time. So for example, if they are given a coordinate pair $$(40, 70)$$, to successfully "complete" that coordinate, runner 1 must go to $$x=40$$, and runner 2 must go to $$x=70$$. They can't move on to the next coordinate pair until both have reached their destination.

So given a large array of coordinate pairs, the runners have to visit each coordinate pair in any order they chose. The runners can move at the same time and have the same speed. The trick is how to optimize the order in which they visit the coordinates. For example, if runner 1 is at $$x=10$$, and runner 2 is at $$x=90$$, it would be inefficient to chose a coordinate pair like $$(80,80)$$, because runner 2 would only travel $$10$$ units, and spend a long time waiting while runner 1 is moving $$70$$ units. This is sort of like the travelling salesman problem, except there are two people involved dependent on each other, and they can visit any point from any other given point in any order.

Does anyone have any ideas how to create an algorithm that would return the best (or at least good) optimized order in which they would visit these coordinate pairs?

As Vince observes, your problem is TSPP (traveling salesman path problem) on the plane with respect to the $$L_\infty$$ metric. On the plane, the $$L_\infty$$ and $$L_1$$ metrics are equivalent (the unit balls differ by a rotation of $$45^\circ$$), so your problem is equivalent to TSPP on the plane with respect to the $$L_1$$ metric. This problem has been addressed on this question.
• For those readers who have less of a background with metrics and unit circles/spheres: Wikipedia article about unit spheres where you can see the $L_\infty$ and $L_1$ circles. – einpoklum Apr 5 at 15:31