Find the minimal number of runs to visit every edge of a directed graph
This looks like a minimum-cost flow problem, but with demands instead of capacities.

A flow in a directed graph $G = (V,E)$ is a function $\phi: E\to \mathbb{R}_{\ge 0}$ that assigns a non-negative real value to every edge, such that for every vertex $v$ except $s$ and $t$, the total flow into $v$ is equal to the total flow out of $v$, or more formally, 
$
    \sum_u \phi(u\mathord\to v) = \sum_w \phi(v\mathord\to w).
$
(This equality is usually called the conservation constraint.)

It's useful to think of a flow as a weighted sum of paths from $s$ to $t$.  In particular, suppose $P$ is a set of simple $(s,t)$-paths, and for any edge $e$, let $\#P(e)$ denote the number of paths in $P$ that use edge $e$.  Then the function $\#P$ is a flow.

In most traditional flow problems, each edge $e$ also has a capacity $c(e)$, and a flow is feasible if and only if $\phi(e) \le c(e)$ for every edge.  However, in your case, you want to force the flow to use every edge; so instead, you have a demand constraint $\phi(e) \ge 1$ at each edge.

Finally, we can define the cost of a flow $\phi$ to be the sum of the flow values: $\$(\phi) = \sum_{e\in E} \phi(e)$.  Possibly up to some off-by-one errors, your goal is to find a flow $\phi$ of minimum cost that satisfies all the conservation and demand constraints.

This problem can be solved in polynomial time using textbook flow algorithms.  Your specific problem is unlikely to appear in any textbook, but all the necessary components are described in Kleinberg and Tardos' Algorithm Design.  You may also find my lecture notes on flow algorithms (groundwork, basic algorithms, and extensions) helpful.