How do I correctly map U-turns in the SQL restriction data?

hluening · April 29, 2026, 3:40pm

Hi everyone, I hope someone here can help me with my problem. I’m trying to set up a routing algorithm that can calculate routes on a custom forest road network. It should also be able to reflect turn restrictions.

My problem is that I can’t properly handle U-turns. Using the path array, I can specify a sequence of edges that must not be used. If I were to model a U-turn, this would result in the same ID in both the from and to fields [edge_id, edge_id]. However, this doesn’t indicate which node this restriction applies to.

Example
If I enter the constraint [1,1], it’s not clear whether it applies to a U-turn at node A or B.

A <—1—> B <—2—> C

To Reproduce
Here is a short code snippet you can use to test the behavior.

DROP TABLE IF EXISTS test_edges;
CREATE TEMP TABLE test_edges (
    id           BIGINT PRIMARY KEY,
    source       BIGINT,
    target      BIGINT,
    cost        DOUBLE PRECISION,
    reverse_cost DOUBLE PRECISION
);

INSERT INTO test_edges VALUES
    (1,  1, 2,  10.0, 10.0),  -- e1: 1 <-> 2
    (2,  2, 3,  10.0, 10.0),  -- e2: 2 <-> 3
    (3,  3, 4,  10.0, 10.0),  -- e3: 3 <-> 4
    (4,  4, 1,  50.0, 50.0);  -- e4: 

DROP TABLE IF EXISTS test_restrictions;
CREATE TEMP TABLE test_restrictions (
    path BIGINT[],
    cost DOUBLE PRECISION
);

INSERT INTO test_restrictions VALUES
    (ARRAY[1,1],99999.0);

SELECT *
FROM pgr_trsp_withpoints(
    'SELECT id, source, target, cost, reverse_cost FROM test_edges',
    'SELECT path, cost FROM test_restrictions',
    'SELECT pid, edge_id, fraction, side
     FROM (VALUES 	(1::BIGINT, 1::BIGINT, 0.5::DOUBLE PRECISION, ''r''::CHAR),
	 				(2::BIGINT, 4::BIGINT, 0.9::DOUBLE PRECISION, ''b''::CHAR))
          AS p(pid, edge_id, fraction, side)',
    ARRAY[-1]::BIGINT[],
    ARRAY[-2]::BIGINT[],
    directed := true,
	details => true
);

Expectation
I can’t imagine being the first person to encounter this problem, so I hope there’s a solution. I would have expected it to be possible to specify a via node to improve the assignment (similar to specifying OSM restrictions).

The only solution I can see right now is to split the edges into forward and backward edges and set the source and target correctly. I would then use these edges to create the restrictions. However, this would double the size of my routing network, and I would have to rewrite a lot of the logic to accommodate it.

Platform/versions
Unfortunately, I’m stuck with pgrouting 3.5, since that’s the latest version available for postgresql for azure.

cvvergara · May 1, 2026, 2:53pm

Hello,

I really do not understand what is your goal.
You want to be able to do U turns?
You do not want to be able to do U turns.

part 1:
The question:
How do I correctly map U turns in SQL.

For me the word “map” I take it as a verb, so for my point of view is more data thing:
here

You can see that you can make a uturn

The line from b->e is the U turn.
Remember we are talking about graphs here, not geometries

In this case

The street is a closed road, so its a two way street, but there is no uturn mapped

(DE for dead end)
shortest path from a to c is a->b->c
Dijkstra algorithm will never take a->b->DE->b->c because then it:

wouldn’t be the shortest path
would be visting the same node twice.

BUT
if for what ever reason you need to map the road to be able to do a U t urn

You just need to add a couple of nodes, so there is a way in and out
(yet again the shortest path from a to c will not take that loop)

part 2:
Everything else in the message is about using pgr_trst_withPoints

But first I will go with the idea you are transmitting:

