<p>I will answer for the general setting. Assume a directed graph $G=(V, E)$ with costs as assumed in the question, that is the costs for entering a node depend on which edge it is left on and vice versa.</p>

<p>Let $v \in V$ arbitrarily; the following construction can be performed iteratively for all nodes in any order. Let $e_1, \dots, e_k \in (V \times \{v\}) \cap E$ (incoming edges) and $f_1, \dots, f_l \in  (\{v\} \times V)\cap E$ (outgoing edges). </p>

<p>Now create for all pairs of $e_i =: (u,v)$ and $f_j =: (v,x)$ a node $v_{ij}$ and edges $(u, v_{ij})$ as well as $(v_{ij}, x)$. Assign the costs as per the described model: costs for edge $(u, v_{ij})$ are the costs for entering $v$ from $u$ when leaving in direction of $x$; costs for edge $(v_{ij}, x)$ are the costs for leaving $v$ to $x$ when having come from $u$.</p>

<p>Add all thusly created $v_{ij}$ and their incident edges to $G$ and remove $v$ and its incident edges from it. Iterate for all nodes.</p>

<p>The resulting graph has $\mathcal{O}(|E|\cdot d^2)$ many edges ad $\mathcal{O}(|V| \cdot d^2)$ many nodes, $d$ the maximum node degree in $G$. It can be reduced by merging (or not splitting) those combinations that have the same costs.</p>

<p>The original problem is equivalent to finding a path with exactly one from each $\{v_{ij} \mid v \in V \}$.</p>

CC BY-SA 2.5
2011-02-15T00:21:38.983Z
2011-02-15T00:40:34.737Z
2011-02-15T00:40:34.737Z
Raphael
<p>I'm trying to find any material on this problem. It extends the Asymmetric Travelling Salesman Problem (ATSP) in that it requires for some destinations that they are approached in the specified direction (but not for all). I couldn't find anything about this problem on the internet. Can anybody point me to some paper or the correct name for this problem? Or maybe similar problem from graph theory?</p>

<p><strong>UPDATE</strong></p>

<p>In my current design each node has a property of direction in which it is being approached. This direction can be restricted or unrestricted. When unrestricted, then I think all possible combinations of directions should be tried to the combination which minimizes the cost function.
Also I have 4 distance matrices corresponding to different direction combinations: 0-0, 0-1, 1-0 and 1-1. Where 0 is positive direction and 1 is negative direction.</p>

<p><strong>UPDATE 2</strong></p>

<p>The calculations are performed on a real street network data. Direction mean street direction (or side of the street). Each point on the street can be aproached from two different directions. Some points are restricted to be approached in a particular direction, some are not.</p>

