Multi-Stage Algorithms for Solving a Generalized Capacitated P-median Location Problem
Journal Title: International Journal of Advanced Computer Science & Applications - Year 2018, Vol 9, Issue 5
Abstract
The capacitated p-median location problem is one of the famous problems widely discussed in the literature, but its generalization to a multi-capacity case has not. This generalization, called multi-capacitated location problem, is characterized by allowing facilities to use one of several capacity levels. For this purpose, a predefined list of capacity levels supported by all potential facilities is established. In this paper, we will detail the mathematical formulation and propose a new solving method. We try to construct, indeed, a multi-stage heuristic algorithm that will be called BDF (Biggest Demand First). This new method appears in two approaches: Integrated BDF (IBDF) and Hybridized BDF (HBDF) will be improved by using a local search optimization. A valid lower bound to the optimal solution value is obtained by solving a lagrangian relaxation dual of the exact formulation. Computational results are presented at the end using new instances with higher ratio between the number of customers, facilities and capacity levels or adapted from those of p-median drawn from the literature. The obtained results show that the IBDF is much faster with medium quality solution while HBDF is slower but provides very good solutions close to the optimality.
Authors and Affiliations
Mohammed EL AMRANI, Youssef BENADADA
Keywords
Related Articles
- EP ID EP316112
- DOI 10.14569/IJACSA.2018.090524
- Views 74
- Downloads 0
Priority Based Dynamic Round Robin (PBDRR) Algorithm with Intelligent Time Slice for Soft Real Time Systems
In this paper, a new variant of Round Robin (RR) algorithm is proposed which is suitable for soft real time systems. RR algorithm performs optimally in timeshared systems, but it is not suitable for soft real time system...
Comparison of 2D and 3D Local Binary Pattern in Lung Cancer Diagnosis
Comparative study between 2D and 3D Local Binary Patter (LBP) methods for extraction from Computed Tomography (CT) imagery data in lung cancer diagnosis is conducted. The lung image classification is performed usi...
Deployment Protocol for Underwater Wireless Sensors Network based on Virtual Force
Recently, Underwater Sensor Networks (UWSNs) have attracted researchers’ attention due to the challenges and the peculiar characteristics of the underwater environment. The initial random deployment of UWSN where sensors...
Feature Descriptor Based on Normalized Corners and Moment Invariant for Panoramic Scene Generation
Panorama generation systems aim at creating a wide-view image by aligning and stitching a sequence of images. The technology is extensively used in many fields such as virtual reality, medical image analysis, and geologi...
Word-Based Grammars for PPM
The Prediction by Partial Matching (PPM) compression algorithm is considered one of the most efficient methods for compressing natural language text. Despite the advances of the PPM method for the English language to pre...