Métodos de optimización exactos y heurísticos para la resolución de nuevos modelos de localización competitiva (MTM2015-70260-P)

Investigadores / Researchers  |  Resumen  |  Summary  |  Resultados / Results: artículos / papers  |  capítulos de libro / chapters of books  |  libros / books  | proceedings |  congresos / meetings


El proyecto de título "Métodos de optimización exactos y heurísticos para la resolución de nuevos modelos de localización competitiva (MTM2015-70260-P)" fue financiado por el Ministerio de Economía, Industria y Competitivdad del Gobierno de España, dentro del Plan Estatal de Investigación Científica y Técnica y de Innovación 2013-2016, Programa Estatal de Fomento de la Investigación Científica y Técnica de Excelencia, Subprograma Estatal de Generación de Conocimiento, y por el Fondo Europeo de Desarrollo Regional (FEDER), con un importe de 39325 euros. La duración del proyecto fue del 01/01/2016 al 30/09/2019.

The research project ''Exact and heuristic optimization methods for solving new competitive facility location models (MTM2015-70260-P)'' was funded by the  Ministry of Economy, Industry and Competitiveness of Spain, within the State Plan for Scientific and Technical Research and Innovation 2013-2016, State Program for the Promotion of Scientific and Technical Research of Excellence, State Subprogram for Knowledge Generation, and by the European Regional Development Fund (ERDF), with an amount of 39325 euros. The duration of the project was from 01/01/2016 to 09/30/2019.

INVESTIGADORES / RESEARCHERS

  1. José Fernández Hernández (leader of the research project). University of Murcia. Spain.
  2. Blas Pelegrín Pelegrín. University of Murcia. Spain.
  3. Pascual Fernández Hernández. University of Murcia. Spain.
  4. María Dolores García Pérez. San Antonio Catholic University of Murcia. Spain.
  5. Boglárka G.-Tóth. University of Szeged. Hungary.
  6. Algirdas Lancinskas. Vilnius University. Lithuania.
  7. Julius Zilinskas. Vilnius University. Lithuania.
  8. Said Salhi. University of Kent. United Kingdom.

RESUMEN DEL PROYECTO

Cuando una empresa desea abrir uno o varios centros que ofrecerán un servicio que también es ofrecido por otras empresas, la determinación de la localización de tales centros, y también de sus características asociadas (su calidad), son fundamentales para conseguir el éxito de la empresa. En este proyecto se propondrán nuevos modelos matemáticos que persiguen maximizar el beneficio obtenido por la empresa (o su cuota de mercado), y se diseñarán e implementarán métodos de optimización para su resolución. Dependiendo del tipo de centro a ubicar, se propondrán modelos discretos, en redes o continuos, en los que se tendrán en cuenta distintos patrones de elección de centro por parte de los consumidores. Se considerarán distintos tipos de posibles restricciones, como la existencia de límites en la cantidad de bienes que se pueden servir desde un determinado centro o la consecución de una cuota de mercado (o beneficio) mínima. Se analizará la posible pérdida de cuota de mercado (o beneficio) por parte de los centros ya existentes de la empresa en expansión (canibalismo). También se estudiará la posibilidad de que la empresa invierta no sólo en la ubicación de nuevos centros, sino también en la variación de la calidad de los centros existentes, contemplando incluso la posibilidad de cierre de algunos de estos.

Las técnicas de optimización que se emplearán dependerán principalmente del espacio de localización donde se puedan ubicar los nuevos centros. Para los problemas discretos se intentará primeramente su linealización, para poder resolverlos con técnicas de programación lineal entera. Cuando ello no se pueda realizar de forma eficiente, se diseñarán tanto algoritmos exactos como heurísticos (principalmente de tipo genético) para su resolución. Para los problemas en redes se tratará inicialmente de discretizarlos, parapoder emplear así las técnicas anteriores. Cuando ello no sea factible, se diseñarán métodos exactos de tipo ramificación y acotación, y también técnicas heurísticas de tipo genético. Los problemas continuos, por su parte, serán abordados con técnicas de ramificación y acotación basadas en el análisis de intervalos, en los que además de nuevos tests de eliminación y del estudio de reglas de selección y de subdivisión, se incluirán algoritmos locales para acelerar el test de corte. Para la resolución de problemas de gran tamaño, se propondrán heurísticas, principalmente algoritmos evolutivos, en los que se introducirán técnicas de eliminación de regiones no prometedoras para concentrar así la búsqueda en las regiones con mayor probabilidad de contener la solución. Para los problemas continuos en los que la calidad de los centros a ubicar se considere como una variable discreta, se modificarán los algoritmos anteriores para la resolución de esos problemas de programación no lineal entera. Cuando los algoritmos diseñados no permitan en sus versiones secuenciales la resolución de problemas de tamaño real, se procederá a su paralelización.

