Location-Allocation Problem (LAP) is a combinatorial optimising network problem which has been widely studied by operational researchers due to its many practical applications. In real life, it is usually very hard to present the customer’s demands in a precise way and thus they are estimated from historical data. There are so many types of the methods like exact, heuristic and metaheuristic methods to solve this problem to get the optimal and near optimal solutions. In this study, a metaheuristic approach is applied in GIS environment which gives quick and near optimal solution. To achieve this, one case study based on supply and demand of milk from Vita Distributors to Vita Booths in Hisar City, Haryana have been performed. In this study, the effectiveness and robustness of the metaheuristic algorithm was tested over a GIS geodatabase based network dataset consisting of road network (line features) and facility and customers locations (point features). The performance of the algorithm was also checked for two types of impedance factors i.e. time and distance. The results of this location-allocation problem are very much satisfactory in term of minimization of total transportation cost in providing high quality service locations (Vita Booths) for milk distribution.