This paper presents two approaches for solving both the minimax and minisum location problems and as well as a bi-objective location problem. The bi-objective location problem is a combination of both minimax and minisum location problems with recti-linear distances and randomly distributed destinations. Wesolowsky. G.O. [Journal of Regional Science 18: 53–60, 1977] has considered the stochastic extension of Weber problem with rectilinear distance norm and suggested some iterative method after dividing the problem into two parts, one for the X coordinates and other for the Y coordinates, where these co-ordinates may be correlated. In the present investigation exact approaches for both Minisum and Minimax objectives with randomly distributed destinations have been considered separately with both bi-variate exponential and bi-variate uniform distributions and formulated as a non-linear programming problem. Also the area restriction concept has been introduced so that the facility to be located should be within certain restricted area. The consideration of area restrictions has been implemented by incorporating a convex polygon as the constraint set. It has been proved that the solution obtained by this method will give the global optimal solution. The second part of this investigation is the bi-objective problem. The aim of the bi-objective problem is to find the satisfying solution which is desired in many realistic situations. Situation in which the proposed model is applicable is the location of a new warehouse where the sources of goods shipped to the warehouse and also the supply points to which the goods will be shipped is not known in advance. Due to the volatile and competitive nature of the market the supply and the demand points or in other words the variable points are not known in advance but some probability distribution can be predicted. It is required to find the location of a new warehouse which is closer to the variable points and simultaneously the total shipping cost per month from the warehouse to the variable points is minimum. For both single as well as bi-objective problems rectilinear distance norm has been considered as it is more appropriate to the different realistic situations. Two types of compromise solution methods have been suggested to get a satisfactory solution of the bi-objective problem.