El proyecto está relacionado con el reto “Transporte sostenible, inteligente e integrado”, en lo concerniente al tema de logística. También con el reto “Economía y sociedad digital”, en relación con la prioridad temática “Aplicaciones y soluciones TIC”, puesto que además de los modelos en sí y de los algoritmos de resolución, se ofrecerán como entregables los códigos informáticos que permitirán a las empresas aplicar los nuevos modelos de localización a su situación particular.

PALABRAS CLAVE: localización competitiva; optimización; algoritmos exactos; heurísticas; paralelización


SUMMARY OF THE PROJECT

When a firm wants to open one or more centers to offer a service already offered by other firms, determining the location of those new centers, as well as their characteristics (eg., quality) is of major concern for the success of the firm. In this research project new mathematical models will be proposed whose aim is to maximize the profit obtained by the firm (or its captured market share); optimization methods will be designed and implemented for their resolution. Depending on the type of center to set up, discrete, network or continuous models will be proposed, which will consider different patronizing behavior of customers. In addition, practical constraints related to the maximum amount of goods that can be available from a given facility, or the requirement that the new facilities will get at least a minimum level of market share (or profit), among others, will be considered. The loss in market share (or profit) suffered by the existing firm-owned facilities will also be studied, including the possibility of using the budget available from the firm not only in the location of new facilities, but in varying the quality of existing centers as well. This may include the possibility of closing down some of the older facilities.

The optimization techniques employed will depend mainly on the location space where the new facilities can be located. For the discrete problems, linearization techniques will be explored first, in order to solve those problems with integer linear programming tools. Exact and heuristic based techniques such as genetic algorithms will be also designed for solving those problems that could not be linearized efficiently. For network problems, discretization techniques will be studied first, but in case this methodology may not be powerful enough, we intend to design exact branch-and-bound methods as well as genetic algorithms. As for the continuous problems, they will be solved with branch-and-bound methods based in interval analysis tools that we aim to revisit and extend. New discarding tests will be developed, as well as new selection and division rules. New local searches will be adapted and embedded into the search to accelerate the cut-off test. Heuristic methods will be proposed to cope with large size problems focusing on evolutionary algorithms, where discarding tests of non-promising areas will be developed to focus the search in the promising regions with a higher probability for containing the optimal solution. In the continuous problems in which the quality of the new facility is considered to be a discrete variable, the methods will be adapted to cope with those mixed integer nonlinear programming problems. In case the algorithms are not able to solve real size problems due to their sequential implementations, parallel implementations will be proposed. The research project is related with the following two challenges, namely, the challenge “Integrated, smart and sustainable transport”, which has a logistical focus area, and the challenge “Economy and digital society”, as related to the priority area “Applications and ICT solutions”. In addition to solving these location models, the codes to solve the corresponding problems will be made available as part of the outputs of the research project to those interested firms. We would be also happy to provide training in the University or in the company sites so to those staff can use them to solve their own location problems.

KEY WORDS: competitive location; optimization; exact algorithms; heuristics; parallelization


RESULTADOS DEL PROYECTO / PROJECT RESULTS

