# Path finding under constraints

Let $G=(V,E)$ be a directed graph with a real weight function $w$ defined on the edges and $a,b \in V$. Let $\alpha$ denote the minimal weight of all paths from $a$ to $b$ and $\beta$ denote the minimal weight of all paths from $b$ to $a$. How do you find two paths $l_1,l_2$ such that:

1. $l_1=(a,v_1,..,v_n,b)$
2. $l_2=(b,u_1,..,u_m,a)$
3. $w(l_1) + w(l_2)\leq 1.1(\alpha + \beta)$
4. From all the paths holding the above, bring to minimum the sum of weights on the edges $e=(u,v)\in l_1$ such that $(v,u)\in l_2$

Less formally, I want to find a path starting at $a$ ending with $b$ and returning to $a$ such that the path is not too long (at most 10% longer than the optimal solution) and tries to use as much as different roads as possible (if it used some road $(x,y)$ when going from $a$ to $b$ , it would try to avoid the road $(y,x)$ when going back to $a$)

• How large is your graph? How many vertices, how many edges? – D.W. Dec 7 '13 at 23:27
• I note the lack of a question; what are you asking? Are you after an algorithm? What have you tried, e.g. adaptions of standard algorithms? What are the properties the algorithm is supposed to have, i.e. what disqualifies sledgehammers like (I)LP? – Raphael Jan 7 '14 at 10:00

One solution would be to use integer linear programming (ILP). This is not guaranteed to have a polynomial worst-case running time (ILP can take exponential time), but ILP solvers are pretty impressive, and for reasonable-sized graphs, this might just be an effective solution in practice.

For each edge $e \in E$, let $x_e,y_e,z_e$ be integer variables with the constraint $0 \le x_e \le 1$, $0 \le y_e \le 1$, $0 \le z_e \le 1$ (so that $x_e,y_ez_e$ are forced to be either 0 or 1). The meaning of $x_e=1$ is that $e$ is part of the path $l_1$, and the meaning of $y_e=1$ is that $e$ is part of $l_2$, and the meaning of $z_e$ is that $e$ is part of both $l_1$ and $l_2$.

Now introduce the following constraints:

• $\sum_{(a,v) \in E} x_{(a,v)} = 1$ (i.e., at least one of the edges out of $a$ must be selected in $l_1$).

• $\sum_{(v,b) \in E} x_{(v,b)} = 1$ (i.e., $l_1$ contains an edge into $b$).

• For each vertex $v \in V \setminus \{a,b\}$, $\sum_{(u,v) \in E} x_{(u,v)} = \sum_{(v,w) \in E} x_{(v,w)}$ (if there's an edge entering $v$, there has to be an edge leaving $v$).

• $\sum_{(b,v) \in E} y_{(b,v)} = 1$ (i.e., $l_2$ contains an edge out of $b$).

• $\sum_{(v,a) \in E} y_{(v,a)} = 1$ (i.e., $l_1$ contains an edge into $a$).

• For each vertex $v \in V \setminus \{a,b\}$, $\sum_{(u,v) \in E} y_{(u,v)} = \sum_{(v,w) \in E} y_{(v,w)}$ (if there's an edge entering $v$, there has to be an edge leaving $v$).

• $\sum_{e \in E} w(e) (x_e + y_e) \le 1.1 (\alpha+\beta)$ (condition 3 in the question holds).

• For each $e \in E$, $z_e \ge x_e + y_{-e} - 1$, $z_e \le x_e$, and $z_e \le y_{-e}$, where $-e$ is the reversal of the edge $e$ (i.e., if $e=(u,v)$, then $-e=(v,u)$). (This enforces that $z_e = 1$ if and only if $x_e = y_{-e} = 1$.)

Now minimize $\sum_{e \in E} w(e) z_e$. This will minimize the total weight of the edges that are common to both $l_1$ and $l_2$.

You can use A* to find the least cost path from a->b and b->a, and combine those paths.

To prefer unused edges when finding the path from b->a, you can increase the weight/cost of edges that were traversed in the path from a->b.

• A* with what heuristic? – David Richerby Feb 11 '14 at 18:59
• @DavidRicherby: Any heuristic you'd like based on the problem space. OP mentions roads, so Euclidean distance might make sense. If all else fails, use a null/0 heuristic and it becomes Dijkstra's algorithm. – Steven Evers Feb 11 '14 at 19:02
• There's no reason to think that the globally optimal solution is obtained by first choosing the shortest path from a->b, and then adding some other path from b->a. It might be that the globally optimal solution involves a path from a->b that is longer than the shortest possible, and a path from b->a that is longer than the shortest possible (maybe the sum of the lengths of those two paths is smaller than you can get if you forced either of those two paths to be the shortest possible). – D.W. Mar 13 '14 at 21:03