PackageCargo：一个高性能集装箱装载问题的决策支持工具

SoftwareX 12（2020）100601原始软件出版物PackageCargo：一个求解稳定集装箱装载问题的决策支持工具Juan Martinez-Franco，Edgar Céspedes-Sabogal，David Álvarez-MartinezLos Andes大学工程学院，Cra 1 N18 A-12 Bogotá D.C，哥伦比亚ar t i cl e i nf o文章历史记录：接收5可以2020收到修订版2020年9月29日接受2020年9月30日关键词：优化货物稳定性物理引擎Unitya b st ra ct本文介绍PackageCargo。一个使用Unity游戏引擎开发的模块化开源应用程序，通过近似优化算法（metabolistics）获得的包装模式。此外，所提出的工具允许我们通过实施数学模型来估计货物稳定性指标，并使用PhysX库构建的仿真环境来验证所述模型的结果。该应用程序的目标是创建一个适用于工业目的的可用决策支持系统以及学术研究平台。它提供了一个可修改的框架，可以适应用户的需求，节省他们的软件开发时间，同时继续通过社区贡献扩展PackageCargo。将由此产生的应用程序与商业软件解决方案进行了比较。此外，每个模块都使用文献中最成功的方法作为基准进行了测试。包装模块进行了比较，对最高性能的算法公布的日期，在类似的计算时间获得类似的结果。货物稳定性模拟模块与高性能模拟软件进行了基准测试，验证了其准确性和性能。因此，PackageCargo被认为具有在学术和商业环境中都有用的竞争性功能集。作为未来的工作，建议结合不同的模块来解决CLP的更复杂的变体，如约束到重量分布曲线的集装箱装载问题©2020作者（S）。由爱思唯尔公司出版这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）中找到。代码元数据当前代码版本v1.0.1用于此代码版本的代码/存储库的永久链接https://github.com/ElsevierSoftwareX/SOFTX_2020_198Code Ocean compute capsule法律代码许可证GPL 3.0使用git的代码版本控制系统使用C++、C#、MySQL、Unity、PhysX的软件代码语言、工具和服务编译要求、操作环境依赖性Unity Editor 5.6.6或更高版本（如果可用）链接到开发人员文档/手册技术支持邮箱：uniandes.edu.co软件元数据当前软件版本1.0.1指向此版本可执行文件的永久链接例如：https://github.com/jcmartinez10/PackageCargo/releases/tag/v1.0.1-alpha法律软件许可证GPL-3.0计算平台/操作系统Microsoft Windows，分布式/基于Unity Editor 5.6.6或更高版本如果可用，请链接到用户手册-如果正式出版，请在参考列表中引用该出版物https://github.com/jcmartinez10/PackageCargo/blob/master/README.md技术支持邮箱：uniandes.edu.co*通讯作者。电子邮件地址：d. uniandes.edu.co（D. 阿尔瓦雷斯-马丁内斯）。https://doi.org/10.1016/j.softx.2020.1006012352-7110/©2020作者。 由Elsevier B.V.出版。这是一篇开放获取的文章，使用CC BY许可证（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表SoftwareX期刊主页：www.elsevier.com/locate/softxJ. Martínez-Franco，E. Céspedes-Sabogal和D. 阿尔瓦雷斯-马丁内斯SoftwareX 12（2020）10060121. 动机和意义货物运输提出了重大的物流挑战，虽然在学术环境中经常探讨，但货运公司和客户几乎没有解决这些挑战之一与集装箱内货物的布置有关，该任务被正式定义为集装箱装载问题（CLP）。CLP具有广泛的适用性和数学特性，使其对研究人员和行业都具有吸引力，但接近它的新策略尚未在现实世界中广泛部署。这可能是因为用于解决这些挑战的软件工具是专有的或许可的，因此不可用于较小的行为者或在学术环境中使用。为了应对所描述的情况，我们引入了一个开源工具，该工具涉及CLP的一个变体的解决方案，该变体考虑了货物的物理行为。有多个应用程序集中在生成基- 为CLP提供解决方案。这些应用程序的功能范围从简单的几何优化到网络连接（Cubemaster®R）、重心相关约束（LoadCargo®R）以及方向和承载约束（EasyCargo®R）。据我们所知，没有软件包提供我们试图在本申请中包括的所有功能，特别是关于货物稳定性和软件可扩展性。在探索的软件选项中，我们找不到一个免费的替代品，其功能与可用的商业解决方案相当，也找不到提供源代码的应用程序。为了解决这个问题，一个新的应用程序开发使用的游戏开发套件的Unity的RightsR （C#），使用模块化设计，其包括计算CLP的解决方案（称为堆积模式）、所述解决方案的可视化以及估计货物的货物稳定性的模拟环境。所提出的工具（PackageCargo）的开源性质允许研究人员以及公众集成他们的设备，无论他们是面向模拟还是优化，而不需要实现整个框架。以这种方式，将侧重于模拟的工作耦合起来涉及允许找到有效封装模式的默认优化算法。与商业解决方案相比，建议的应用程序具有竞争性的功能集。1.1. 集装箱装载问题集装箱装载问题包括将矩形箱子装入矩形空间或集装箱中，确保箱子不重叠，并使体积利用率最大化[1]。这个问题在切割和包装问题中非常重要，被归类为NP-Hard问题[2]。这种分类导致CLP通常使用近似优化算法来接近。增加CLP复杂性的一些因素是与问题变体相关的实际约束。Bortfeldt [3]编制了一套适用于CLP的功能约束，其中，这项工作非常关注货物稳定性。几位作者认为货物稳定性是最重要的约束[4除了货物稳定性之外，PackageCargo还考虑了箱子方向、承载强度、重量限制、全支撑定位和多个目的地的拆分装载（多点约束）的约束。1.2. 货物稳性货物稳性是指货物在运输过程中的平衡。实质上，如果货物的几何构造和物理完整性在装载和卸载操作期间以及在运输时的加速期间被保持，则货物被认为是稳定的。用于评估货物稳定性的两个指标是掉落箱数（NFB）和损坏边界曲线（NB_DBC）内的盒子。前者是指在集装箱运动的初始状态和最终状态之间沿着集装箱的垂直轴线永久移位的箱子的数量。与此同时，后者是遭受剧烈变化的盒子数量，在给定的时刻，速度或过度的加速度。可接受的加速度和速度增量值基于[7]中所述的测试，用于确定物品的易碎性。通常，通过在专用的高精度仿真软件或称为物理引擎的实时仿真中间件上运行动态仿真来获得稳定性度量。2. 软件描述PackageCargo是一个为货物实例生成和可视化包装模式的应用程序。货物实例是物品的结构化列表，具有预定义的大小、方向约束和将被加载到预定大小的容器中的承载约束货物定义，以及生成的模式，可以可视化，保存和检索（见图。①的人。打包模式也可以进行模拟，使用不同的技术返回稳定性度量。2.1. 软件构架图2说明了程序的架构。该体系结构包括四个模块：可视化，由渲染器和用户界面组成，包括模拟和优化结果以及性能指标;模拟模块，测试装载模式的货物稳定性;优化，允许包含用于生成包装模式的不同算法;以及数据库，管理注册数据以及由优化和模拟模块生成的数据。3D环境中的包和容器的可视化是使用Unity的渲染引擎实现的Unity还包括一个广泛的UI库，允许为工具创建界面（见图10）。3）。动态模拟可以使用Unity（Nvidia的PhysX）提供的物理引擎进行，也可以使用基于货物简化机械模型的算法进行PhysX存在两个关键限制：它产生的随机结果可能会在多次执行中发生变化，并且它优先考虑性能而不是准确性[10]。物理引擎的准确性通过使用Autodesk Inventor中的高精度仿真环境的基准测试进行了测试[9]。打包模式生成器使用[11]中描述的GRASP算法来生成有效的打包模式。尽管如此，这个任务可以由大量的算法来执行，这些算法可以通过内存或系统文件直接链接到应用程序优化模块与默认包含的GRASP算法相关联[11]。该算法在CLP的3500个经典实例中表现出了竞争力[12]，如表1所示。表1说明了大型类人猿生存项目方法和已公布的同类最佳方法之间的公平J. Martínez-Franco，E. Céspedes-Sabogal和D. 阿尔瓦雷斯-马丁内斯SoftwareX 12（2020）1006013Fig. 1. 应用程序接口。不同的菜单选项与组成该工具的每个模块相关。 集装箱和货物配置实时更新和可视化提供了一些可视化选项，包括可切换的集装箱和/或托盘可见性图二. PackageCargo的架构。不同的协议将应用程序客户端连接到外部数据库、运行打包算法的服务器或该类型算法的本地实例。函数调用从默认物理引擎（PhysX）或自定义解决方案获取模拟结果的请求。可视化管理通过客户端的内部Unity设置一种解决集装箱装载问题的方法，该方法考虑了与箱子方向、重量限制、完整包装支撑、承载限制和多个货物目的地有关的对于每个数量的客户（1、2、5、10、50）和问题族（BR 1-BR 7），将确定一组100个实例，并报告每组的平均卷利用率。在合理的计算时间内，该算法在具有上述约束的CLP实例然而，可以通过连接到服务器的套接字或通过直接调用可执行程序来使用其他加载算法，使得用户可以比较它们并生成关于与稳定性有关的性能指标的报告。对于通过套接字的数据流，在客户端-服务器架构中建立TCP/IP连接，这意味着外部加载算法必须定义为从客户端应用程序接收请求的服务器。对于可执行文件，用户必须将其算法构建为目标平台（Windows、macOS或Linux）支持的可执行文件。数据存储模块管理所有信息，无论是由用户注册还是由其他模块 生 成 。 结 果 记 录 在 位 于 中 心 化 服 务 器 上 的 数 据 库（MySQLSQLServer）中，任何用户都可以通过请求访问该此模块执行调用以记录、更新和删除与用户创建的实例相关的信息。它有一个PHP接口，可以修改数据库SQL命令数据库存储货物信息、集装箱尺寸、包装模式和（可选地）货物稳定性度量。3. 示例使用PackageCargo可以为CLP实例生成和可视化打包模式，同时考虑到文献中公布在PackageCargo中，1500个经典的测试实例被默认存储[12]，用户可以定义一个新的实例并存储它。当一个算法被执行以立即解决一个测试用例时，它的结果被存储在云中。这样，用户可以决定加载现有的实验（测试实例或解决方案及其性能指标）或开始新的实验。开始一个新的实验包括定义货物和集装箱的属性，如图所示。3 . 第 三 章 。 当 用 户 创 建 实 例 并 为 其 执 行 优 化 算 法 时 ，PackageCargo将实例的结构化数据发送到在服务器端运行的之后，用户可以选择保存数据（执行因此将在远程数据库中存储所述实例和生成的解决方案）、计算若干性能度量、或者甚至手动修改解决方案。J. Martínez-Franco，E. Céspedes-Sabogal和D. 阿尔瓦雷斯-马丁内斯SoftwareX 12（2020）1006014表1GRASP性能（以卷利用率百分比和计算时间衡量）与同类最佳算法[11]。客户把握克里斯滕森·鲁索BR1BR2BR3BR4BR5BR6BR7平均192,4792,7592,7692,2291,6891,0189,6291,7989,07291,7790,7689,4788,5687,7886,6985,5188,6585,96588,5686,0283,1581,3680,1478,3076,1281,9578,521085,2881,4377,8276,1474,4772,4570,2276,8372,645079,3273,9668,9866,8764,8563,2560,6168,2664,45平均87,4884,9882,4481,0379,7878,3476,4281,5078,13时间（秒）30,2934,0137,9341,9857,1863,3569,9447,8160,00图三. 应用程序中新CLP实例的定义。图形界面允许用户定义货物种类、尺寸、约束和数量。该信息被转换为用于打包模式生成算法的输入文件4. 扩展性软件架构允许程序的不同模块被用户定义的模块取代。例如，发动机的动态模拟可以交换为返回相同模拟度量的简单机械模型。动态模拟的函数调用甚至可以引用在外部运行物理引擎。作为替代模拟环境的一个例子，我们包括一个基于运动力学的算法，该算法从包装配置解决方案中估计货物稳定性。该算法通过修改模拟GUI中的一个简单函数调用类似地，产生集装箱装载问题的实例的解决方案的优化模块可以通过以下方式切换：用户定义的算法。新算法的钩子可以指向本地可执行文件或外部套接字解决方案。打包的解决方案基于在客户端运行的GRASP算法的实现5. 影响PackageCargo在两个方面做出了重大贡献：商业应用和研究援助。在前者中，我们的软件工具实现了与EasyCargo [13]和LoadCargo [14]等专业工业应用程序相当的功能再加上优化和模拟的复杂算法开发，它将自己定位为付费软件但与此同时，它鼓励开发者（行业参与者和研究人员）用他们认为必要的功能来补充它。PackageCargo的开源性质使该软件易于获得，以寻求增强其超出本工作范围的能力。它还使- fered优化和仿真工具提供给科学和学术界，允许仿真模型和优化算法的评估。该软件已被用来测试一种新的算法，能够预测货物稳定性指标非常短。模拟模块被替换为对使用cargo定义参数的C#方法与动态模拟相比，在更短的时间内产生结果。软件中包含了增强功能6. 结论我们介绍了PackageCargo，一个模块化的软件工具，能够获得集装箱装载问题的实例的解决方案PackageCargo允许定义货物属性、集装箱大小和运输约束，以及用于为定义的实例生成打包模式的该软件已被用于研究涉及货物稳定性约束，并被认为是一个可行的替代客户使用现有的商业解决方案。该工具提供了一个模块化的体系结构，允许学术和工业部门轻松地扩展或修改应用程序，以更好地J. Martínez-Franco，E. Céspedes-Sabogal和D. 阿尔瓦雷斯-马丁内斯SoftwareX 12（2020）1006015满足他们的需求。此外，可以使用应用程序中的网络功能远程保存和访问实例和算法。竞合利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作致谢该项目是作为SIC项目的一部分实施的，哥伦比亚科学、技术和创新部。引用[1] 放大图片作者：Wäscher G，Haußner H，Schumann H.改进的切割和包装问题的类型学。E J Oper Res2007;183（3）：1109-30。[2] 皮辛格湾集装箱装载问题的启发式算法。European J OperRes2002;141（2）：382-92.[3] Bortfeldt A，Wäscher G.集装箱装载中的约束--最先 进 的 综 述 。European JOper Res 2013;229（1）：1[4]Bischoff EE.托盘装载的稳定性方面。OR Specktrum1991;13（4）：189-97.[5]A，Oliveira JF.集装箱装载问题的GRASP方法。IEEE Intell Syst2005;20（4）：50-7.[6]Parreño F，Alvarez R，Oliveira J，Tamarit J.集装箱装载问题的最大空间算法。Inform J Compt 2008;20（3）：412[7]ASTM International.机械冲击脆性的标准试验方法的产品。2010年。[8]Unity Technologies。Unity是一款世界性的软件，在游戏行业中非常流行。2017年，在线提供http://www.unity.com/。发布（2017年2月2日）。[9]Martinez-Franco J，Alvarez-Martinez D. PhysX作为集装箱装载问题动态模拟的中间件，2018年冬季模拟会议论文集。2018年[10]PhysX 是 一 个 可 扩 展 的 多 平 台 游 戏 物 理 解 决 方 案 。 2016 年 ， 在 线 提 供https://developer.nvidia.com/physx-sdk。发布（2016年12月20日）。[11]Alvarez-Martínez D，Alvarez R，Parreño F.多点约束集装箱装载问题的抓取算法。Pesq Oper2015;35：1-24.[12]比肖夫EE，拉特克利夫MSW。制定集装箱装载方法方面的问题。欧米茄1995;23：377-90.[13]EasyCargo 。 Easycargo 是 卡 车 和 集 装 箱 装 载 软 件 。 2017 年 ， 在 线 提 供http://www.easycargo3d.com/。发布（16/04/2017）。[14]装货集装箱和卡车装载软件。2017年，在线提供https://www.loadcargo.in/。发布（16/04/2017）。