ARTÍCULOS / PAPERS

  1. A. Elshaikh, S. Salhi, J. Brimberg, N. Mladenovic, B. Callaghan and G. Nagy (2016), An adaptive perturbation-based heuristics: Application to the continuous p-center problem, Computers and Operations Research 75, 1-11 (doi: 10.1016/j.cor.2016.04.018).
  2. A. Lančinskas, P. Fernández , B. Pelegrín and J. Žilinskas (2016), Solution of Discrete Competitive Facility Location Problem for Firm Expansion, INFORMATICA 27, 451-462 (doi: 10.15388/Informatica.2016.94).
  3. B. Pelegrín, P. Fernández and J.D. Pelegrín (2016), On the location of new routes to a destination for airline expansion, European Journal of Industrial Engineering 10, 664-281 (doi: 10.1504/EJIE.2016.078806).
  4. C.A.Irawan, S. Salhi and Z. Drezner (2016), Hybrid Meta-heuristics with VNS and Exact Methods: Application to Large Unconditional and Conditional Vertex p-Centre Problems,  Journal of Heuristics 22, 507-537 (doi: 10.1007/s10732-014-9277-7).
  5. J.L. Redondo, J. Fernández and P.M. Ortigosa, FEMOEA: a Fast and Efficient Multi-Objective Evolutionary Algorithm. Mathematical Methods of Operations Research 85 (2017) 113-135, (doi:10.1007/s00186-016-0560-2).
  6. J. Fernández, B. G.-Tóth, J.L. Redondo, P.M. Ortigosa, A.G. Arrondo, A planar single-facility competitive location and design problem under the multi-deterministic choice rule. Computers and Operations Research 78 (2017) 305-315 (doi: 10.1016/j.cor.2016.09.019).
  7. P. Fernández, B. Pelegrín, A. Lančinskas, J. Žilinskas (2017), New heuristic algorithms for discrete competitive location problems with binary and partially binary customer behavior, Computers and Operations Research 79, 12-18 ( 10.1016/j.cor.2016.10.002).
  8. B. Callaghan, S. Salhi and G. Nagy (2017), Speeding up the optimal method of Drezner for the p-center problem in the plane, European Journal of Operational Research 257, 722-734 (doi: 10.1016/j.ejor.2016.08.038).
  9. C. Irawan, S. Salhi and L.Martino, N. Azizi (2017), The Continuous single source capacitated location problem with and without capacity and zone-dependent fixed cost, European Journal of Operational Research 263, 94-107 (doi: 10.1016/j.ejor.2017.04.004).
  10. A. Lančinskas, P. Fernández , B. Pelegrín and J. Žilinskas (2017) , Improving solution of discrete competitive facility location problems, Optimization Letters 11, 259-270 (doi: 10.1007/s11590-015-0930-3).
  11. B. Pelegrín, P. Fernández, M.D. García (2018), Computation of multi-facility location Nash equilibria on a network under quantity competition, Networks and Spatial Economics 18, 999 – 1017 (doi: 10.1007/s11067-019-09463-8)
  12. J. Fernández, B. G.-Tóth, J.L. Redondo, P.M. Ortigosa (2019), The probabilistic customer's choice rule with a threshold attraction value: effect on the location of competitive facilities. Computers and Operations Research 101,234-249. (doi: https://doi.org/10.1016/j.cor.2018.08.001)
  13. B. Pelegrín, P. Fernández, J.D. Pelegrín, M.D. García (2019), Threshold distance versus side payment to reduce the cannibalization effect in retail chain expansión, IMA Journal of Management Mathematics 30, 105-123 (doi:  10.1093/imaman/dpx011)
  14. B. Callaghan, S. Salhi, J. Brimberg (2019), Optimal solutions for the continuous p-centre problem and related α-neighbour and conditional problems: A relaxation-based algorithm, Journal of the Operational Research Society 70, 192-211 (doi: 10.1080/01605682.2017.1421854)
  15. Z. Drezner, P. Kalczynski, S. Salhi (2019), The planar multiple obnoxious facilities location problem: A Voronoi based heuristic, Omega 87, 105-116, (doi: 10.1016/j.omega.2018.08.013)
  16. C.A. Irawan, M. Luis, S. Salhi, A. Imran  (2019) The incorporation of fixed cost and multilevel capacities into the discrete and continuous single source capacitated facility location problem, Annals of Operations Research 275, 367-392 (doi: 10.1007/s10479-018-3014-9). 
  17. E. Filatovas, O. Kurasova, J.L. Redondo, J. Fernández (2020),  A reference point-based evolutionary algorithm for approximating regions of interest in multiobjective problems, Top (to appear), (doi: https://doi.org/10.1007/s11750-019-00535-z )
  18. M.D. García and B. Pelegrin (2020), Exact equilibrium quantities in spatially separated markets under production constraints, Journal of Interdisciplinary Mathematics (to appear) (doi: https://doi.org/10.1080/09720502.2020.1741220)

CAPÍTULOS DE LIBRO / CHAPTERS OF BOOKS

  1. A. Lančinskas, P. Fernández, B. Pelegrín, J. Žilinskas (2016). Estimating the Pareto Front of a Hard Bi-criterion Competitive Facility Location Problem. En “Advances in Stochastic and Deterministic Global Optimization”, Springer Optimization and Its Applications 107. Editado por P.M. Pardalos, A. Zhigljavsky and J. Žilinskas. Capítulo 14, 255-272. Springer. ISBN 978-3-319-29973-0, 978-3-319-29975-4 (doi: 10.1007/978-3-319-29975-4_14).
  2. B. Pelegrín, P. Fernández and M.D. García (2017). Nash equilibria in network facility location under delivered prices. En “Spatial interaction models: Facility location using game theory”, Springer Optimization and Its Applications 118. Editado por L. Mallozzi, E. D’Amato, P.M. Pardalos. Capítulo 13, 273-292. Springer. ISBN 978-3-319-52654-6, 978-3-319-52653-9 (doi: 10.1007/978-3-319-52654-6_13)
  3. J. Fernández, J.L. Redondo, P.M. Ortigosa, B.G.-Tóth (2017), Huff-like Stackelberg location problems on the plane, in "Spatial Interaction Models - Facility location using game theory", (Edited by L. Mallozzi, E. D'Amato, P.M. Pardalos), Springer Optimization and Its Applications 118, Springer (ISBN 978-3-319-52654-6, 978-3-319-52653-9, DOI 10.1007/978-3-319-52654-6_7), pp. 129-169.
  4. P. Fernández, B. Pelegrín, A. Lancinskas, J. Zilinskas (2018), The Huff versus the Pareto-Huff customer choice rules in a discrete competitive location model. In Lecture Notes in Computer Science 10961: Computational Science and Its Applications Part II. ICCSA 2018. Springer International Publishing (ISBN 978-3-319-95164-5), 583 – 592 (doi: 10.1007/978-3-319-95165-2_41)
  5. B. G.-Tóth, L. Anton-Sanchez, J. Fernández, J.L. Redondo and P.M. Ortigosa (2020), A continuous competitive facility location and design problem for firm expansion, in "Optimizacion of complex systems: theory, models, algorithms and applications", (Edited by H.A. Le Thi, H.M. Le and T. Pham Dinh), Advances in Intelligent Systems and Computing 991, Springer (ISBN 978-3-030-21802-7, 978-3-030-21803-4, DOI: 10.1007/978-3-030-21803-4_100), pp. 1013-1022.

LIBROS / BOOKS

  1. A.G. Arrondo, J. Fernández, J.L. Redondo and P.M. Ortigosa, Evolutionary algorithms applied to competitive facility location - sequential and parallel implementations for single and multi-objective models, Lambert Academic Publishing, 2016 (128 pages), ISBN: 978-3-659-89601-9.

PROCEEDINGS

  1. A. Lančinskas, P. Fernández, B. Pelegrín, J. Žilinskas (2019). Ranking-based algorithm for facility location with constraints. AIP Conference Proceedings 2070, 020030; https://doi.org/10.1063/1.5089997

PONENCIAS EN CONGRESOS / TALKS IN MEETINGS

  1. E. Filatovas, J.L. Redondo, J. Fernández, O. Kurasova. NSGA-NBI: a preference based multi-objective evolutionary algorithm. Euro 2016, Poznan (Poland), 3-6 July, 2016.
  2. J. Žilinskas A. Lančinskas, P. Fernández, B. Pelegrín. Ranking based heuristic algorithm for discrete competitive facility location problems. Euro 2016, Poznan (Poland), 3–6 July 2016.
  3. S. Salhi. Enhancement of the Drezner optimal method for the continuous p-centre problem. Euro 2016, Poznan (Poland), 3–6 July 2016.
  4. B. Pelegrín, P. Fernández, M.D. García and J.D. Pelegrín, A mathematical model for planning store location in the franchise industry. VII European Congress of Mathematics, Berlín (Germany), 18-22 July, 2016.
  5. J. Fernández, J.L. Redondo, P.M. Ortigosa, B.G.-Tóth. A Huff-like single facility location and design problem with closing and/or modification of existing facilities. International Conference on Management and Operations Research, Beijing (China), 12-14 August, 2016.
  6. P. Fernández, B. Pelegrín, A. Lancinskas, J. Zilinskas, New heuristic algorithms for discrete competitive location problems with different customer behavior. International Conference on Management and Operations Research, Beijing (China), 12-14 August, 2016.
  7. E. Filatovas, O. Kurasova, J.L. Redondo, J. Fernández. A preference-based multi-objective evolutionary algorithm for approximating the region of interest. XIII Global Optimization Workshop, Braga (Portugal), 4-8 September, 2016.
  8. J. Fernández, B.G.-Tóth, J.L. Redondo, P.M. Ortigosa. Locating a facility with the partially probabilistic choice rule. XIII Global Optimization Workshop, Braga (Portugal), 4-8 September, 2016.
  9. J. Fernández, J.L. Redondo, P.M. Ortigosa, B.G.-Tóth. A continuous competitive facility location model with attractiveness adjustment of the existing facilities. XXIII Euro Working Group on Locational Analysis (EWGLA23), Málaga (Spain), 14-16 September, 2016.
  10. B. Pelegrín, P. Fernández, J.D. Pelegrín. Finding new routes to a destination for airline revenue maximization. XXIII Euro Working Group on Locational Analysis (EWGLA23), Málaga (Spain), 14-16 September, 2016.
  11.  B. Pelegrín, P. Fernández, J. Zilinskas, A. Lanzinskas. Discrete competitive location problems with different customer behavior and additional constraints. XXIII Euro Working Group on Locational Analysis (EWGLA23), Málaga (Spain), 14-16 September, 2016.
  12. J. Fernández, J.L. Redondo, P.M. Ortigosa, B.G. Tóth. Chain expansion: deciding the location and design of a new facility and/or the modification of the quality or closing of existing facilities. IV International Workshop on Competitive Location, Murcia (Spain), 28-30 May, 2017.
  13. P. Fernández, B. Pelegrín, A. Lancinskas, J. Zilinskas, Discrete competitive location problems with additional constraints. IV International Workshop on Competitive Location, Murcia (Spain), 28-30 May, 2017.
  14. B. Pelegrín, P. Fernández and M.D. García, How to find Nash equilibria in location games. IV International Workshop on Competitive Location, Murcia (Spain), 28-30 May, 2017.
  15. A. Lancinskas, J. Zilinskas, Heuristic algorithms for discrete competitive facility location problems. IV International Workshop on Competitive Location, Murcia (Spain), 28-30 May, 2017.
  16. B.G.-Tóth, J. Fernández. MINLP feladatok megoldása intervallumus B&B módszerrel, Magyar Operációkutatási Konferencia, Cegléd (Hungary), 14-16 June, 2017.
  17. J. Fernández, J.L. Redondo, P.M. Ortigosa, B.G. Tóth. A MINLP model for locating a competitive facility in the plane when attractiveness adjustment and/or closing of the existing chain-owned facilities is allowed. 21st Conference of the International Federation of Operational Research Societies (IFORS21), Québec City (Canada), 17-21 July, 2017.
  18. P. Fernández, B. Pelegrín, A. Lancinskas, J. Zilinskas, A discrete competitive location problem with additional constraints. 21st Conference of the International Federation of Operational Research Societies (IFORS21), Québec City (Canada), 17-21 July, 2017.
  19. J. Zilinskas, A. Lancinskas, B. Pelegrín, P. Fernández, Ranking based heuristic algorithm for discrete competitive facility location problems. 21st Conference of the International Federation of Operational Research Societies (IFORS21), Québec City (Canada), 17-21 July, 2017.
  20. B. Pelegrín, P. Fernández, M.D. García, The follower location choice under quantity competition. 21st Conference of the International Federation of Operational Research Societies (IFORS21), Québec City (Canada), 17-21 July, 2017.
  21. A. Lancinskas, J. Zilinskas, P. Fernández, B. Pelegrín, Ranking-based random search algorithm for discrete competitive facility location. Optimization 2017, Lisbon (Portugal), 6-8 September, 2017.
  22. J. Fernández, S. Salhi, B.G. Tóth, A location-price game for locating a competitive facility in the plane, XII International Conference on Game Theory and Management, Saint Petersburg (Russia), 27-29 June 2018.
  23. B. Pelegrín, P. Fernández, M.D. García, Optimal multi-facility location for competing firms under quantity competition. International Symposium on Mathematical Programming, Bourdeaux (Francia), 1-6 July, 2018.
  24. P. Fernández, B. Pelegrín, A. Lancinskas, J. Zilinskas, The Huff versus the Pareto-Huff Customer Choice Rules in a Discrete Competitive Location Model. 18th International Conference on Computational Science and Its Applications, ICCSA 2018, Melbourne (Australia), 2-5 July, 2018.
  25. L. Simeonova, N. Wassan, S. Salhi, An integrated mixed method approach for decision making in a multi-facility supply chain: a real life case from the UK steel industry, 29th Conference on Operational Research (EURO 2018), Valencia (Spain), 8-11 July 2018.
  26. A. Lancinskas, J. Zilinskas, P. Fernández, B. Pelegrín, Ranking-based heuristic algorithm for competitive facility location. 29th European Conference on Operational Research (EURO 2018), Valencia (Spain), 8-11 July, 2018.
  27. S. Salhi, C. Irawan, M. Abdulrahman, Compromise programming for closed loop supply chain networks, 29th Conference on Operational Research (EURO 2018), Valencia (Spain), 8-11 July 2018.
  28. B.G. Tóth, J. Fernández, J.L. Redondo, P.M. Ortigosa, An interval branch-and-bound method for solving a MINLP competitive facility location and design problem, 16th EUROPT Workshop on Advances in Continuous Optimization (EUROPT2018), Almería (Spain), 12-13 July 2018.
  29. L. Antón-Sánchez, J.L. Redondo, J. Fernández, P.M. Ortigosa, A heuristic algorithm for solving a competitive facility location and design MINLP problem, 16th EUROPT Workshop on Advances in Continuous Optimization (EUROPT2018), Almería (Spain), 12-13 July 2018.
  30. A. Lancinskas, J. Zilinskas, P. Fernández, B. Pelegrín, Ranking-based algorithm for facility location with constraints. XIV Global Optimization Workshop (LeGO 2018), Leiden (The Netherlands), 18-21 September, 2018.
  31. A. Lancinskas, J. Zilinskas, P. Fernández, B. Pelegrín, Ranking-based algorithm for discrete facility location. 10th International Workshop on Data Analysis Methods for Software Systems, Druskininkai (Lithuania), 29 November-1 December, 2018.
  32. B. Pelegrín, P. Fernández, M.D. García, Finding location Nash equilibrium for firms competing with Cournot quantities. Joint Meeting of "12th Int. ISDG Workshop" and "13th Int. Conference on Game
    Theory and Management" (ISDG12-GTM2019), San Petersburgo (Rusia), 3-5 July, 2019.
  33. B. Pelegrín, P. Fernández, M.D. García, On the existence of location Nash equilibria under delivered prices and price sensitive demand: an empirical study. Joint Meeting of "12th Int. ISDG Workshop" and "13th Int. Conference on Game Theory and Management" (ISDG12-GTM2019), San Petersburgo (Rusia), 3-5 July, 2019.
  34. B.G. Tóth, L. Antón-Sánchez, J. Fernández, J.L. Redondo, P.M. Ortigosa, A continuous competitive facility location and design problem for firm expansion, 6th World Congress on Global Optimization (WCGO 2019), Metz (France), 8-10 July 2019.
  35. J. Fernández, B.G. Tóth, L. Antón-Sánchez, J.L. Redondo, P.M. Ortigosa, Firm expansion: how to invest? A MINLP model and B&B and heuristic procedures to deal with it, Sixth International Conference on Continuous Optimization, Berlin (Germany), 5-8 August 2019.
  36. L. Antón-Sánchez, B.G. Tóth, J. Fernández, J.L. Redondo, P.M. Ortigosa, A heuristic algorithm for solving a competitive facility location and design MINLP problem for firm expansion, XXXVIII Congreso Nacional de Estadística e Investigación Operativa (SEIIO XXVIII), Alcoy (Spain), 3-6 September 2019.