OSRM wrong waypoint index?

1
votes

I'm trying to use OSRM to get a list of locations ordered by the distance between them. For that I'm using the Trip service (https://github.com/Project-OSRM/osrm-backend/blob/master/docs/http.md#trip-service).

Given the encoded polyline:

omq~Fji_vOg@sHQcnAjCtrAkCs|AvHpcBwCeeB

I receive the following:

"waypoints": [
        {
            "waypoint_index": 0,
            "trips_index": 0,
            "hint": "RzfEg1U3xIPaAAAAJgAAAAAAAAAAAAAANgAAAAoAAAAAAAAAAAAAAHM6AACFecb6__B-AoR5xvoQ8X4CAACPBd_PZ4A=",
            "name": "",
            "location": [
                -87.656059,
                41.873663
            ]
        },
        {
            "waypoint_index": 2,
            "trips_index": 0,
            "hint": "OTfEg5M4xINDAwAAnwEAAAAAAAAAAAAA0AAAAGgAAAAAAAAAAAAAAHM6AACJf8b6xvF-Aoh_xvrY8X4CAADPEN_PZ4A=",
            "name": "",
            "location": [
                -87.654519,
                41.873862
            ]
        },
        {
            "waypoint_index": 5,
            "trips_index": 0,
            "hint": "WuVchFzlXIQ6AwAAbwUAAAAAAAAAAAAAzgAAAFwBAAAAAAAAAAAAAHM6AAD3sMb6EPN-Avywxvoy8n4CAACfBd_PZ4A=",
            "name": "",
            "location": [
                -87.641865,
                41.874192
            ]
        },
        {
            "waypoint_index": 1,
            "trips_index": 0,
            "hint": "PDfEg343xIOuAQAAggQAAAAAAAAAAAAAawAAACEBAAAAAAAAAAAAAHM6AACsfMb6su9-Aq58xvp2734CAADPEN_PZ4A=",
            "name": "",
            "location": [
                -87.655252,
                41.87333
            ]
        },
        {
            "waypoint_index": 3,
            "trips_index": 0,
            "hint": "VuVchFjlXITqAQAA0QEAAAAAAAC1BAAAegAAAHUAAAAAAAAALQEAAHM6AACYtsb6L_J-AjK3xvoy8n4CAABvFt_PZ4A=",
            "name": "",
            "location": [
                -87.640424,
                41.873967
            ]
        },
        {
            "waypoint_index": 6,
            "trips_index": 0,
            "hint": "6WJUhBgEhoTTBAAAdgQAAAAAAAAAAAAANAEAAB4BAAAAAAAAAAAAAHM6AAAJesb6H-x-Alh4xvoa7H4CAAB_Ft_PZ4A=",
            "name": "",
            "location": [
                -87.655927,
                41.872415
            ]
        },
        {
            "waypoint_index": 4,
            "trips_index": 0,
            "hint": "TOVchFDlXIRTAgAAhQEAACoAAADuAAAAlAAAAGIAAAAKAAAAPAAAAHM6AAAtuMb6FvB-Aja4xvoS734CAQCPBd_PZ4A=",
            "name": "",
            "location": [
                -87.640019,
                41.87343
            ]
        }
    ]

URL for testing: http://router.project-osrm.org/trip/v1/driving/polyline(omq~Fji_vOg@sHQcnAjCtrAkCs|AvHpcBwCeeB)?overview=false

This is how they were plotted (for better understanding): enter image description here

If I understood the docs correctly, waypoint_index was supposed to provide the order of the locations by distance. If so, it doesn't seem to be working given the result. Check it here:

Wanted

Group 1
lat: 41.87368, lon: -87.65606
lat: 41.87388, lon: -87.65452
lat: 41.87327, lon: -87.65525
lat: 41.87241, lon: -87.65636

Group 2
lat: 41.87317, lon: -87.64001
lat: 41.87397, lon: -87.64186
lat: 41.87397, lon: -87.64027

Actual

Group 1
lat: 41.873663, lon: -87.656059
lat: 41.87333, lon: -87.655252
lat: 41.873862, lon: -87.654519

Group 2
lat: 41.873967, lon: -87.640424
lat: 41.87343, lon: -87.640019
lat: 41.874192, lon: -87.641865

Group 1
lat: 41.872415, lon: -87.655927

As you can see the order provided by waypoint_index under Actual does exclude the last item from its supposed group (1). I think this might be related to the roundtrip option, is this the case? If so, is there an option I can set on the trip service that will provide me with the result I need?

Or, is there another service that will receive a list of locations and return them ordered by the distance between them? Given that I can't provide the start/end.

I'd like to just send a list of locations and receive them ordered by proximity, not using roundtrip (if that's what's breaking the previous request).

Thanks!

1
osrm

1 Answers

1
votes

ordered by the distance between them

What the trip service does is order them in a way that minimizes the total drive-time if you need to visit all waypoints, not cluster them by straight-line distance.

If you look at the route that was actually generated, the order makes sense: It is a circular trip that includes all provides locations (and at least looks optimal)

route