Example
If I enter the constraint [1,1], it’s not clear whether it applies to a U-turn at node A or B.
A <—1—> B <—2—> C

first interpretation
From the graph: A <—1—> B <—2—> C
so from 1 you can go to A & B
from 2 you can to to B & C
From A, B and C you can not go anywhere (they are dead ends)
The graph looks:

second interpretation
From the graph: A <—1—> B <—2—> C
So the original graph is:

because you are using with points:
the graph gets modified as follows:

Dijkstra, will never ever do a U turn ( aka pass thru the same vertex twice)
Turn restrictions: basically is "sequence of edges that you are not allowed to take.

the TRSP part will:
do a dijkstra: finds a solution, checks if part of the solution passes thru the sequence of edges, if it does it will look for an alternative, if it does not find it then it will return the dijkstra.
In this case there are no alternatives (why use TRSP?)

Regards
Vicky

cvvergara · May 1, 2026, 2:56pm

Forgot to mention:
in Discourse use [graphviz] (graphvizcode) [/graphviz] to write graphs
test your code here

regards

hluening · May 4, 2026, 9:40am

Hello,

First of all, thank you for your answer. I see some flaws in my description of the problem, so I will try to explain it in more detail. Thanks also for the tip to use graphviz!

In my dataset, the network is relatively simple, with most of the connections being straightforward. It only consists of bidirectional edges and nodes. Every turn restriction is mapped as a point object linked to an edge. Therefore, I need to construct turn restrictions depending on edges leading to and from junctions/nodes. Turn restrictions such as “no left/right turn” work fine. However, the “u-turn2 restriction causes problems in the network because only allowed turning points are specified in the dataset. Therefore, I need to allow U-turns at specified turning points and forbid them at every other node. In my original post, I wanted to ask how U-turn restrictions are constructed in general. I will try to explain my issues using this graph as an example: (f = turning point).

The function pgr_trsp_withPoints is doing u-turns at every node. With no restrictions set, the returned route will turn around at every node.

Here I added two temporary points via the points sql. The network got driving side=”r”. Point 1 got side=”b” and point 2 got side=“r”.

Route from 2 to 1: (Nodes) 2 → e → c → b → 1, (Edges) e4, e4, e2, e1
(While this representation of edge e4 is not semantically correct, it reflects how pgRouting displays the route when temporary nodes are used.)

Now, I want to restrict the network, that I get the correct route: 2 → e → f → e → c → b → 1. In my understanding, I need to restrict every node apart from the turning point. If I want to tackle this problem only with restrictions, I would set every edge at a node as [to_edge,from_edge] with the same id. For example at node e: [e4,e4], [e5,e5]. But at node f a turn around would be allowed, so I need to delete the [e5,e5] restriction, which would allow the turn around at node e from f (f → e → f).

I hope to handle this problem only via restrictions so that I don’t have to add any new nodes or edges. If that’s possible, I’d really appreciate it. But based on what I understand so far, I don’t see any way around solving this problem other than by making some adjustments to the network.

Idea: I split the bidirectional edges into two unidirectional edges. That way, each direction would have a unique ID, and I could use the restrictions to specify the exact edges. (Sorry for the poor rendering… I really tried )

Now I can specify the turn restrictions exactly. No U-turns at node e: [e5_2, e5_1], [e4_1, e4_2]. In that case, the sequence [e5_1, e5_2] would be free, and a U-turn at edge f would be possible.

This strategy involves a certain amount of effort, since the edges and logic would need to be adjusted in the background. That’s why I was hoping to be able to solve the problem using restrictions alone.

If you have any other ideas on how I can solve this in a smart way, please let me know! Feel free to suggest them!

Best regards
Hendrik

cvvergara · May 6, 2026, 9:03pm

I think I get what is your problem:

Lets clear some statements,

statement 1

Dijkstra algorithm will never use the same vertex twice.

You are in vertex 2 and want to go to vertex 1, given this graph

the route is:

The solution you need:

