Calculate the Shortest or Fastest Route
This use case explains how to parametrize the calculation of the "very shortest" or the "very fastest" connection from one location to another using the PTV xRoute service. The parametrization stays valid if a route
A route corresponds to a path of a vehicle through the underlying transport network. The main attributes of a route are the distance and the time that the vehicle travels along the path. through an arbitrary chain of locations
(often called a via route) is calculated.
The "very shortest" route connects two locations with the shortest possible path compared to all other paths. The "very fastest" route connects two locations with a path which takes the lowest possible driving time compared to all other possible paths.
The resulting course of the shortest or fastest route is almost always not immediately usable for car or truck drivers. E. g. the very shortest route will use any possible road from highways to forest roads and create a lot of right and left turns. It approximates the air line between start and destination on the road network and can be used as the lowest bound for distance (or driving time in case of the very fastest route) or as a course for pedestrians or bicyclists.
In general a parametrization similar to the shipped profiles A profile is a collection of parameters used to configure the request. Full profiles consist of a number of specialized sub-profiles like the VehicleProfile which describes the properties of a vehicle. is recommended.
Benefits
- Users learn how to parametrize the current use case.
- Calculation of the lowest bounds for distance and travel time.
- Basic insight into how to influence the course of a route.
Prerequisites
- An installed and licensed PTV xRoute service.
Concepts
The calculation of a route results in a path on the PTV xServer digital map which has the lowest possible rating. Often this rating of a certain path is called a cost function. The path is called a route. The cost function is calculated from properties which are attached to each road segment. An obvious example of such a cost function is the length of each road segment. Another one could be the travel time on each segment. To use the PTV xRoute service in the most flexible way the user is able to parametrize the cost function in various ways to fulfill his needs.
To search for the best rated path (route) all paths starting at a
certain location have to be evaluated in an efficient manner. The PTV
xRoute service uses a combination of acceleration mechanisms like
bidirectional search Bidirectional search is an exact algorithm to calculate the route between two waypoints. Thereby the search process is initiated at the start and at the destination waypoint. It reduces the number of road segments to be considered., AStar AStar is an acceleration technique for the search of the best route betweeen two waypoints. During the search process it prefers road segments which are geographically near the air line between the waypoints. or leveling Leveling is the heuristic acceleration of the search for the best route. It concentrates the search process to high level road segment like highways after a given distance from the waypoints is exceeded.. Most of these
mechanisms guarantee to find the best rated path in any case, but some of them are heuristics. Therefore in addition to parameters which define the
rating of a path also parameters which influence the algorithm can be
adjusted. All parameters are already preset to sensible default values in the PTV xRoute service. Such defaults are suitable for many standard situations.
Parametrization to calculate the shortest or the fastest route
In this use case only the length or the driving time of each road segment is used as cost function for calculating the route.
The table shows the field settings for the shortest or the fastest route:
| Field | Value | Remark | ||
|---|---|---|---|---|
| distanceTimeWeighting | 0/100 | Set to 0 for the shortest route or set to 100 for the fastest route. | ||
| Fields which control the routing algorithm. | ||||
| heuristicAggressiveness | 0 | Field which influences the search algorithm. See the API documentation for details. This field setting leads to an increased runtime for each routing. | ||
| minimumDistanceFromWaypoint[] | set all to UNBOUND | This setting disables a heuristic which is used to reduce the number of roads our algorithm considers for finding the best path. As a consequence the runtime for each routing is increased. | ||
| Set all fields controlling the course on the road network to 0. | ||||
| penalties[], violations.cost , rampPenalty, residentsOnlyPenalty, urbanPenalty, seasonalClosurePenalty, forbiddenLowEmissionZonePenalty, deliveryOnlyPenalty, deliveryOnlyGateCost, boatPenalty, railPenalty, uTurnCost | ||||
Programming Guide
The example below shows the calculation of the shortest route using the JavaScript bindings to the xRoute API:
var A = { "$type": "OffRoadWaypoint", "location": { "offRoadCoordinate": { "x": 6.097592281341554, "y": 49.60986178122983 } } }; var B = { "$type": "OffRoadWaypoint", "location": { "offRoadCoordinate": {"x": 6.103880139846803,"y": 49.60598956829434 } } }; var map = new L.Map('map', { center: [49.61, 6.125], zoom: 13 }); // Add tile layer to map var tileUrl = xServerUrl + '/services/rest/XMap/tile/{z}/{x}/{y}'; var tileLayer = new L.TileLayer(tileUrl, { minZoom: 3, maxZoom: 18, noWrap: true }).addTo(map); var outputString=''; function calculateSpecificRoute(dtw) { xroute.calculateRoute({ "waypoints": [A, B], "resultFields": { "polyline": true }, "requestProfile": { "routingProfile": { "searchSpace": { "heuristicAggressiveness": 0, "excludeByNetworkClass": { "minimumDistancesFromWaypoint": [ "UNBOUNDED", "UNBOUNDED", "UNBOUNDED", "UNBOUNDED", "UNBOUNDED", "UNBOUNDED", "UNBOUNDED", "UNBOUNDED" ] } }, "course": { "distanceTimeWeighting": dtw, "network": { "rampPenalty": 0, "penaltiesByNetworkClass": { "penalties": [0, 0, 0, 0, 0, 0, 0, 0] } }, "specialAreas": { "residentsOnlyPenalty": 0, "urbanPenalty": 0, "forbiddenLowEmissionZonePenalty": 0 }, "maneuver": { "uTurnCost": 0 } } } }, "geometryOptions": { "responseGeometryTypes": ["GEOJSON"] } }, function(route, exception) { var geoJson = route.polyline.geoJSON; if(dtw < 50) { displayGeoJson(geoJson, '#ffa225'); outputString += 'shortest route: '+ route.distance +' m in ' + route.travelTime + ' s '; } else { displayGeoJson(geoJson, '#2882C8'); outputString += 'fastest route: '+ route.distance +' m in ' + route.travelTime + ' s '; } print(outputString); }); } function displayGeoJson(geoJson,color) { var jsonObject = JSON.parse(geoJson); var geoJsonLayer = new L.GeoJSON(jsonObject, { style: { color: color, weight: 8 } }).addTo(map); map.fitBounds(geoJsonLayer.getBounds()); }; calculateSpecificRoute(0); calculateSpecificRoute(100);In the example above the shortest route (orange) and the fastest route (blue) are calculated and displayed together. The field distanceTimeWeighting is adjusted in the calculateSpecificRoute JavaScript callback function. For further information about the way this sample is implemented see the use-case Calculating a route
As mentioned above for the very shortest route only the length of each road segment is important, other road attributes are not considered at all. In this example the very shortest route consists of small roads with many turns. If penalties of 50 are set for the last four entries of penaltiesByNetworkClass, the orange route calculated with a distanceTimeWeighting of 0 is not anymore the very shortest route. In this case it is even identical to the fastest route since there are no other alternatives.
Related Topics
The following topics might be relevant for this use case.