2
$\begingroup$

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.

$\endgroup$
15
  • 5
    $\begingroup$ Can't you build this requirement into the distance matrix? $\endgroup$ Feb 14, 2011 at 18:27
  • $\begingroup$ @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. $\endgroup$
    – Max
    Feb 14, 2011 at 18:43
  • $\begingroup$ 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 $\endgroup$
    – Max
    Feb 14, 2011 at 18:46
  • 2
    $\begingroup$ 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? $\endgroup$ Feb 14, 2011 at 20:29
  • 2
    $\begingroup$ @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. $\endgroup$ Feb 14, 2011 at 23:18

1 Answer 1

1
$\begingroup$

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 \}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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