Route Selection = Selection of the "best" route
The simplest task of route calculation may be defined as: Given a vehicleThe term vehicle describes what is being routed or planned for. Vehicles are used in route calculation, distance matrix calculation and effectively also in tour planning. In route calculation, vehicle properties like overall size, weight and speed are in focus. In tour planning, it is vehicle properties like capacity and availability. Commonly a vehicle is motorized, like a truck - including its trailer or a car. However also a bike or even a pedestrian are included in this definition., a start and a destination waypointA waypoint is a geographic location used to specify start, destination and possible stopovers for a route., select from the usually many possible routes the "best" route through the transport network for the vehicle to travel from start to destination.
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.
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.
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 and travel time, weighted with the field distanceTimeWeighting. The travel time in seconds is multiplied by the distanceTimeWeighting and the distance in meters is multiplied by . The division by 10 is done in order to make sure that with a distanceTimeWeighting of 50% a distance of 10m corresponds to a travel time of 1s.
For example, assume a distanceTimeWeighting of 70%. For a road segment with travel time 6s and distance 120m the basic routing cost is calculated as .
For a more flexible route selection based on further attributes of the segments the basic routing cost may be modified by penalties. Penalties are profileA 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 . 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.
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.
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.
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 travel time 6s and distance 120m and without toll costs the basic routing cost is calculated as euro.
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 are usually part of the costs per kilometer. However, it is also possible to configure the energy cost separately as cost per energy 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 an energy cost 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.
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.
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.
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.
|Integration Sample||Calculating a route|
|Integration Sample||Calculate the shortest or fastest route|
|Integration Sample||Calculating the best route for rush hour traffic|