×

Solution methods for the bi-objective (cost-coverage) unconstrained facility location problem with an illustrative example. (English) Zbl 1183.90293

Summary: The Colombian coffee supply network, managed by the Federación Nacional de Cafeteros de Colombia (Colombian National Coffee-Growers Federation), requires slimming down operational costs while continuing to provide a high level of service in terms of coverage to its affiliated coffee growers. We model this problem as a biobjective (cost-coverage) uncapacitated facility location problem (BOUFLP). We designed and implemented three different algorithms for the BOUFLP that are able to obtain a good approximation of the Pareto frontier. We designed an algorithm based on the Nondominated Sorting Genetic Algorithm; an algorithm based on the Pareto Archive Evolution Strategy; and an algorithm based on mathematical programming. We developed a random problem generator for testing and comparison using as reference the Colombian coffee supply network with 29 depots and 47 purchasing centers. We compared the algorithms based on the quality of the approximation to the Pareto frontier using a nondominated space metric inspired on Zitzler and Thiele’s. We used the mathematical programming-based algorithm to identify unique tradeoff opportunities for the reconfiguration of the Colombian coffee supply network. Finally, we illustrate an extension of the mathematical programming-based algorithm to perform scenario analysis for a set of uncapacitated location problems found in the literature.

MSC:

