資源目錄里展示的全都有預覽可以查看的噢，，下載就有,,請放心下載，原稿可自行編輯修改=【QQ：11970985 可咨詢交流】====================喜歡就充值下載吧。。。資源目錄里展示的全都有，，下載后全都有,,請放心下載，原稿可自行編輯修改=【QQ：197216396 可咨詢交流】==================== 由一個單一的存儲/檢索機服務的多巷道自動化立體倉庫存在的揀選分揀問題Yaghoub Khojasteh-Ghamari Yaghoub Khojasteh Jae-Dong Son 加馬里筑波大學 崇實大學 日本 韓國 Abstract摘要 隨著Recent technological developments have revolutionized the design and operation of ware-現(xiàn)代化科技的發(fā)展，倉庫式存儲系統(tǒng)在設計與運行方面出現(xiàn)了巨大的改革。自動化立體倉庫（AS / RS）嵌入計算機驅動正變得越來越普遍。由于AS / RS使用的增加對計算機控制的需要與支持也在提高。這項研究解決了在多巷道立體倉庫的揀選問題，在這種存儲/檢索（S / R）操作中，每種貨物可以在多個存儲位置被尋址到。提出運算方法的目標是，通過S/R系統(tǒng)揀選貨物來最大限度的減少行程時間。我們開發(fā)的遺傳式和啟發(fā)式算法，以及通過比較從大量的問題中得到一個最佳的解決方案。 Keywords: Automated Warehouse, AS/RS, Order Picking, Genetic Algorithms. 關鍵詞：自動化立體倉庫，AS / RS系統(tǒng)，揀選，遺傳算法。 1.Introduction導言 在現(xiàn)今的生產(chǎn)環(huán)境中，庫存等級保持低于過去。那是因為這種較小的存儲系統(tǒng)不僅降低庫存量還增加了揀選貨物的速度。自動化立體倉庫（AS / RS），一方面通過提供快速響應，來達到高操作效率；另一方面它還有助于運作方面的系統(tǒng)響應時間，減少的揀選完成的總行程時間。因此，它常被用于制造業(yè)、儲存?zhèn)}庫和分配設備等行業(yè)中。 揀選是倉庫檢索功能的基本組成部分。它的主要目的是，在預先指定的地點中選擇適當數(shù)量的貨物以滿足客戶揀選要求。雖然揀選操作僅僅是物體在倉儲中裝卸操作之一，但它卻是“最耗時間和花費最大的倉儲功能。許多情形下，倉儲盈利的高低就在于是否能將揀選操作運行處理好”。 （Bozer和White） Ratliff和Rosenthal，他們關于自動化立體倉庫系統(tǒng)（AS/RS）的揀選問題進行的研究，發(fā)明了基圖算法，在階梯式布局中選取最短的訪問路徑。Roodbergen 和 de Koster 拓展了Ratliff 和Rosenthal算法。他們認為，在平行巷道揀選問題上，應該穿越巷道末端和中間端進行揀選，就此他們發(fā)明了一種動態(tài)的規(guī)劃算法解決這問題。就此Van den Berg 和 Gademann發(fā)明了一種運輸模型(TP)，它是對于指定的存儲和卸載進行測算的儀器。他們表示，最好的解決運輸問題的方法是以機械的最佳布局來盡量減少運行時間。 Elsayed對階梯結構的立體倉庫問題的研究表明，要在多巷道中揀選貨物并擬定最佳方案，是非常困難和并且耗時的。 Elsayed 和 Stern提出了啟發(fā)式算法，但據(jù)說，他們并沒有在實際生產(chǎn)過程中得到滿意的結果。黃禹錫等人，研究了立體倉庫系統(tǒng)中的單巷道選道的問題，并提出決定了每個S /R系統(tǒng)揀選效率的啟發(fā)式算法。Thealgorithms在聚集前人分析的基礎上，采取了一些相似的措施。在1983年，通過仿真，把計算得到的參數(shù)與Elsayed和Sterns的結論進行了比較。 Bozer、White、Han、Lee和Schaefer等人提出了一個程序，在檢索測序的基礎上進行優(yōu)化，解決了線性分配的問題。Lee 和 Schaefer介紹了一些優(yōu)化和啟發(fā)式的測序方法，其中包括存儲指令如何被分配到預先確定的存儲位置。Mahajan通過對小件貨物的貯存系統(tǒng)進行了改善，得到了一種新的檢索測序方案，提出最近檢索原則并開發(fā)了一個驗證模型來預測效果。黃禹錫制作了非線性數(shù)學模型，開發(fā)出以一種啟發(fā)式程序設計的自動化立體倉，與此同時還可以確定單位負載的大小。Van den Berg 和 Rouwenhorst 調查了倉庫規(guī)劃和控制的文獻，規(guī)劃文件包括存儲位置的分配問題，倉庫儲存系統(tǒng)的控制問題包括路由、排序、調度、停留點的選擇和秩序配料。 Goetschalckx 和 Wei提交1985年至1992年揀選系統(tǒng)的參考文獻。 Koh提出了一些關于在存儲倉庫中，帶有塔式起重機的自動化立體倉庫的模式。他們推論出的這個模式是建立在隨機存儲分配規(guī)則的基礎上的一個單、雙指令周期。他們還根據(jù)營業(yè)額的存儲分配規(guī)則計算出相應行程時間。Koh提出了優(yōu)化模式，在揀選系統(tǒng)的巷道最末端尋找到了一個最佳緩沖的區(qū)域，在那里S/R系統(tǒng)可提供多若干個通行巷道。Amato以colored timed Petri nets網(wǎng)站的資料為基礎提出了對順序檢索的揀選優(yōu)化算法。他們還提出了兩項對于起重機和航天飛機的運作的優(yōu)化控制算法。Hsu審議多巷道的倉庫的順序配料問題，提出了遺傳算法來減少總旅行距離。Hwang 和 Cho提出了采摘的供應中心倉庫秩序的績效評估模式。他們研究的目的是通過減少運輸數(shù)量、計算性能和設備利用率來減少盡量減少成本。在近期的研究中，De Koster 對設計與控制手冊中揀選工程的典型決定問題進行了文獻回顧。他們主要關注于存儲分配方法、路徑的選擇、配料和分區(qū)。 然而，我們沒有這么多的文獻上的知識，在處理自動化立體倉庫的揀選問題上，每個物品都能夠被儲存在多個儲存點里。事實上，許多廠家的產(chǎn)品有許多類型、種類和形狀，這也是他們成品倉庫面臨的問題。例如一個瓷磚制造商，他的產(chǎn)品有兩個類型（墻磚和地磚）,分別有7中不同的尺寸，4種不同耐久性（磨損差餉)和100多種不同的顏色、圖案、顏色和形狀，總共有5600多種不同的產(chǎn)品類型。作為存儲策略，要一件剛進來的貨物存放在最近的空倉位位置上。當一個來自倉庫中物品，由于產(chǎn)品種類繁多，有很大的可能性從一個地方存入到另一個地方。因此，一件物品需要有幾個在倉庫中存儲位置。換句話說，由于分類和分區(qū)，每個單獨類型的產(chǎn)品在倉庫中需要一個更大的空間，一個物品在幾個地方存儲時不可避免的。 2.問題描述 在本研究中，我們考慮到了小件物品的自動存儲和檢索系統(tǒng)，那有一個或多個巷道。每個巷道包含了關于巷道兩旁倉儲貨架。每個巷道結束的地方都有一個輸入/輸出口（I/O）。在那里還有一個單獨的存儲/檢索（S / R）的儀器來為所有巷道的系統(tǒng)服務，它可以同時在垂直和水平方向移動。因此，在兩點之間的行程等于最小的水平和垂直行程。在收到命令之前S/R儀器已經(jīng)定位了輸入/輸出口中的位置。儀器的起始位置取決于最后一件貨物的最后一個命令的存儲位置。S/R計算行程中以恒定的速度水平和垂直移動。一個命令可以由多個貨物請求組成的。同樣每個貨物也可以在倉庫中多個位置存儲。當檢索請求包括多個貨物，并且這些貨物在多個不同的倉庫位置時，S/R儀器必須到多個不同的存儲地點完成各個命令。本次研究的目的就是提出計算方法來減少S/R走過的總時間來完成命令程序。 3.運算方法 我們現(xiàn)在有兩種運算方法來解決這個問題：一種是探索式算法，還有一種是遺傳式算法。為了顯示所提出算法的優(yōu)越性，我們把它與其他方法進行了比較。由于我們的解決問題方法是新提出的，沒有前人在這個領域進行過研究，那么我們最先提出的一種運算法，用它來獲取的最佳的解決方案，這種方法我們稱它為例證算法。其結果作為對于兩種擬議算法比較的基準解決方案。 在例證法中，我們確定所有可行的解決方法并將他們互相比較找出最好的解決方法來。為此，這個方案首先要找所有可行的方法來選擇一個命令。然后，S/R系統(tǒng)的計算獲得每個方法行程的總時間，最后，選取的解決方案要求在最短時間內完成要求。這個解決方案被認為是該問題的最佳解決方案?？紤]到一個命令的由k種不同類型的貨物組成，其中在ni(i = 1, 2, . . . , k)項貨物中第i項貨物被提出請求。在可行的解決辦法總數(shù)挑選順序可以給出： 其中，mi是在第i項貨物在倉庫中的總庫存，得出： 通過例證法已經(jīng)解決了各種類型的問題，并且確定了這種低金額低行程的最佳方案。我們發(fā)現(xiàn)，在當前巷道上存在貨物（如：該巷道的S/R系統(tǒng)是在檢索過程的起始端）是解決這個問題的關鍵技術。我們基于先前提到的運算結果發(fā)現(xiàn)了一種計算方法，稱它為現(xiàn)有巷道探索式（CAH)算法。 在現(xiàn)有巷道探索式算法中，在當前巷道中現(xiàn)存的貨物是首先被檢索的對象。其后，對該命令的其余部分（如果有的話）選中并運用各種檢索方式進行研究計算。我們可以簡單的對其進行表達，如果設r表示在現(xiàn)有巷道中指令貨物的數(shù)目，那么如果r=0時，該運算方法就類似于原來的例證法。如果r=1時，該運算方法首先要通過S/R系統(tǒng)對行程時間進行計算，設t1表示在當前巷道中，現(xiàn)存貨物為了避免與揀選中的貨物沖突，對于其余的貨物(如果有的話)進行同等于例證法的計算，以此來得到最小的計算行程時間。設t2表示在S/R系統(tǒng)中總的行程時間。最后將t1和t2之和作為最終的解決方案。 如果r>1時，則該方法首先分配揀選順序，揀選所有的r貨物，既巷道中的現(xiàn)存貨物。在計算好行程時間之后，進入t1階段開始移除列表中指令的貨物。在這之后，其余貨物(如果有的話)進行類似于例證法的運算,就如同，通過對每一個可行的方法計算出行程時間，最終選取其中最小的那個值，即t2階段。最后，在S/R系統(tǒng)中將t1和t2的和設為最終的解決方案。 Khojasteh-Ghamari詳細的對在現(xiàn)有巷道中的貨物的揀選順序的分配方法進行了討論。如果任何待命的貨物存在于現(xiàn)有巷道中，那么就將倉庫中現(xiàn)存貨物的數(shù)目除以解決方案的數(shù)目。因此，這項任務目的就是降低總方案的數(shù)目，以此來減少CPU時間（程序的處理時間）。 3.1.遺傳算法 遺傳算法是一種優(yōu)化過程，它將問題域比作基因類（個體或染色體），基因類是有多個基因體組成，其中基因體成符號形式串行。每一個基因類都有一個可能的解，通過對問題域中的染色體進行評估來尋求可能的解決方案。 在每一代中，我們對每個染色體進行評估，選擇一個分布優(yōu)秀的區(qū)域，在其中對染色體進行變異和交叉操作，重新組合，得到新的染色體。這樣幾代之后，在進一步觀察后沒有得到新進展的情況下，那么就將所得到最具適應度的染色體視為（所有可能的）最佳解決方案。運算常常會在出現(xiàn)大量的迭代速度和資料后終止（Michalewicz）。 表示法 每一個染色體表示待求解問題的一個可能解，將其中每一個等位基因被歸為一個貨物序列中。如此類推，在染色體中的每個基因序列表示貨物的種類和相對等位基因的存儲位置。因此，每個解決方案包括一個染色體，其中基因的數(shù)量等于所收到命令的貨物數(shù)目。如給出一個例子，圖 1 如圖1可見，一個可行方案中的貨物設為A,B,C和D代碼，他們被檢索位置為：貨物C在5號位置，貨物B在7號位置，貨物A在4號位置，貨物D在3好位置。 圖1.代表一個可行的解決方案 其表格表示為，貨物被揀選的順尋也顯示在其中。在這個例子中，在5號位置中貨物C將被首先檢索，其次是貨物B，再是貨物A，最后是貨物D。 初始化 初始域是隨機產(chǎn)生的。擁有隨機序列的指令貨物組成了染色體。在染色體中，每個貨物被賦予一個隨機代號。由此可見，每個可行方案所給予的條件是相同的。然而，在每一次重新運算過程中，都會有一套適合的程序來解決方案。因此，染色體中的指令貨物將會無重復的隨機分布，貨物的地址代碼也會隨機選取，所分配的代號范圍會在1到該貨物的總倉庫庫存數(shù)之間。 假設在倉庫內現(xiàn)有總共A、B、C和D4件貨物，它們分別對應代碼是6、9、7和4。為了形成如圖1所示的解決方案，首先，指令貨物死隨機選取的（C,B,A和D），然后，貨物C選取[1,7]的隨機整數(shù)，貨物B在[1，9]中選取，A在[1,6]之間選取，最后D在[1，4]中間隨機選取一個。 交叉操作 在置換問題的操作描述里，部分匹配交叉（簡稱PMX）常被用于揀選問題上，部分匹配交叉被視為一種交叉的排列，它確保所有的貨物能迅速的被后裔所發(fā)現(xiàn)。也就是說，兩個后裔全面的接受了父輩基因，接著再填充到其父輩的等位基因上。在圖2中，兩個父輩用p1和p2來表示，交叉點是1和3。根據(jù)在相應的[M,R]和[E,A]之間，重復做貨物的取代，這就是說，在第一個父輩中的A和E由R和M所取代，而在第二個父輩中的R和M就由A和E來取代。生成的后代是O1和O2(圖2)。 同時，根據(jù)PMX中的揀選問題得知，交叉操作的關鍵是只交換在染色體中的貨物區(qū)域并且不交換相關的等位基因。 圖2.PMX操作 變異操作 我們現(xiàn)在用二進制位(0和1)來表示基因。在揀選的問題上，相關聯(lián)的等位基因通過變異操作，將庫存中一個基因替代另外一個等位基因。換而言之，這個操作并沒有對貨物的序列起到任何作用，僅僅只是貨物選擇了另外一個序列代碼。 假設在O1中，第三個基因被選為變異基因。由于貨物A在各儲存位置上的總數(shù)有6個，通過變異操作在[1,6]范圍里產(chǎn)生隨機整數(shù)來代替原來的第三個基因(圖 3)，當然，產(chǎn)生的代碼等于現(xiàn)有代碼時(如2)，則操作重復進行，直到取得一個新代碼(除了2)。在這個范例中，4就是最后產(chǎn)生的代碼。 評估與選擇 在每代中，對于染色體的評估使用了一些有效的方法。 圖3.變異操作 在大量的優(yōu)化應用中，適應度是對目標客觀本質的計算。在揀選問題中，目標函數(shù)的作用是將S/R系統(tǒng)的行程時間降低到最小。通過S/R系統(tǒng)對總行程時間做標準化的計算來得到下一代。Khojasteh-Ghamari對S/R系統(tǒng)計算的行程時間進行做了一下說明。 由于這個問題是最小化的問題，所以我們可以將每個染色體的目標函數(shù)值改變成適應值，適應值大的染色體就更具適應能力，這樣就能更清晰的表達他們的價值程度(cheng等人提出)： 其中，eval(vk)是第K個染色體的適應函數(shù)，f(vk)是第k個染色體在S/R系統(tǒng)下總行程時間。問題域的大小(簡稱pop size)決定了每個染色體應被給的時間。 現(xiàn)在來做個比喻，我們對下一代染色體的選擇比作為(賭臺上的)輪盤，適應度大的染色體在下一代遺傳中被選的概率更高。在此方案中，行程時間短的更容易被選中作下一代的遺傳。賭盤的執(zhí)行如下： 1.計算對于每個染色體的vk(k=1,2,...,最大范圍值)在S/R系統(tǒng)的總行程時間。 2.計算每個染色體的適應度eval(vk)(k=1,2,...,最大范圍值)。 3.求得所有適應的總數(shù)量 4. 計算對于每個染色體Vk的選擇概率pk(k=1,2,...,范圍最大值)。 5. 計算每個染色體vk的累積概率qk(k=1,2,...,范圍最大值)。 每次選擇是在旋轉的賭盤中進行的，其結果是動態(tài)的，被選中的染色體作為下一代的范圍域。 -生成的一個隨機實數(shù)r在[0，1]范圍內； -如果r≤1，那么選擇的第一個染色體v1，否則選擇第k個染色體vk(2 ≤ k ≤ pop size)，這樣就有qk?1 < r ≤qk。 在上一代中的染色體被新一代的染色體所替代。 4.仿真結果 我們制作了一個擁有36種不同貨物的立體倉庫，在其中還有5種不同類型的指令，對此比較3種運算法的性能。每個貨物首先先用例證法來解決。以獲取最佳的行程時間和CPU占用率。接著用另外兩種解法來解決。研究結果如下2表。 4.1.仿真模型 我們創(chuàng)建了一個在36種不同物理規(guī)格情況下的倉庫，通過對于每一個倉庫施加5種不同的指令來對這3種算法的性能進行比較。每種情況首先按例證法來得到最佳的行程時間和CPU占用率，然后再通過另外兩種計算方法來解決問題。研究結果顯示在下面兩個表格中。 利用倉庫的主要3個參數(shù)（倉儲容量、密度和形狀）來設計36種不同存儲的情況。由于倉儲容量與倉庫中的巷道成比例關系，我們將倉儲容量劃分為4種情況，分別是1、2、3和4種巷道的形式。每個倉儲貨架有780個存儲位置。因為每個巷道有兩個貨架，則一個巷道就擁有1560個存儲位置。由于一個系統(tǒng)對倉庫中大量巷道進行服務的話，將會大大降低其系統(tǒng)實際效率。所以在不考慮5個或更多巷道的情況下，就由一個S/R系統(tǒng)對所有巷道進行服務。對于倉儲密度，我們假定倉庫中的使用率為60%、75%和95%。Bozer 和 White對倉儲形狀的配置進行了相關描述為，倉儲形狀，它是一種對于貨架高度與長度的空間比例，假設倉儲容量與S/R系統(tǒng)的水平和垂直速度都是常數(shù)。那么我們將這3個值設定為（0.6,0.73和1）。 此外還要補充的是，對上述每種情況的描述中，5種不同的指令為別是1，2，3，4和5，5種所要求的貨物編碼分別是一，二，三，四和五。 4.2.結果 在個人電腦配置是：“奔騰III,1000MHz的處理器,512 MB內存和2 GB虛擬內存”的情況下進行了試驗。結果列于表1和表2中。表1表示在3種運算法下，4種類型“S/R系統(tǒng)平均行程時間”和“S/R系統(tǒng)平均CPU占用率”。兩種倉儲參數(shù)（倉儲密度和形狀）的組合形成了每個倉庫(倉庫分別有1、2、3和4個巷道)的9種情況，每種情況下的值表示了5種命令下的平均值。表2表示在倉儲形狀為0.6和1，4種巷道情況下的平均行程時間和平均CPU占用率。 在表格中，例證法、現(xiàn)有巷道探索式算法和遺傳算法分別用“Enumeration”，“CAH”，“GA”所表示。 5.分析結果 通過對表1分析可知，在所有情況下的各類倉庫(1，2，3和4個巷道)，CAH算法是能獲得最大行程時間和最小CPU占用率的解決方案。換而言之，它是占用較小CPU使用率的方法。然而，它對S/R系統(tǒng)的行程時間超過了其他兩個。 在倉庫中只有一個巷道的情況下，通過遺傳算法解決獲得的方案中89%為最佳的方案。其余的方案里次優(yōu)和最優(yōu)的解決方案平均只相差0.09％（但需要更大的CPU時間）。在擁有2個3個和4個巷道的倉庫中，遺傳法提供的11%的解決方案為最佳方案，其余方案里，獲得方案與最佳方案差別不大，分別是2巷道相差3.86%，3巷道相差4.83%和4巷道相差4.69%。 倉庫中巷道的層架數(shù)目會影響到運算效率。由于增加的總數(shù)是實際問題中出現(xiàn)的，例證法中要增加較大的CPU占用率才能獲得最佳解決方案。然而在大多數(shù)情況下，遺傳法則需要相比于例證法較少的CPU占用率就能完成S/R系統(tǒng)的最佳方案。 表格1. 3種算法的性能 表格2.3中算法在倉儲形狀上的比較 此外，運算方法的性能是受貨架配置所影響的。表2顯示了通過對S/R系統(tǒng)的平均行程時間和平均CPU占用率在多巷道中的兩種倉儲形狀（0.6和1）的比較。在此表中顯示了當倉儲容量增加時，兩個貨架配置的算法比較。在一個倉庫只有一個巷道時，例證法提供了最佳的方案，并且它的CPU占用率低于遺傳法。然而，如果倉庫有多個巷道時，遺傳算法需要的CPU占用率低于例證法。由于各種倉儲形狀B的結果相似，我們將倉儲形狀B設為0.73。因為對B的3種算法性能大致相同，所以在倉庫里的貨架配置對算法性能沒有影響。 6. 總結 在本次研究中，我們討論了多巷道自動化立體倉庫系統(tǒng)，并得到了結果。就同類貨物在不同存儲位置被尋找的情況下，我們發(fā)明了兩種算法來解決這個問題，我們將第一種探索式算法命名為現(xiàn)有巷道探索式算法（簡稱CAH），第二種命名為可接受遺傳算法。為顯示每種算法的實際效率，我們將他們與例證法做了對比，例證法在獲得最佳方案的同時需要大量的CPU占用率，因此它并不是最理想的解決方案。CAH算法需要較小的CPU占用率，但獲得的方案大多數(shù)是需要較長的S/R系統(tǒng)行程時間的次佳的方案。而遺傳算法提供的方案大多是最佳和準佳(平均占3.37%)的方案。因此，模擬的遺傳算法顯示，它的效率高于其他兩種算法。 不久的將來，在功效和雙命令（DC）的自動化倉庫系統(tǒng)領域中，將對元啟發(fā)式方法和分支定界算法進行評估，以便能在自動化倉庫揀選問題上創(chuàng)造最佳的解決方案。 7. 鳴謝 我們感謝來自Tarbiat Modarres 大學M.M. Sepehri教授的寶貴建議。我們也同樣的感謝為我們提出建議的匿名審稿人。 參考文獻 [1] Amato, F., Basile, F., Carbone, C. and Chiacchio, P., An approach to control automated warehouse systems, Control Engineering Practice, Vol. 13, pp.1223-1241, 2005. [2] Bozer, Y. A. and White, J. A., Travel-time models for automated storage/retrieval systems, IIE Transactions, Vol. 16, No. 4, pp.329-338, 1984. [3] Bozer, Y. A. andWhite, J. A., Design and performance models for end-of-aisle order picking systems, Management Science, Vol. 36, No. 7, pp.852-866, 1990. [4] Cheng, R., Gen, M. and Sasaki, M., Film-copy deliverer problem using genetic algorithms, Computers & Industrial Engineering, Vol. 29, pp.549-553, 1995. [5] Elsayed, E. A., Algorithms for optimal material handling in automatic warehousing systems, International Journal of Production Research, Vol. 19, pp.525-535, 1981. [6] Elsayed, E. A. and Stern, R. G., Computerized algorithms for order processing in automated warehousing systems, International Journal of Production Research, Vol. 21, pp.579-586, 1983. [7] Goetschalckx, M. and Wei, R., Bibliography on order picking systems, Vol. 1, pp.1985-1992, 1994, available at http://www.isye.gatech.edu/people/faculty/Marc Goetschalckx/research.html. [8] Han, M.-H., McGinnis, L. F., Shieh, J. S. andWhite, J. A., On sequencing retrievals in an automated storage/retrieval system, IIE Transactions, Vol. 19, pp.56-66, 1987. [9] Hwang, H., Baek, W. and Lee, M.-K., Clustering algorithms for order picking in an automated storage and retrieval system, International Journal of Production Research, Vol. 26, pp.189-201,1988. [10] Hwang, H., Moon, S. and Gen, M., An integrated model for the design of end-of-aisle order picking system and the determination of unit load sizes of AGVs, Computers & Industrial Engineering, Vol. 42, pp.249-258, 2002. [11] Khojasteh-Ghamari, Y., Order picking problem in an AS/RS with multiple stock locations. M.Sc. thesis, Tarbiat Modarres University, 2000. [12] Koh, S. G., Kim, B. S. and Kim, B. N., Travel time model for the warehousing system with a tower crane S/R machine, Computers & Industrial Engineering, Vol. 43, pp.495-507, 2002. [13] Koh, S. G., Kwon, H. M. and Kim, Y. J., An analysis of the end-of-aisle order picking system: Multi-aisle served by a single order picker, International Journal of Production Economics, Vol. 98, pp.162-171, 2005. [14] Lee, H. F. and Schaefer, S. K., Retrieval sequencing for unit-load automated storage and retrieval systems with multiple openings, International Journal of Production Research, Vol. 34, pp.2943-2962, 1996. [15] Lee, H. F. and Schaefer, S. K., Sequencing methods for automated storage and retrieval systems with dedicated storage, Computers & Industrial Engineering, Vol. 32, pp.351-362, 1997. [16] Mahajan, S., Rao, B. V. and Peters, B. A., A retrieval sequencing heuristic for miniload end-ofaisle automated storage/retrieval systems, International Journal of Production Research, Vol. 36, pp.1715-1731, 1998. [17] Michalewicz, Z., Genetic Algorithms + Data Structures = Evolution Programs, 1992 (SpringerVerlag: Berlin) [18] Ratliff, H. D. and Rosenthal, A. S., Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem, Operations Research, Vol. 31, pp.507-521, 1983. [19] Roodbergen, K. J. and de Koster, R., Routing order pickers in a warehouse with a middle aisle, European Journal of Operational Research, Vol. 133, pp.32-43, 2001. [20] Rouwenhorst, B., Reuter, B., Stockeahm, V., van Houtum, G. J., Mantel, R. J. and Zijm, W. H. M.,Warehouse design and control: framework and literature review, European Journal of Operational Research, Vol. 122, pp.515-533, 2000. [21] Van den Berg, J. P., A literature survey on planning and control of warehousing systems, IIE Transactions, Vol. 31, pp.751-762, 1999. [22] Van den Berg, J. P. and Gademann, A. J. R. M., Optimal routing in an automated storage/retrieval system with dedicated storage, IIE Transactions, Vol.31, pp.407-415, 1999. [23] Hsu, C. M., Chen, K. Y. and Chen, M. C., Batching orders in warehouses by minimizing travel distance with genetic algorithms, Computers in Industry, Vol. 56, pp.169-178, 2005. [24] Hwang, H. S. and Cho, G. S., A performance evaluation model for order picking warehouse design, Computers & Industrial Engineering, Vol. 51, pp.335-342, 2006. [25] De Koster, R., Le-Duc, T. and Roodbergen K. J., Design and control of warehouse order picking: A literature review, European Journal of Operational Research, Vol. 182, pp.481-501, 2007. Order Picking Problem in a Multi-Aisle Automated Warehouse Served by a Single Storage/Retrieval Machine Yaghoub Khojasteh-Ghamari Jae-Dong Son University of Tsukuba Soongsil University Japan Korea Abstract Recent technological developments have revolutionized the design and operation of ware-housing systems. Automated storage and retrieval systems (AS/RS) driven by embedded computers are becoming increasingly more prevalent. The increased use of AS/RS is creating the need for computerized control algorithms to support the scheduling and picking decisions.This research addresses an order picking problem in a multi-aisle automated warehouse, in which a single storage/retrieval (S/R) machine performs storage and retrieval operations, and each item can be found in several storage locations. Our objective is to propose algorithms that minimize the total time traveled by the S/R machine to complete the retrieval process of orders. We develop a genetic algorithm and an ordinary heuristic, and provide a performance comparison of them with optimal solution. Numerical results from a large set of problems are reported. Keywords: Automated Warehouse, AS/RS, Order Picking, Genetic Algorithms. 1. Introduction In today’s manufacturing environments, inventories are maintained at lower levels than in the past. These reduced inventories have led to smaller storage systems, which in turn have created the need for quick access to the material being held in warehouse.Hence, automated storage and retrieval systems (AS/RS) used in manufacturing, ware-housing, and distribution applications must be designed to provide quick response times to service requests in order to keep the system operating efficiently. One important operational aspect of the AS/RS, which contributes to the system response time, is to minimize the total time traveled by the S/R machine to complete the retrieval process of orders. Order picking is a fundamental component of the retrieval function performed in warehouses. The main purpose of an order picking system is to fill customer orders by selecting the appropriate amount of material from a pre-designated storage medium known as the picking or forward area. Order picking represents only a subset of the material handling operations performed in warehousing. However, it is ‘one of the most costly and time-consuming functions of warehousing. In many warehouses, the difference between profit and loss depends on how well the order picking operation is run’ (Bozer and White ). There are many studies on order picking problems in AS/RS and automated ware-housing systems. Ratliff and Rosenthal developed a graph-based algorithm to find the shortest path to visit a set of pick locations in a ladder layout. Roodbergen and de Koster extended the work of Ratliff and Rosenthal. They considered the order picking problem in a parallel aisle warehouse in which order pickers can cross over the aisles at the ends of aisles as well as at a middle cross aisle. They developed a dynamic programming algorithm to solve the problem. Van den Berg and Gademann developed a transportation problem (TP) model for a block sequencing in an AS/RS with dedicated storage and a single-load machine. They proved that the optimal solution of the TP problem is the optimal sequence of the machine to minimize the travelling time. Elsayed made a chain of studies on the problem of optimally batching several orders in a two-dimensional warehouse with ladder structure. Recognizing that the exact solutions of the problem are very difficult and time consuming to obtain, Elsayed and Stern presented some heuristic algorithms, but reported that none of them produces consistently superior results through experimentations. Hwang et al. studied a similar order picking problem in a single-aisle AS/RS and presented heuristic algorithms,which determine an efficient batching of orders for each tour of the S/R machine. Thealgorithms were based on cluster analysis with some similarity measures. Through simulation, they compared performances of the proposed algorithms with Elsayed and Sterns’ results in 1983. Bozer and White, Han et al., and Lee and Schaefer proposed a procedure to optimize the sequencing of retrieval requests based on the solution of a linear assignment problem. Lee and Schaefer also presented several optimum and heuristic sequencing methods, where a storage request is assigned to a predetermined storage location. Mahajan et al. developed a retrieval sequencing scheme aimed at improving the throughput of miniload AS/RS. They proposed a nearest-neighbor retrieval sequencing heuristic and developed an analytical model to predict its performance. Hwang et al. formulated a nonlinear mathematical model and developed an efficient heuristic solution procedure to design the AS/RS and determine the unit load size of the vehicle simultaneously. Van den Berg and Rouwenhorst et al. surveyed literature on warehouse planning and control. Planning includes the storage location assignment problem, and the control of a warehousing system includes routing, sequencing, scheduling, dwell-point selection, and order batching. Goetschalckx and Wei presented a bibliography on order picking systems for 1985 through to 1992. Koh et al. proposed some models for travel times of the S/R machine in a warehouse with a tower crane. They derived the models for both single and dual command cycles based on the randomized storage assignment rule. They also calculated the travel time under the turnover-based storage assignment rule through a numerical approach. Koh et al. proposed an optimization model to find an optimal buffer size in end-of-aisle order picking system, where a single S/R machine serves several aisles.Amato et al. proposed an algorithm to optimally sequence the retrieval orders based on colored timed Petri nets framework. They also proposed two control algorithms to optimize the operations of the cranes and shuttle. Hsu et al. considered the order batching problem in a multi-aisle warehouse and proposed a genetic algorithm to minimize the total travel distance. Hwang and Cho presented a performance evaluation model for the order picking warehouse in a supply center. The objective of their study was to minimize the cost by minimizing the number of transporters and to calculate the performance and facility utilization rate. In a recent study, De Koster et al. carried out a literature review on typical decision problems in design and control of manual order picking processes. They focused on optimal layout design, storage assignment methods,routing methods, order batching and zoning. However, we have no knowledge of papers in the literature that address the order picking problem in automated storage and retrieval systems, where each item can be stocked at several storage locations. In fact, some manufacturers whose products have a large variety of types, shapes, and sizes are faced with this problem in their finished goods warehouses. A tile manufacturer, for example, whose products a