Enhanced OTIS-cube (E-OTIS-Q_{n}), a variation of the OTIS-cube (OTIS-Q_{n}) was proposed in [1]. E-OTIS-Q_n is regular of degree n + 1 and is obtained from the normal OTIS-cube by adding some extra links. In [1], it was shown that the diameter of E-OTIS-Qn is less than or equal to \left\lfloor {\frac{{4n + 5}} {3}} \right\rfloor and a heuristic for point-to-point routing has been proposed. In this paper, an optimal algorithm for one-to-one routing in E-OTIS-Q_n has been developed. We have shown that the diameter of E-OTIS-Qn is equal to \left\lfloor {\frac{{4n + 4}} {3}} \right\rfloor which is almost two-third of the diameter of OTIS-Q_n.