Abstract: Whatever the field of activity, the design of the distribution network is a strategic decision that affects both the commercial performance as the tactical and operational management of the supply chain. In this article, we address a problem of distribution network extension. The decision to open a new store and the choice of its location in an existing distribution network takes into account the customer demand and service objectives of the relevant geographic area. It also takes into account other logistics and techniques parameters. In this article we suggest a model of the distribution network, identical to a TLCLAP model (Two Level Capacitated Location Allocation Problem), with a list of parameters and logistical constraints related to business and a resolution approach based on an effective Variable Neighborhood Search VNS method.