Route Selection

Characteristic

Short description

Route Selection = Selection of the "best" route

Detailed Consideration

In the following the concepts that are offered to influence the route selection are described. In particular, the effect of routing profile parameters on the route selection is shown. Note that the route selection is done in the same way for all PTV xServer services involving routes.

Route Selection by Abstract Costs

By default each route is assigned an abstract routing cost. The routing cost cannot necessarily be assigned a unit like seconds or meters since it is a combination of different parameters which will be explained in more detail below.

More precisely, each road segment is assigned a routing cost based on its distance and travel time. Also the other segments of the transport network like rail or boat connections are assigned such a cost. These routing costs of single segments can easily be extended to routes. The routing cost of a route is the sum of the routing costs of all segments of the route.

The route selection is done solely based on the routing cost. The best route is a valid route with minimal routing cost.

Distance-Time Weighting

As is explained in more detail in the article travel speed and travel time, each segment of the transport network is assigned a distance and a travel time (the latter depends on the vehicle).

The basic routing cost of a segment is a linear combination of its distance (in meters) and travel time (in seconds multiplied with 10), weighted with the field distanceTimeWeighting:

basicRoutingCost = distanceInMeters * (100 - distanceTimeWeighting) / 100 + travelTimeInSeconds * 10 * distanceTimeWeighting / 100

For example, assume a distanceTimeWeighting of 70%. For a road segment with distance 120m and travel time 6s the basic routing cost is calculated as 120 * 0.3 + 6 * 10 * 0.7 = 36 + 42 = 78.

Relative Penalties

For a more flexible route selection based on further attributes of the segments the basic routing cost may be modified by penalties. Penalties are profileClosed 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. parameters, and each penalty is applied only to segments of the transport network with specific attributes. For example, the tollPenalty is applied only to toll roads and a toll penalty of more than 0 has the effect that routes with toll roads get a higher routing cost and thus are more likely avoided in the route selection.

A penalty is an integer value in the range [-99, 2501]. The value of 2501 is a special case: the segments connected to a penalty of 2501 will be treated like prohibited segments. Prohibited segments are treated as if they do not exist at all for route selection. For all other penalties the basic routing cost of a segment is multiplied by (penalty + 100)/100. Because of this multiplication the penalties are relative to the basic routing cost and thus relative to the distance and travel time of the segment.

A negative penalty reduces the basic routing cost and thus has the effect that routes with such segments are usually preferred for route selection.

Absolute Costs

In some cases relative penalties are not useful. For example, we might want to prefer routes without a U-turn to those with a U-turn. However, a U-turn is not a segment attribute, it is a maneuver at a certain point in the road network. In such cases we allow to add absolute routing costs, for example see the profile field uTurnCost.

Route Selection by Monetary Costs

With the introduction of the monetary cost options it is not only possible to retrieve the monetary costs report of a route but also to calculate the route with the lowest monetary costs. This route selection by monetary costs can be enabled by setting the calculationCriteria to MONETARY_COSTS in the route options.

Monetary Distance and Time Cost

The costs of a segment are not abstract costs based on a distance-time weighting as described in the previous section, but instead actual monetary costs per distance and time unit specified in the monetary cost options are used.

For example, assume that one kilometer costs 1 euro and one hour costs 10 euros. For a road segment with distance 120m and travel time 6s and without toll costs the basic routing cost is calculated as (1 * 120 / 1000) + (10 * 6 / 3600) = 0.12 + 0.01666 = 0.013666 euro.

Toll Costs

Since our distance and time costs are now monetary costs, also toll costs - which are naturally monetary costs - are added. The toll prices are now accurately integrated into the cost model, which is one major advantage compared to the abstract cost model.

Note that with increasing cost values for time and distance the impact of the toll costs on the route selection diminishes.

Energy Costs

Energy costs are usually part of the costs per kilometer. However, it is also possible to configure the energy cost separately as cost per fuel unit and/or as cost per electricity unit. The benefit of doing this is that the energy consumption depends on the vehicle's speed, which can even be customized with the consumption factors per speed. At low speeds in cities with stop-and-go traffic the energy consumption is relatively high compared to traveling constantly at 80 km/h, and using such energy costs has the effect that the low-speed inner city roads are rather avoided. This yields more practical routes. If the cost per energy unit is used, the energy cost of the route is reported separately.

For example, assume we use fuel costs of 1 euro for a liter Diesel and an average fuel consumption of 35 liters per 100 km. That means the average energy cost per kilometer is 0.35 euro. Since we now calculate the energy cost separately we reduce the general cost per kilometer from the example above from 1 euro to 0.65 euro. The energy cost of a segment now depends on its speed: With a consumption factor of 1.7 at 10 km/h we calculate the energy costs with 0.595 euro per kilometer, whereas with a consumption factor of 0.8 at 80 km/h we calculate with 0.28 euro per kilometer.

Relative penalties

The relative penalties of the routing profile are not considered in the optimization for monetary costs, except they have the special value of 2501 which means the segments connected to those penalties are treated as prohibited segments.

Another exception concerns the residents only penalty and the delivery only penalty. If violations are enabled, here a value of 2500 (which is the default value) has the same effect as a value of 2501: the segments connected to the penalty are treated as prohibited segments.

Further Parameterization and Behavior

Violations are supported and the costs for a violation are determined internally like for standard route calculation.

The parameter uTurnCost is not used and instead determined internally.

Currently only conventional routing in xroute is supported. If it is important to be sure that the optimal route with the lowest monetary cost is calculated it is recommended to disable the heuristics for conventional routing (see Troubleshooting below). In particular, we recommend to set the heuristic aggressiveness to 0.

Good to know

Troubleshooting

With conventional routing (i.e., no high-performance routing) some heuristics are applied for performance reasons. For standard situations these heuristics are most suitable, but the optimality of the route cannot be guaranteed in all cases. There is a trade-off between routing performance and optimality of the solution. The heuristics can be parameterized and even disabled with the search space profile fields, see also the integration sample calculate the shortest or fastest route.

There is a a similar trade-off for banned turns and U-turn costs. By default, a heuristic is applied with good routing performance, but also this heuristic can in rare cases cause not optimal routes. If you experience obviously wrong routes the heuristic can be switched off by setting the field useFastTurningBanHeuristic to false.