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