CC BY-SA 2.5
2011-02-14T18:27:17.410Z
Can't you build this requirement into the distance matrix?
Peter Shor 
CC BY-SA 2.5
2011-02-14T18:43:54.033Z
@Peter Shor: I tried, but I couldn't find a way to do this. Also if I could put all those restrictions inside a distance matrix this would mean that the complexity of the problem hasn't changed. This doesn't seem right, because each unrestricted node can be placed in two different ways: with positive and negative direction.
Max
CC BY-SA 2.5
2011-02-14T18:46:10.320Z
At the moment I have 4 different distance matrices: 1 from positive direction to positive direction, 2 from positive to negative, 3 from negative to positive, 4 from negative to negative
Max
CC BY-SA 2.5
2011-02-14T19:32:16.880Z
It is not even clear what "direction" means. A node can have multiple incoming and outgoing edges; are we talking about restricting valid paths to a subset of all possible pairs in some nodes? Or are those nodes always of in- and out-degree $1$? Or is direction an independent property, in which case you could just minimize cost locally?
Raphael
CC BY-SA 2.5
2011-02-14T19:55:52.163Z
@Raphael: I'm using distance matrix calculated based on street network, rather than a metric distance matrix. Each street has a positive and a negative direction, and this is what I had in mind. So direction is an independent property.
Max
CC BY-SA 2.5
2011-02-14T20:17:02.570Z
If you have a street which connects A --> B, and you can traverse it in this one direction, but not in the other, why can't you just modify the metric to make d(B --> A) = infinity (or some suitably high constant). If the cost is high enough, no (approximately) optimal tour will ever traverse an edge "in the wrong direction".
Aaron Roth
CC BY-SA 2.5
2011-02-14T20:27:50.763Z
@ Aaron. I do as you say, but I have 4 different distances for A --> B. A direction 0 --> B direction 0, A direction 1 --> B direction 0, A direction 0 --> B direction 1,  A direction 1 --> B direction 1.
Max
CC BY-SA 2.5
2011-02-14T20:29:28.433Z
I think I understand the problem. The points are street addresses, and, say, you can reach a certain address either by going east or going west. However, if you reach an address by going east, then there might be an additional cost to turning around and leaving this address by going west. So if you reach node X by coming from the east, then it might be a lot cheaper to depart going to the east, whereas if you reach it from the west, it might be a lot cheaper to depart going west. Is that the problem?
Peter Shor 
CC BY-SA 2.5
2011-02-14T20:50:02.927Z
@Peter Shor. Yes. Also for some adresses there's a restriction that you can only visit them in a particular direction. Another example is a bus which can visit some stops in any direction but for some stops it can only visit them in a particular direction.
Max
CC BY-SA 2.5
2011-02-14T23:18:30.780Z
@Max: The constraints on addresses you can only visit in one direction can be built into the distance matrix. It's the two-direction (but not symmetric) addresses that give you problems.
Peter Shor 
CC BY-SA 2.5
2011-02-14T23:25:11.937Z
@ Peter Shor: That's right. Is there any standard name for this problem?
Max
CC BY-SA 2.5
2011-02-15T00:22:14.677Z
I understand how you can model points on a street with those four combinations, but what about crossings?
Raphael
CC BY-SA 2.5
2011-02-15T12:04:37.303Z
@Raphael: I'm not sure what do you mean by "crossing"?
Max
CC BY-SA 2.5
2011-02-15T12:33:39.697Z
A street crossing/junction/crossorads.
Raphael
CC BY-SA 2.5
2011-02-15T14:47:16.837Z
@Raphael: I'm assuming that addresses are always on single road segment.
Max
<ds.algorithms><reference-request><graph-algorithms><tsp>
ATSP with direction restrictions
Max
# ATSP with direction restrictions

(Asked by: username_0 on 2011-02-14)

I'm trying to find any material on this problem. It extends the Asymmetric Travelling Salesman Problem (ATSP) in that it requires for some destinations that they are approached in the specified direction (but not for all). I couldn't find anything about this problem on the internet. Can anybody point me to some paper or the correct name for this problem? Or maybe similar problem from graph theory?

**UPDATE**

In my current design each node has a property of direction in which it is being approached. This direction can be restricted or unrestricted. When unrestricted, then I think all possible combinations of directions should be tried to the combination which minimizes the cost function.
Also I have 4 distance matrices corresponding to different direction combinations: 0-0, 0-1, 1-0 and 1-1. Where 0 is positive direction and 1 is negative direction.

**UPDATE 2**

The calculations are performed on a real street network data. Direction mean street direction (or side of the street). Each point on the street can be aproached from two different directions. Some points are restricted to be approached in a particular direction, some are not.

