Yes, it is possible.
Consider the graph $\Gamma$ of
$$z=\phi\left(\sqrt{x^2+y^2}\right),$$ where $\phi\colon\mathbb R\to \mathbb R$ is a convex even function with $\phi(0)=0$.
With its intrinsic metric, $\Gamma$ forms an Alexandrov space.
Note that the curve $\gamma$ on the graph described by $y=0$
is formed by two geodesics starting at the origin.
For an appropriate choice of $\phi$ there is always a shortcut which goes around the origin, from say from $(\varepsilon,0,\phi(\varepsilon))$ to $(-\varepsilon,0,\phi(\varepsilon))$.
That is, arbitrary small segment of $\gamma$ containing the origin does not minimize the length.
Roughly, $\phi$ has to have infinite second derivative at $0$ in a strong sense.