A greedy randomized adaptive search with probabilistic learning for solving the uncapacitated plant cycle location problem

  1. Israel López-Plata 1
  2. Christopher Expósito-Izquierdo 1
  3. Eduardo Lalla-Ruiz 2
  4. Belén Melián-Batista 1
  5. J. Marcos Moreno-Vega 1
  1. 1 Universidad de La Laguna
    info

    Universidad de La Laguna

    San Cristobal de La Laguna, España

    ROR https://ror.org/01r9z8p25

  2. 2 University of Twente
    info

    University of Twente

    Enschede, Holanda

    ROR https://ror.org/006hf6230

Revista:
IJIMAI

ISSN: 1989-1660

Año de publicación: 2023

Volumen: 8

Número: 2

Páginas: 123-133

Tipo: Artículo

DOI: 10.9781/IJIMAI.2022.04.003 DIALNET GOOGLE SCHOLAR lock_openDialnet editor

Otras publicaciones en: IJIMAI

Resumen

In this paper, we address the Uncapacitated Plant Cycle Location Problem. It is a location-routing problem aimed at determining a subset of locations to set up plants dedicated to serving customers. We propose a mathematical formulation to model the problem. The high computational burden required by the formulation when tackling large scenarios encourages us to develop a Greedy Randomized Adaptive Search Procedure with Probabilistic Learning Model. Its rationale is to divide the problem into two interconnected sub-problems. The computational results indicate the high performance of our proposal in terms of the quality of reported solutions and computational time. Specifically, we have overcome the best approach from the literature on a wide range of scenarios.

