# Minimising sum of consecutive points distances Manhattan metric

I have two sets $X$ and $Y$ of 2-dimensional points. The points are floating point numbers. The objective is to sort them in such way that sum of differences in distances of consecutive sorted points is minimal.

I tried to solve this problem by localisation (dividing the plane by smaller grids of sorted points) and then connecting clusters - but this is a greedy and an approximate approach - the problem here is in setting grid size, but this is not guaranteed to give any bounds on how optimal the solution is, and it is rather time consuming (without a well-defined objective function).

Another attempt was to sort them by the x-coordinate, then find the minimum. But this approach fails. Normal sorting by two coordinates fails and is highly unstable.

The problem resembles the TSP problem, but the "path" is not closed and metric used is L1 (Manhattan, TaxiCab).

The solution I am looking for will probably be approximate. Finding the minimal and the second minimal distance from every point and connecting them gives good but for sure not minimal sum.

The problem I am having is with giving the objective function.