IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v9y2020i1p5-d466269.html
   My bibliography  Save this article

An Approach Integrating Simulated Annealing and Variable Neighborhood Search for the Bidirectional Loop Layout Problem

Author

Listed:
  • Gintaras Palubeckis

    (Faculty of Informatics, Kaunas University of Technology, Studentu 50-408, 51368 Kaunas, Lithuania)

Abstract

In the bidirectional loop layout problem (BLLP), we are given a set of machines, a set of locations arranged in a loop configuration, and a flow cost matrix. The problem asks to assign machines to locations so as to minimize the sum of the products of the flow costs and distances between machines. The distance between two locations is calculated either in the clockwise or in the counterclockwise direction, whichever path is shorter. We propose a hybrid approach for the BLLP which combines the simulated annealing (SA) technique with the variable neighborhood search (VNS) method. The VNS algorithm uses an innovative local search technique which is based on a fast insertion neighborhood exploration procedure. The computational complexity of this procedure is commensurate with the size of the neighborhood, that is, it performs O ( 1 ) operations per move. Computational results are reported for BLLP instances with up to 300 machines. They show that the SA and VNS hybrid algorithm is superior to both SA and VNS used stand-alone. Additionally, we tested our algorithm on two sets of benchmark tool indexing problem instances. The results demonstrate that our hybrid technique outperforms the harmony search (HS) heuristic which is the state-of-the-art algorithm for this problem. In particular, for the 4 Anjos instances and 4 sko instances, new best solutions were found. The proposed algorithm provided better average solutions than HS for all 24 Anjos and sko instances. It has shown robust performance on these benchmarks. For 20 instances, the best known solution was obtained in more than 50 % of the runs. The average time per run was below 10 s. The source code implementing our algorithm is made publicly available as a benchmark for future comparisons.

