基于PLC立體倉(cāng)庫(kù)畢業(yè)設(shè)計(jì)外文翻譯

河南理工大學(xué)2013中英文對(duì)照翻譯本科畢業(yè)設(shè)計(jì)（論文）中英文對(duì)照翻譯院（系部）機(jī)械與動(dòng)力工程學(xué)院專業(yè)名稱測(cè)控技術(shù)與儀器年級(jí)班級(jí)1203班學(xué)生姓名張賀指導(dǎo)老師王耿20由一個(gè)單一的存儲(chǔ)/檢索機(jī)服務(wù)的多巷道自動(dòng)化立體倉(cāng)庫(kù)存在的揀選分揀問(wèn)題YaghoubKhojastehJae-DongSon加馬里筑波大學(xué)崇實(shí)大學(xué)日本韓國(guó)摘要隨著現(xiàn)代化科技的發(fā)展，倉(cāng)庫(kù)式存儲(chǔ)系統(tǒng)在設(shè)計(jì)與運(yùn)行方面出現(xiàn)了巨大的改革。自動(dòng)化立體倉(cāng)庫(kù)（AS/RS）嵌入計(jì)算機(jī)驅(qū)動(dòng)正變得越來(lái)越普遍。由于AS/RS使用的增加對(duì)計(jì)算機(jī)控制的需要與支持也在提高。這項(xiàng)研究解決了在多巷道立體倉(cāng)庫(kù)的揀選問(wèn)題，在這種存儲(chǔ)/檢索（S/R）操作中，每種貨物可以在多個(gè)存儲(chǔ)位置被尋址到。提出運(yùn)算方法的目標(biāo)是，通過(guò)S/R系統(tǒng)揀選貨物來(lái)最大限度的減少行程時(shí)間。我們開發(fā)的遺傳式和啟發(fā)式算法，以及通過(guò)比較從大量的問(wèn)題中得到一個(gè)最佳的解決方案。關(guān)鍵詞：自動(dòng)化立體倉(cāng)庫(kù)，AS/RS系統(tǒng)，揀選，遺傳算法。1.言在現(xiàn)今的生產(chǎn)環(huán)境中，庫(kù)存等級(jí)保持低于過(guò)去。那是因?yàn)檫@種較小的存儲(chǔ)系統(tǒng)不僅降低庫(kù)存量還增加了揀選貨物的速度。自動(dòng)化立體倉(cāng)庫(kù)（AS/RS），一方面通過(guò)提供快速響應(yīng)，來(lái)達(dá)到高操作效率；另一方面它還有助于運(yùn)作方面的系統(tǒng)響應(yīng)時(shí)間，減少的揀選完成的總行程時(shí)間。因此，它常被用于制造業(yè)、儲(chǔ)存?zhèn)}庫(kù)和分配設(shè)備等行業(yè)中。揀選是倉(cāng)庫(kù)檢索功能的基本組成部分。它的主要目的是，在預(yù)先指定的地點(diǎn)中選擇適當(dāng)數(shù)量的貨物以滿足客戶揀選要求。雖然揀選操作僅僅是物體在倉(cāng)儲(chǔ)中裝卸操作之一，但它卻是“最耗時(shí)間和花費(fèi)最大的倉(cāng)儲(chǔ)功能。許多情形下，倉(cāng)儲(chǔ)盈利的高低就在于是否能將揀選操作運(yùn)行處理好”。（Bozer和White）Ratliff和Rosenthal，他們關(guān)于自動(dòng)化立體倉(cāng)庫(kù)系統(tǒng)（AS/RS）的揀選問(wèn)題進(jìn)行的研究，發(fā)明了基圖算法，在階梯式布局中選取最短的訪問(wèn)路徑。Roodbergen和deKoster拓展了Ratliff和Rosenthal算法。他們認(rèn)為，在平行巷道揀選問(wèn)題上，應(yīng)該穿越巷道末端和中間端進(jìn)行揀選，就此他們發(fā)明了一種動(dòng)態(tài)的規(guī)劃算法解決這問(wèn)題。就此VandenBerg和Gademann發(fā)明了一種運(yùn)輸模型(TP)，它是對(duì)于指定的存儲(chǔ)和卸載進(jìn)行測(cè)算的儀器。他們表示，最好的解決運(yùn)輸問(wèn)題的方法是以機(jī)械的最佳布局來(lái)盡量減少運(yùn)行時(shí)間。Elsayed對(duì)階梯結(jié)構(gòu)的立體倉(cāng)庫(kù)問(wèn)題的研究表明，要在多巷道中揀選貨物并擬定最佳方案，是非常困難和并且耗時(shí)的。Elsayed和Stern提出了啟發(fā)式算法，但據(jù)說(shuō)，他們并沒(méi)有在實(shí)際生產(chǎn)過(guò)程中得到滿意的結(jié)果。黃禹錫等人，研究了立體倉(cāng)庫(kù)系統(tǒng)中的單巷道選道的問(wèn)題，并提出決定了每個(gè)S/R系統(tǒng)揀選效率的啟發(fā)式算法。Thealgorithms在聚集前人分析的基礎(chǔ)上，采取了一些相似的措施。在1983年，通過(guò)仿真，把計(jì)算得到的參數(shù)與Elsayed和Sterns的結(jié)論進(jìn)行了比較。Bozer、White、Han、Lee和Schaefer等人提出了一個(gè)程序，在檢索測(cè)序的基礎(chǔ)上進(jìn)行優(yōu)化，解決了線性分配的問(wèn)題。Lee和Schaefer介紹了一些優(yōu)化和啟發(fā)式的測(cè)序方法，其中包括存儲(chǔ)指令如何被分配到預(yù)先確定的存儲(chǔ)位置。Mahajan通過(guò)對(duì)小件貨物的貯存系統(tǒng)進(jìn)行了改善，得到了一種新的檢索測(cè)序方案，提出最近檢索原則并開發(fā)了一個(gè)驗(yàn)證模型來(lái)預(yù)測(cè)效果。黃禹錫制作了非線性數(shù)學(xué)模型，開發(fā)出以一種啟發(fā)式程序設(shè)計(jì)的自動(dòng)化立體倉(cāng)，與此同時(shí)還可以確定單位負(fù)載的大小。VandenBerg和Rouwenhorst調(diào)查了倉(cāng)庫(kù)規(guī)劃和控制的文獻(xiàn)，規(guī)劃文件包括存儲(chǔ)位置的分配問(wèn)題，倉(cāng)庫(kù)儲(chǔ)存系統(tǒng)的控制問(wèn)題包括路由、排序、調(diào)度、停留點(diǎn)的選擇和秩序配料。Goetschalckx和Wei提交1985年至1992年揀選系統(tǒng)的參考文獻(xiàn)。Koh提出了一些關(guān)于在存儲(chǔ)倉(cāng)庫(kù)中，帶有塔式起重機(jī)的自動(dòng)化立體倉(cāng)庫(kù)的模式。他們推論出的這個(gè)模式是建立在隨機(jī)存儲(chǔ)分配規(guī)則的基礎(chǔ)上的一個(gè)單、雙指令周期。他們還根據(jù)營(yíng)業(yè)額的存儲(chǔ)分配規(guī)則計(jì)算出相應(yīng)行程時(shí)間。Koh提出了優(yōu)化模式，在揀選系統(tǒng)的巷道最末端尋找到了一個(gè)最佳緩沖的區(qū)域，在那里S/R系統(tǒng)可提供多若干個(gè)通行巷道。Amato以coloredtimedPetrinets網(wǎng)站的資料為基礎(chǔ)提出了對(duì)順序檢索的揀選優(yōu)化算法。他們還提出了兩項(xiàng)對(duì)于起重機(jī)和航天飛機(jī)的運(yùn)作的優(yōu)化控制算法。Hsu審議多巷道的倉(cāng)庫(kù)的順序配料問(wèn)題，提出了遺傳算法來(lái)減少總旅行距離。Hwang和Cho提出了采摘的供應(yīng)中心倉(cāng)庫(kù)秩序的績(jī)效評(píng)估模式。他們研究的目的是通過(guò)減少運(yùn)輸數(shù)量、計(jì)算性能和設(shè)備利用率來(lái)減少盡量減少成本。在近期的研究中，DeKoster對(duì)設(shè)計(jì)與控制手冊(cè)中揀選工程的典型決定問(wèn)題進(jìn)行了文獻(xiàn)回顧。他們主要關(guān)注于存儲(chǔ)分配方法、路徑的選擇、配料和分區(qū)。然而，我們沒(méi)有這么多的文獻(xiàn)上的知識(shí)，在處理自動(dòng)化立體倉(cāng)庫(kù)的揀選問(wèn)題上，每個(gè)物品都能夠被儲(chǔ)存在多個(gè)儲(chǔ)存點(diǎn)里。事實(shí)上，許多廠家的產(chǎn)品有許多類型、種類和形狀，這也是他們成品倉(cāng)庫(kù)面臨的問(wèn)題。例如一個(gè)瓷磚制造商，他的產(chǎn)品有兩個(gè)類型（墻磚和地磚）,分別有7中不同的尺寸，4種不同耐久性（磨損差餉)和100多種不同的顏色、圖案、顏色和形狀，總共有5600多種不同的產(chǎn)品類型。作為存儲(chǔ)策略，要一件剛進(jìn)來(lái)的貨物存放在最近的空倉(cāng)位位置上。當(dāng)一個(gè)來(lái)自倉(cāng)庫(kù)中物品，由于產(chǎn)品種類繁多，有很大的可能性從一個(gè)地方存入到另一個(gè)地方。因此，一件物品需要有幾個(gè)在倉(cāng)庫(kù)中存儲(chǔ)位置。換句話說(shuō)，由于分類和分區(qū)，每個(gè)單獨(dú)類型的產(chǎn)品在倉(cāng)庫(kù)中需要一個(gè)更大的空間，一個(gè)物品在幾個(gè)地方存儲(chǔ)時(shí)不可避免的。2.問(wèn)題描述在本研究中，我們考慮到了小件物品的自動(dòng)存儲(chǔ)和檢索系統(tǒng)，那有一個(gè)或多個(gè)巷道。每個(gè)巷道包含了關(guān)于巷道兩旁倉(cāng)儲(chǔ)貨架。每個(gè)巷道結(jié)束的地方都有一個(gè)輸入/輸出口（I/O）。在那里還有一個(gè)單獨(dú)的存儲(chǔ)/檢索（S/R）的儀器來(lái)為所有巷道的系統(tǒng)服務(wù)，它可以同時(shí)在垂直和水平方向移動(dòng)。因此，在兩點(diǎn)之間的行程等于最小的水平和垂直行程。在收到命令之前S/R儀器已經(jīng)定位了輸入/輸出口中的位置。儀器的起始位置取決于最后一件貨物的最后一個(gè)命令的存儲(chǔ)位置。S/R計(jì)算行程中以恒定的速度水平和垂直移動(dòng)。一個(gè)命令可以由多個(gè)貨物請(qǐng)求組成的。同樣每個(gè)貨物也可以在倉(cāng)庫(kù)中多個(gè)位置存儲(chǔ)。當(dāng)檢索請(qǐng)求包括多個(gè)貨物，并且這些貨物在多個(gè)不同的倉(cāng)庫(kù)位置時(shí)，S/R儀器必須到多個(gè)不同的存儲(chǔ)地點(diǎn)完成各個(gè)命令。本次研究的目的就是提出計(jì)算方法來(lái)減少S/R走過(guò)的總時(shí)間來(lái)完成命令程序。3.運(yùn)算方法我們現(xiàn)在有兩種運(yùn)算方法來(lái)解決這個(gè)問(wèn)題：一種是探索式算法，還有一種是遺傳式算法。為了顯示所提出算法的優(yōu)越性，我們把它與其他方法進(jìn)行了比較。由于我們的解決問(wèn)題方法是新提出的，沒(méi)有前人在這個(gè)領(lǐng)域進(jìn)行過(guò)研究，那么我們最先提出的一種運(yùn)算法，用它來(lái)獲取的最佳的解決方案，這種方法我們稱它為例證算法。其結(jié)果作為對(duì)于兩種擬議算法比較的基準(zhǔn)解決方案。在例證法中，我們確定所有可行的解決方法并將他們互相比較找出最好的解決方法來(lái)。為此，這個(gè)方案首先要找所有可行的方法來(lái)選擇一個(gè)命令。然后，S/R系統(tǒng)的計(jì)算獲得每個(gè)方法行程的總時(shí)間，最后，選取的解決方案要求在最短時(shí)間內(nèi)完成要求。這個(gè)解決方案被認(rèn)為是該問(wèn)題的最佳解決方案。考慮到一個(gè)命令的由k種不同類型的貨物組成，其中在ni(i=1,2,...,k)項(xiàng)貨物中第i項(xiàng)貨物被提出請(qǐng)求。在可行的解決辦法總數(shù)挑選順序可以給出：其中，mi是在第i項(xiàng)貨物在倉(cāng)庫(kù)中的總庫(kù)存，得出：通過(guò)例證法已經(jīng)解決了各種類型的問(wèn)題，并且確定了這種低金額低行程的最佳方案。我們發(fā)現(xiàn)，在當(dāng)前巷道上存在貨物（如：該巷道的S/R系統(tǒng)是在檢索過(guò)程的起始端）是解決這個(gè)問(wèn)題的關(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ì)算。我們可以簡(jiǎn)單的對(duì)其進(jìn)行表達(dá)，如果設(shè)r表示在現(xiàn)有巷道中指令貨物的數(shù)目，那么如果r=0時(shí)，該運(yùn)算方法就類似于原來(lái)的例證法。如果r=1時(shí)，該運(yùn)算方法首先要通過(guò)S/R系統(tǒng)對(duì)行程時(shí)間進(jìn)行計(jì)算，設(shè)t1表示在當(dāng)前巷道中，現(xiàn)存貨物為了避免與揀選中的貨物沖突，對(duì)于其余的貨物(如果有的話)進(jìn)行同等于例證法的計(jì)算，以此來(lái)得到最小的計(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)算,就如同，通過(guò)對(duì)每一個(gè)可行的方法計(jì)算出行程時(shí)間，最終選取其中最小的那個(gè)值，即t2階段。最后，在S/R系統(tǒng)中將t1和t2的和設(shè)為最終的解決方案。Khojasteh-Ghamari詳細(xì)的對(duì)在現(xiàn)有巷道中的貨物的揀選順序的分配方法進(jìn)行了討論。如果任何待命的貨物存在于現(xiàn)有巷道中，那么就將倉(cāng)庫(kù)中現(xiàn)存貨物的數(shù)目除以解決方案的數(shù)目。因此，這項(xiàng)任務(wù)目的就是降低總方案的數(shù)目，以此來(lái)減少CPU時(shí)間（程序的處理時(shí)間）。3.1.遺傳算法遺傳算法是一種優(yōu)化過(guò)程，它將問(wèn)題域比作基因類（個(gè)體或染色體），基因類是有多個(gè)基因體組成，其中基因體成符號(hào)形式串行。每一個(gè)基因類都有一個(gè)可能的解，通過(guò)對(duì)問(wèn)題域中的染色體進(jìn)行評(píng)估來(lái)尋求可能的解決方案。在每一代中，我們對(duì)每個(gè)染色體進(jìn)行評(píng)估，選擇一個(gè)分布優(yōu)秀的區(qū)域，在其中對(duì)染色體進(jìn)行變異和交叉操作，重新組合，得到新的染色體。這樣幾代之后，在進(jìn)一步觀察后沒(méi)有得到新進(jìn)展的情況下，那么就將所得到最具適應(yīng)度的染色體視為（所有可能的）最佳解決方案。運(yùn)算常常會(huì)在出現(xiàn)大量的迭代速度和資料后終止（Michalewicz）。表示法每一個(gè)染色體表示待求解問(wèn)題的一個(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)算過(guò)程中，都會(huì)有一套適合的程序來(lái)解決方案。因此，染色體中的指令貨物將會(huì)無(wú)重復(fù)的隨機(jī)分布，貨物的地址代碼也會(huì)隨機(jī)選取，所分配的代號(hào)范圍會(huì)在1到該貨物的總倉(cāng)庫(kù)庫(kù)存數(shù)之間。假設(shè)在倉(cāng)庫(kù)內(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è)。交叉操作在置換問(wèn)題的操作描述里，部分匹配交叉（簡(jiǎn)稱PMX）常被用于揀選問(wèn)題上，部分匹配交叉被視為一種交叉的排列，它確保所有的貨物能迅速的被后裔所發(fā)現(xiàn)。也就是說(shuō)，兩個(gè)后裔全面的接受了父輩基因，接著再填充到其父輩的等位基因上。在圖2中，兩個(gè)父輩用p1和p2來(lái)表示，交叉點(diǎn)是1和3。根據(jù)在相應(yīng)的[M,R]和[E,A]之間，重復(fù)做貨物的取代，這就是說(shuō)，在第一個(gè)父輩中的A和E由R和M所取代，而在第二個(gè)父輩中的R和M就由A和E來(lái)取代。生成的后代是O1和O2(圖2)。同時(shí)，根據(jù)PMX中的揀選問(wèn)題得知，交叉操作的關(guān)鍵是只交換在染色體中的貨物區(qū)域并且不交換相關(guān)的等位基因。圖2.PMX操作變異操作我們現(xiàn)在用二進(jìn)制位(0和1)來(lái)表示基因。在揀選的問(wèn)題上，相關(guān)聯(lián)的等位基因通過(guò)變異操作，將庫(kù)存中一個(gè)基因替代另外一個(gè)等位基因。換而言之，這個(gè)操作并沒(méi)有對(duì)貨物的序列起到任何作用，僅僅只是貨物選擇了另外一個(gè)序列代碼。假設(shè)在O1中，第三個(gè)基因被選為變異基因。由于貨物A在各儲(chǔ)存位置上的總數(shù)有6個(gè)，通過(guò)變異操作在[1,6]范圍里產(chǎn)生隨機(jī)整數(shù)來(lái)代替原來(lái)的第三個(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ì)算。在揀選問(wèn)題中，目標(biāo)函數(shù)的作用是將S/R系統(tǒng)的行程時(shí)間降低到最小。通過(guò)S/R系統(tǒng)對(duì)總行程時(shí)間做標(biāo)準(zhǔn)化的計(jì)算來(lái)得到下一代。Khojasteh-Ghamari對(duì)S/R系統(tǒng)計(jì)算的行程時(shí)間進(jìn)行做了一下說(shuō)明。由于這個(gè)問(wèn)題是最小化的問(wèn)題，所以我們可以將每個(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í)間。問(wèn)題域的大小(簡(jiǎn)稱popsize)決定了每個(gè)染色體應(yīng)被給的時(shí)間。現(xiàn)在來(lái)做個(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≤popsize)，這樣就有qk?1<r≤qk。在上一代中的染色體被新一代的染色體所替代。4.仿真結(jié)果我們制作了一個(gè)擁有36種不同貨物的立體倉(cāng)庫(kù)，在其中還有5種不同類型的指令，對(duì)此比較3種運(yùn)算法的性能。每個(gè)貨物首先先用例證法來(lái)解決。以獲取最佳的行程時(shí)間和CPU占用率。接著用另外兩種解法來(lái)解決。研究結(jié)果如下2表。4.1.仿真模型我們創(chuàng)建了一個(gè)在36種不同物理規(guī)格情況下的倉(cāng)庫(kù)，通過(guò)對(duì)于每一個(gè)倉(cāng)庫(kù)施加5種不同的指令來(lái)對(duì)這3種算法的性能進(jìn)行比較。每種情況首先按例證法來(lái)得到最佳的行程時(shí)間和CPU占用率，然后再通過(guò)另外兩種計(jì)算方法來(lái)解決問(wèn)題。研究結(jié)果顯示在下面兩個(gè)表格中。利用倉(cāng)庫(kù)的主要3個(gè)參數(shù)（倉(cāng)儲(chǔ)容量、密度和形狀）來(lái)設(shè)計(jì)36種不同存儲(chǔ)的情況。由于倉(cāng)儲(chǔ)容量與倉(cāng)庫(kù)中的巷道成比例關(guān)系，我們將倉(cāng)儲(chǔ)容量劃分為4種情況，分別是1、2、3和4種巷道的形式。每個(gè)倉(cāng)儲(chǔ)貨架有780個(gè)存儲(chǔ)位置。因?yàn)槊總€(gè)巷道有兩個(gè)貨架，則一個(gè)巷道就擁有1560個(gè)存儲(chǔ)位置。由于一個(gè)系統(tǒng)對(duì)倉(cāng)庫(kù)中大量巷道進(jìn)行服務(wù)的話，將會(huì)大大降低其系統(tǒng)實(shí)際效率。所以在不考慮5個(gè)或更多巷道的情況下，就由一個(gè)S/R系統(tǒng)對(duì)所有巷道進(jìn)行服務(wù)。對(duì)于倉(cāng)儲(chǔ)密度，我們假定倉(cāng)庫(kù)中的使用率為60%、75%和95%。Bozer和White對(duì)倉(cāng)儲(chǔ)形狀的配置進(jìn)行了相關(guān)描述為，倉(cāng)儲(chǔ)形狀，它是一種對(duì)于貨架高度與長(zhǎng)度的空間比例，假設(shè)倉(cāng)儲(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的處理器,512MB內(nèi)存和2GB虛擬內(nèi)存”的情況下進(jìn)行了試驗(yàn)。結(jié)果列于表1和表2中。表1表示在3種運(yùn)算法下，4種類型“S/R系統(tǒng)平均行程時(shí)間”和“S/R系統(tǒng)平均CPU占用率”。兩種倉(cāng)儲(chǔ)參數(shù)（倉(cāng)儲(chǔ)密度和形狀）的組合形成了每個(gè)倉(cāng)庫(kù)(倉(cāng)庫(kù)分別有1、2、3和4個(gè)巷道)的9種情況，每種情況下的值表示了5種命令下的平均值。表2表示在倉(cāng)儲(chǔ)形狀為0.6和1，4種巷道情況下的平均行程時(shí)間和平均CPU占用率。在表格中，例證法、現(xiàn)有巷道探索式算法和遺傳算法分別用“Enumeration”，“CAH”，“GA”所表示。5.分析結(jié)果通過(guò)對(duì)表1分析可知，在所有情況下的各類倉(cāng)庫(kù)(1，2，3和4個(gè)巷道)，CAH算法是能獲得最大行程時(shí)間和最小CPU占用率的解決方案。換而言之，它是占用較小CPU使用率的方法。然而，它對(duì)S/R系統(tǒng)的行程時(shí)間超過(guò)了其他兩個(gè)。在倉(cāng)庫(kù)中只有一個(gè)巷道的情況下，通過(guò)遺傳算法解決獲得的方案中89%為最佳的方案。其余的方案里次優(yōu)和最優(yōu)的解決方案平均只相差0.09％（但需要更大的CPU時(shí)間）。在擁有2個(gè)3個(gè)和4個(gè)巷道的倉(cāng)庫(kù)中，遺傳法提供的11%的解決方案為最佳方案，其余方案里，獲得方案與最佳方案差別不大，分別是2巷道相差3.86%，3巷道相差4.83%和4巷道相差4.69%。倉(cāng)庫(kù)中巷道的層架數(shù)目會(huì)影響到運(yùn)算效率。由于增加的總數(shù)是實(shí)際問(wèn)題中出現(xiàn)的，例證法中要增加較大的CPU占用率才能獲得最佳解決方案。然而在大多數(shù)情況下，遺傳法則需要相比于例證法較少的CPU占用率就能完成S/R系統(tǒng)的最佳方案。表格1.3種算法的性能表格2.3中算法在倉(cāng)儲(chǔ)形狀上的比較此外，運(yùn)算方法的性能是受貨架配置所影響的。表2顯示了通過(guò)對(duì)S/R系統(tǒng)的平均行程時(shí)間和平均CPU占用率在多巷道中的兩種倉(cāng)儲(chǔ)形狀（0.6和1）的比較。在此表中顯示了當(dāng)倉(cāng)儲(chǔ)容量增加時(shí)，兩個(gè)貨架配置的算法比較。在一個(gè)倉(cāng)庫(kù)只有一個(gè)巷道時(shí)，例證法提供了最佳的方案，并且它的CPU占用率低于遺傳法。然而，如果倉(cāng)庫(kù)有多個(gè)巷道時(shí)，遺傳算法需要的CPU占用率低于例證法。由于各種倉(cāng)儲(chǔ)形狀B的結(jié)果相似，我們將倉(cāng)儲(chǔ)形狀B設(shè)為0.73。因?yàn)閷?duì)B的3種算法性能大致相同，所以在倉(cāng)庫(kù)里的貨架配置對(duì)算法性能沒(méi)有影響。6.總結(jié)在本次研究中，我們討論了多巷道自動(dòng)化立體倉(cāng)庫(kù)系統(tǒng)，并得到了結(jié)果。就同類貨物在不同存儲(chǔ)位置被尋找的情況下，我們發(fā)明了兩種算法來(lái)解決這個(gè)問(wèn)題，我們將第一種探索式算法命名為現(xiàn)有巷道探索式算法（簡(jiǎn)稱CAH），第二種命名為可接受遺傳算法。為顯示每種算法的實(shí)際效率，我們將他們與例證法做了對(duì)比，例證法在獲得最佳方案的同時(shí)需要大量的CPU占用率，因此它并不是最理想的解決方案。CAH算法需要較小的CPU占用率，但獲得的方案大多數(shù)是需要較長(zhǎng)的S/R系統(tǒng)行程時(shí)間的次佳的方案。而遺傳算法提供的方案大多是最佳和準(zhǔn)佳(平均占3.37%)的方案。因此，模擬的遺傳算法顯示，它的效率高于其他兩種算法。不久的將來(lái)，在功效和雙命令（DC）的自動(dòng)化倉(cāng)庫(kù)系統(tǒng)領(lǐng)域中，將對(duì)元啟發(fā)式方法和分支定界算法進(jìn)行評(píng)估，以便能在自動(dòng)化倉(cāng)庫(kù)揀選問(wèn)題上創(chuàng)造最佳的解決方案。7.鳴謝我們感謝來(lái)自TarbiatModarres大學(xué)M.M.Sepehri教授的寶貴建議。我們也同樣的感謝為我們提出建議的匿名審稿人。參考文獻(xiàn)[1]Amato,F.,Basile,F.,Carbone,C.andChiacchio,P.,Anapproachtocontrolautomatedwarehousesystems,ControlEngineeringPractice,Vol.13,pp.1223-1241,2005.[2]Bozer,Y.A.andWhite,J.A.,Travel-timemodelsforautomatedstorage/retrievalsystems,IIETransactions,Vol.16,No.4,pp.329-338,1984.[3]Bozer,Y.A.andWhite,J.A.,Designandperformancemodelsforend-of-aisleorderpickingsystems,ManagementScience,Vol.36,No.7,pp.852-866,1990.[4]Cheng,R.,Gen,M.andSasaki,M.,Film-copydelivererproblemusinggeneticalgorithms,Computers&IndustrialEngineering,Vol.29,pp.549-553,1995.[5]Elsayed,E.A.,Algorithmsforoptimalmaterialhandlinginautomaticwarehousingsystems,InternationalJournalofProductionResearch,Vol.19,pp.525-535,1981.[6]Elsayed,E.A.andStern,R.G.,Computerizedalgorithmsfororderprocessinginautomatedwarehousingsystems,InternationalJournalofProductionResearch,Vol.21,pp.579-586,1983.[7]Goetschalckx,M.andWei,R.,Bibliographyonorderpickingsystems,Vol.1,pp.1985-1992,1994,availableat/people/faculty/MarcGoetschalckx/research.html.[8]Han,M.-H.,McGinnis,L.F.,Shieh,J.S.andWhite,J.A.,Onsequencingretrievalsinanautomatedstorage/retrievalsystem,IIETransactions,Vol.19,pp.56-66,1987.[9]Hwang,H.,Baek,W.andLee,M.-K.,Clusteringalgorithmsfororderpickinginanautomatedstorageandretrievalsystem,InternationalJournalofProductionResearch,Vol.26,pp.189-201,1988.[10]Hwang,H.,Moon,S.andGen,M.,Anintegratedmodelforthedesignofend-of-aisleorderpickingsystemandthedeterminationofunitloadsizesofAGVs,Computers&IndustrialEngineering,Vol.42,pp.249-258,2002.[11]Khojasteh-Ghamari,Y.,OrderpickingprobleminanAS/RSwithmultiplestocklocations.M.Sc.thesis,Tarbiat[12]Koh,S.G.,Kim,B.S.andKim,B.N.,TraveltimemodelforthewarehousingsystemwithatowercraneS/Rmachine,Computers&IndustrialEngineering,Vol.43,pp.495-507,2002.[13]Koh,S.G.,Kwon,H.M.andKim,Y.J.,Ananalysisoftheend-of-aisleorderpickingsystem:Multi-aisleservedbyasingleorderpicker,InternationalJournalofProductionEconomics,Vol.98,pp.162-171,2005.[14]Lee,H.F.andSchaefer,S.K.,Retrievalsequencingforunit-loadautomatedstorageandretrievalsystemswithmultipleopenings,InternationalJournalofProductionResearch,Vol.34,pp.2943-2962,1996.[15]Lee,H.F.andSchaefer,S.K.,Sequencingmethodsforautomatedstorageandretrievalsystemswithdedicatedstorage,Computers&IndustrialEngineering,Vol.32,pp.351-362,1997.[16]Mahajan,S.,Rao,B.V.andPeters,B.A.,Aretrievalsequencingheuristicforminiloadend-ofaisleautomatedstorage/retrievalsystems,InternationalJournalofProductionResearch,Vol.36,pp.1715-1731,1998.[17]Michalewicz,Z.,GeneticAlgorithms+DataStructures=EvolutionPrograms,1992(SpringerVerlag:Berlin)[18]Ratliff,H.D.andRosenthal,A.S.,Order-pickinginarectangularwarehouse:asolvablecaseofthetravelingsalesmanproblem,OperationsResearch,Vol.31,pp.507-521,1983.[19]Roodbergen,K.J.anddeKoster,R.,Routingorderpickersinawarehousewithamiddleaisle,EuropeanJournalofOperationalResearch,Vol.133,pp.32-43,2001.[20]Rouwenhorst,B.,Reuter,B.,Stockeahm,V.,vanHoutum,G.J.,Mantel,R.J.andZijm,W.H.M.,Warehousedesignandcontrol:frameworkandliteraturereview,EuropeanJournalofOperationalResearch,Vol.122,pp.515-533,2000.[21]VandenBerg,J.P.,Aliteraturesurveyonplanningandcontrolofwarehousingsystems,IIETransactions,Vol.31,pp.751-762,1999.[22]VandenBerg,J.P.andGademann,A.J.R.M.,Optimalroutinginanautomatedstorage/retrievalsystemwithdedicatedstorage,IIETransactions,Vol.31,pp.407-415,1999.[23]Hsu,C.M.,Chen,K.Y.andChen,M.C.,Batchingordersinwarehousesbyminimizingtraveldistancewithgeneticalgorithms,ComputersinIndustry,Vol.56,pp.169-178,2005.[24]Hwang,H.S.andCho,G.S.,Aperformanceevaluationmodelfororderpickingwarehousedesign,Computers&IndustrialEngineering,Vol.51,pp.335-342,2006.[25]DeKoster,R.,Le-Duc,T.andRoodbergenK.J.,Designandcontrolofwarehouseorderpicking:Aliteraturereview,EuropeanJournalofOperationalResearch,Vol.182,pp.481-501,2007.