Referencias bibliográficas

  • G. Cornuéjols, G. Nemhauser, and L. Wolsey, “The uncapacitated facility location problem,” tech. rep., Cornell University Operations Research and Industrial Engineering, 1983. International Journal of Interactive Multimedia and Artificial Intelligence, Vol. 8, Nº2 - 132 -
  • W. Ho, P. Ji, and P. K. Dey, “A multi-depot travelling salesman problem and its iterative and integrated approaches,” International Journal of Operational Research, vol. 1, no. 4, pp. 382–395, 2006.
  • S. V. Ukkusuri and W. F. Yushimito, “Location routing approach for the humanitarian prepositioning problem,” Transportation research record, vol. 2089, no. 1, pp. 18–25, 2008.
  • S. Schwarze, E. Lalla-Ruiz, and S. Voß, “Modeling the capacitated p-cable trench problem with facility costs,” Central European journal of operations research, pp. 1–23, 2020.
  • E. Lalla-Ruiz and S. Voß, “A popmusic approach for the multi-depot cumulative capacitated vehicle routing problem,” Optimization Letters, vol. 14, no. 3, pp. 671–691, 2020.
  • R. T. Berger, C. R. Coullard, and M. S. Daskin, “Location-routing problems with distance constraints,” Transportation Science, vol. 41, no. 1, pp. 29– 43, 2007.
  • S. Çetiner, C. Sepil, and H. Süral, “Hubbing and routing in postal delivery systems,” Annals of Operations research, vol. 181, no. 1, pp. 109–124, 2010.
  • A. Bruns, A. Klose, and P. Stähly, “Restructuring of swiss parcel delivery services,” OR-Spektrum, vol. 22, no. 2, pp. 285–302, 2000.
  • G. Reinelt, “Tsplib–a traveling salesman problem library,” ORSA journal on computing, vol. 3, no. 4, pp. 376–384, 1991.
  • H. Min, V. Jayaraman, and R. Srivastava, “Combined location-routing problems: A synthesis and future research directions,” European Journal of Operational Research, vol. 108, no. 1, pp. 1 – 15, 1998.
  • D. Tuzun and L. Burke, “A two-phase tabu search approach to the location routing problem,” European Journal of Operational Research, vol. 116, no. 1, pp. 87 – 99, 1999.
  • A. Balakrishnan, J. Ward, and R. Wong, “Integrated facility location and vehicle routing models: Recent work and future prospects,” American Journal of Mathematical and Management Sciences, vol. 7, no. 1-2, pp. 35–61, 1987.
  • G. Nagy and S. Salhi, “Location-routing: Issues, models and methods,” European Journal of Operational Research, vol. 177, no. 2, pp. 649 – 672, 2007.
  • C. Prodhon and C. Prins, “A survey of recent research on locationrouting problems,” European Journal of Operational Research, vol. 238, no. 1, pp. 1 – 17, 2014.
  • M. Schneider and M. Drexl, “A survey of the standard location-routing problem,” Annals of Operations Research, vol. 259, no. 1-2, pp. 389–414, 2017.
  • M. Drexl and M. Schneider, “A survey of variants and extensions of the location-routing problem,” European Journal of Operational Research, vol. 241, no. 2, pp. 283 – 308, 2015.
  • S. Alumur and B. Y. Kara, “A new model for the hazardous waste locationrouting problem,” Computers & Operations Research, vol. 34, no. 5, pp. 1406–1423, 2007.
  • X. Yu, Y. Zhou, and X.-F. Liu, “The two-echelon multi-objective location routing problem inspired by realistic waste collection applications: The composable model and a metaheuristic algorithm,” Applied Soft Computing, p. 106477, 2020.
  • S. Kumar, V. Kumar-Solanki, S. K. Choudhary, A. Selamat, and R. González-Crespo, “Comparative study on ant colony optimization (aco) and k-means clustering approaches for jobs scheduling and energy optimization model in internet of things (iot),” International Journal of Interactive Multimedia and Artificial Intelligence, vol. 1, pp. 107–116, 2020.
  • M. Rabbani, R. Heidari, H. Farrokhi-Asl, and N. Rahimi, “Using metaheuristic algorithms to solve a multi-objective industrial hazardous waste location-routing problem considering incompatible waste types,” Journal of Cleaner Production, vol. 170, pp. 227–241, 2018.
  • A. Billionnet, S. Elloumi, and L. G. Djerbi, “Designing radio-mobile access networks based on synchronous digital hierarchy rings,” Computers & operations research, vol. 32, no. 2, pp. 379–394, 2005.
  • S. Zhang, M. Chen, and W. Zhang, “A novel location-routing problem in electric vehicle transportation with stochastic demands,” Journal of Cleaner Production, vol. 221, pp. 567–581, 2019.
  • I. A. Martínez-Salazar, J. Molina, F. Ángel-Bello, T. Gómez, and R. Caballero, “Solving a bi-objective transportation location routing problem by metaheuristic algorithms,” European Journal of Operational Research, vol. 234, no. 1, pp. 25–36, 2014.
  • M. Borhani, K. Akbari, A. Matkan, and M. Tanasan, “A multicriteria optimization for flight route networks in large-scale airlines using intelligent spatial information,” International Journal of Interactive Multimedia and Artificial Intelligence, vol. 6, no. 1, pp. 123 – 131, 2019.
  • B. Jarboui, H. Derbel, S. Hanafi, and N. Mladenović, “Variable neighborhood search for location routing,” Computers & Operations Research, vol. 40, no. 1, pp. 47–57, 2013.
  • C.-J. Ting and C.-H. Chen, “A multiple ant colony optimization algorithm for the capacitated location routing problem,” International Journal of Production Economics, vol. 141, no. 1, pp. 34–44, 2013.
  • T.-H. Wu, C. Low, and J.-W. Bai, “Heuristic solutions to multi-depot location-routing problems,” Computers & Operations Research, vol. 29, no. 10, pp. 1393–1415, 2002.
  • P. Yang and B. Li-Jun, “An integrated optimization problem in logistics and the pso solution,” in 2006 International Conference on Service Systems and Service Management, vol. 2, pp. 965–970, IEEE, 2006.
  • Y. Marinakis and M. Marinaki, “A particle swarm optimization algorithm with path relinking for the location routing problem,” Journal of Mathematical Modelling and Algorithms, vol. 7, no. 1, pp. 59–78, 2008.
  • R. Caballero, M. González, F. M. Guerrero, J. Molina, and Paralera, “Solving a multiobjective location routing problem with a metaheuristic based on tabu search. application to a real case in andalusia,” European Journal of Operational Research, vol. 177, no. 3, pp. 1751–1763, 2007.
  • C. Prins, C. Prodhon, and R. W. Calvo, “Solving the capacitated locationrouting problem by a grasp complemented by a learning process and a path relinking,” 4OR, vol. 4, no. 3, pp. 221–238, 2006.
  • S. Barreto, C. Ferreira, J. Paixao, and B. S. Santos, “Using clustering analysis in a capacitated location-routing problem,” European Journal of Operational Research, vol. 179, no. 3, pp. 968–977, 2007.
  • I. López-Plata, C. Expósito-Izquierdo, E. Lalla-Ruiz,B. Melián-Batista, and J. M. Moreno-Vega, “A greedy randomized adaptive search procedure for solving the uncapacitated plant cycle problem,” in International Conference on Computer Aided Systems Theory, pp. 263–270, Springer, 2015.
  • J. Escobar, R. Linfati, M. Baldoquin, and P. Toth, “A granular variable tabu neighborhood search for the capacitated location-routing problem,” Transportation Research Part B: Methodological, vol. 67, no. 0, pp. 344 – 356, 2014.
  • R. Baldacci, A. Mingozzi, and R. Calvo, “An exact method for the capacitated location-routing problem.,” Operations Research, vol. 59, no. 5, pp. 1284–1296, 2011.
  • J. Belenguer, E. Benavent, C. Prins, C. Prodhon, and R. Calvo, “A branchand-cut method for the capacitated location-routing problem,” Computers & Operations Research, vol. 38, no. 6, pp. 931 – 941, 2011.
  • C. Contardo, J.F. Cordeau, and B. Gendron, “An exact algorithm based on cut-and-column generation for the capacitated location-routing problem,” INFORMS Journal on Computing, vol. 26, pp. 88–102, 2014.
  • A. Perugia, L. Moccia, J. Cordeau, and G. Laporte, “Designing a home-towork bus service in a metropolitan area,” Transportation Research Part B: Methodological, vol. 45, no. 10, pp. 1710 – 1726, 2011.
  • I. Rodríguez-Martín, J.-J. Salazar-González, and H. Yaman, “A branchand-cut algorithm for two-level survivable network design problems,” Computers & Operations Research, vol. 67, pp. 102–112, 2016.
  • M. Labbé, I. Rodríguez-Martín, and J. Salazar-Rodríguez, “A branchand-cut algorithm for the plant-cycle location problem,” Journal of the Operational Research Society, vol. 55, no. 5, pp. 513 – 520, 2004.
  • M. Albareda-Sambola, J. Díaz, and E. Fernández, “A compact model and tight bounds for a combined location-routing problem,” Computers & Operations Research, vol. 32, no. 3, pp. 407 – 428, 2005.
  • B. Melián-Batista, J. Moreno-Vega, N. Vaswani, and R. Yumar, “A nature inspired approach for the uncapacitated plant cycle location problem,” in Nature Inspired Cooperative Strategies for Optimization (NICSO 2008) (N. Krasnogor, M. B. Melián-Batista, J. A. Moreno-Pérez, J. M. Moreno- Vega, and D. A. Pelta, eds.), vol. 236 of Studies in Computational Intelligence, pp. 49–60, Springer Berlin Heidelberg, 2009.
  • C. Fleming, S. Griffis, and J. Bell, “The effects of triangle inequality on the vehicle routing problem,” European Journal of Operational Research, vol. 224, no. 1, pp. 1 – 7, 2013.
  • G. Gutin and A. Punnen, The Traveling Salesman Problem and Its Variations. Springer, 1 edition ed., 2002.
  • T. Feo and M. Resende, “Greedy randomized adaptive search procedures,” Journal of Global Optimization, vol. 6, no. 2, pp. 109–133, 1995. Regular Issue - 133 -
  • W. W. Daniel, Applied nonparametric statistics. Boston: PWS-Kent Publishing Company, 1990.
  • F. Wilcoxon, “Individual comparisons by ranking methods,” Biometrics Bulletin, vol. 1, no. 6, pp. 80–83, 1945.
Fuente de los datos: Dialnet