Abstract

We report on a joint project with industry that had the aim to sequence transportation requests within an automatic storage system in such a way that the overall travel time is minimized. The manufacturing environment is such that scheduling decisions have to be made before all jobs are known. We have modeled this task as an online Asymmetric Traveling Salesman Problem (ATSP). Several heuristics for the online ATSP are compared computationally within a simulation environment to judge which should be used in practice. Compared to the priority rule used so far, the optimization package reduced the unloaded travel time by about 40 %. Because of these significant savings our procedure was implemented as part of the control software for the stacker cranes of the storage systems
Keywords : Traveling Salesman Problem, Online-Algorithm, Automatic Storage System

1 Introduction

摘 要
我們和企業(yè)提出了一個聯(lián)合項目，旨在通過最短的時間用自動化存儲系統(tǒng)將運輸請求按順序排列。其生產(chǎn)工作環(huán)境是在所有工作確定前要安排決定。我們將這種任務(wù)稱為在線非對稱旅行商問題（ATSP）。在一個模擬環(huán)境里，一些針對在線ATSP問題的啟發(fā)式方法被通過計算比較來判定什么方法將在實踐中被采用。比較到目前為止所采用的主要規(guī)則，包裹優(yōu)化減少了無載貨運輸時間的40%。由于這重要的節(jié)省，我們的程序被作為存儲系統(tǒng)中堆垛起重機控制軟件的一部分執(zhí)行。
關(guān)鍵詞：TSP問題，在線算法，自動化存儲系統(tǒng)