Enumerating all ways of pairing odd nodes
Your question doesn't have much to do with the route inspection problem. You are looking for all perfect matchings of $K_{2n}$ (the complete graph on $2n$ vertices), or equivalently, for an algorithm that enumerates all partitions of $\{1,\ldots,2n\}$ into pairs. A simple recursive approach is quite efficient:

Input: A non-empty list $L$ of even size.
Output: All possible partitions of $L$ into pairs.
Algorithm:

If $L = \{a,b\}$, return $(a,b)$.

Otherwise, let $a$ be an arbitrary element of $L$. Go over all elements $b \in L \setminus \{a\}$. For each $b$, generate (recursively) all perfect matchings of $L \setminus \{a,b\}$, and add $(a,b)$ to all of them.



The number of perfect matchings is quite large:
$$
(2n-1) (2n-3) \cdots (1) = \frac{(2n!)}{2^nn!} \sim \frac{\sqrt{4\pi n} (2n/e)^{2n}}{2^n\sqrt{2\pi n}(n/e)^n} = \sqrt{2} \cdot (2n/e)^n.
$$