IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v338y2024i2d10.1007_s10479-024-06039-9.html
   My bibliography  Save this article

A uniform sampling method for permutation space

Author

Listed:
  • Lin Gui

    (Huazhong University of Science and Technology
    City University of Hong Kong)

  • Xinyu Li

    (Huazhong University of Science and Technology)

  • Qingfu Zhang

    (City University of Hong Kong)

  • Liang Gao

    (Huazhong University of Science and Technology)

Abstract

Uniform sampling in the permutation space is very important for solving permutation problems with NP-hard nature. However, due to the complexity of this space, there is no uniform sampling method for it up to now. In this paper, the description of permutation space and a review of uniform sampling in other space are given. After that, the limitation of the random method for uniform sampling is analyzed, and a k-means clustering algorithm with an improved Borda's method is introduced for sampling based on the above analysis. An extended Latin matrix is defined, and a sampling method based on this matrix that can only solve for a fixed number of sampling is presented. The properties of this method are explored and demonstrated. A uniform sampling method is then proposed for an arbitrary number of sampling points. Experiments are implemented under different sizes of permutation spaces and the results show that the method proposed in this paper has superior performance, which is more than 100 times better than the random method.

Suggested Citation

  • Lin Gui & Xinyu Li & Qingfu Zhang & Liang Gao, 2024. "A uniform sampling method for permutation space," Annals of Operations Research, Springer, vol. 338(2), pages 925-945, July.
    • Handle: RePEc:spr:annopr:v:338:y:2024:i:2:d:10.1007_s10479-024-06039-9
    DOI: 10.1007/s10479-024-06039-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-024-06039-9
    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/s10479-024-06039-9?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. Nour El Houda Tellache & Mourad Boudhar, 2018. "Flow shop scheduling problem with conflict graphs," Annals of Operations Research, Springer, vol. 261(1), pages 339-363, February.
    2. Chi, H. & Mascagni, M. & Warnock, T., 2005. "On the optimal Halton sequence," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 70(1), pages 9-21.
    3. Michael Hassoun & Shraga Shoval & Eran Simchon & Liron Yedidsion, 2020. "The single line moving target traveling salesman problem with release times," Annals of Operations Research, Springer, vol. 289(2), pages 449-458, June.
    4. D.C. Mattfeld & C. Bierwirth & H. Kopfer, 1999. "A search space analysis of the Job Shop Scheduling Problem," Annals of Operations Research, Springer, vol. 86(0), pages 441-453, January.
    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. Zhuang, Yanling & Zhou, Yun & Yuan, Yufei & Hu, Xiangpei & Hassini, Elkafi, 2022. "Order picking optimization with rack-moving mobile robots and multiple workstations," European Journal of Operational Research, Elsevier, vol. 300(2), pages 527-544.
    2. Said Aqil & Karam Allali, 2021. "On a bi-criteria flow shop scheduling problem under constraints of blocking and sequence dependent setup time," Annals of Operations Research, Springer, vol. 296(1), pages 615-637, January.
    3. Vandewoestyne, Bart & Chi, Hongmei & Cools, Ronald, 2010. "Computational investigations of scrambled Faure sequences," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 81(3), pages 522-535.
    4. Maskooki, Alaleh & Deb, Kalyanmoy & Kallio, Markku, 2022. "A customized genetic algorithm for bi-objective routing in a dynamic network," European Journal of Operational Research, Elsevier, vol. 297(2), pages 615-629.
    5. Yong Chen & Yinhui Cai & Longcheng Liu & Guangting Chen & Randy Goebel & Guohui Lin & Bing Su & An Zhang, 2022. "Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph," Journal of Combinatorial Optimization, Springer, vol. 43(3), pages 571-588, April.
    6. Maskooki, Alaleh & Kallio, Markku, 2023. "A bi-criteria moving-target travelling salesman problem under uncertainty," European Journal of Operational Research, Elsevier, vol. 309(1), pages 271-285.
    7. Chi Hongmei, 2013. "Generation of parallel modified Kronecker sequences," Monte Carlo Methods and Applications, De Gruyter, vol. 19(4), pages 261-271, December.
    8. Jaromił Najman & Dominik Bongartz & Alexander Mitsos, 2021. "Linearization of McCormick relaxations and hybridization with the auxiliary variable method," Journal of Global Optimization, Springer, vol. 80(4), pages 731-756, August.
    9. Chi, Hongmei & Beerli, Peter, 2014. "Quasi-Monte Carlo method in population genetics parameter estimation," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 103(C), pages 33-38.
    10. Miriyala, Srinivas Soumitri & Subramanian, Venkat & Mitra, Kishalay, 2018. "TRANSFORM-ANN for online optimization of complex industrial processes: Casting process as case study," European Journal of Operational Research, Elsevier, vol. 264(1), pages 294-309.
    11. Xinyu Sun & Xin-Na Geng & Tao Liu, 2020. "Due-window assignment scheduling in the proportionate flow shop setting," Annals of Operations Research, Springer, vol. 292(1), pages 113-131, September.
    12. Bayousef Manal & Mascagni Michael, 2019. "A computational investigation of the optimal Halton sequence in QMC applications," Monte Carlo Methods and Applications, De Gruyter, vol. 25(3), pages 187-207, September.
    13. Dong, Gracia Y. & Lemieux, Christiane, 2022. "Dependence properties of scrambled Halton sequences," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 200(C), pages 240-262.
    14. Aparecida de Fátima Castello Rosa & Fabio Henrique Pereira, 2024. "An intensification approach based on fitness landscape characteristics for job shop scheduling problem," Journal of Combinatorial Optimization, Springer, vol. 47(5), pages 1-21, July.

    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:annopr:v:338:y:2024:i:2:d:10.1007_s10479-024-06039-9. 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.