Euclidean distance

[nielsenko]

It would be nice with an option to use Euclidean distance (and maybe Haversine).

For some large problems the runtime is dominated by matrix calculations, and perhaps you can accept a simple distance metric, without specifying it explicitly.

[jcoupey]

We used to have a dedicated wrapper to parse TSPLIB files and compute the matrix with euclidean distance back in v1.0.
I removed it to avoid supporting multiple input formats. It's been replaced with the ability to input a matrix. This is now how the various benchmarks are used (see *_to_json.py scripts here).

So the first answer would be that using euclidean (or any other) distance is doable with a pre-treatment to compute the matrix from your input problem.

Now including a way to use euclidean/Haversine out of the box could make sense and would be quite straightforward. Just like we have a RoutingWrapper class that has multiple children for specific routing engines, we could have an abstract DistanceWrapper class and a couple of children implementations for euclidean or Haversine.

The only limitation I can think of is that all time-related constraints (if used) need then be homogeneous with the computed distances.

@nielsenko happy to help and merge a PR if you feel like giving this a try!

[nielsenko]

Those input matrices just get really really big sometimes :-)

Anyway, challenge accepted, but I probably won't get around to it until August.

[nielsenko]

Wrt. time constraints, then I think specifying a speed when using either Euclidean or Haversine distance calculations will be required to map distances to durations.

[jcoupey]

Anyway, challenge accepted, but I probably won't get around to it until August.

Great, let me know if you need any other pointers to get started.

I think specifying a speed will be required

This is the tricky part as the input matrix is really expected to be durations because it's used to compute arrival times and decide validity wrt time windows constraints. The usual approach (at least for academic benchmarks) is to consider that euclidean distance is a duration, and set time windows accordingly.

As for introducing a scaling factor, I'm not too keen on expanding the API with something that is irrelevant for the "usual" routing wrappers. What about scaling the time windows values in input if required instead?

[nielsenko]

Okay. But requiring the user to scale his time windows is not the most intuitive interface.

[jcoupey]

requiring the user to scale his time windows is not the most intuitive interface.

Agreed. But we're talking about users that explicitly ask to compute costs that are distances (probably with something like -r euclidean instead of -r osrm) and at the same time provide time window constraints that are durations. Shouldn't those be aware there is some kind of mismatch here?

[jcoupey]

Since the last posts here, we now have the ability to use separate matrices for costs and travel times, which may simplify above concerns.

@nielsenko any chance of picking this up at some point or shall we simply close for lack of time/interest in the feature?

[nielsenko]

Yes, I'm unlikely to spend time on this, as I'm no longer involved with logistics