Version:

/match/graph

URL: http://GPUDB_IP_ADDRESS:GPUDB_PORT/match/graph

Matches a directed route implied by a given set of latitude/longitude points to an existing underlying road network graph using a given solution type. See Network Graph Solvers for more information.

Input Parameter Description

Name Type Description
graph_name string Name of the underlying geospatial graph resource to match to using input parameter sample_points.
sample_points array of strings Sample points used to match to an underlying geospatial graph. Sample points must be specified using identifiers; identifiers are grouped as combinations. Identifiers can be used with: existing column names, e.g., 'table.column AS SAMPLE_X'; expressions, e.g., 'ST_MAKEPOINT(table.x, table.y) AS SAMPLE_WKTPOINT'; or raw values, e.g., '{1, 2, 10} AS SAMPLE_TRIPID'.
solve_method string

The type of solver to use for graph matching.

Supported Values Description
markov_chain Matches input parameter sample_points to the graph using the Hidden Markov Model (HMM)-based method, which conducts a range-tree closest-edge search to find the best combinations of possible road segments (num_segments) for each sample point to create the best route. The route is secured one point at a time while looking ahead chain_width number of points, so the prediction is corrected after each point. This solution type is the most accurate but also the most computationally intensive.
incremental_weighted Matches input parameter sample_points to the graph using time and/or distance between points to influence one or more shortest paths across the sample points.
match_od_pairs Matches input parameter sample_points to find the most probable path between origin and destination pairs with cost constraints
match_supply_demand Matches input parameter sample_points to optimize scheduling multiple supplies (trucks) with varying sizes to varying demand sites with varying capacities per depot
solution_table string The name of the table used to store the results; this table contains a track of geospatial points for the matched portion of the graph, a track ID, and a score value. Also outputs a details table containing a trip ID (that matches the track ID), the latitude/longitude pair, the timestamp the point was recorded at, and an edge ID corresponding to the matched road segment. Has the same naming restrictions as tables. Must not be an existing table of the same name. The default value is ''.
options map of string to strings

Additional parameters. The default value is an empty map ( {} ).

Supported Parameters (keys) Parameter Description
gps_noise GPS noise value (in meters) to remove redundant sample points. Use -1 to disable noise reduction. The default value accounts for 95% of point variation (+ or -5 meters). The default value is '5.0'.
num_segments Maximum number of potentially matching road segments for each sample point. For the markov_chain solver, the default is 3; for the incremental_weighted, the default is 5. The default value is ''.
search_radius Maximum search radius used when snapping sample points onto potentially matching surrounding segments. The default value corresponds to approximately 100 meters. The default value is '0.001'.
chain_width For the markov_chain solver only. Length of the sample points lookahead window within the Markov kernel; the larger the number, the more accurate the solution. The default value is '9'.
max_solve_length For the incremental_weighted solver only. Maximum number of samples along the path on which to solve. The default value is '200'.
time_window_width For the incremental_weighted solver only. Time window, also known as sampling period, in which points are favored. To determine the raw window value, the time_window_width value is multiplied by the mean sample time (in seconds) across all points, e.g., if time_window_width is 30 and the mean sample time is 2 seconds, points that are sampled greater than 60 seconds after the previous point are no longer favored in the solution. The default value is '30'.
detect_loops

For the incremental_weighted solver only. If true, a loop will be detected and traversed even if it would make a shorter path to ignore the loop. The supported values are:

  • true
  • false
source Optional WKT starting point from input parameter sample_points for the solver. The default behavior for the endpoint is to use time to determine the starting point. The default value is 'POINT NULL'.
destination Optional WKT ending point from input parameter sample_points for the solver. The default behavior for the endpoint is to use time to determine the destination point. The default value is 'POINT NULL'.
partial_loading

For the match_supply_demand solver only. When false (non-default), trucks do not off-load at the demand (store) side if the remainder is less than the store's need

Supported Values Description
true Partial off loading at multiple store (demand) locations
false No partial off loading allowed if supply is less than the store's demand.
max_combinations For the match_supply_demand solver only. This is the cutoff for the number of generated combinations for sequencing the demand locations - can increase this upto 2M. The default value is '10000'.

Output Parameter Description

The GPUdb server embeds the endpoint response inside a standard response structure which contains status information and the actual response to the query. Here is a description of the various fields of the wrapper:

Name Type Description
status String 'OK' or 'ERROR'
message String Empty if success or an error message
data_type String 'match_graph_request' or 'none' in case of an error
data String Empty string
data_str JSON or String

This embedded JSON represents the result of the /match/graph endpoint:

Name Type Description
result boolean Indicates a successful solution.
match_score float The mean square error calculation representing the map matching score. Values closer to zero are better.
info map of string to strings Additional information.

Empty string in case of an error.