In this paper, a simplified and direct computation method formulated by the fixed coordinate system and relative meridian concept in conjunction with vector algebra is developed to deal with the classical problems of celestial navigation. It is found that the proposed approach, the Simultaneous Equal-altitude Equation Method (SEEM), can directly calculate the Astronomical Vessel Position (AVP) without an additional graphical procedure. The SEEM is not only simpler than the matrix method but is also more straightforward than the Spherical Triangle Method (STM). Due to tedious computation procedures existing in the commonly used methods for determining the AVP, a set of optimal computation procedures for the STM is also suggested. In addition, aimed at drawbacks of the intercept method, an improved approach with a new computation procedure is also presented to plot the celestial line of position without the intercept. The improved approach with iteration scheme is used to solve the AVP and validate the SEEM successfully. Methods of solving AVP problems are also discussed in detail. Finally, a benchmark example is included to demonstrate these proposed methods.