90B90 Case-oriented studies in operations research
90B50 Management decision making, including multiple objectives
90B80 Discrete location and assignment
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Badhury, J., R. Batta, and J. Jaramillo. (2002). ”On the Use of Genetic Algorithms to Solve Location Problems.” Computers & Operations Research, 29, 761–779. · Zbl 0995.90060
[2] Badri, M.A., A.K. Mortagy, and C.A. Alsayed. (1998). ”A Multi-Objective Model for Locating Fire Stations.” European Journal of Operational Research, 110, 243–260. · Zbl 0948.90094
[3] Beasley, D., D.R. Bull, and R. Martin. (1993a). ”An Overview of Genetic Algorithms: Part 1, Fundamental.” University Computing, 15(2), 58–69.
[4] Beasley, D., D.R. Bull, and R. Martin. (1993a). ”An Overview of Genetic Algorithms: Part 2, Research Topics.” University Computing, 15(4), 170–181.
[5] Beasley, J. (2000). ”Population Heuristics.” In P.M. Pardalos and M.G.C. Resende (Eds.), Handbook of Applied Optimization. Oxford University Press.
[6] Brandeau, M. and S. Chiu. (1989). ”An Overview of Representative Problems in Location Research.” Management Science, 35, 645–674. · Zbl 0669.90040
[7] Çela, E. (1998). The Quadratic Assignment Problem: Theory and Algorithms. Kluwer. · Zbl 0909.90226
[8] Coello, C.A. (1999). ”An Updated Survey of Evolutionary Multiobjective Optimization Techniques: State of the Art and Future Trends.” In P. Angeline, Z. Michalewicz, M. Schoenauer, X. Yao, and A. Zalzala (Eds.), Proceedings of the Congress on Evolutionary Computation, Vol. 1, pp. 3–13. IEEE Press, Washington D.C.
[9] Coello, C.A., G.A. Lamont, and D.A.V. Veldhuizen. (2002). Evolutionary Algorithms for Solving Multi-Objective Problems. Kluwer, New York. · Zbl 1130.90002
[10] Comision de Ajuste a la Institucionalidad Cafetera (2002). El Café Capital Social y Estratégico. Comision de Ajuste a la Institucionalidad Cafetera, Bogota.
[11] Current, J., M. Daskin, and D. Schilling. (1995). Facility Location: A Survey of Applications and Methods, pp. 86–122. Springer Verlag, New York, Chapter Discrete Network Location Models.
[12] Daskin, M. (1995). Network and Discrete Location. Models, Algorithms and Applications. Wiley, New York. · Zbl 0870.90076
[13] Owen, S.H. and Daskin, M.S. (1998). ”Strategic Facility Location: A Review.” European Journal of Operational Research, 111, 423–447. · Zbl 0938.90048
[14] Day, R.O., M.P. Kleeman, and G.B. Lamont. (2003). Solving the Multi-Objective Quadratic Assignment Problem Using a Fast Messy Genetic Algorithm. In Proceedings of the 2003 Congress on Evolutionary Computation (CEC 2003), Vol. 3, pp. 2277–2283, IEEE Press.
[15] Deb, K., S. Agrawal, A. Pratap, and T. Meyarivan. (2000). ”A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II.” KanGAL Report 200001, Indian Institute of Technology. Kanpur, India.
[16] Deb, K., A. Pratap, S. Agrawal, and T. Meyarivan. (2002). ”A Fast and Elitist Multi-Objective Genetic Algorithm: NSGA-II.” IEEE Transactions on Evolutionary Computation, 6(2), 182–197. · Zbl 05451853
[17] Deb, K. and N. Srinivas. (1994). ”Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms.” Evolutionary Computation, 2(3), 221–248. · Zbl 05412883
[18] Eaton, D., M. Daskin, D. Simmons, B. Bulloch, and G. Jansma. (1985). ”Determining Medical Service Vehicle Deployment in Austin, Texas.” Interfaces, 15, 96–108.
[19] Ehrgott, M. and X. Gandibleux. (2000). ”A Survey and Annotated Bibliography of Multiobjective Combinatorial Optimization.” OR Spektrum, 22(4), 425–460. · Zbl 1017.90096
[20] Elshafei, A.N. (1977). ”Hospital Layout as a Quadratic Assignment Problem.” Operations Research Quarterly, 28, 167–179. · Zbl 0353.90096
[21] Federación Nacional de Cafeteros de Colombia. (2003). ”Cafe de Colombia Website.” http://www. cafedecolombia.com/federacion.html .
[22] Fernandez, E. and J. Puerto. (2003). ”Multiobjetive Solution of Uncapacitated Plant Location Problem.” European Journal of Operational Research, 145, 509–529. · Zbl 1011.90034
[23] Gen, M. and R. Cheng. (1997). Genetic Algorithms & Engineering Design. John Wiley & Sons.
[24] Goicochea, A., D. Hansen, and L. Dukstein. (1982). Multiobjective Decision Analysis with Engineering and Business applications. John Wiley and Sons, New York.
[25] Goldberg, D. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Adisson-Wesley, Reading M.A. · Zbl 0721.68056
[26] Haimes, Y.Y., L. Lasdon, and D.A. Wismer. (1971). ”On a Bicriterion Formulation of the Problems of Integrated System Identification and System Optimization.” IEEE Transactions on Systems, Man, and Cybernetics, SMC-1(3), 296–297. · Zbl 0224.93016
[27] Hoefer, M. (2003). ”UflLib, Benchmark Instances for the Uncapacitated Facility Location Problem.” Accessed from http://www.mpi-sb.mpg.de/units/ag1/projects/benchmarks/UflLib/ .
[28] Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor. · Zbl 0317.68006
[29] International Coffee Organization. (2003). ”ICO website.” Accessed from http://www.ico.org .
[30] Jayaraman, V. (1999). ”A Multi-Objective Logistics Model for a Capacitated Service Facility Problem.” International Journal of Physical Distribution & Logistics, 29(1), 65–81.
[31] Jensen, M.T. (2003). ”Reducing the Run-Time Complexity of Multiobjective EAs: The NSGA-II and Other Algorithms.” IEEE Transactions on Evolutionary Computation, 7(5), 503–515. · Zbl 05452031
[32] Jones, D., S. Mirrazavi, and M. Tamiz. (2002). ”Multi-Objective Meta-Heuristics: An Overview of the Current State-of-the-Art.” European Journal of Operational Research, 137, 1–9. · Zbl 1002.90060
[33] Kleeman, M.P., R.O. Day, and G. Lamont. (2004). ”Analysis of Parallel Moea Solving the Multi-Objective Quadratic Assignment Problem.” In K.D., et al. (Ed.), Genetic and Evolutionary Computation GECCO 2004 Proceedings of the Genetic and Evolutionary Computation Conference, Vol. 3103 of Lecture Notes in Computer Science, pp. 402–403. Part II. Springer-Verlag, Seattle.
[34] Knowles, J. and D. Corne. (1999). ”The Pareto Archived Evolution Strategy: A New Baseline Algorithm for Pareto Multiobjective Optimisation.” In P. Angeline, Z. Michalewicz, M. Schoenauer, X. Yao, and A. Zalzala (Eds.), Proceedings of the Congress on Evolutionary Computation, Vol. 1, pp. 98–105. IEEE Press, Washington D.C.
[35] Knowles, J. and D. Corne. (2000). ”Approximating the Nondominated Front using the Pareto Archived Evolution Strategy.” Evolutionary Computation, 8(2), 149–172. · Zbl 05412708
[36] Knowles, J. and D. Corne. (2002). ”On Metrics for Comparing Non-Dominated Sets.” In Congress on Evolutionary Computation Conference (CEC02), pp. 711–716. IEEE Press.
[37] Knowles, J.D. and D.W. Corne. (2002). ”Instance Generators and Test Suites for the Multiobjective Quadratic Assignment Problem.” In Proceedings of the Evolutionary Multi-Criterion Optimization (EMO 2003) Second International Conference, pp. 295–310. · Zbl 1036.90542
[38] Knowles, J.D. and D.W. Corne. (2002). ”Towards Landscape Analyses to Inform the Design of a Hybrid Local Search for the Multiobjective Quadratic Assignment Problem.” In A. Abraham, J. Ruiz-del Solar, and M. Koppen (Eds.), Soft Computing Systems: Design, Management and Applications, pp. 271–279. IOS Press, Amsterdam.
[39] Koksalan, M. and A. Keha. (2003). ”Using Genetic Algorithms for Single Machine Bicriteria Scheduling Problems.” European Journal of Operational Research, 145, 543–556. · Zbl 1011.90021
[40] Kratica, J., V. Filipovic, and D. Tosic. (1998). ”Solving the Uncapacitated Warehouse Location Problem by Sga with Add-Heuristic.” In XV ECPD International Conference on Material Handling and Warehousing, Belgrade.
[41] Kratica, J., D. Tosic, V. Filipovic, and I. Liubic. (2001). ”Solving the Simple Plant Location Problem by Genetic Algorithm.” RAIRO Operations Research, 35, 127–142. · Zbl 0995.90055
[42] Lopez-Ibañez, M., P.L., and T. Stützle. (2004). ”On the Design of ACO for the Biobjective Quadratic Assignment Problem.” In M. Dorigo, L. Gambardella, F. Mondada, T. Stützle, M. Birratari, and C. Blum (Eds.), ANTS 2004 Fourth Internatinal Workshop on Ant Algorithms and Swarm Intelligence, Lecture Notes in Computer Science, Springer Verlag, Berlin, Germany.
[43] Marsh, M. and D. Schilling. (1994). ”Equity Measurement in Facility Location Analysis. A Review and Framework.” European Journal of Operational Research, 74, 1–17. · Zbl 0800.90631
[44] Mavrotas, G. and D. Diakoulaki. (1998). ”A Branch and Bound Algorithm for Mixed Zero-One Multiple Objective Linear Programming.” European Journal of Operational Research, 107, 530–541. · Zbl 0943.90063
[45] Medaglia, A.L. and S.C. Fang. (2003). ”A Genetic-Based Framework for Solving (Multicriteria) Weighted Matching Problems.” European Journal of Operational Research, 149(1), 77–101. · Zbl 1035.90073
[46] Michalewicz, Z. (1996). Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, Berlin. · Zbl 0841.68047
[47] Mirchandani, P. and R. Francis. (1990). Discrete Location Theory. Wiley, New York. · Zbl 0718.00021
[48] Nozick, L.K. (2001). ”The Fixed Charge Facility Location Problem with Coverage Restrictions.” Transportation Research Part E, 37, 281–296.
[49] Nozick, L.K. and M.A. Turnquist. (2001). ”Inventory, Transportation, Service Quality and the Location of Distribution Centers.” European Journal of Operational Research, 129, 362–371. · Zbl 0980.90006
[50] Osleeb, J. and S. Ratick. (1983). ”A Mixed Integer and Multiple Objective Programming Model to Analyze Coal Handling in New England.” European Journal of Operational Research, 83, 302–313.
[51] Paquete, L. and T. Stützle. (2003). ”Fast Stochastic Local Searches for the Biobjective Quadratic Assignment Problem.” Technical Report AIDA-03-02, TU Darmstadt. FG Intellektik/FB Informatik. · Zbl 1036.90561
[52] Revelle, C. and G. Laporte. (1996). ”The Plant Location Problem: New Models and Research Prospects.” Operations Research, 44, 864–874. · Zbl 0879.90130
[53] Revelle, C., D. Marks, and J. Liebman. (1970). ”An Analysis of Private and Public Sector Location Models.” Management Science, 16, 692–707. · Zbl 0195.21901
[54] Ringuest, J.L. (1992). Multiobjective Optimization: Behavioral and Computational Considerations. Kluwer Academic Publishers.
[55] Ross, G. and R. Soland. (1980). ”A Multicriteria Approach to the Location of Public Facilities.” European Journal of Operational Research, 4, 307–321. · Zbl 0432.90028
[56] Schaffer, J.D. (1985). ”Multiple Objective Optimization with Vector Evaluated Genetic Algorithms.” In J.J. Grefenstette (Ed.), Proceedings of the 1st International Conference on Genetic Algorithms, pp. 93–100. Erlbaum, Hillsdale, NJ.
[57] Schniederjans, M.J., N.K. Kwak, and M.C. Helmer. (1982). ”An Application of Goal Programming to Resolve a Site Location Problem.” Interfaces, pp. 65–72.
[58] Steuer, R.E. (1989). Multiple Criteria Optimization: Theory, Computation, and Application. Robert E. Krieger Publishing Company. · Zbl 0742.90068
[59] Zhou, G. and M. Gen. (1999). ”Genetic Algorithm Approach on Multi-Criteria Minimum Spanning Tree Problem.” European Journal of Operational Research, 114, 141–152. · Zbl 0945.90009
[60] Zitzler, E., M. Laumanns, L. Thiele, C. Fonseca, and V. da Fonseca. (2002). ”Why Quality Assessment of Multiobjective Optimizers is Difficult.” In GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 666–674. Morgan Kaufmann Publishers, New York.
[61] Zitzler, E. and L. Thiele. (1998). ”Multiobjective Optimization Using Evolutionary Algorithms–A Comparative Case Study.” Parallel Problem Solving from Nature–PPSN–V, pp. 292–303.
[62] Zitzler, E., L. Thiele, M. Laumanns, C. Fonseca, and V.G. da Fonseca. (2003). ”Performance Assessment of Multiobjective Optimizers: An analysis and review.” IEEE Transactions on Evolutionary Computation, 7(2), 117–132. · Zbl 05452216
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.