Optimally locating a transportation facility and automotive service enterprise is an interesting and important problem. In practice, many related factors, e.g., customer demands, allocations, and locations of customers and facilities, are changing, and thus the problem features with uncertainty. To account for this uncertainty, some researchers have addressed its stochastic time and cost issues. A new research issue arises when a) decision-makers want to minimize the transportation time of customers while minimizing their transpiration cost when locating a facility; and b) users prefer to arrive at the destination within the specific time and cost. By taking a vehicle inspection station as a typical automotive service enterprise example, this work proposes a novel stochastic multi-objective optimization approach to address it. Moreover, some regional constraints can greatly influence its solution; while vehicle velocity is an uncertain variable due to the influence of some unpredictable factors in a location process. This work builds a practical stochastic expected value multi-objective programming model of its location with regional constraints and varying velocity. A hybrid algorithm integrating stochastic simulation and Genetic Algorithms (GA), namely a random weight based multi-objective GA, is proposed to solve the proposed models. A numerical example is given to illustrate the proposed models and the effectiveness of the proposed algorithm.