OrderPickingProbleminaMulti-AisleAutomatedWarehouseServedbyaSingleStorage/RetrievalMachineYaghoubKhojasteh-Ghamari Jae-DongSonUniversityofTsukubaSoongsilJapanKoreaAbstractRecenttechnologicaldevelopmentshaverevolutionizedthedesignandoperationofware-housingsystems.Automatedstorageandretrievalsystems(AS/RS)drivenbyembeddedcomputersarebecomingincreasinglymoreprevalent.TheincreaseduseofAS/RSiscreatingtheneedforcomputerizedcontrolalgorithmstosupporttheschedulingandpickingdecisions.Thisresearchaddressesanorderpickingprobleminamulti-aisleautomatedwarehouse,inwhichasinglestorage/retrieval(S/R)machineperformsstorageandretrievaloperations,andeachitemcanbefoundinseveralstoragelocations.OurobjectiveistoproposealgorithmsthatminimizethetotaltimetraveledbytheS/Rmachinetocompletetheretrievalprocessoforders.Wedevelopageneticalgorithmandanordinaryheuristic,andprovideaperformancecomparisonofthemwithoptimalsolution.Numericalresultsfromalargesetofproblemsarereported.Keywords:AutomatedWarehouse,AS/RS,OrderPicking,GeneticAlgorithms.1.IntroductionIntoday’smanufacturingenvironments,inventoriesaremaintainedatlowerlevelsthaninthepast.Thesereducedinventorieshaveledtosmallerstoragesystems,whichinturnhavecreatedtheneedforquickaccesstothematerialbeingheldinwarehouse.Hence,automatedstorageandretrievalsystems(AS/RS)usedinmanufacturing,ware-housing,anddistributionapplicationsmustbedesignedtoprovidequickresponsetimestoservicerequestsinordertokeepthesystemoperatingefficiently.OneimportantoperationalaspectoftheAS/RS,whichcontributestothesystemresponsetime,istominimizethetotaltimetraveledbytheS/Rmachinetocompletetheretrievalprocessoforders.Orderpickingisafundamentalcomponentoftheretrievalfunctionperformedinwarehouses.Themainpurposeofanorderpickingsystemistofillcustomerordersbyselectingtheappropriateamountofmaterialfromapre-designatedstoragemediumknownasthepickingorforwardarea.Orderpickingrepresentsonlyasubsetofthematerialhandlingoperationsperformedinwarehousing.However,itis‘oneofthemostcostlyandtime-consumingfunctionsofwarehousing.Inmanywarehouses,thedifferencebetweenprofitandlossdependsonhowwelltheorderpickingoperationisrun’(BozerandWhite).TherearemanystudiesonorderpickingproblemsinAS/RSandautomatedware-housingsystems.RatliffandRosenthaldevelopedagraph-basedalgorithmtofindtheshortestpathtovisitasetofpicklocationsinaladderlayout.RoodbergenanddeKosterextendedtheworkofRatliffandRosenthal.Theyconsideredtheorderpickingprobleminaparallelaislewarehouseinwhichorderpickerscancrossovertheaislesattheendsofaislesaswellasatamiddlecrossaisle.Theydevelopedadynamicprogrammingalgorithmtosolvetheproblem.VandenBergandGademanndevelopedatransportationproblem(TP)modelforablocksequencinginanAS/RSwithdedicatedstorageandasingle-loadmachine.TheyprovedthattheoptimalsolutionoftheTPproblemistheoptimalsequenceofthemachinetominimizethetravellingtime.Elsayedmadeachainofstudiesontheproblemofoptimallybatchingseveralordersinatwo-dimensionalwarehousewithladderstructure.Recognizingthattheexactsolutionsoftheproblemareverydifficultandtimeconsumingtoobtain,ElsayedandSternpresentedsomeheuristicalgorithms,butreportedthatnoneofthemproducesconsistentlysuperiorresultsthroughexperimentations.Hwangetal.studiedasimilarorderpickingprobleminasingle-aisleAS/RSandpresentedheuristicalgorithms,whichdetermineanefficientbatchingofordersforeachtouroftheS/Rmachine.Thealgorithmswerebasedonclusteranalysiswithsomesimilaritymeasures.Throughsimulation,theycomparedperformancesoftheproposedalgorithmswithElsayedandSterns’resultsin1983.BozerandWhite,Hanetal.,andLeeandSchaeferproposedaproceduretooptimizethesequencingofretrievalrequestsbasedonthesolutionofalinearassignmentproblem.LeeandSchaeferalsopresentedseveraloptimumandheuristicsequencingmethods,whereastoragerequestisassignedtoapredeterminedstoragelocation.Mahajanetal.developedaretrievalsequencingschemeaimedatimprovingthethroughputofminiloadAS/RS.Theyproposedanearest-neighborretrievalsequencingheuristicanddevelopedananalyticalmodeltopredictitsperformance.Hwangetal.formulatedanonlinearmathematicalmodelanddevelopedanefficientheuristicsolutionproceduretodesigntheAS/RSanddeterminetheunitloadsizeofthevehiclesimultaneously.VandenBergandRouwenhorstetal.surveyedliteratureonwarehouseplanningandcontrol.Planningincludesthestoragelocationassignmentproblem,andthecontrolofawarehousingsystemincludesrouting,sequencing,scheduling,dwell-pointselection,andorderbatching.GoetschalckxandWeipresentedabibliographyonorderpickingsystemsfor1985throughto1992.KposedsomemodelsfortraveltimesoftheS/Rmachineinawarehousewithatowercrane.Theyderivedthemodelsforbothsingleanddualcommandcyclesbasedontherandomizedstorageassignmentrule.Theyalsocalculatedthetraveltimeundertheturnover-basedstorageassignmentrulethroughanumericalapproach.Kposedanoptimizationmodeltofindanoptimalbuffersizeinend-of-aisleorderpickingsystem,whereasingleS/Rmachineservesseveralaisles.AposedanalgorithmtooptimallysequencetheretrievalordersbasedoncoloredtimedPetrinetsframework.Theyalsoproposedtwocontrolalgorithmstooptimizetheoperationsofthecranesandshuttle.Hsuetal.consideredtheorderbatchingprobleminamulti-aislewarehouseandproposedageneticalgorithmtominimizethetotaltraveldistance.HwangandChopresentedaperformanceevaluationmodelfortheorderpickingwarehouseinasupplycenter.Theobjectiveoftheirstudywastominimizethecostbyminimizingthenumberoftransportersandtocalculatetheperformanceandfacilityutilizationrate.Inarecentstudy,DeKosteretal.carriedoutaliteraturereviewontypicaldecisionproblemsindesignandcontrolofmanualorderpickingprocesses.Theyfocusedonoptimallayoutdesign,storageassignmentmethods,routingmethods,orderbatchingandzoning.However,wehavenoknowledgeofpapersintheliteraturethataddresstheorderpickingprobleminautomatedstorageandretrievalsystems,whereeachitemcanbestockedatseveralstoragelocations.Infact,somemanufacturerswhoseproductshavealargevarietyoftypes,shapes,andsizesarefacedwiththisproblemintheirfinishedgoodswarehouses.Atilemanufacturer,forexample,whoseproductsareintwotypes(wallandfloor),eachofwhichin7differentsizes,4groupsofdurability(P.E.I.WearRating),and100differentcolors,designsandshadeshastotally5600differentproducttypes.Asastoragepolicy,acomingpackofaproductintothewarehouseisplacedinthenearestemptystoragelocation.Whenanitemisretrievedfromthewarehouse,becauseofthelargevarietyoftheproducts,thereisastrongprobabilitythattheplacebefilledwithanothertype.Therefore,anitemcanbefoundinseveralstoragelocationsinthewarehouse.Inotherwords,sinceclassifyingandzoningeachindividualtypeofproductinthewarehouseneedsawarehousewithalargespace,thestorageofaniteminseveralplacesisunavoidable.2.ProblemDescriptionInthisresearch,weconsideraminiloadautomatedstorageandretrievalsystem,wherethereareoneormoreaisles.Eachaislecontainsastoragerackonbothsidesoftheaisle.Thereisaninput/output(I/O)stationattheendofeachaisle.Thereisalsoasinglestorage/retrieval(S/R)machinededicatedtoallaislesofthesystem,whichcansimultaneouslymoveinverticalandhorizontaldirections.Hence,thetraveltimebetweentwopointsisequaltothemaximumofthehorizontalandverticaltravels.TheS/RmachineispositionedatoneoftheI/Ostationsbeforethereceiptofanorder.Thestartingplaceofthemachinedependsonthestoragelocation(aisle)ofthelastitemofthelastorder.IncalculatingthetraveltimeoftheS/Rmachine,constantvelocitiesareusedforhorizontalandverticaltravels.Anordercanbearequestformorethanoneitem.Alsoeachitemcanbeinseveralstoragelocationsinthewarehouse.Whenretrievalrequestsconsistofmultipleitemsandtheitemsareinmultiplestocklocations,theS/Rmachinemusttraveltonumerousstoragelocationstocompleteeachorder.TheaimofthisresearchistoproposealgorithmstominimizethetotaltimetraveledbytheS/Rmachinetocompletetheretrievalprocessofanorder.3.TheAlgorithmsWepresenttwoalgorithmstosolvetheproblem:anordinaryheuristic,andasuitablegeneticalgorithm.Toshowthesuperiorityofthepresentedalgorithms,itisnecessarytocomparethemwithothermethodsaswellastheoptimalsolution.Sinceourproblemisnew,noresearchhasbeenconductedinthisfield,wefirstpresentanalgorithmtoobtainthebestsolutionfortheproblem,socalledtheenumerationalgorithm.Itsresultsareusedasbenchmarksolutionsforperformancecomparisonofthetwoproposedalgorithms.Intheenumerationalgorithm,weidentifyallfeasiblesolutionsandcomparethemwitheachothertofindthebestsolution.Todothis,themethodfirstfindsallfeasiblewaystopickanorder.Then,itcalculatesthetotaltimetraveledbytheS/Rmachineforeachone,andfinallyselectsthesolutionrequiringtheleastamountoftimetoaccomplishtheorder.Thissolutionisconsideredastheoptimumsolutionfortheproblem.Consideranorderconsistsofkdistincttypesofitems,inwhichni(i=1,2,...,k)itemsoftheithtypearerequested.Thetotalnumberoffeasiblesolutionstopicktheordercanbegivenby：where,miisthetotalinventoryoftheithtypeinthewarehouse,and.Havingsolvedvariousproblemsbytheenumerationalgorithmandidentifyingthebestsolutionthathadtheminimumamountoftraveltime,wefoundthattheexistingitemsinthecurrentaisle(i.e.theaisleinwhichtheS/Rmachineisinatthebeginningoftheretrievingprocess)arethekeytothefinalsolution.Wedevelopanalgorithmonthebasisofthementionedresults,andcallitthecurrent-aisleheuristic(CAH)algorithm.IntheCAHalgorithm,theexistingitemsinthecurrentaisleareselectedfirstforretrieval.Afterwards,theremainderoftheorder(ifany)isselectedandallthevariousretrievalmethodsarestudied.Wecansimplifythepreviousstatementsbystatingthatifrdenotesthenumberoftheordereditemsexistinginthecurrentaisle,andifr=0,themethodthenbecomessimilartotheenumerationalgorithm.Ifr=1,thenthemethodfirstcalculatesthetimetraveledbytheS/Rmachine,t1,foronlyoneexistingiteminthecurrentaisle,andremovesthatitemfromthelistofordereditems,andthenfortheremainingitems(ifany),itproceedsassameastheenumerationalgorithmtoobtaintheminimumtraveltime,t2.ThetotaltraveltimeoftheS/Rmachinewillbesumoft1andt2asthefinalsolution.Ifr>1,thenthemethodfirstassignsthepickingsequencetopickupallritemswhichexistinthecurrentaisle.Aftercalculatingthetraveltime,t1,itremovestheitemsfromthelistofordereditems.Then,fortheremainingitems(ifany),itproceedsliketheenumerationalgorithm,i.e.findingallfeasiblewaysfollowedbycalculatingthetraveltimeforeachoneandfinallyselectingtheminimumvalueamongthem,t2.ThetotaltraveledtimeoftheS/Rmachinewillbesumoft1andt2asthefinalsolution.Khojasteh-Ghamaridiscussedindetailthemethodofassigningapickingsequenceoftheordereditemsexistinginthecurrentaisle.Ifanyordereditemsexistinthecurrentaisle,thenthenumberofwaysstudiedwillbedividedbythenumberoftheitemsexistinginthewarehouse.Therefore,thistaskcausesthetotalnumberofpotentialsolutionstodecreasedramatically,andhence,theCPUtime(processtimeoftheprogram)wouldbedecreasedaswell.3.1.GeneticalgorithmAgeneticalgorithmisanoptimizationprocessthatemploysgenotypes(individualsorchromosomes)inapopulation,andthegenotypesaremadeofunitscalledgenesarrangedinlinearsuccession.Eachgenotypewouldrepresentapotentialsolutiontoaproblem;anevaluationprocessrunonapopulationofchromosomescorrespondstoasearchthroughaspaceofpotentialsolutions.Ineachgeneration,weevaluateeachchromosome,selectanewpopulationwithrespecttotheprobabilitydistributionbasedonfitnessvalues,andrecombinethechromosomesinthenewpopulationbymutationandcrossoveroperators.Afteranumberofgenerations,whennofurtherimprovementisobserved,thebestchromosomerepresentsanoptimal(possiblytheglobal)solution.Thealgorithmisoftenterminatedafterafixednumberofiterationsdependingonspeedandresourcecriteria(Michalewicz).RepresentationAchromosomerepresentsapotentialsolution,whereeachoneisviewedasasequenceofitemseachwithitsownassociatedallele.Byanalogy,eachgeneinachromosomerepresentstheitemtype,anditsassociatedallelerepresentsthestoragelocation.Therefore,eachpotentialsolutionconsistsofachromosome,inwhichthenumberofgenesisequaltothenumberofitemsinthereceivedorder.AnexampleisgiveninFigure1.Figure1showsapotentialsolutioninwhichtheitemswithcodesA,B,CandDhavebeenordered.ItemCwithlocationnumber5,itemBwithlocationnumber7,itemAwithlocationnumber4,anditemDwithlocationnumber3havebeenselectedforretrieval.Figure1.Representationofapotentialsolution.Itshouldbenotedthatthesequenceofpickingitemshasalsobeenconsideredintherepresentation.Inthisexample,itemCwithlocationnumber5willberetrievedfirst,