Finding shortest path while maximizing the number of overlapping edges The shortest path problem between 2 arbitrary nodes is one that has been covered extensively and the solution is well-known. Consider the edge costs to be arbitrary.

Consider the following variant:

Find the two shortest paths between 2 pairs of arbitrary nodes, however the cost is considered to be the length of the paths minus a positive coefficient times the number of common edges in the two paths, i.e. cost is $|P_1|+|P_2|-C|P_1\cap P_2|$.

Has this problem been addressed before?
There is a polynomial-time algorithm for this problem in the case where $C \le 2$.  There is also a polynomial-time algorithm when $C &gt; 2$, assuming paths are not required to be simple.  If you require paths to be simple and have $C&gt;2$, the problem is NP-hard, as explained by Neal Young.   So in the remainder of this answer I will assume that either $C \le 2$, or $C &gt;2$ and you allow non-simple paths.  I will describe the polynomial-time algorithm below.

First, note that in an optimal solution (wlog) the common part of the two paths must be contiguous, i.e., there is a single contiguous segment of $P_1$ that overlaps with $P_2$, and the rest does not.  In particular, if we want shortest paths between $s_1 \leadsto t_1$ and $s_2 \leadsto t_2$, then there must exist some vertices $v,w$ such that $P_1$ has the form $s_1 \leadsto v \leadsto w \leadsto t_1$ and $P_2$ has the form $s_2 \leadsto v \leadsto w \leadsto t_2$ and the $s_1 \leadsto v$ and $w \leadsto t_1$ parts have no overlap with $P_2$, and the $v \leadsto w$ is common to both.  The cost of this solution is then

$$|s_1 \leadsto v| + |w \leadsto t_1| + |s_2 \leadsto v| + |w \leadsto t_2| + (2-C) |v \leadsto w|.$$

So, compute all-pairs shortest paths and all-pairs longest paths; let $d(a,b)$ denote the distance (length of the shortest path) from $a$ to $b$, and $d^*(a,b)$ the length of the longest path.  If $C \le 2$, iterate over all possible choices for $v,w$, and compute

$$d(s_1,v) + d(w,t_1) + d(s_2,v) + d(w,t_2) + (2-C) d(v,w).$$

If $C &gt; 2$, do the same but for the expression

$$d(s_1,v) + d(w,t_1) + d(s_2,v) + d(w,t_2) + (2-C) d^*(v,w).$$

Keep the smallest value of this obtainable (i.e., the minimum over all $v,w$).  That will be the solution to your problem.  (We don't need to enforce the lack of overlap between, say, $s_1 \leadsto v$ and $s_2 \leadsto v$ in this calculation, because any overlap will only further lower the cost of the solution.)

The running time is something like $O(n^3)$, since the time is dominated by the time to compute all-pairs shortest paths.  I make no claim that  this is optimal.

My thanks to Neal Young for showing how to solve this when $C\le 2$, and for helping me make explicit my assumptions about whether paths are required to be simple or not.