If you create a simple "decoration" which simply draws a stroke from the initial to the final point, you can use the raise
option for decorated paths to get a parallel path. Applying shorten >
and shorten <
to this raised path, and putting arrow tips on it, you get the desired result:

Here is the code (the style parallel arrow
takes care of all):
\documentclass{article}
\usepackage{tikz}
\begin{document}
\usetikzlibrary{decorations}
\pgfdeclaredecoration{sl}{initial}{
\state{initial}[width=\pgfdecoratedpathlength-1sp]{
\pgfmoveto{\pgfpointorigin}
}
\state{final}{
\pgflineto{\pgfpointorigin}
}
}
\tikzset{parallel arrow/.style={->,
shorten >=2mm, shorten <=2mm,
decoration={sl,raise=1mm},decorate}}
\begin{tikzpicture}
\begin{scope}
\foreach \x/\y/\name/\label/\where in {1.2/1.4/a/{El Paso}/below,
1/3.2/b/Albuquerque/above, 2.5/3/c/Amarillo/below, 3.8/4/d/Wichita/above,
4.3/3.3/e/Tulsa/45, 5.2/2.8/f/{Little Rock}/right, 4.2/2/g/Dallas/left,
4.8/1/h/Houston/right, 3.6/0.6/i/{San Antonio}/below} {
\draw (\x,\y) circle (.4mm);
\node[draw,circle,minimum size=2mm,inner sep=0mm,label=\where:{\footnotesize \label}] (\name) at (\x,\y) {};
}
\foreach \s/\t in {a/b, b/c, c/e, e/d, e/f, f/g, h/g, h/i} {
\path[draw] (\s) edge (\t);
\path[draw] (\s) edge[parallel arrow] (\t);
\path[draw] (\t) edge[parallel arrow] (\s);}
\end{scope}
\end{tikzpicture}
\end{document}
Update
I added the numbers in each route. I had some fun parametrizing their position so that they can be all put in a single loop.
\documentclass{article}
\usepackage{tikz}
\usetikzlibrary{decorations,calc}
\begin{document}
\pgfdeclaredecoration{sl}{initial}{
\state{initial}[width=\pgfdecoratedpathlength-1sp]{
\pgfmoveto{\pgfpointorigin}
}
\state{final}{
\pgflineto{\pgfpointorigin}
}
}
\tikzset{parallel arrow/.style={latex-,
shorten >=2mm, shorten <=2mm,
decoration={sl,raise=1mm},decorate}}
\begin{tikzpicture}
\begin{scope}
\foreach \x/\y/\name/\label/\where in {1.2/1.4/a/{El Paso}/below,
1/3.2/b/Albuquerque/above, 2.5/3/c/Amarillo/below, 3.8/4/d/Wichita/above,
4.3/3.3/e/Tulsa/45, 5.2/2.8/f/{Little Rock}/right, 4.2/2/g/Dallas/left,
4.8/1/h/Houston/right, 3.6/0.6/i/{San Antonio}/below} {
\draw (\x,\y) circle (.4mm);
\node[draw,circle,minimum size=2mm,inner sep=0mm,label=\where:{\footnotesize \label}] (\name) at (\x,\y) {};
}
\tikzset{edge label/.style={font=\tiny, inner sep=1.6mm},
ab/.style={edge label, left},
ba/.style={edge label, right},
bc/.style={edge label, above},
cb/.style={edge label, below},
ce/.style={bc},
ec/.style={cb},
ed/.style={ab},
de/.style={ba},
ef/.style={edge label, below left, inner sep=1mm},
fe/.style={edge label, above right, inner sep=1mm},
fg/.style={edge label, above left, inner sep=1mm},
gf/.style={edge label, below right, inner sep=1mm},
hg/.style={ab},
gh/.style={ba},
hi/.style={bc},
ih/.style={cb}
}
\foreach \s/\t/\from/\to in {a/b/9/10, b/c/8/11, c/e/7/12, e/d/6/5,
e/f/13/4, f/g/14/3, h/g/15/2, h/i/16/1} {
\path[draw] (\s) edge (\t) ($(\s)!.5!(\t)$) node[\s\t] {\from} node[\t\s]{\to};
\path[draw] (\s) edge[parallel arrow] (\t);
\path[draw] (\t) edge[parallel arrow] (\s);
}
\end{scope}
\end{tikzpicture}
\end{document}
