資源目錄里展示的全都有預(yù)覽可以查看的噢，，下載就有,,請(qǐng)放心下載，原稿可自行編輯修改=【QQ：11970985 可咨詢交流】====================喜歡就充值下載吧。。。資源目錄里展示的全都有，，下載后全都有,,請(qǐng)放心下載，原稿可自行編輯修改=【QQ：197216396 可咨詢交流】==================== 由一個(gè)單一的存儲(chǔ)/檢索機(jī)服務(wù)的多巷道自動(dòng)化立體倉庫存在的揀選分揀問題Yaghoub Khojasteh-Ghamari Yaghoub Khojasteh Jae-Dong Son 加馬里筑波大學(xué) 崇實(shí)大學(xué) 日本 韓國 Abstract摘要 隨著Recent technological developments have revolutionized the design and operation of ware-現(xiàn)代化科技的發(fā)展，倉庫式存儲(chǔ)系統(tǒng)在設(shè)計(jì)與運(yùn)行方面出現(xiàn)了巨大的改革。自動(dòng)化立體倉庫（AS / RS）嵌入計(jì)算機(jī)驅(qū)動(dòng)正變得越來越普遍。由于AS / RS使用的增加對(duì)計(jì)算機(jī)控制的需要與支持也在提高。這項(xiàng)研究解決了在多巷道立體倉庫的揀選問題，在這種存儲(chǔ)/檢索（S / R）操作中，每種貨物可以在多個(gè)存儲(chǔ)位置被尋址到。提出運(yùn)算方法的目標(biāo)是，通過S/R系統(tǒng)揀選貨物來最大限度的減少行程時(shí)間。我們開發(fā)的遺傳式和啟發(fā)式算法，以及通過比較從大量的問題中得到一個(gè)最佳的解決方案。 Keywords: Automated Warehouse, AS/RS, Order Picking, Genetic Algorithms. 關(guān)鍵詞：自動(dòng)化立體倉庫，AS / RS系統(tǒng)，揀選，遺傳算法。 1.Introduction導(dǎo)言 在現(xiàn)今的生產(chǎn)環(huán)境中，庫存等級(jí)保持低于過去。那是因?yàn)檫@種較小的存儲(chǔ)系統(tǒng)不僅降低庫存量還增加了揀選貨物的速度。自動(dòng)化立體倉庫（AS / RS），一方面通過提供快速響應(yīng)，來達(dá)到高操作效率；另一方面它還有助于運(yùn)作方面的系統(tǒng)響應(yīng)時(shí)間，減少的揀選完成的總行程時(shí)間。因此，它常被用于制造業(yè)、儲(chǔ)存?zhèn)}庫和分配設(shè)備等行業(yè)中。 揀選是倉庫檢索功能的基本組成部分。它的主要目的是，在預(yù)先指定的地點(diǎn)中選擇適當(dāng)數(shù)量的貨物以滿足客戶揀選要求。雖然揀選操作僅僅是物體在倉儲(chǔ)中裝卸操作之一，但它卻是“最耗時(shí)間和花費(fèi)最大的倉儲(chǔ)功能。許多情形下，倉儲(chǔ)盈利的高低就在于是否能將揀選操作運(yùn)行處理好”。 （Bozer和White） Ratliff和Rosenthal，他們關(guān)于自動(dòng)化立體倉庫系統(tǒng)（AS/RS）的揀選問題進(jìn)行的研究，發(fā)明了基圖算法，在階梯式布局中選取最短的訪問路徑。Roodbergen 和 de Koster 拓展了Ratliff 和Rosenthal算法。他們認(rèn)為，在平行巷道揀選問題上，應(yīng)該穿越巷道末端和中間端進(jìn)行揀選，就此他們發(fā)明了一種動(dòng)態(tài)的規(guī)劃算法解決這問題。就此Van den Berg 和 Gademann發(fā)明了一種運(yùn)輸模型(TP)，它是對(duì)于指定的存儲(chǔ)和卸載進(jìn)行測(cè)算的儀器。他們表示，最好的解決運(yùn)輸問題的方法是以機(jī)械的最佳布局來盡量減少運(yùn)行時(shí)間。 Elsayed對(duì)階梯結(jié)構(gòu)的立體倉庫問題的研究表明，要在多巷道中揀選貨物并擬定最佳方案，是非常困難和并且耗時(shí)的。 Elsayed 和 Stern提出了啟發(fā)式算法，但據(jù)說，他們并沒有在實(shí)際生產(chǎn)過程中得到滿意的結(jié)果。黃禹錫等人，研究了立體倉庫系統(tǒng)中的單巷道選道的問題，并提出決定了每個(gè)S /R系統(tǒng)揀選效率的啟發(fā)式算法。Thealgorithms在聚集前人分析的基礎(chǔ)上，采取了一些相似的措施。在1983年，通過仿真，把計(jì)算得到的參數(shù)與Elsayed和Sterns的結(jié)論進(jìn)行了比較。 Bozer、White、Han、Lee和Schaefer等人提出了一個(gè)程序，在檢索測(cè)序的基礎(chǔ)上進(jìn)行優(yōu)化，解決了線性分配的問題。Lee 和 Schaefer介紹了一些優(yōu)化和啟發(fā)式的測(cè)序方法，其中包括存儲(chǔ)指令如何被分配到預(yù)先確定的存儲(chǔ)位置。Mahajan通過對(duì)小件貨物的貯存系統(tǒng)進(jìn)行了改善，得到了一種新的檢索測(cè)序方案，提出最近檢索原則并開發(fā)了一個(gè)驗(yàn)證模型來預(yù)測(cè)效果。黃禹錫制作了非線性數(shù)學(xué)模型，開發(fā)出以一種啟發(fā)式程序設(shè)計(jì)的自動(dòng)化立體倉，與此同時(shí)還可以確定單位負(fù)載的大小。Van den Berg 和 Rouwenhorst 調(diào)查了倉庫規(guī)劃和控制的文獻(xiàn)，規(guī)劃文件包括存儲(chǔ)位置的分配問題，倉庫儲(chǔ)存系統(tǒng)的控制問題包括路由、排序、調(diào)度、停留點(diǎn)的選擇和秩序配料。 Goetschalckx 和 Wei提交1985年至1992年揀選系統(tǒng)的參考文獻(xiàn)。 Koh提出了一些關(guān)于在存儲(chǔ)倉庫中，帶有塔式起重機(jī)的自動(dòng)化立體倉庫的模式。他們推論出的這個(gè)模式是建立在隨機(jī)存儲(chǔ)分配規(guī)則的基礎(chǔ)上的一個(gè)單、雙指令周期。他們還根據(jù)營業(yè)額的存儲(chǔ)分配規(guī)則計(jì)算出相應(yīng)行程時(shí)間。Koh提出了優(yōu)化模式，在揀選系統(tǒng)的巷道最末端尋找到了一個(gè)最佳緩沖的區(qū)域，在那里S/R系統(tǒng)可提供多若干個(gè)通行巷道。Amato以colored timed Petri nets網(wǎng)站的資料為基礎(chǔ)提出了對(duì)順序檢索的揀選優(yōu)化算法。他們還提出了兩項(xiàng)對(duì)于起重機(jī)和航天飛機(jī)的運(yùn)作的優(yōu)化控制算法。Hsu審議多巷道的倉庫的順序配料問題，提出了遺傳算法來減少總旅行距離。Hwang 和 Cho提出了采摘的供應(yīng)中心倉庫秩序的績效評(píng)估模式。他們研究的目的是通過減少運(yùn)輸數(shù)量、計(jì)算性能和設(shè)備利用率來減少盡量減少成本。在近期的研究中，De Koster 對(duì)設(shè)計(jì)與控制手冊(cè)中揀選工程的典型決定問題進(jìn)行了文獻(xiàn)回顧。他們主要關(guān)注于存儲(chǔ)分配方法、路徑的選擇、配料和分區(qū)。 然而，我們沒有這么多的文獻(xiàn)上的知識(shí)，在處理自動(dòng)化立體倉庫的揀選問題上，每個(gè)物品都能夠被儲(chǔ)存在多個(gè)儲(chǔ)存點(diǎn)里。事實(shí)上，許多廠家的產(chǎn)品有許多類型、種類和形狀，這也是他們成品倉庫面臨的問題。例如一個(gè)瓷磚制造商，他的產(chǎn)品有兩個(gè)類型（墻磚和地磚）,分別有7中不同的尺寸，4種不同耐久性（磨損差餉)和100多種不同的顏色、圖案、顏色和形狀，總共有5600多種不同的產(chǎn)品類型。作為存儲(chǔ)策略，要一件剛進(jìn)來的貨物存放在最近的空倉位位置上。當(dāng)一個(gè)來自倉庫中物品，由于產(chǎn)品種類繁多，有很大的可能性從一個(gè)地方存入到另一個(gè)地方。因此，一件物品需要有幾個(gè)在倉庫中存儲(chǔ)位置。換句話說，由于分類和分區(qū)，每個(gè)單獨(dú)類型的產(chǎn)品在倉庫中需要一個(gè)更大的空間，一個(gè)物品在幾個(gè)地方存儲(chǔ)時(shí)不可避免的。 2.問題描述 在本研究中，我們考慮到了小件物品的自動(dòng)存儲(chǔ)和檢索系統(tǒng)，那有一個(gè)或多個(gè)巷道。每個(gè)巷道包含了關(guān)于巷道兩旁倉儲(chǔ)貨架。每個(gè)巷道結(jié)束的地方都有一個(gè)輸入/輸出口（I/O）。在那里還有一個(gè)單獨(dú)的存儲(chǔ)/檢索（S / R）的儀器來為所有巷道的系統(tǒng)服務(wù)，它可以同時(shí)在垂直和水平方向移動(dòng)。因此，在兩點(diǎn)之間的行程等于最小的水平和垂直行程。在收到命令之前S/R儀器已經(jīng)定位了輸入/輸出口中的位置。儀器的起始位置取決于最后一件貨物的最后一個(gè)命令的存儲(chǔ)位置。S/R計(jì)算行程中以恒定的速度水平和垂直移動(dòng)。一個(gè)命令可以由多個(gè)貨物請(qǐng)求組成的。同樣每個(gè)貨物也可以在倉庫中多個(gè)位置存儲(chǔ)。當(dāng)檢索請(qǐng)求包括多個(gè)貨物，并且這些貨物在多個(gè)不同的倉庫位置時(shí)，S/R儀器必須到多個(gè)不同的存儲(chǔ)地點(diǎn)完成各個(gè)命令。本次研究的目的就是提出計(jì)算方法來減少S/R走過的總時(shí)間來完成命令程序。 3.運(yùn)算方法 我們現(xiàn)在有兩種運(yùn)算方法來解決這個(gè)問題：一種是探索式算法，還有一種是遺傳式算法。為了顯示所提出算法的優(yōu)越性，我們把它與其他方法進(jìn)行了比較。由于我們的解決問題方法是新提出的，沒有前人在這個(gè)領(lǐng)域進(jìn)行過研究，那么我們最先提出的一種運(yùn)算法，用它來獲取的最佳的解決方案，這種方法我們稱它為例證算法。其結(jié)果作為對(duì)于兩種擬議算法比較的基準(zhǔn)解決方案。 在例證法中，我們確定所有可行的解決方法并將他們互相比較找出最好的解決方法來。為此，這個(gè)方案首先要找所有可行的方法來選擇一個(gè)命令。然后，S/R系統(tǒng)的計(jì)算獲得每個(gè)方法行程的總時(shí)間，最后，選取的解決方案要求在最短時(shí)間內(nèi)完成要求。這個(gè)解決方案被認(rèn)為是該問題的最佳解決方案?？紤]到一個(gè)命令的由k種不同類型的貨物組成，其中在ni(i = 1, 2, . . . , k)項(xiàng)貨物中第i項(xiàng)貨物被提出請(qǐng)求。在可行的解決辦法總數(shù)挑選順序可以給出： 其中，mi是在第i項(xiàng)貨物在倉庫中的總庫存，得出： 通過例證法已經(jīng)解決了各種類型的問題，并且確定了這種低金額低行程的最佳方案。我們發(fā)現(xiàn)，在當(dāng)前巷道上存在貨物（如：該巷道的S/R系統(tǒng)是在檢索過程的起始端）是解決這個(gè)問題的關(guān)鍵技術(shù)。我們基于先前提到的運(yùn)算結(jié)果發(fā)現(xiàn)了一種計(jì)算方法，稱它為現(xiàn)有巷道探索式（CAH)算法。 在現(xiàn)有巷道探索式算法中，在當(dāng)前巷道中現(xiàn)存的貨物是首先被檢索的對(duì)象。其后，對(duì)該命令的其余部分（如果有的話）選中并運(yùn)用各種檢索方式進(jìn)行研究計(jì)算。我們可以簡單的對(duì)其進(jìn)行表達(dá)，如果設(shè)r表示在現(xiàn)有巷道中指令貨物的數(shù)目，那么如果r=0時(shí)，該運(yùn)算方法就類似于原來的例證法。如果r=1時(shí)，該運(yùn)算方法首先要通過S/R系統(tǒng)對(duì)行程時(shí)間進(jìn)行計(jì)算，設(shè)t1表示在當(dāng)前巷道中，現(xiàn)存貨物為了避免與揀選中的貨物沖突，對(duì)于其余的貨物(如果有的話)進(jìn)行同等于例證法的計(jì)算，以此來得到最小的計(jì)算行程時(shí)間。設(shè)t2表示在S/R系統(tǒng)中總的行程時(shí)間。最后將t1和t2之和作為最終的解決方案。 如果r>1時(shí)，則該方法首先分配揀選順序，揀選所有的r貨物，既巷道中的現(xiàn)存貨物。在計(jì)算好行程時(shí)間之后，進(jìn)入t1階段開始移除列表中指令的貨物。在這之后，其余貨物(如果有的話)進(jìn)行類似于例證法的運(yùn)算,就如同，通過對(duì)每一個(gè)可行的方法計(jì)算出行程時(shí)間，最終選取其中最小的那個(gè)值，即t2階段。最后，在S/R系統(tǒng)中將t1和t2的和設(shè)為最終的解決方案。 Khojasteh-Ghamari詳細(xì)的對(duì)在現(xiàn)有巷道中的貨物的揀選順序的分配方法進(jìn)行了討論。如果任何待命的貨物存在于現(xiàn)有巷道中，那么就將倉庫中現(xiàn)存貨物的數(shù)目除以解決方案的數(shù)目。因此，這項(xiàng)任務(wù)目的就是降低總方案的數(shù)目，以此來減少CPU時(shí)間（程序的處理時(shí)間）。 3.1.遺傳算法 遺傳算法是一種優(yōu)化過程，它將問題域比作基因類（個(gè)體或染色體），基因類是有多個(gè)基因體組成，其中基因體成符號(hào)形式串行。每一個(gè)基因類都有一個(gè)可能的解，通過對(duì)問題域中的染色體進(jìn)行評(píng)估來尋求可能的解決方案。 在每一代中，我們對(duì)每個(gè)染色體進(jìn)行評(píng)估，選擇一個(gè)分布優(yōu)秀的區(qū)域，在其中對(duì)染色體進(jìn)行變異和交叉操作，重新組合，得到新的染色體。這樣幾代之后，在進(jìn)一步觀察后沒有得到新進(jìn)展的情況下，那么就將所得到最具適應(yīng)度的染色體視為（所有可能的）最佳解決方案。運(yùn)算常常會(huì)在出現(xiàn)大量的迭代速度和資料后終止（Michalewicz）。 表示法 每一個(gè)染色體表示待求解問題的一個(gè)可能解，將其中每一個(gè)等位基因被歸為一個(gè)貨物序列中。如此類推，在染色體中的每個(gè)基因序列表示貨物的種類和相對(duì)等位基因的存儲(chǔ)位置。因此，每個(gè)解決方案包括一個(gè)染色體，其中基因的數(shù)量等于所收到命令的貨物數(shù)目。如給出一個(gè)例子，圖 1 如圖1可見，一個(gè)可行方案中的貨物設(shè)為A,B,C和D代碼，他們被檢索位置為：貨物C在5號(hào)位置，貨物B在7號(hào)位置，貨物A在4號(hào)位置，貨物D在3好位置。 圖1.代表一個(gè)可行的解決方案 其表格表示為，貨物被揀選的順尋也顯示在其中。在這個(gè)例子中，在5號(hào)位置中貨物C將被首先檢索，其次是貨物B，再是貨物A，最后是貨物D。 初始化 初始域是隨機(jī)產(chǎn)生的。擁有隨機(jī)序列的指令貨物組成了染色體。在染色體中，每個(gè)貨物被賦予一個(gè)隨機(jī)代號(hào)。由此可見，每個(gè)可行方案所給予的條件是相同的。然而，在每一次重新運(yùn)算過程中，都會(huì)有一套適合的程序來解決方案。因此，染色體中的指令貨物將會(huì)無重復(fù)的隨機(jī)分布，貨物的地址代碼也會(huì)隨機(jī)選取，所分配的代號(hào)范圍會(huì)在1到該貨物的總倉庫庫存數(shù)之間。 假設(shè)在倉庫內(nèi)現(xiàn)有總共A、B、C和D4件貨物，它們分別對(duì)應(yīng)代碼是6、9、7和4。為了形成如圖1所示的解決方案，首先，指令貨物死隨機(jī)選取的（C,B,A和D），然后，貨物C選取[1,7]的隨機(jī)整數(shù)，貨物B在[1，9]中選取，A在[1,6]之間選取，最后D在[1，4]中間隨機(jī)選取一個(gè)。 交叉操作 在置換問題的操作描述里，部分匹配交叉（簡稱PMX）常被用于揀選問題上，部分匹配交叉被視為一種交叉的排列，它確保所有的貨物能迅速的被后裔所發(fā)現(xiàn)。也就是說，兩個(gè)后裔全面的接受了父輩基因，接著再填充到其父輩的等位基因上。在圖2中，兩個(gè)父輩用p1和p2來表示，交叉點(diǎn)是1和3。根據(jù)在相應(yīng)的[M,R]和[E,A]之間，重復(fù)做貨物的取代，這就是說，在第一個(gè)父輩中的A和E由R和M所取代，而在第二個(gè)父輩中的R和M就由A和E來取代。生成的后代是O1和O2(圖2)。 同時(shí)，根據(jù)PMX中的揀選問題得知，交叉操作的關(guān)鍵是只交換在染色體中的貨物區(qū)域并且不交換相關(guān)的等位基因。 圖2.PMX操作 變異操作 我們現(xiàn)在用二進(jìn)制位(0和1)來表示基因。在揀選的問題上，相關(guān)聯(lián)的等位基因通過變異操作，將庫存中一個(gè)基因替代另外一個(gè)等位基因。換而言之，這個(gè)操作并沒有對(duì)貨物的序列起到任何作用，僅僅只是貨物選擇了另外一個(gè)序列代碼。 假設(shè)在O1中，第三個(gè)基因被選為變異基因。由于貨物A在各儲(chǔ)存位置上的總數(shù)有6個(gè)，通過變異操作在[1,6]范圍里產(chǎn)生隨機(jī)整數(shù)來代替原來的第三個(gè)基因(圖 3)，當(dāng)然，產(chǎn)生的代碼等于現(xiàn)有代碼時(shí)(如2)，則操作重復(fù)進(jìn)行，直到取得一個(gè)新代碼(除了2)。在這個(gè)范例中，4就是最后產(chǎn)生的代碼。 評(píng)估與選擇 在每代中，對(duì)于染色體的評(píng)估使用了一些有效的方法。 圖3.變異操作 在大量的優(yōu)化應(yīng)用中，適應(yīng)度是對(duì)目標(biāo)客觀本質(zhì)的計(jì)算。在揀選問題中，目標(biāo)函數(shù)的作用是將S/R系統(tǒng)的行程時(shí)間降低到最小。通過S/R系統(tǒng)對(duì)總行程時(shí)間做標(biāo)準(zhǔn)化的計(jì)算來得到下一代。Khojasteh-Ghamari對(duì)S/R系統(tǒng)計(jì)算的行程時(shí)間進(jìn)行做了一下說明。 由于這個(gè)問題是最小化的問題，所以我們可以將每個(gè)染色體的目標(biāo)函數(shù)值改變成適應(yīng)值，適應(yīng)值大的染色體就更具適應(yīng)能力，這樣就能更清晰的表達(dá)他們的價(jià)值程度(cheng等人提出)： 其中，eval(vk)是第K個(gè)染色體的適應(yīng)函數(shù)，f(vk)是第k個(gè)染色體在S/R系統(tǒng)下總行程時(shí)間。問題域的大小(簡稱pop size)決定了每個(gè)染色體應(yīng)被給的時(shí)間。 現(xiàn)在來做個(gè)比喻，我們對(duì)下一代染色體的選擇比作為(賭臺(tái)上的)輪盤，適應(yīng)度大的染色體在下一代遺傳中被選的概率更高。在此方案中，行程時(shí)間短的更容易被選中作下一代的遺傳。賭盤的執(zhí)行如下： 1.計(jì)算對(duì)于每個(gè)染色體的vk(k=1,2,...,最大范圍值)在S/R系統(tǒng)的總行程時(shí)間。 2.計(jì)算每個(gè)染色體的適應(yīng)度eval(vk)(k=1,2,...,最大范圍值)。 3.求得所有適應(yīng)的總數(shù)量 4. 計(jì)算對(duì)于每個(gè)染色體Vk的選擇概率pk(k=1,2,...,范圍最大值)。 5. 計(jì)算每個(gè)染色體vk的累積概率qk(k=1,2,...,范圍最大值)。 每次選擇是在旋轉(zhuǎn)的賭盤中進(jìn)行的，其結(jié)果是動(dòng)態(tài)的，被選中的染色體作為下一代的范圍域。 -生成的一個(gè)隨機(jī)實(shí)數(shù)r在[0，1]范圍內(nèi)； -如果r≤1，那么選擇的第一個(gè)染色體v1，否則選擇第k個(gè)染色體vk(2 ≤ k ≤ pop size)，這樣就有qk?1 < r ≤qk。 在上一代中的染色體被新一代的染色體所替代。 4.仿真結(jié)果 我們制作了一個(gè)擁有36種不同貨物的立體倉庫，在其中還有5種不同類型的指令，對(duì)此比較3種運(yùn)算法的性能。每個(gè)貨物首先先用例證法來解決。以獲取最佳的行程時(shí)間和CPU占用率。接著用另外兩種解法來解決。研究結(jié)果如下2表。 4.1.仿真模型 我們創(chuàng)建了一個(gè)在36種不同物理規(guī)格情況下的倉庫，通過對(duì)于每一個(gè)倉庫施加5種不同的指令來對(duì)這3種算法的性能進(jìn)行比較。每種情況首先按例證法來得到最佳的行程時(shí)間和CPU占用率，然后再通過另外兩種計(jì)算方法來解決問題。研究結(jié)果顯示在下面兩個(gè)表格中。 利用倉庫的主要3個(gè)參數(shù)（倉儲(chǔ)容量、密度和形狀）來設(shè)計(jì)36種不同存儲(chǔ)的情況。由于倉儲(chǔ)容量與倉庫中的巷道成比例關(guān)系，我們將倉儲(chǔ)容量劃分為4種情況，分別是1、2、3和4種巷道的形式。每個(gè)倉儲(chǔ)貨架有780個(gè)存儲(chǔ)位置。因?yàn)槊總€(gè)巷道有兩個(gè)貨架，則一個(gè)巷道就擁有1560個(gè)存儲(chǔ)位置。由于一個(gè)系統(tǒng)對(duì)倉庫中大量巷道進(jìn)行服務(wù)的話，將會(huì)大大降低其系統(tǒng)實(shí)際效率。所以在不考慮5個(gè)或更多巷道的情況下，就由一個(gè)S/R系統(tǒng)對(duì)所有巷道進(jìn)行服務(wù)。對(duì)于倉儲(chǔ)密度，我們假定倉庫中的使用率為60%、75%和95%。Bozer 和 White對(duì)倉儲(chǔ)形狀的配置進(jìn)行了相關(guān)描述為，倉儲(chǔ)形狀，它是一種對(duì)于貨架高度與長度的空間比例，假設(shè)倉儲(chǔ)容量與S/R系統(tǒng)的水平和垂直速度都是常數(shù)。那么我們將這3個(gè)值設(shè)定為（0.6,0.73和1）。 此外還要補(bǔ)充的是，對(duì)上述每種情況的描述中，5種不同的指令為別是1，2，3，4和5，5種所要求的貨物編碼分別是一，二，三，四和五。 4.2.結(jié)果 在個(gè)人電腦配置是：“奔騰III,1000MHz的處理器,512 MB內(nèi)存和2 GB虛擬內(nèi)存”的情況下進(jìn)行了試驗(yàn)。結(jié)果列于表1和表2中。表1表示在3種運(yùn)算法下，4種類型“S/R系統(tǒng)平均行程時(shí)間”和“S/R系統(tǒng)平均CPU占用率”。兩種倉儲(chǔ)參數(shù)（倉儲(chǔ)密度和形狀）的組合形成了每個(gè)倉庫(倉庫分別有1、2、3和4個(gè)巷道)的9種情況，每種情況下的值表示了5種命令下的平均值。表2表示在倉儲(chǔ)形狀為0.6和1，4種巷道情況下的平均行程時(shí)間和平均CPU占用率。 在表格中，例證法、現(xiàn)有巷道探索式算法和遺傳算法分別用“Enumeration”，“CAH”，“GA”所表示。 5.分析結(jié)果 通過對(duì)表1分析可知，在所有情況下的各類倉庫(1，2，3和4個(gè)巷道)，CAH算法是能獲得最大行程時(shí)間和最小CPU占用率的解決方案。換而言之，它是占用較小CPU使用率的方法。然而，它對(duì)S/R系統(tǒng)的行程時(shí)間超過了其他兩個(gè)。 在倉庫中只有一個(gè)巷道的情況下，通過遺傳算法解決獲得的方案中89%為最佳的方案。其余的方案里次優(yōu)和最優(yōu)的解決方案平均只相差0.09％（但需要更大的CPU時(shí)間）。在擁有2個(gè)3個(gè)和4個(gè)巷道的倉庫中，遺傳法提供的11%的解決方案為最佳方案，其余方案里，獲得方案與最佳方案差別不大，分別是2巷道相差3.86%，3巷道相差4.83%和4巷道相差4.69%。 倉庫中巷道的層架數(shù)目會(huì)影響到運(yùn)算效率。由于增加的總數(shù)是實(shí)際問題中出現(xiàn)的，例證法中要增加較大的CPU占用率才能獲得最佳解決方案。然而在大多數(shù)情況下，遺傳法則需要相比于例證法較少的CPU占用率就能完成S/R系統(tǒng)的最佳方案。 表格1. 3種算法的性能 表格2.3中算法在倉儲(chǔ)形狀上的比較 此外，運(yùn)算方法的性能是受貨架配置所影響的。表2顯示了通過對(duì)S/R系統(tǒng)的平均行程時(shí)間和平均CPU占用率在多巷道中的兩種倉儲(chǔ)形狀（0.6和1）的比較。在此表中顯示了當(dāng)倉儲(chǔ)容量增加時(shí)，兩個(gè)貨架配置的算法比較。在一個(gè)倉庫只有一個(gè)巷道時(shí)，例證法提供了最佳的方案，并且它的CPU占用率低于遺傳法。然而，如果倉庫有多個(gè)巷道時(shí)，遺傳算法需要的CPU占用率低于例證法。由于各種倉儲(chǔ)形狀B的結(jié)果相似，我們將倉儲(chǔ)形狀B設(shè)為0.73。因?yàn)閷?duì)B的3種算法性能大致相同，所以在倉庫里的貨架配置對(duì)算法性能沒有影響。 6. 總結(jié) 在本次研究中，我們討論了多巷道自動(dòng)化立體倉庫系統(tǒng)，并得到了結(jié)果。就同類貨物在不同存儲(chǔ)位置被尋找的情況下，我們發(fā)明了兩種算法來解決這個(gè)問題，我們將第一種探索式算法命名為現(xiàn)有巷道探索式算法（簡稱CAH），第二種命名為可接受遺傳算法。為顯示每種算法的實(shí)際效率，我們將他們與例證法做了對(duì)比，例證法在獲得最佳方案的同時(shí)需要大量的CPU占用率，因此它并不是最理想的解決方案。CAH算法需要較小的CPU占用率，但獲得的方案大多數(shù)是需要較長的S/R系統(tǒng)行程時(shí)間的次佳的方案。而遺傳算法提供的方案大多是最佳和準(zhǔn)佳(平均占3.37%)的方案。因此，模擬的遺傳算法顯示，它的效率高于其他兩種算法。 不久的將來，在功效和雙命令（DC）的自動(dòng)化倉庫系統(tǒng)領(lǐng)域中，將對(duì)元啟發(fā)式方法和分支定界算法進(jìn)行評(píng)估，以便能在自動(dòng)化倉庫揀選問題上創(chuàng)造最佳的解決方案。 7. 鳴謝 我們感謝來自Tarbiat Modarres 大學(xué)M.M. Sepehri教授的寶貴建議。我們也同樣的感謝為我們提出建議的匿名審稿人。 參考文獻(xiàn) [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