Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

Shortest path routing will often return routes with a lot of turns (zigzag shape).

If you want to get routes with fewer turns, you can use turn penalties to make turning more "expensive".

What are best practices for determining such turn penalties?

The use case: I would specifically like to get fuel-efficient routes for vehicles. Slowing down, turning and accelerating costs more fuel than driving straight ahead. (Traffic signs - such as stop signs - don't have to be considered.)

share|improve this question
1  
It's a great question, but I believe the answer will depend on your application. For instance, when routing pipes that carry gases or fluids, the cumulative penalty can be computed from physical principles and depends both on the numbers of turns and on the turn angles. So, what application(s) do you have in mind? –  whuber Jan 24 '12 at 21:22
7  
UPS shipping is a great example of this topic. They have their own route management rules that they have applied to save on time and money, which even includes never making left turns‌​. While not an answer, maybe they can help guide your direction. Penn State has a good video in their GeoSpatial Revolution series on this topic, too. –  RyanDalton Jan 24 '12 at 22:04
    
The typical options in GPS routing systems are shortest time and shortest distance. The problem then lies in the cost based heuristic formulas used in these systems do kinda suck. In the end "heuristic" is just another name for guessing. A heuristic is only as good as your data and your mathematical model of the real world. –  Stephen Quan Jan 25 '12 at 3:44
    
@BicycleDude I do not think that heuristics "suck", rather GIS solutions usually work best on "macro" rather than "micro" problems. Turning penalties and restrictions are analyzed for a small number of intersection(s) (micro level) as apposed to applying generic factors (macro). To model trip volumes, usually a modeller does an intersection per intersection analysis to determine the penalties based on volumes, gaps, green cycles, geometric layout, etc. After determining those values you can initiate the trip assignment phase to get a modeled output for volumes per roads –  dassouki Jan 25 '12 at 13:17
    
I am curious to know how you ended up solving this problem –  dassouki Aug 2 '12 at 14:39
add comment

2 Answers 2

Disclaimer: I haven't been up to speed on the research or best practice on this so forgive me if I miss anything and it's been 3 years since I worked with a Travel Demand Model. And when I did travel demand models, I didn't spend a whole lot of time and effort into building turning penalty/restriction models.

Turning restrictions and penalty settings (TR/TP) for the most part are different from intersection to intersection. Usually you can lump sum them into different groups if you're doing macro type analysis.

TR/TP values are usually deployed in the "trip assignment" phase of a modelling process when you know the volumes at each leg of an intersection as well as the intersection geographic layout and green cycle time configuration. Other variables that come into effect are arrival rates, queues, peak hour factors, Average Annual Daily Traffic, Hourly volume data, headways, gaps, etc.. Please check some of the books and publications especially from ITE and TRB. If you are in a university or have access to an academic search engine, metapress has a plethora of articles on turning restrictions and penalties

Some of the issues to consider:

Intersection Type and Configuration

The first issue to look at is signalized vs. non-signalized intersection. In non-signalized intersections, right turns from the major to minor road have a low turning penalty; however, left turning in any direction has a very high turning penalty. Right turns from Minor to Major have a mediocre turning penalty. However, these number change if let's say downstream from the non signalized intersection you have a traffic light. This will generate enough of a natural gap for vehicles to be able to do their turns. On the other hand if let's say you know there is a big generator close by (apartment building or grocery store), then you might have platoons coming up in one direction. For example, vehicle exiting the grocery store onto the major street want to turn left on the minor street. This demand can happen for a very short period during but it could cause massive traffic pattern implications.

In signalized intersections, the main issue becomes the intersection Geometry. The few things to look for are green times including advanced greens, dedicated greens etc, dedicated lanes, and if the dedicated lanes go far enough that in the case of other lanes getting clogged up, does it affect the usage of the dedicated lane. For example an intersection with an advanced green turning left with a dedicated lane will have a low-ish turning penalty value; however, a leg of an intersection that is sharing left/through lanes with no dedicated green turning will have a very high TR/TP. The other thing to look for in signalized intersections is right pocket lanes. At some intersections vehicles will have a dedicated right turning lane. if the lane is long enough and extends far enough then it'll have a low turning penalty otherwise it'll be high.

Calculation method(s)

This is by no means is an exclusive list of methods to calculate TR/TP. Also for the following few days I don't have access to my Highway capacity manual, ITE trip generation manuals, Transportation Planning handbook, and modelling transport book. I have a fewer selection of manuals on me and here is what they have to provide on this issue:

Note that this is my initial take on the matter. I am missing a lot of technical information that is not included in this answerI will probably update this answer more in 24 hours or so. I hope this helps

share|improve this answer
    
this link is broken unfortunately: people.hofstra.edu/geotrans/eng/ch2en/meth2en/turnpenalty.html –  underdark Jul 13 '13 at 10:59
add comment

I'm not sure if a turn would need a penalty if it is, in fact, the shortest route; the alternate would require a longer distance and impose it's own penalty in time and money.

If the turn gets you on to a higher value network that has less turns and higher speeds, better surfaces such as interstates and major inter regional roads I would give a positive value. If the trun takes you down into a less optimized network such as city grid local traffic I might impose a negative values. FCC classifications and speeds, sharp angles could be give a segment by segment values that totals per intersection object or sums per routing interval.

I guess my point is that a turn is a sum of other factors that intersect at objects called intersections that = high valence nodes where a decision point is reached that have attributes that can be values differently and summed. You would need to tune your algorithm and define your intersection objects, perhaps by polygonizing or valuing paths through object based on fcc, speed, angle and restrict path segments based on rule sets for local vs interregional transit. Fuel cost and speed would be the greatest optimizers, angles would have a speed cost that might be compensated by entering the optimized network.

Further costs could be calculated for dropping form higher to lower and back again as this would indicated non optimized routing legs.

share|improve this answer
1  
but at an intersection, isn't there a penalty for a vehicle turning left vs. right. Assuming that you can turn right on red versus you have to wait for your own light on left. The other situation is that if there is always queuing on a particular direction of the intersection. so Leg 1 through always has a queue and therefore prevents vehicles from turning left or right. –  dassouki Jul 12 '13 at 14:07
    
Without turn penalty, a zig-zag route which is only a little shorter based on link travel times would be preferred to a much better route with fewer turns which in reality is going to be much faster because you don't get stuck at intersections trying to turn. –  underdark Jul 13 '13 at 10:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.