The Global Positioning System (GPS) has been widely used in land vehicle navigation applications. However, the positioning systems based on GPS alone face great problems in the so-called urban canyon environments, where the GPS signals are often blocked by high-rise buildings and there are not enough available satellite signals to estimate the positioning information of a fix. To solve the problem, a constrained method is presented by approximately modeling the path of the vehicle in the urban canyon environments as pieces of lines. By adding this constraint, the minimum number of available satellites reduces to two, which is satisfied in many urban canyon environments. Then, different approaches using the constrained method are systematically developed. In addition, a state-augmentation method is proposed to simultaneously estimate the positions of the GPS receiver and the parameters of the line. Furthermore, the interacting multiple model method is used to determine the correct path which the vehicle follows after passing an intersection of roads. Simulation results show that this approach can solve the urban canyon problems successfully.