/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.

IMPORTANT: It's highly recommended that you review the Network Graphs & Solvers concepts documentation, the Graph REST Tutorial, and/or some /match/graph examples before using this endpoint.

Input Parameter Description

NameTypeDescription
graph_namestringName of the underlying geospatial graph resource to match to using input parameter sample_points.
sample_pointsarray of stringsSample 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 constant values, e.g., '{1, 2, 10} AS SAMPLE_TRIPID'.
solve_methodstring

The type of solver to use for graph matching. The default value is markov_chain.

Supported ValuesDescription
markov_chainMatches 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. Related options: num_segments and chain_width.
match_od_pairsMatches input parameter sample_points to find the most probable path between origin and destination pairs with cost constraints.
match_supply_demandMatches input parameter sample_points to optimize scheduling multiple supplies (trucks) with varying sizes to varying demand sites with varying capacities per depot. Related options: partial_loading and max_combinations.
match_batch_solvesMatches input parameter sample_points source and destination pairs for the shortest path solves in batch mode.
match_loopsMatches closed loops (Eulerian paths) originating and ending at each graph node within min and max hops (levels).
solution_tablestringThe name of the table used to store the results, in [schema_name.]table_name format, using standard name resolution rules and meeting table naming criteria. 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. Must not be an existing table of the same name. The default value is ''.
optionsmap of string to strings

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

Supported Parameters (keys)Parameter Description
gps_noiseGPS 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_segmentsMaximum number of potentially matching road segments for each sample point. For the markov_chain solver, the default is 3. The default value is '3'.
search_radiusMaximum 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_widthFor 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'.
sourceOptional 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'.
destinationOptional 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 The default value is true.

Supported ValuesDescription
truePartial off-loading at multiple store (demand) locations
falseNo partial off-loading allowed if supply is less than the store's demand.
max_combinationsFor the match_supply_demand solver only. This is the cutoff for the number of generated combinations for sequencing the demand locations - can increase this up to 2M. The default value is '10000'.
left_turn_penaltyThis will add an additonal weight over the edges labelled as 'left turn' if the 'add_turn' option parameter of the /create/graph was invoked at graph creation. The default value is '0.0'.
right_turn_penaltyThis will add an additonal weight over the edges labelled as' right turn' if the 'add_turn' option parameter of the /create/graph was invoked at graph creation. The default value is '0.0'.
intersection_penaltyThis will add an additonal weight over the edges labelled as 'intersection' if the 'add_turn' option parameter of the /create/graph was invoked at graph creation. The default value is '0.0'.
sharp_turn_penaltyThis will add an additonal weight over the edges labelled as 'sharp turn' or 'u-turn' if the 'add_turn' option parameter of the /create/graph was invoked at graph creation. The default value is '0.0'.
aggregated_outputFor the match_supply_demand solver only. When it is true (default), each record in the output table shows a particular truck's scheduled cumulative round trip path (MULTILINESTRING) and the corresponding aggregated cost. Otherwise, each record shows a single scheduled truck route (LINESTRING) towards a particular demand location (store id) with its corresponding cost. The default value is 'true'.
output_tracksFor the match_supply_demand solver only. When it is true (non-default), the output will be in tracks format for all the round trips of each truck in which the timestamps are populated directly from the edge weights starting from their originating depots. The default value is 'false'.
max_trip_costFor the match_supply_demand solver only. If this constraint is greater than zero (default) then the trucks will skip travelling from one demand location to another if the cost between them is greater than this number (distance or time). Zero (default) value means no check is performed. The default value is '0.0'.
filter_folding_paths

For the markov_chain solver only. When true (non-default), the paths per sequence combination is checked for folding over patterns and can significantly increase the execution time depending on the chain width and the number of gps samples. The default value is false.

Supported ValuesDescription
trueFilter out the folded paths.
falseDo not filter out the folded paths
unit_unloading_costFor the match_supply_demand solver only. The unit cost per load amount to be delivered. If this value is greater than zero (default) then the additional cost of this unit load multiplied by the total dropped load will be added over to the trip cost to the demand location. The default value is '0.0'.
max_num_threadsFor the markov_chain solver only. If specified (greater than zero), the maximum number of threads will not be greater than the specified value. It can be lower due to the memory and the number cores available. Default value of zero allows the algorithm to set the maximal number of threads within these constraints. The default value is '0'.
truck_service_limitFor the match_supply_demand solver only. If specified (greater than zero), any truck's total service cost (distance or time) will be limited by the specified value including multiple rounds (if set). The default value is '0.0'.
enable_truck_reuse

For the match_supply_demand solver only. If specified (true), all trucks can be scheduled for second rounds from their originating depots. The default value is false.

Supported ValuesDescription
trueAllows reusing trucks for scheduling again.
falseTrucks are scheduled only once from their depots.
max_truck_stopsFor the match_supply_demand solver only. If specified (greater than zero), a truck can at most have this many stops (demand locations) in one round trip. Otherwise, it is unlimited. If 'enable_truck_reuse' is on, this condition will be applied separately at each round trip use of the same truck. The default value is '0'.
server_idIndicates which graph server(s) to send the request to. Default is to send to the server, amongst those containing the corresponding graph, that has the most computational bandwidth. The default value is ''.
inverse_solve

For the match_batch_solves solver only. Solves source-destination pairs using inverse shortest path solver. The default value is false.

Supported ValuesDescription
trueSolves using inverse shortest path solver.
falseSolves using direct shortest path solver.
min_loop_levelFor the match_loops solver only. Finds closed loops around each node deducible not less than this minimal hop (level) deep. The default value is '0'.
max_loop_levelFor the match_loops solver only. Finds closed loops around each node deducible not more than this maximal hop (level) deep. The default value is '5'.
search_limitFor the match_loops solver only. Searches within this limit of nodes per vertex to detect loops. The value zero means there is no limit. The default value is '10000'.
output_batch_sizeFor the match_loops solver only. Uses this value as the batch size of the number of loops in flushing(inserting) to the output table. The default value is '1000'.

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:

NameTypeDescription
statusString'OK' or 'ERROR'
messageStringEmpty if success or an error message
data_typeString'match_graph_request' or 'none' in case of an error
dataStringEmpty string
data_strJSON or String

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

NameTypeDescription
resultbooleanIndicates a successful solution.
match_scorefloatThe mean square error calculation representing the map matching score. Values closer to zero are better.
infomap of string to stringsAdditional information.

Empty string in case of an error.