IDEAS home Printed from https://ideas.repec.org/a/spr/operea/v21y2021i3d10.1007_s12351-020-00549-7.html
   My bibliography  Save this article

A greedy evolutionary hybridization algorithm for the optimal network and quadratic assignment problem

Author

Listed:
  • Mouhamadou A. M. T. Baldé

    (Université Cheikh Anta Diop)

  • Serigne Gueye

    (Avignon Université)

  • Babacar M. Ndiaye

    (Université Cheikh Anta Diop)

Abstract

Our paper deals with a combinatorial optimization problem called the optimal network and quadratic assignment problem. The problem has been introduced by Los (Region Sci Urban Econ 8:21–42, 1978) as a model of an urban planning problem that consists in optimizing simultaneously the best location of the activities of an urban area (land-use), as well as the road network design (transportation network) in such a way to minimize as much as possible the routing and network costs. We propose a mixed-integer programming formulation of the problem, and a hybrid algorithm based on greedy and evolutionary heuristic methods. Some numerical experiments on randomly generated instances, and on real-life big data from Dakar city, show the efficiency of the method.

Suggested Citation

  • Mouhamadou A. M. T. Baldé & Serigne Gueye & Babacar M. Ndiaye, 2021. "A greedy evolutionary hybridization algorithm for the optimal network and quadratic assignment problem," Operational Research, Springer, vol. 21(3), pages 1663-1690, September.
    • Handle: RePEc:spr:operea:v:21:y:2021:i:3:d:10.1007_s12351-020-00549-7
    DOI: 10.1007/s12351-020-00549-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s12351-020-00549-7
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s12351-020-00549-7?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Ioannis Gamvros & Bruce Golden & S. Raghavan & Daliborka Stanojević, 2005. "Heuristic Search for Network Design," International Series in Operations Research & Management Science, in: H J. G (ed.), Tutorials on Emerging Methodologies and Applications in Operations Research, chapter 0, pages 1-1-1-46, Springer.
    2. Jen-Jia Lin & Cheng-Min Feng, 2003. "A bi-level programming model for the land use – network design problem," The Annals of Regional Science, Springer;Western Regional Science Association, vol. 37(1), pages 93-105, February.
    3. Los, Marc, 1979. "A discrete-convex programming approach to the simultaneous optimization of land use and transportation," Transportation Research Part B: Methodological, Elsevier, vol. 13(1), pages 33-48, March.
    4. Michael Scriabin & Roger C. Vergin, 1975. "Comparison of Computer Algorithms and Visual Based Methods for Plant Layout," Management Science, INFORMS, vol. 22(2), pages 172-181, October.
    5. Lundqvist, Lars, 1973. "Integrated location -- transportation analysis; a decomposition approach," Regional and Urban Economics, Elsevier, vol. 3(3), pages 233-262, August.
    6. S. W. Hadley & F. Rendl & H. Wolkowicz, 1992. "A New Lower Bound Via Projection for the Quadratic Assignment Problem," Mathematics of Operations Research, INFORMS, vol. 17(3), pages 727-739, August.
    7. Roberto Battiti & Giampietro Tecchiolli, 1994. "The Reactive Tabu Search," INFORMS Journal on Computing, INFORMS, vol. 6(2), pages 126-140, May.
    8. Christopher E. Nugent & Thomas E. Vollmann & John Ruml, 1968. "An Experimental Comparison of Techniques for the Assignment of Facilities to Locations," Operations Research, INFORMS, vol. 16(1), pages 150-173, February.
    9. Los, Marc, 1978. "Simultaneous optimization of land use and transportation : A synthesis of the quadratic assignment problem and the optimal network problem," Regional Science and Urban Economics, Elsevier, vol. 8(1), pages 21-42, February.
    10. James C. Bean, 1994. "Genetic Algorithms and Random Keys for Sequencing and Optimization," INFORMS Journal on Computing, INFORMS, vol. 6(2), pages 154-160, May.
    11. Eugene L. Lawler, 1963. "The Quadratic Assignment Problem," Management Science, INFORMS, vol. 9(4), pages 586-599, July.
    12. Jadranka Skorin-Kapov, 1990. "Tabu Search Applied to the Quadratic Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 2(1), pages 33-45, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Jinzhong Zhang & Tan Zhang & Gang Zhang & Min Kong, 2023. "Parameter optimization of PID controller based on an enhanced whale optimization algorithm for AVR system," Operational Research, Springer, vol. 23(3), pages 1-26, September.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Zvi Drezner & Peter Hahn & Éeric Taillard, 2005. "Recent Advances for the Quadratic Assignment Problem with Special Emphasis on Instances that are Difficult for Meta-Heuristic Methods," Annals of Operations Research, Springer, vol. 139(1), pages 65-94, October.
    2. Loiola, Eliane Maria & de Abreu, Nair Maria Maia & Boaventura-Netto, Paulo Oswaldo & Hahn, Peter & Querido, Tania, 2007. "A survey for the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 176(2), pages 657-690, January.
    3. Zvi Drezner, 2003. "A New Genetic Algorithm for the Quadratic Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 320-330, August.
    4. Yuelin Shen, 2008. "Reactive Tabu Search in a Team-Learning Problem," INFORMS Journal on Computing, INFORMS, vol. 20(4), pages 500-509, November.
    5. Bolte, Andreas & Thonemann, Ulrich Wilhelm, 1996. "Optimizing simulated annealing schedules with genetic programming," European Journal of Operational Research, Elsevier, vol. 92(2), pages 402-416, July.
    6. Vittorio Maniezzo, 1999. "Exact and Approximate Nondeterministic Tree-Search Procedures for the Quadratic Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 11(4), pages 358-369, November.
    7. Ravindra K. Ahuja & Krishna C. Jha & James B. Orlin & Dushyant Sharma, 2007. "Very Large-Scale Neighborhood Search for the Quadratic Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 19(4), pages 646-657, November.
    8. Ahuja, Ravindra & Jha, Krishna & Orlin, James & Sharma, Dushyant, 2003. "Very Large-Scale Neighborhood Search For The Quadratic Assignment Problem," Working papers 4386-02, Massachusetts Institute of Technology (MIT), Sloan School of Management.
    9. Yichuan Ding & Henry Wolkowicz, 2009. "A Low-Dimensional Semidefinite Relaxation for the Quadratic Assignment Problem," Mathematics of Operations Research, INFORMS, vol. 34(4), pages 1008-1022, November.
    10. Kazuhiro Tsuchiya & Sunil Bharitkar & Yoshiyasu Takefuji, 1996. "A neural network approach to facility layout problems," European Journal of Operational Research, Elsevier, vol. 89(3), pages 556-563, March.
    11. Mans, Bernard & Mautor, Thierry & Roucairol, Catherine, 1995. "A parallel depth first search branch and bound algorithm for the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 81(3), pages 617-628, March.
    12. Qing Zhao & Stefan E. Karisch & Franz Rendl & Henry Wolkowicz, 1998. "Semidefinite Programming Relaxations for the Quadratic Assignment Problem," Journal of Combinatorial Optimization, Springer, vol. 2(1), pages 71-109, March.
    13. Silva, Allyson & Coelho, Leandro C. & Darvish, Maryam, 2021. "Quadratic assignment problem variants: A survey and an effective parallel memetic iterated tabu search," European Journal of Operational Research, Elsevier, vol. 292(3), pages 1066-1084.
    14. Paola Festa & Panos Pardalos, 2012. "Efficient solutions for the far from most string problem," Annals of Operations Research, Springer, vol. 196(1), pages 663-682, July.
    15. Shen, Liji & Buscher, Udo, 2012. "Solving the serial batching problem in job shop manufacturing systems," European Journal of Operational Research, Elsevier, vol. 221(1), pages 14-26.
    16. Luca Maria Gambardella & Marco Dorigo, 2000. "An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem," INFORMS Journal on Computing, INFORMS, vol. 12(3), pages 237-255, August.
    17. Fowler, John W. & Mönch, Lars, 2022. "A survey of scheduling with parallel batch (p-batch) processing," European Journal of Operational Research, Elsevier, vol. 298(1), pages 1-24.
    18. Qingzheng Xu & Na Wang & Lei Wang & Wei Li & Qian Sun, 2021. "Multi-Task Optimization and Multi-Task Evolutionary Computation in the Past Five Years: A Brief Review," Mathematics, MDPI, vol. 9(8), pages 1-44, April.
    19. Xiao, Lei & Zhang, Xinghui & Tang, Junxuan & Zhou, Yaqin, 2020. "Joint optimization of opportunistic maintenance and production scheduling considering batch production mode and varying operational conditions," Reliability Engineering and System Safety, Elsevier, vol. 202(C).
    20. Wei Wang & Yaofeng Xu & Liguo Hou, 2019. "Optimal allocation of test times for reliability growth testing with interval-valued model parameters," Journal of Risk and Reliability, , vol. 233(5), pages 791-802, October.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:operea:v:21:y:2021:i:3:d:10.1007_s12351-020-00549-7. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.