基于临界多边形的二维不规则排样问题的研究.docx

基于临界多边形的二维不规则排样问题的研究
摘要：
二维不规则排样问题是指在给定的平面上，将一系列不规则形状的物体进行排列，使得它们相互之间不发生重叠。在物流、制造等领域中，不规则排样问题具有重要的应用价值。本论文以临界多边形为基础，研究了二维不规则排样问题，并提出了一种基于临界多边形的排样算法。
第一节引言
1.1研究背景
随着物流和制造技术的发展，不规则排样问题的研究越来越受到重视。不规则排样问题的解决可以提高物体的利用率，减少生产成本和空间浪费，提高生产效率。因此，不规则排样问题在实际应用中具有重要的意义。
1.2研究目的
本论文旨在研究二维不规则排样问题，探索基于临界多边形的排样算法，提高排样效率和空间利用率。
第二节相关工作
2.1传统排样算法
传统的排样算法通常基于启发式方法，如贪心算法、遗传算法等。这些算法在某些特定情况下有效，但在处理不规则形状时存在一定的局限性。
2.2临界多边形
临界多边形是指能够完全包围物体的最小凸多边形。临界多边形的研究可以帮助我们更好地理解和处理不规则形状。
第三节基于临界多边形的二维不规则排样算法
3.1临界多边形的生成
根据物体的形状，在给定平面中生成能够完全包围物体的临界多边形。利用凸包算法可以有效地生成临界多边形。
3.2优化排样结果
根据生成的临界多边形，将不规则物体进行排列。通过遗传算法和局部搜索算法等方法，优化排样结果，使得物体之间的空隙最小化。
第四节实验结果和分析
通过对比传统排样算法和基于临界多边形的算法，我们发现基于临界多边形的算法在处理不规则形状时具有更好的效果。排样效率和空间利用率较传统算法有明显的提升。
第五节结论和展望
本论文基于临界多边形的二维不规则排样问题进行了研究，并提出了一种基于临界多边形的排样算法。通过对实验结果的分析，我们发现该算法能够在处理不规则形状时展现出优势。然而，还有许多问题有待解决，例如算法的时间复杂度和适用范围的问题。未来的研究方向可以是进一步优化算法，增加算法的鲁棒性和适用性。
参考文献：
[1]GutiérrezR,etal.Asurveyoftwo-dimensionalbinpackingalgorithmswithnewheuristicfortheorthogonalshapes[J].AnnalsofOperationsResearch,2020,286(1-2):319-343.
[2]SongX,LuoY,ZongY.Atwo-dimensionalirregularpackingalgorithmbasedondynamicboundary[J].TheInternationalJournalofAdvancedManufacturingTechnology,2016,82(1-4):583-594.
[3]HaS.AnImprovedRectangleBinPackingAlgorithmforSoftwareOptimizations[J].arXivpreprintarXiv:1802.03834,2018.