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

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

随着物联网、云计算、大数据等新技术的发展，自动化仓储系统被广泛应用于集装箱码头等场景中。然而，自动化仓库的运作机制与传统仓库截然不同，导致传统仓储系统存取策略无法适用于自动化仓储系统。自动货物存取过程的本质是一类属于NP-hard的TSP（Traveling 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)。