Communications - Scientific Letters of the University of Zilina 2006, 8(3):19-24 | DOI: 10.26552/com.C.2006.3.19-24
Lagrangean Relaxation Based Approximate Approach to the Capacitated Location Problem
- 1 Department of Transportation Networks, Faculty of Management and Informatics, University of Zilina, Slovak Republic
- 2 Department of Mathematical Methods, Faculty of Management and Informatics, University of Zilina, Slovak Republic
When a distribution system is to be designed, limits on terminal capability often must be taken into account. These capacity constraints in this and other facility location problems constitute severe obstacles in exact solving processes. Within this paper, we focused on study of approximate methods based on Lagrangean relaxation of the capacity constraints, which has several advantageous properties. The first of them is that the relaxed problem, known as the uncapacitated location problem, can be solved exactly even for real sized instances [6], [4]. The second useful property of the Lagrangean relaxation is that the objective function value of the optimal solution of the relaxed problem provides lower bound of the optimal solution of the original problem. We present two methods for obtaining suitable values of Lagrangean multipliers. The classical one is based on a sub-gradient method applied on capacity constraints after their special adjustment. The second method is designed as an adaptive method with random experiments for determination of candidates for move from the current solution to the next one. These two methods were tested, compared and the associated results are reported in the concluding part of this paper.
Keywords: no keywords
Published: September 30, 2006 Show citation
| ACS | AIP | APA | ASA | Harvard | Chicago | Chicago Notes | IEEE | ISO690 | MLA | NLM | Turabian | Vancouver |
References
- BEASLEY, J. E. (1993): Lagrangean relaxation. In: Modern Heuristic Techniques for Combinatorial Problems (edited by Reeves C.R.), Blackwell Scientific Publications, London, pp. 243-303
- ERLENKOTTER, D. (1978): A Dual-Based Procedure for Uncapacitated Facility Location. Operations Research, Vol. 26, No 6, pp. 992-1009
Go to original source... - DREZNER, Z. (2004): Facility Location Application and Theory. Springer Verlag, Berlin, Heidlberg, New York, 457 p.
- JANÁČEK, J., BUZNA, Ą. (2004): A Comparison Continuous Approximation with Mathematical Programming Approach to Location Problems. Central European Journal of Operations Research, Vol. 12, No 3, pp. 295-305
- JANÁČEK, J., GÁBRI©OVÁ, L. (2005): Fuzzy Set Operations for Capacity Constraint Relaxation. Journal of Information, Control and Management Systems, ®U ®ilina, No 2, pp. 81-89
- JANÁČEK, J., KOVÁČIKOVÁ, J. (1997): Exact Solution Techniques for Large Location Problems. In: Proceedings of the Math. Methods in Economics, Ostrava, pp. 80-84
- JANÁČKOVÁ, M., SZENDREYOVÁ, A. (2005): An Impact of Transportation Network Topology on Time Consumption of an Exact Algorithm for Distribution System Design. Zeszyty naukove, No 1691, November 2005, Wydawnictwo politechniky ©laskiej, pp. 175-179
- KÖRKEL, M. (1989): On the exact solution of large - scale simple plant location problem. European Journal of Operational Research 39, pp. 157-173. Go to original source...
This is an open access article distributed under the terms of the Creative Commons Attribution 4.0 International License (CC BY 4.0), which permits use, distribution, and reproduction in any medium, provided the original publication is properly cited. No use, distribution or reproduction is permitted which does not comply with these terms.