Route Matcher

Algorithm

At each step, the algorithm stores only a maximum number of paths (the number is configurable) that are considered to be the “best” paths according to a cost function assigned to each path by the algorithm. The main steps of the algorithm are:

The algorithm starts associating some arcs to the first point.
At the n^thpoint, the algorithm considers a list of plausible paths, built during the n−1 previous steps.
- If the (n−1)^th and the n^th points are close enough (the threshold is configurable), a recursive function to find the path connecting them is applied.
- If the two points are instead far enough (according to the same threshold as above), the A* algorithm that finds some path connecting the points is applied.
Once some path has been found, these points are connected to the path determined in the previous step.

The cost function is computed as a weighted sum of several functions:

Sum of GPS point-link distances.
Sum of difference between travel time and timestamps associated to GPS points (0 for route matching).
Sum of the difference between the straight-line distance of the GPS points and the distance needed to cover the path between the feet of the GPS points projections.
Sum of penalties for U turns.
Sum of angles between the GPS points’ direction and the path’s direction.

The best paths are those that have the lowest score of the cost function.

Request Endpoint

Request

POST optima-wsi/routeMatcher/<strt>

POST optima-wsi/routeMatcher/<link>

Request resource

Not applicable.

Request parameters

Not applicable.

Request content-type

XML/JSON

Request body (payload)

The payload is defined as a list of points.

Payload JSON: example

{
"points": [
    {
        "x": 55.099991,
        "y": 25.024388
    },
    {
        "x": 55.146617,
        "y": 25.070885
    }
]
}

Payload XML: example

<locationRequest>
    <points>
        <x> 55.099991 </x>
        <y> 25.024388 </y>
    </points>
    <points>
        <x> 55.146617 </x>
        <y> 25.070885 </y>
    </points>
</locationRequest>

Response

Response status

HTTP status	Description
200 OK	Result of the processed request.
429 Too many requests	In a specific time interval, too much requests directed to the service (rate-limiting schemes).

Response content-type

JSON or XML

Response output

The default output you get is a JSON object containing a map-matched route on the street or link.

To have a response in XML instead of default JSON, can be used the following header in the request:

'Accept: application/xml'

Example: response based on a JSON object containing a route (street)

Request

https://<OPTIMA_HOST_IP_ADDRESS>:<PORT_NUMBER>/optima-wsi/routeMatcher/strt

Response status

HTTP status	Description
200 OK	The processing request has been accepted.

Response output

{
    "route": [
        {
            "id": 1,
            "part": 1,
            "link": [
                {
                    "order": 1,
                    "idno": 923510078,
                    "fromNode": 190843,
                    "toNode": 190841,
                    "startProg": 0.824957548110839,
                    "endProg": 1.0
                },
...,
                {
                    "order": 97,
                    "idno": 1034855519,
                    "fromNode": 4460,
                    "toNode": 275807,
                    "startProg": 0.0,
                    "endProg": 0.3889309070600028
                }
            ],
            "shape": "MULTILINESTRING ((55.0999506444302 25.024401573167847, 55.10029 25.02523, 55.1005700002 25.0258399999), ..., (55.1464600002 25.0704999999, 55.14669203115147 25.070843406075713))",
"direction": null
        }
    ],
    "isError": false,
    "message": null
}

Example: response based on a JSON object containing a route (link)

Request

https://<OPTIMA_HOST_IP_ADDRESS>:<PORT_NUMBER>/optima-wsi/routeMatcher/link

Response status

HTTP status	Description
200 OK	The processing request has been accepted.

Response output

{
    "route": [
        {
            "id": 1,
            "part": 1,
            "link": [
                {
                    "order": 1,
                    "idno": 923510077,
                    "fromNode": 160014,
                    "toNode": 190844,
                    "startProg": 0.8654095730152781,
                    "endProg": 1.0
                },
...,
                {
                    "order": 32,
                    "idno": 1034855519,
                    "fromNode": 4457,
                    "toNode": 275807,
                    "startProg": 0.0,
                    "endProg": 0.5923467500897718
                }
            ],
            "shape": "MULTILINESTRING ((55.0999506444302 25.024401573167847, 55.10029 25.02523, 55.1005700002 25.0258399999, 55.10062 25.02595, 55.1006700002 25.0260599999, 55.10086 25.02646, 55.1010500002 25.0268599999), ..., (55.1461800002 25.0700499999, 55.1464600002 25.0704999999, 55.14669203115147 25.070843406075713))",
            "direction": null
        }
    ],
    "isError": false,
    "message": null,
    "referencePoint": [
        {
            "point": {
                "x": 55.0999506444302,
                "y": 25.024401573167847,
                "order": 1
            },
            "strtName": " E11 - Sheikh Zayed Road"
        },
        {
            "point": {
                "x": 55.14669203115147,
                "y": 25.070843406075717,
                "order": 2
            },
            "strtName": " D86 - First Al Khail Street"
        }
    ]
}