当前位置:首页  科研成果  论文与专著
最小化双进出口自动存取系统总旅行时间的多项式时间算法
作者:张鑫   来源:现代物流与供应链安徽省重点实验室 阅读次数:68 日期:2021-01-16
  

Polynomial Time Algorithms to Minimize Total Travel Time in a Two-Depot Automated Storage/Retrieval System

(最小化双进出口自动存取系统总旅行时间的多项式时间算法)

 

随着物联网、云计算、大数据等新技术的发展,自动化仓储系统被广泛应用于集装箱码头等场景中。然而,自动化仓库的运作机制与传统仓库截然不同,导致传统仓储系统存取策略无法适用于自动化仓储系统。自动货物存取过程的本质是一类属于NP-hardTSPTraveling Salesman Problem)问题,即非对称旅行商问题(Asymmetric TSP,简称ATSP)。相关问题的求解一直存在着理论瓶颈,只有在特定场景下才能找到精确或多项式算法。本中心首先将双进出口自动存取系统(Automated Storage/Retrieval System,简称AS/RS)的存取顺序优化归为ATSP。为优化双进出口AS/RS货物存取的总旅行时间,本中心利用存取货物进出口位置不同的5种情形下双进出口AS/RS的存储特点,构建子回路消除约束(图5举例说明),并分别给出了相应的多项式时间算法。对比已经普遍使用的First Come First Served(先到先服务)和Nearest Neighbor(最近邻域)算法,本中心提出的算法能够把平均集装箱存取时间分别减少超过30%15%

 

5. 双进出口AS/RS总旅行时间优化问题中的子回路以及子回路合并消除示例

该研究填补了双进出口AS/RS货物存取顺序优化研究的空白,相关研究成果发表于交通运输领域顶尖期刊Transportation Science (2017,51(1),19-33)





 


Copyright 2014 中国科学技术大学现代物流和供应链安徽省重点实验室 All Rights Reserved.
地址:合肥市滨湖新区广西路1789号 邮编:230029 电话:+86-551-63602689