Basically because node f is where vehicles are allowed to do U turns is the reason you want that solution.

Is using twice vertex e which contradicts the statement: Dijkstra algorithm will never use the same vertex twice.
Therefore: Dijkstra (or trsp, or the withPoints family of functions which use Dijkstra under the covers) is/are not the algorithm to use.

How to exit a cul de sac

Given: the nodes where a u-turn can be done. (p, z, and many more from other culdesac)
Find those dead ends with pgr_degree

Is a Street(s) with only one combined inlet and outlet.

solution I think I can think

Given the culDeSac and vertex 2 in the culDeSac

If located in point 2 with direction to p, The shortest path to the exist of the culDeSac is

2->n->x->w->culdesac
The edges table has the following row
(id, source, target,cost,reverse_cost)=(e1, x, n, 5, 5)

So lets break the problem into two parts.
part 1: do not include the edge n->x
(id, source, target,cost, -reverse_cost)=(e1, x, n, 5, 5)

so now the graph looks like:

Then you don’t get a solution, but because you have the node ids where a U-turn can be done (p, z, and many more from other culdesac)
Then do a pgr_dijkstraNear From 2. That will find the closest node-route where a u turn can be done.
2->n->p

part 2
Then from start vertex p using the original graph you find the route to 1
p->n->x->w->culDeSac → … ->1

paste the two routes:
2->n->p->n->x->w->culDeSac → … ->1

Are we good with the statement: Dijkstra algorithm will never use the same vertex twice. ?
Yes, because the solution is using the same vertex n twice, but its because it is done with 2 different Dijkstra calls.

Let me know if this is what you need?

Regards:
Vicky

hluening · May 11, 2026, 10:08am

Hello, as I understand it, there are now two possible solutions. However, both of these solutions present a few problems.

Problem 1:

The term, “Dijkstra will not use the same vertex twice”, is clear to me. However, I was confused because my implementation of the TRSP function returned the same vertex twice. I read through the documentation again and saw this: “The internal TRSP algorithm performs a look-ahead over the Dijkstra algorithm in order to find out if the attempted path has a restriction. This allows the algorithm to pass twice on the same vertex.” [doc]. So, does the TRSP function use Dijkstra’s algorithm to compare the route with the restrictions, calculate another Dijkstra and therefore use the same vertex twice?

With this behavior, I have one crucial problem:

Problem 2:

The shortest path of the TRSP function can turn around at every node. I have a simple dataset consisting of two-way edges (cost, reverse_cost) and nodes between them. I have defined turn restrictions and turning points at the nodes. Due to the turn restrictions, I have to use the trsp functions. This means that I have to restrict U-turns at every node, but not at the turning points.

In my opinion, the turn around at every node is a significant limitation. It is not logical in many use cases. If I want to use turn restrictions with a normal road dataset, I have to use TRSP functions, but turning around at every junction is often not possible in reality. Is there a way to configure this behaviour in the settings? This would be a great addition to the TRSP functions. For example, it would be useful if turn restrictions could also define turning points or if they could be defined more precisely using edges AND nodes. I look forward to hearing your thoughts on this.

Solution 1: build u-turns through the network

To define the U-turn restrictions exactly, I would have to add extra nodes and edges to the original dataset nodes. One node would be placed before the dataset node and one after it. However, this solution would result in a large number of fake nodes being added to the network. This would need to be done for every node other than the turning points.

Solution 2: routing algorithm searching for u-turns

I am considering a similar approach to your suggestion here. I could calculate different routes and filter out those with wrong turns. If there is no direct route, I could plan a route to a turning point, and then plan a route from the turning point to the target. However, I think I will still have problems with turnarounds at every node.

I’m really looking forward to hearing from you.

cvvergara · May 18, 2026, 2:04pm

Hi,

Right TRSP calls dijkstra many times, and right the resulting solution can pass the same node twice:

In the following graph, suppose there is a turn restriction 1->2->6
So the TRSP could find something like:

