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 56
- Downloads 0
Security and Privacy Awareness: A Survey for Smartphone User
Smartphone becomes one of the most popular devices in last few years due to the integration of powerful technologies in it. Now-a-days a smartphone can provide different services as like as a computer provides. Smartphon...
Synergies of Advanced Technologies and Role of VANET in Logistics and Transportation
In Intelligent Transport Systems (ITS), Vehicular Ad-hoc Network (VANET) is one of key wireless technologies, which helps in managing road safety, traffic efficiency, fleet, logistics and transportation. The objective of...
Study of the Performance of Multi-hop Routing Protocols in Wireless Sensor Networks
Currently in the literature, there are quite a num-ber of multi-hop routing algorithms, some of which are subject to normalization. Routing protocols based on clustering provide an efficient method for extending the life...
OPTIMIZING THE USE OF AN SPI FLASH PROM IN MICROBLAZE-BASED EMBEDDED SYSTEMS
This paper aims to simplify FPGA designs that incorporate Embedded Software Systems using a soft core Processor. It describes a simple solution to reduce the need of multiple non-volatile memory devices by using one SPI...
Discovering Gaps in Saudi Education for Digital Health Transformation
The growing complexity of healthcare systems worldwide and the medical profession’s increasing dependency on information technology for accurate practice and treatment call for specific standardized education in health i...