**Tags:** ds.algorithms, reference-request, graph-algorithms, tsp
> **Comments:**
> **username_1**: Can't you build this requirement into the distance matrix?  
> **username_0**: @Peter Shor: I tried, but I couldn't find a way to do this. Also if I could put all those restrictions inside a distance matrix this would mean that the complexity of the problem hasn't changed. This doesn't seem right, because each unrestricted node can be placed in two different ways: with positive and negative direction.  
> **username_0**: At the moment I have 4 different distance matrices: 1 from positive direction to positive direction, 2 from positive to negative, 3 from negative to positive, 4 from negative to negative  
> **username_2**: It is not even clear what "direction" means. A node can have multiple incoming and outgoing edges; are we talking about restricting valid paths to a subset of all possible pairs in some nodes? Or are those nodes always of in- and out-degree $1$? Or is direction an independent property, in which case you could just minimize cost locally?  
> **username_0**: @Raphael: I'm using distance matrix calculated based on street network, rather than a metric distance matrix. Each street has a positive and a negative direction, and this is what I had in mind. So direction is an independent property.  
> **username_3**: If you have a street which connects A --> B, and you can traverse it in this one direction, but not in the other, why can't you just modify the metric to make d(B --> A) = infinity (or some suitably high constant). If the cost is high enough, no (approximately) optimal tour will ever traverse an edge "in the wrong direction".  
> **username_0**: @ Aaron. I do as you say, but I have 4 different distances for A --> B. A direction 0 --> B direction 0, A direction 1 --> B direction 0, A direction 0 --> B direction 1,  A direction 1 --> B direction 1.  
> **username_1**: I think I understand the problem. The points are street addresses, and, say, you can reach a certain address either by going east or going west. However, if you reach an address by going east, then there might be an additional cost to turning around and leaving this address by going west. So if you reach node X by coming from the east, then it might be a lot cheaper to depart going to the east, whereas if you reach it from the west, it might be a lot cheaper to depart going west. Is that the problem?  
> **username_0**: @Peter Shor. Yes. Also for some adresses there's a restriction that you can only visit them in a particular direction. Another example is a bus which can visit some stops in any direction but for some stops it can only visit them in a particular direction.  
> **username_1**: @Max: The constraints on addresses you can only visit in one direction can be built into the distance matrix. It's the two-direction (but not symmetric) addresses that give you problems.  
> **username_0**: @ Peter Shor: That's right. Is there any standard name for this problem?  
> **username_2**: I understand how you can model points on a street with those four combinations, but what about crossings?  
> **username_0**: @Raphael: I'm not sure what do you mean by "crossing"?  
> **username_2**: A street crossing/junction/crossorads.  
> **username_0**: @Raphael: I'm assuming that addresses are always on single road segment.  

---

## 1 answers

### Answer by username_2 on 2011-02-15. Score: 1

I will answer for the general setting. Assume a directed graph $G=(V, E)$ with costs as assumed in the question, that is the costs for entering a node depend on which edge it is left on and vice versa.

Let $v \in V$ arbitrarily; the following construction can be performed iteratively for all nodes in any order. Let $e\_1, \dots, e\_k \in (V \times \{v\}) \cap E$ (incoming edges) and $f\_1, \dots, f\_l \in (\{v\} \times V)\cap E$ (outgoing edges).

Now create for all pairs of $e\_i =: (u,v)$ and $f\_j =: (v,x)$ a node $v\_{ij}$ and edges $(u, v\_{ij})$ as well as $(v\_{ij}, x)$. Assign the costs as per the described model: costs for edge $(u, v\_{ij})$ are the costs for entering $v$ from $u$ when leaving in direction of $x$; costs for edge $(v\_{ij}, x)$ are the costs for leaving $v$ to $x$ when having come from $u$.

Add all thusly created $v\_{ij}$ and their incident edges to $G$ and remove $v$ and its incident edges from it. Iterate for all nodes.

The resulting graph has $\mathcal{O}(|E|\cdot d^2)$ many edges ad $\mathcal{O}(|V| \cdot d^2)$ many nodes, $d$ the maximum node degree in $G$. It can be reduced by merging (or not splitting) those combinations that have the same costs.

The original problem is equivalent to finding a path with exactly one from each $\{v\_{ij} \mid v \in V \}$.


---

