SOLVING CAPACITATED P-MEDIAN PROBLEM BY A NEW STRUCTURE OF NEURAL NETWORK

One of the most popular and renowned location-allocation problems is Capacitated P-Median Problem (CPMP). In CPMP locations of p capacitated medians are selected to serve a set of (n) customers, so that the total distance between customers and medians is minimized. In this paper primarily we present a new dynamic assignment method based on urgency function. After that a new formulation for CPMP, based on two types of decision variables with 2(n + p) linear constraints, is proposed. Later on, based on the newly presented formulation, we propose a novel neural network structure that comprises five layers. This neural network is a combination of two-layered Hopfield neural network with location and allocation layers and three other layers that control the Hopfield neural network. The advantage of the proposed network is that it always provides feasible solutions, and since the constraints are united in this neural structure instead of the energy function, the need for tuning parameters is avoided. According to the computational dynamic of the new neural network, the amount of energy function always decreases or remains constant. The effectiveness and efficiency of this algorithm, for standard and simulated problems with different sizes, are analyzed. Our results show that the proposed neural network generates excellent quality and acceptable solutions.