or something like:

The red path is also a dijsktra

pgr_TRSP is NOT pgr_dijkstra, (it uses pgr_dijsktra under the covers)
So pgr_TRSP :

does not return the shortest path,
Can pass thru many vertices more than once.

Trying to understand your problem 2

Focus on This means that I have to restrict U-turns at every node, which is true
You are going on a car,

on one way streets you do NOT want to make a U turn: that will make you go on the wrong way and have a head on crash with an incoming car.
On two way streets, driving in Mexico, maybe you can do a U turn in an intersection and you didn’t notice the police car and it will chase you to give you a ticket.

Focus on but not at the turning points.

So you want all your streets to be able to do a U turn? in all the nodes?

I am now confused on what is your original problem.
I thought it was to get out of a cul de sac.

So let me think of what you want:

Suppose the turning point is at an intersection (node) in this image

let me represent that street in graphviz terms

the car is going 1->2->1 passing thru the node 1 twice

Well, dijkstra, astar, etc will never ever give a result that will pass thru the same node twice.

So there is a “NO U-TURN restriction” implicit on the algorithms. (if you read about them, they never mention U-turns because that is a street concept, not a graph concept)

Let me build the u turn on that street:

This abstracted as a graph has 5 edges all directed

< ----------------------+--------------------
                        ^
                        |
 -----------------------+------------------>

in graphviz terms

Remember, dijkstra, astar, etc will never ever give a result that will pass thru the same node twice.

So there is a “NO U-TURN restriction” implicit on the algorithms. (if you read about them, they never mention U-turns because that is a street concept, not a graph concept)

I will reiterate on the following: dijkstra, astar, etc will never ever give a result that will pass thru the same node twice.
So there is a “NO U-TURN restriction” implicit on the algorithms. (if you read about them, they never mention U-turns because that is a street concept, not a graph concept)

focus on To define the U-turn restrictions exactly
If you want to define where NO U-TURNS take place.
There is a “NO U-TURN restriction” implicit on the algorithms. (if you read about them, they never mention U-turns because that is a street concept, not a graph concept)

If you want to release “NO U-TURNS” aka, have all nodes to be able to do U-TURNS.
There is a “NO U-TURN restriction” implicit on the algorithms. (if you read about them, they never mention U-turns because that is a street concept, not a graph concept)
Then you do need to change the whole graph.
A rough sketch would be:

for every node a create a’ and add a bidirectional edge (a’,a)
for every edge e(a, b) create e’(b’,a’)
get the solution you want and map back the solution to the original vertices and edges id.
Of course if your application is about cars, the solution might contain doing a U turn in a one way street and then have head on accident on your users.

focus on I could plan a route to a turning point, and then plan a route from the turning point to the target. However, I think I will still have problems with turnarounds at every node.

There is a “NO U-TURN restriction” implicit on the algorithms. (if you read about them, they never mention U-turns because that is a street concept, not a graph concept)

So, if your problem is how to exit a cul-de-sac: (which is a guess of mine) where sometimes you have to do a UTURN and
here is a sketch of a function: assuming you are passing points and source is a pt, and target is a vertex

function exit_cul_de_sac(edges, points, sourcept, target, deadends )
Do a `pgr_withPoints(edges, points, sourcept, target)` 
if result takes you to the target, that means that the car was pointing to an exist of the cul-de-sac, RETURN the results
if the result is empty  that means then the car was pointing to the inside of the cul de sac so continue

(we do not have a pgr_dijkstraNearWithPoints so you simulate it)
n = node in sourcept's edge
do a   `pgr_dijkstraNear(edges, points, n, deadends)` -> solution1
closest = from the solution1 get the id of the closes dead end

do a `pgr_dijkstra(edges, points, closest, target)` -> solution2
RETURN the Join solutions

That is a very very rough scketch,
I hope you get some ideas from it.

Remember we are a library, and you call functions as needed.

Regards
Vicky