Suggested Citation

  • Gintaras Palubeckis, 2020. "An Approach Integrating Simulated Annealing and Variable Neighborhood Search for the Bidirectional Loop Layout Problem," Mathematics, MDPI, vol. 9(1), pages 1-30, December.
  • Handle: RePEc:gam:jmathe:v:9:y:2020:i:1:p:5-:d:466269
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/9/1/5/pdf
    Download Restriction: no

    File URL: https://www.mdpi.com/2227-7390/9/1/5/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Öncan, Temel & AltInel, I. Kuban, 2008. "Exact solution procedures for the balanced unidirectional cyclic layout problem," European Journal of Operational Research, Elsevier, vol. 189(3), pages 609-623, September.
    2. Yu, Junfang & Sarker, Bhaba R., 2003. "Directional decomposition heuristic for a linear machine-cell location problem," European Journal of Operational Research, Elsevier, vol. 149(1), pages 142-184, August.
    3. Palubeckis, Gintaras, 2015. "Fast simulated annealing for single-row equidistant facility layout," Applied Mathematics and Computation, Elsevier, vol. 263(C), pages 287-301.
    4. Adil Baykasoğlu & Fehmi Burcin Ozsoydan, 2016. "An improved approach for determination of index positions on CNC magazines with cutting tool duplications by integrating shortest path algorithm," International Journal of Production Research, Taylor & Francis Journals, vol. 54(3), pages 742-760, February.
    5. Panagiotis Kouvelis & Michael W. Kim, 1992. "Unidirectional Loop Network Layout Problem in Automated Manufacturing Systems," Operations Research, INFORMS, vol. 40(3), pages 533-550, June.
    6. Ventura, José A. & Rieksts, Brian Q., 2009. "Optimal location of dwell points in a single loop AGV system with time restrictions on vehicle availability," European Journal of Operational Research, Elsevier, vol. 192(1), pages 93-104, January.
    7. Hansen, Pierre & Mladenovic, Nenad, 2001. "Variable neighborhood search: Principles and applications," European Journal of Operational Research, Elsevier, vol. 130(3), pages 449-467, May.
    8. Nearchou, Andreas C., 2006. "Meta-heuristics from nature for the loop layout design problem," International Journal of Production Economics, Elsevier, vol. 101(2), pages 312-328, June.
    9. Jadranka Skorin-Kapov, 1990. "Tabu Search Applied to the Quadratic Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 2(1), pages 33-45, February.
    10. Palubeckis, Gintaras & Tomkevičius, Arūnas & Ostreika, Armantas, 2019. "Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimization," Applied Mathematics and Computation, Elsevier, vol. 348(C), pages 84-101.
    11. Ghosh, Diptesh, 2016. "A new genetic algorithm for the tool indexing problem," IIMA Working Papers WP2016-03-17, Indian Institute of Management Ahmedabad, Research and Publication Department.
    12. Pierre Hansen & Nenad Mladenović & José Moreno Pérez, 2010. "Variable neighbourhood search: methods and applications," Annals of Operations Research, Springer, vol. 175(1), pages 367-407, March.
    13. Ahonen, H. & de Alvarenga, A.G. & Amaral, A.R.S., 2014. "Simulated annealing and tabu search approaches for the Corridor Allocation Problem," European Journal of Operational Research, Elsevier, vol. 232(1), pages 221-233.
    14. Boysen, Nils & Emde, Simon & Stephan, Konrad & Weiß, Markus, 2015. "Synchronization in hub terminals with the circular arrangement problem," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 79444, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    15. Nils Boysen & Simon Emde & Konrad Stephan & Markus Weiß, 2015. "Synchronization in hub terminals with the circular arrangement problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 62(6), pages 454-469, September.
    16. Sarker, Bhaba R. & Wilhelm, Wilbert E. & Hogg, Gary L., 1998. "One-dimensional machine location problems in a multi-product flowline with equidistant locations," European Journal of Operational Research, Elsevier, vol. 105(3), pages 401-426, March.
    17. Dahlbeck, Mirko & Fischer, Anja & Fischer, Frank, 2020. "Decorous combinatorial lower bounds for row layout problems," European Journal of Operational Research, Elsevier, vol. 286(3), pages 929-944.
    18. G. Manita & I. Chaieb & O. Korbaa, 2016. "A new approach for loop machine layout problem integrating proximity constraints," International Journal of Production Research, Taylor & Francis Journals, vol. 54(3), pages 778-798, February.
    19. Ghosh, Diptesh, 2016. "Allocating tools to index positions in tool magazines using tabu search," IIMA Working Papers WP2016-02-06, Indian Institute of Management Ahmedabad, Research and Publication Department.
    20. Anjos, Miguel F. & Fischer, Anja & Hungerländer, Philipp, 2018. "Improved exact approaches for row layout problems with departments of equal length," European Journal of Operational Research, Elsevier, vol. 270(2), pages 514-529.
    21. S. Borağan Aruoba & Jesús Fernández-Villaverde, 2014. "A Comparison of Programming Languages in Economics," NBER Working Papers 20263, National Bureau of Economic Research, Inc.
    Full references (including those not matched with items on IDEAS)

    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. Palubeckis, Gintaras, 2015. "Fast simulated annealing for single-row equidistant facility layout," Applied Mathematics and Computation, Elsevier, vol. 263(C), pages 287-301.
    2. Dahlbeck, Mirko & Fischer, Anja & Fischer, Frank, 2020. "Decorous combinatorial lower bounds for row layout problems," European Journal of Operational Research, Elsevier, vol. 286(3), pages 929-944.
    3. Dahlbeck, Mirko & Fischer, Anja & Fischer, Frank & Hungerländer, Philipp & Maier, Kerstin, 2023. "Exact approaches for the combined cell layout problem," European Journal of Operational Research, Elsevier, vol. 305(2), pages 530-546.
    4. Hungerländer, Philipp & Anjos, Miguel F., 2015. "A semidefinite optimization-based approach for global optimization of multi-row facility layout," European Journal of Operational Research, Elsevier, vol. 245(1), pages 46-61.
    5. 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.
    6. Asef-Vaziri, Ardavan & Jahandideh, Hossein & Modarres, Mohammad, 2017. "Loop-based facility layout design under flexible bay structures," International Journal of Production Economics, Elsevier, vol. 193(C), pages 713-725.
    7. 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.
    8. Martín Barragán, Belén, 2016. "A Partial parametric path algorithm for multiclass classification," DES - Working Papers. Statistics and Econometrics. WS 22390, Universidad Carlos III de Madrid. Departamento de Estadística.
    9. Zhaowei Miao & Feng Yang & Ke Fu & Dongsheng Xu, 2012. "Transshipment service through crossdocks with both soft and hard time windows," Annals of Operations Research, Springer, vol. 192(1), pages 21-47, January.
    10. H-Y Lin & C-J Liao & C-T Tseng, 2011. "An application of variable neighbourhood search to hospital call scheduling of infant formula promotion," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(6), pages 949-959, June.
    11. Bhuvnesh Sharma & M. Ramkumar & Nachiappan Subramanian & Bharat Malhotra, 2019. "Dynamic temporary blood facility location-allocation during and post-disaster periods," Annals of Operations Research, Springer, vol. 283(1), pages 705-736, December.
    12. Tarik Chargui & Anne-Laure Ladier & Abdelghani Bekrar & Shenle Pan & Damien Trentesaux, 2022. "Towards designing and operating Physical Internet cross-docks: problem specifications and research perspectives," Post-Print hal-03624314, HAL.
    13. Ade Irawan, Chandra & Starita, Stefano & Chan, Hing Kai & Eskandarpour, Majid & Reihaneh, Mohammad, 2023. "Routing in offshore wind farms: A multi-period location and maintenance problem with joint use of a service operation vessel and a safe transfer boat," European Journal of Operational Research, Elsevier, vol. 307(1), pages 328-350.
    14. Dolinskaya, Irina & Shi, Zhenyu (Edwin) & Smilowitz, Karen, 2018. "Adaptive orienteering problem with stochastic travel times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 109(C), pages 1-19.
    15. Yıldız, Gazi Bilal & Soylu, Banu, 2019. "A multiobjective post-sales guarantee and repair services network design problem," International Journal of Production Economics, Elsevier, vol. 216(C), pages 305-320.
    16. Dimitris Fouskakis & David Draper, 2002. "Stochastic Optimization: a Review," International Statistical Review, International Statistical Institute, vol. 70(3), pages 315-349, December.
    17. Grzegorz Waligóra, 2016. "Comparative Analysis of Some Metaheuristics for Discrete-Continuous Project Scheduling with Activities of Identical Processing Rates," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(03), pages 1-32, June.
    18. Chargui, Tarik & Ladier, Anne-Laure & Bekrar, Abdelghani & Pan, Shenle & Trentesaux, Damien, 2022. "Towards designing and operating physical internet cross-docks: Problem specifications and research perspectives," Omega, Elsevier, vol. 111(C).
    19. Shandong Mou, 2022. "Integrated Order Picking and Multi-Skilled Picker Scheduling in Omni-Channel Retail Stores," Mathematics, MDPI, vol. 10(9), pages 1-19, April.
    20. Palubeckis, Gintaras & Tomkevičius, Arūnas & Ostreika, Armantas, 2019. "Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimization," Applied Mathematics and Computation, Elsevier, vol. 348(C), pages 84-101.

    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:gam:jmathe:v:9:y:2020:i:1:p:5-:d:466269. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.