本文關(guān)鍵詞：自動化立體倉庫揀選作業(yè)路徑優(yōu)化問題研究，由筆耕文化傳播整理發(fā)布。

專利名稱訂單揀選方法及系統(tǒng)的制作方法
技術(shù)領(lǐng)域本發(fā)明涉及物流倉儲中的倉庫揀選作業(yè)領(lǐng)域，特別涉及一種需要在多個(gè)巷道中水 平移動的訂單揀選方法及系統(tǒng)。
背景技術(shù)倉庫揀選作業(yè)是現(xiàn)代化物流配送的核心，物流配送的現(xiàn)代化程度的高低取決于揀 選技術(shù)。許多大型倉庫或配送中心采用高層貨架式立體倉庫，相鄰兩排貨架之間有一條巷 道，每條巷道有一臺堆垛機(jī)，堆垛機(jī)可以同時(shí)沿垂直方向和水平方向移動，存取巷道兩側(cè)垂 直貨架上的貨物。如圖1所示，0點(diǎn)為巷道出入口，a、b、C、d、e、f為垂直貨架上的幾個(gè)取貨 點(diǎn)，堆垛機(jī)一次可以揀選若干個(gè)貨位上的貨物，，然后返回到0點(diǎn)將貨箱放置到傳送系統(tǒng)上。目前，已經(jīng)存在很多對揀選作業(yè)進(jìn)行優(yōu)化的方法�！痘谙伻核惴ǖ膾x作業(yè)優(yōu)化 問題》(系統(tǒng)工程理論與實(shí)踐，2009. 2 ，第179-184頁)提出一種蟻群算法，對取貨點(diǎn)的存 取順序進(jìn)行優(yōu)化，以使得作業(yè)時(shí)間最短。但是，該方法假定堆垛機(jī)一次作業(yè)可以揀選所有取 貨點(diǎn)的貨物，沒有考慮堆垛機(jī)所攜帶的貨箱的容量限制。針對上述問題，《自動化立體倉庫揀選作業(yè)路徑優(yōu)化問題研究》(系統(tǒng)工程理論與 實(shí)踐，2007. 2，第139-143頁)提出一種遺傳算法，在堆垛機(jī)一次作業(yè)容量受限的情況下，針 對垂直貨架上的多個(gè)取貨點(diǎn)，安排若干次揀選作業(yè)使得總的揀選代價(jià)最小。如圖2所示，圖 2中表示兩次揀選作業(yè)，第一次的揀選順序?yàn)镺-a-e-f-O，第二次揀選順序?yàn)?-b-C-d_0。對 于堆垛機(jī)需要行進(jìn)到其它巷道中進(jìn)行揀選的問題，該方法不能夠解決，當(dāng)然，對于自動化立 體倉庫，一般每個(gè)巷道都有一臺堆垛機(jī)，負(fù)責(zé)揀選該巷道兩側(cè)貨架上的貨物，某一巷道的堆 垛機(jī)不需要行進(jìn)到其它巷道進(jìn)行揀選。在某些情況下，需要一臺堆垛機(jī)揀選多個(gè)巷道中的貨物，《多巷道固定貨架揀選作 業(yè)優(yōu)化問題的研究》(控制與決策，2008. 12，第1338-1342頁)對此問題進(jìn)行了研究。如圖 3所示，堆垛機(jī)從0點(diǎn)出發(fā)，依次揀選巷道1、巷道2、…、巷道j兩側(cè)貨架中的貨物，而后返 回到0點(diǎn)，在揀選過程中，堆垛機(jī)所攜帶的貨箱容量有限，裝滿一箱貨物就返回到0點(diǎn)把貨 物放置到傳送系統(tǒng)上，并且，前一巷道的揀選作業(yè)全部完成后才能進(jìn)入下一巷道進(jìn)行作業(yè)。但是，對于貨架擺放更加復(fù)雜，并且需要在多個(gè)巷道內(nèi)移動進(jìn)行揀選的情況，上述 方法不能解決。倉庫中貨架長短不一，橫豎不一，需要作業(yè)人員在多個(gè)巷道中移動揀選這些 貨物。例如，大型超市、書店、藥店、網(wǎng)店、倉庫等的補(bǔ)貨發(fā)貨作業(yè)。在這類企業(yè)中，訂單的 批量較小、訂單所涉及的商品種類較多，需要在更大范圍內(nèi)進(jìn)行揀選，在這類倉庫中貨架高 度不高，許多揀選作業(yè)是靠人工進(jìn)行的，作業(yè)人員可以較容易的取下貨架高層中的商品，因 此，在垂直方向上的作業(yè)距離可以忽略不計(jì)，上述方法不能解決此問題。
發(fā)明內(nèi)容
本發(fā)明實(shí)施例提供一種訂單揀選方法及系統(tǒng)，通過從數(shù)據(jù)庫中查找訂單中所需貨 物所在的貨位、大小及重量后求解最佳揀選路徑；可高效地計(jì)算出揀選路徑，降低作業(yè)成本，提高作業(yè)效率。為達(dá)到上述目的，本發(fā)明實(shí)施例提供一種訂單揀選的方法，應(yīng)用于需要在多個(gè)巷 道中水平移動的訂單揀選，所述方法包括根據(jù)倉庫貨架的擺放情況，生成倉庫平面布置 圖；計(jì)算并存儲巷道和節(jié)點(diǎn)的信息；計(jì)算并存儲倉庫中各節(jié)點(diǎn)之間的最短路徑；存儲貨物 的貨位信息、貨物的大小及重量信息；在進(jìn)行訂單揀選時(shí)，從預(yù)存的數(shù)據(jù)中查找所述訂單中所需貨物的貨位、大小及重 量；根據(jù)所述訂單中所需貨物的數(shù)量、以及查找到的貨物的大小及重量計(jì)算所需貨物的需 求量；并利用預(yù)先存儲的各節(jié)點(diǎn)之間的最短路徑計(jì)算任意兩個(gè)所需貨物之間的最短路徑；根據(jù)揀選設(shè)備的容量、所述任意兩個(gè)所需貨物之間的最短路徑以及所述訂單中所 需貨物的需求量，通過遺傳算法和LK算法求解最佳揀選路徑，以使所述揀選設(shè)備根據(jù)所述 最佳揀選路徑進(jìn)行訂單揀選。本發(fā)明實(shí)施例還提供一種訂單揀選的系統(tǒng)，應(yīng)用于需要在多個(gè)巷道中水平移動的 訂單揀選，所述系統(tǒng)包括服務(wù)器、無線局域網(wǎng)絡(luò)與移動終端；其中，所述服務(wù)器包括制圖單元，根據(jù)倉庫貨架的擺放情況，生成倉庫平面布置圖；計(jì)算出巷道和節(jié)點(diǎn)的 信息；計(jì)算倉庫中各節(jié)點(diǎn)之間的最短路徑；存儲單元，存儲貨物的貨位、大小及重量的信息，以及所述巷道和節(jié)點(diǎn)的信息；存 儲倉庫中各節(jié)點(diǎn)之間的最短路徑；計(jì)算單元，用于從預(yù)存的數(shù)據(jù)中查找所述訂單中所需貨物的貨位、大小及重量；根 據(jù)所述訂單中所需貨物的數(shù)量、以及查找到的貨物的大小及重量計(jì)算所需貨物的需求量; 并利用預(yù)先存儲的各節(jié)點(diǎn)之間的最短路徑計(jì)算任意兩個(gè)所需貨物之間的最短路徑；求解單元，用于根據(jù)揀選設(shè)備的容量、所述任意兩個(gè)所需貨物之間的最短路徑以 及所述訂單中所需貨物的需求量，通過遺傳算法和LK算法求解最佳揀選路徑，以使所述揀 選設(shè)備根據(jù)所述最佳揀選路徑進(jìn)行訂單揀選。本發(fā)明實(shí)施例的有益效果在于，通過從數(shù)據(jù)庫中查找訂單中所需貨物所在的貨 位、大小及重量后求解最佳揀選路徑；可高效地計(jì)算出揀選路徑，降低作業(yè)成本，提高作業(yè) 效率；解決在貨架擺放不一、貨架高度相對較小、對同一貨位不同層的貨架上的貨物存取時(shí) 所用代價(jià)差異不大、揀選作業(yè)需要優(yōu)化的主要是揀選作業(yè)人員水平移動距離的情況下訂單 的揀選問題。
附圖說明

此處所說明的附圖用來提供對本發(fā)明的進(jìn)一步理解，構(gòu)成本申請的一部分，并不 構(gòu)成對本發(fā)明的限定。在附圖中圖1是現(xiàn)有技術(shù)中巷道堆垛機(jī)在垂直貨架上的存取示意圖；圖2是現(xiàn)有技術(shù)中巷道堆垛機(jī)在垂直貨架上的兩次存取作業(yè)示意圖；圖3是現(xiàn)有技術(shù)中堆垛機(jī)在多巷道中的揀選示意圖；圖4是本發(fā)明實(shí)施例1的訂單揀選方法的流程圖；圖5是本發(fā)明實(shí)施例2的訂單揀選方法的流程圖；圖6是本發(fā)明實(shí)施例2的倉庫的示意圖；圖7是本發(fā)明實(shí)施例2的優(yōu)化過程的流程圖8是本發(fā)明實(shí)施例2的交叉操作的流程圖；圖9是本發(fā)明實(shí)施例2的變異操作的流程圖；圖10是本發(fā)明實(shí)施例2的獲取最優(yōu)個(gè)體過程中的迭代示意圖；圖11是本發(fā)明實(shí)施例2的最優(yōu)個(gè)體表示的揀選路徑示意圖；圖12是本發(fā)明實(shí)施例3的訂單揀選系統(tǒng)的構(gòu)成13是本發(fā)明實(shí)施例3的服務(wù)器的構(gòu)成示意圖；圖14是本發(fā)明實(shí)施例4的路徑獲取單元的構(gòu)成示意圖。
具體實(shí)施例方式為使本發(fā)明的目的、技術(shù)方案和優(yōu)點(diǎn)更加清楚明白，下面結(jié)合附圖對本發(fā)明實(shí)施 例作進(jìn)一步詳細(xì)說明。在此，本發(fā)明的示意性實(shí)施例及其說明用于解釋本發(fā)明，但并不作為 對本發(fā)明的限定。實(shí)施例1本發(fā)明實(shí)施例提供一種訂單揀選的方法，應(yīng)用于包括多種所需貨物的訂單，所需 貨物存放在倉庫的貨位上，縱向巷道和橫向巷道形成節(jié)點(diǎn)。如圖4所示，所述方法包括步驟401，根據(jù)倉庫貨架的擺放情況，生成倉庫平面布置圖；計(jì)算并存儲巷道和節(jié) 點(diǎn)的信息；計(jì)算并存儲倉庫中各節(jié)點(diǎn)之間的最短路徑；存儲貨物的貨位信息、貨物的大小
及重量信息。步驟402，在進(jìn)行訂單揀選時(shí)，從預(yù)存的數(shù)據(jù)中查找訂單中所需貨物所在的貨位、 大小及重量；根據(jù)所需貨物的數(shù)量、以及查找到的貨物的大小及重量計(jì)算所需貨物的需求 量；并利用預(yù)先存儲的各節(jié)點(diǎn)之間的最短路徑計(jì)算任意兩個(gè)所需貨物之間的最短路徑；步驟403，根據(jù)揀選設(shè)備的容量、任意兩個(gè)所需貨物之間的最短路徑、以及訂單中 所需貨物的需求量，通過遺傳算法和LK算法求解最佳揀選路徑，以使揀選設(shè)備根據(jù)最佳揀 選路徑進(jìn)行訂單揀選。在本實(shí)施例中，訂單可包括多種所需貨物、以及每種所需貨物的數(shù)量。每種所需貨 物所在的貨位、大小及重量等信息可預(yù)先存儲在數(shù)據(jù)庫中。在本實(shí)施例中，訂單中的所需貨物存放在貨架上，同一種貨物存放在同一貨位。貨 架擺放不一、貨架高度相對較小、對同一位置不同層的貨架上的貨物存取時(shí)所用代價(jià)差異 不大，揀選作業(yè)人員需要利用揀選設(shè)備在多個(gè)巷道中水平移動對訂單進(jìn)行揀選。由上述實(shí)施例可知，通過從數(shù)據(jù)庫中查找訂單中所需貨物所在的貨位、大小及重 量后求解最佳揀選路徑；可高效地計(jì)算出揀選路徑，降低作業(yè)成本，提高作業(yè)效率。實(shí)施例2本發(fā)明實(shí)施例提供一種訂單揀選的方法，應(yīng)用于包括多種所需貨物的訂單，以下 在實(shí)施例1的基礎(chǔ)上對上述方法進(jìn)行詳細(xì)說明，與實(shí)施例1相同的內(nèi)容不再贅述。如圖5所示，上述訂單揀選的方法包括步驟501，根據(jù)倉庫貨架的擺放情況，生成倉庫平面布置圖；計(jì)算出巷道和節(jié)點(diǎn)的 信息；計(jì)算倉庫中各節(jié)點(diǎn)之間的最短路徑。在一個(gè)實(shí)施例中，所需貨物的存取位置在巷道中，縱向巷道和橫向巷道形成節(jié)點(diǎn)。
6例如，如圖6所示，巷道是存取貨物的供揀選作業(yè)人員行走的通道，假定只有縱向和橫向兩 種直線巷道。節(jié)點(diǎn)是縱向巷道和橫向巷道的交叉點(diǎn)。貨位是存儲貨物的單元，必須位于巷 道的特定位置才能存取這個(gè)貨位中的貨物，有的貨位存取位置在它的左邊巷道，有的貨位 存取時(shí)必須走到它右側(cè)巷道上，有的貨位存取位置在其緊鄰的上邊的巷道，有的存取位置 在其緊鄰的下邊的巷道。在一個(gè)實(shí)施例中，為了生成并存儲這些元素的信息，把倉庫平面分成若干行和列， 行列交叉位置為一倉庫單元格，這個(gè)倉庫單元格可以是一個(gè)巷道單元也可以是貨位單元， 因此，可以設(shè)計(jì)“倉庫單元格”這樣一種數(shù)據(jù)結(jié)構(gòu)來記錄每個(gè)倉庫單元格的信息；可以采用 矩陣的形式，矩陣的第m行第η列的元素值為1，表示倉庫的第m行第η列的單元格為一貨 位，并且取貨位置在上方巷道；值為2表示為貨位，取貨位置在下方巷道；值為3表示為貨 位，取貨位置在左邊巷道；值為4表示為貨位，取貨位置在右邊巷道；值為5表示此單元格 為一巷道單元；值為6表示為一障礙物單元�！皞}庫單元格”矩陣記錄下了每個(gè)倉庫單元的 信息，由此矩陣可以計(jì)算出所有的貨位、巷道和節(jié)點(diǎn)。在一個(gè)實(shí)施例中，還可以設(shè)計(jì)“巷道”這種數(shù)據(jù)結(jié)構(gòu)，該數(shù)據(jù)結(jié)構(gòu)也可為一矩陣。例 如，矩陣的一行表示一個(gè)巷道，矩陣共有四列。第一列表示巷道類型，為1，表示為橫向巷道， 為0表示縱向巷道。第二列表示該巷道所在的行號或列號，如果是橫向巷道，該列存儲該巷 道在“倉庫單元格”矩陣中的行號；如果是縱向巷道，該列存儲該巷道在“倉庫單元格”矩陣 中的列號。第三列表示巷道的起始位置，橫向巷道的起始位置是指該巷道最左邊單元在“倉 庫單元格”矩陣中的列號，縱向巷道的起始位置是指該巷道最上邊單元在“倉庫單元格”矩 陣中的行號。第四列表示巷道的結(jié)束位置，橫向巷道的結(jié)束位置是指該巷道最右邊單元在 “倉庫單元格”矩陣中的列號，縱向巷道的結(jié)束位置是指該巷道最下邊單元在“倉庫單元格” 矩陣中的行號。在一個(gè)實(shí)施例中，可從“倉庫單元格”矩陣的第一行第一列開始逐行逐列查找值為 5的元素，即巷道單元，找到一巷道單元后，記錄下其行號和列號，假設(shè)其行號為R，列號為 C0在一個(gè)實(shí)施例中，還可把巷道單元所在的橫向巷道找到并保存到“巷道”矩陣中。
具體實(shí)施方式
可為遍歷“巷道”矩陣，查找行號為R的橫向巷道，如果C介于該巷道的起始 列號與結(jié)束列號之間，說明該巷道單元位于這個(gè)橫向巷道上，并且其所在的橫向巷道已經(jīng) 找到并保存在了 “巷道”矩陣中。否則，繼續(xù)找下一個(gè)行號為R的橫向巷道，判斷該巷道單 元是否位于這個(gè)橫向巷道上，如果遍歷完“巷道”矩陣后，不存在相應(yīng)的橫向巷道，則說明該 巷道單元所在的橫向巷道還沒有記錄在“巷道”矩陣中。這時(shí)，從“倉庫單元格”矩陣的第R 行第C列開始向右遍歷，查找值為5的元素。如果第R行，C+1列、C+2列、…、C+n列的元 素值為5，第C+η+Ι列元素值不為5，則找到了一條橫向巷道，該巷道所在行號為R，起始位置 為C，結(jié)束位置為C+n，把該巷道的一行信息插入“巷道”矩陣中。同理，可以把該巷道單元 所在的縱向巷道找到并保存到“巷道”矩陣中。在一個(gè)實(shí)施例中，可繼續(xù)查找下一個(gè)巷道單元所在的巷道，直到遍歷完所有的巷 道單元。一個(gè)巷道單元至少位于一條巷道上。至此，“巷道”矩陣中記錄了所有的巷道信息， 然后根據(jù)“巷道”矩陣，可以找出所有的節(jié)點(diǎn)，節(jié)點(diǎn)是縱向巷道和橫向巷道的交叉點(diǎn)。定義 一個(gè)“節(jié)點(diǎn)”矩陣記錄下所有節(jié)點(diǎn)的行號、列號、該節(jié)點(diǎn)所在橫向巷道的編號、該節(jié)點(diǎn)所在縱向巷道的編號。一個(gè)巷道上的兩個(gè)相鄰的節(jié)點(diǎn)為鄰接節(jié)點(diǎn)。步驟502，存儲貨物的貨位、大小及重量的信息，以及所述巷道和節(jié)點(diǎn)的信息；存 儲倉庫中各節(jié)點(diǎn)之間的最短路徑。在一個(gè)實(shí)施例中，可先計(jì)算出所有鄰接節(jié)點(diǎn)間的最短路徑和距離。鄰接節(jié)點(diǎn)指的 是同一個(gè)巷道上的兩個(gè)相鄰的節(jié)點(diǎn)。對于任意兩個(gè)互為鄰接的節(jié)點(diǎn)，如果它們位于一條縱 向巷道上，則其行號之差即為其最短距離，如果它們位于同一條橫向巷道上，則其列號之差 即為其最短距離。它們之間的最短路徑為沿其所在巷道的一條連接這兩個(gè)節(jié)點(diǎn)的直線段。在一個(gè)實(shí)施例中，可把任意兩個(gè)鄰接節(jié)點(diǎn)的最短距離保存到“節(jié)點(diǎn)距離，，矩陣中， 該矩陣的行列編號表示節(jié)點(diǎn)編號，元素的值為兩個(gè)節(jié)點(diǎn)之間的最短距離。然后由弗洛伊德 Floyd算法計(jì)算出所有節(jié)點(diǎn)間的最短距離及最短路徑。弗洛伊德算法為現(xiàn)有技術(shù)，可參考 《運(yùn)籌學(xué)教程》(清華大學(xué)出版社，1998. 6)，此處不再贅述。在一個(gè)實(shí)施例中，由于節(jié)點(diǎn)的數(shù)量較少，因此可以把節(jié)點(diǎn)之間的最短距離和最短 路徑計(jì)算完畢后，存儲到磁盤上。步驟503，在進(jìn)行訂單揀選時(shí)，從預(yù)存的數(shù)據(jù)中查找訂單的所需貨物的貨位、大小
及重量。步驟504，根據(jù)所需貨物的數(shù)量、以及查找到的貨物的大小及重量計(jì)算所需貨物 的需求量；并利用預(yù)先存儲的各節(jié)點(diǎn)之間的最短路徑計(jì)算任意兩個(gè)所需貨物之間的最短路徑。在一個(gè)實(shí)施例中，若兩個(gè)所需貨物的存取位置位于同一巷道中，則兩個(gè)存取位置 之間的最短路徑和距離為沿同一巷道的路徑和距離。例如，設(shè)這兩個(gè)存取位置的行列號分 別為(xl，yl)、(x2, y2)，由于其位于同一個(gè)巷道上，因此有xl = χ2或者yl = y2，其最短
距離為+ (少i-P)2，最短路徑即是沿該巷道從一個(gè)存取位置到另一存取位置的
一條直線段。若兩個(gè)存取位置位于不同巷道中，則可首先分別確定存取位置的所在巷道距離該 存取位置最近的節(jié)點(diǎn)；根據(jù)預(yù)存的任意兩個(gè)節(jié)點(diǎn)之間的最短路徑和距離，確定最近的節(jié)點(diǎn) 之間的最短路徑和距離；根據(jù)最近的節(jié)點(diǎn)之間的最短路徑和距離、以及兩個(gè)存取位置到最 近的節(jié)點(diǎn)之間的距離確定兩個(gè)存取位置之間的最短路徑和距離。例如，假設(shè)這兩個(gè)存取位置分別為巷道單元A和巷道單元B。A1、A2為A所在巷道 上距離A最近的兩個(gè)節(jié)點(diǎn)，Bi、B2為B所在巷道上距離B最近的兩個(gè)節(jié)點(diǎn)。A與B之間的 路徑必須經(jīng)由其各自的臨近節(jié)點(diǎn)，因此，計(jì)算A、B之間的最短距離就轉(zhuǎn)化為求A-A1-B1-B、 A-A2-B1-B、A-A1-B2-B、A-A2-B2-B這四條路徑中的最短路徑。任意兩個(gè)節(jié)點(diǎn)之間的最短距 離在步驟502中已經(jīng)求得，而A與A1、A2之間距離很容易求得，因?yàn)樗鼈兾挥谕恢本�巷道 上。B與B1、B2之間距離也很容易求得。因此任意兩個(gè)貨位之間的最短路徑和距離可以求 得。步驟505，根據(jù)揀選設(shè)備的容量、任意兩個(gè)所需貨物之間的最短路徑、以及訂單中 所需貨物的需求量求解最佳揀選路徑，以使揀選設(shè)備根據(jù)最佳揀選路徑進(jìn)行訂單揀選。在一個(gè)實(shí)例中，求解最佳揀選路徑可在遺傳算法(Genetic Algorithm, GA)的基礎(chǔ) 上進(jìn)行求解。遺傳算法是Holland教授最早提出的，是求解復(fù)雜組合優(yōu)化問題的有效方法， 典型的遺傳算法主要包括選擇、交叉、變異三個(gè)基本的遺傳算子，其中交叉操作是遺傳算法的主要搜索手段，是影響算法收斂性及搜索效率的關(guān)鍵因素，常用的交叉操作有單點(diǎn)交叉 和雙點(diǎn)交叉，雙點(diǎn)交叉能更有效的離散雜交子代群體，更有利于尋找到最優(yōu)解�？蓞⒖棘F(xiàn)有 技術(shù)，此處不再贅述。在一個(gè)實(shí)施例中，可采用雙點(diǎn)交叉的交叉運(yùn)算。在染色體適應(yīng)度值的計(jì)算以及重 插入的操作中，可使用英國設(shè)菲爾德(Sheffield)大學(xué)的MATLAB遺傳算法工具箱中的有 關(guān)函數(shù)。具體函數(shù)可參考《MATLAB遺傳算法工具箱及應(yīng)用》(西安電子科技大學(xué)出版社， 2005. 4)，此處不再贅述。在一個(gè)實(shí)施例中，步驟505可具體包括如下步驟首先，根據(jù)揀選設(shè)備的容量、訂單中需求點(diǎn)以及所需貨物的需求量確定訂單的最 大揀選次數(shù)，以獲得K-I個(gè)虛擬需求點(diǎn)；其中，K為訂單的最大揀選次數(shù)。例如，假設(shè)揀選設(shè)備容量為Q，一個(gè)訂單所涉及的需求點(diǎn)個(gè)數(shù)為n，每個(gè)需求點(diǎn) 的需求量不大于Q，總的需求量為P，則使總揀選路徑最短的揀選作業(yè)次數(shù)K滿足條件
權(quán)利要求
一種訂單揀選方法，應(yīng)用于需要在多個(gè)巷道中水平移動的訂單揀選，其特征在于，所述方法包括根據(jù)倉庫貨架的擺放情況，生成倉庫平面布置圖；計(jì)算并存儲巷道和節(jié)點(diǎn)的信息；計(jì)算并存儲倉庫中各節(jié)點(diǎn)之間的最短路徑；存儲貨物的貨位信息、貨物的大小及重量信息；在進(jìn)行訂單揀選時(shí)，從預(yù)存的數(shù)據(jù)中查找所述訂單中所需貨物的貨位、大小及重量；根據(jù)所述訂單中所需貨物的數(shù)量、以及查找到的貨物的大小及重量計(jì)算所需貨物的需求量；并利用預(yù)先存儲的各節(jié)點(diǎn)之間的最短路徑計(jì)算任意兩個(gè)所需貨物之間的最短路徑；根據(jù)揀選設(shè)備的容量、所述任意兩個(gè)所需貨物之間的最短路徑以及所述訂單中所需貨物的需求量，通過遺傳算法和LK算法求解最佳揀選路徑，以使所述揀選設(shè)備根據(jù)所述最佳揀選路徑進(jìn)行訂單揀選。
2.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述利用預(yù)先存儲的各節(jié)點(diǎn)之間的最短 路徑計(jì)算任意兩個(gè)所需貨物之間的最短路徑，具體包括若所述兩個(gè)所需貨物的存取位置位于同一巷道中，則所述兩個(gè)所需貨物之間的最短路 徑為沿所述同一巷道的路徑；若所述兩個(gè)所需貨物的存取位置位于不同巷道中，則分別確定這兩個(gè)巷道上距離所述 存取位置最近的兩對節(jié)點(diǎn)；從預(yù)先存儲的各節(jié)點(diǎn)之間的最短路徑中獲取這兩對節(jié)點(diǎn)之間的 最短路徑；再根據(jù)所述存取位置到其最近的節(jié)點(diǎn)之間的距離確定所述兩個(gè)所需貨物之間的 最短路徑。
3.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述根據(jù)揀選設(shè)備的容量、所述任意兩個(gè) 所需貨物之間的最短路徑以及所述訂單中所需貨物的需求量，通過遺傳算法和LK算法求 解最佳揀選路徑，具體包括根據(jù)所述揀選設(shè)備的容量、所述訂單中需求點(diǎn)以及所需貨物的需求量確定所述訂單的 最大揀選次數(shù)，以獲得K-I個(gè)虛擬需求點(diǎn)；其中，K為所述訂單的最大揀選次數(shù)；根據(jù)所述虛擬需求點(diǎn)以及所需貨物的貨位隨機(jī)產(chǎn)生多個(gè)初始的染色體，每個(gè)初始的染 色體包括(n+K-1)個(gè)需求點(diǎn)；其中，η為所述訂單中需求點(diǎn)的數(shù)量；利用所述任意兩個(gè)所需貨物之間的最短路徑，通過遺傳算法和LK算法對所述多個(gè)初 始的染色體進(jìn)行多次迭代優(yōu)化，并根據(jù)優(yōu)化后的多個(gè)染色體確定所述最佳揀選路徑。
4.根據(jù)權(quán)利要求3所述的方法，其特征在于，在通過遺傳算法和LK算法對所述多個(gè)初 始的染色體進(jìn)行多次迭代優(yōu)化中，一次迭代過程包括通過遺傳算法對多個(gè)染色體進(jìn)行選擇、交叉、變異、重插入操作，獲得下一代的染色體；通過LK算法對下一代的最優(yōu)染色體進(jìn)行優(yōu)化。
5.根據(jù)權(quán)利要求4所述的方法，其特征在于，所述對多個(gè)染色體進(jìn)行選擇，具體包括 計(jì)算所述多個(gè)染色體中每一個(gè)染色體的適應(yīng)度；根據(jù)所述適應(yīng)度獲得所述染色體被選擇的概率；根據(jù)所述被選擇的概率從所述多個(gè)染色體中選擇出下一代的染色體。
6.根據(jù)權(quán)利要求4所述的方法，其特征在于，所述對多個(gè)染色體進(jìn)行交叉操作，具體包括根據(jù)預(yù)設(shè)的交叉概率，選擇待交叉的染色體；為任意兩個(gè)待交叉的染色體選擇交配區(qū)域； 交換所述兩個(gè)選擇交配區(qū)域后的染色體的交配區(qū)域；為每個(gè)交換后的染色體去掉重復(fù)的基因；具體包括查找到所述重復(fù)基因?qū)?yīng)的交換 前所述染色體中的等位基因；用所述等位基因替換交換后的染色體中的所述重復(fù)基因。
7.根據(jù)權(quán)利要求4所述的方法，其特征在于，所述對多個(gè)染色體進(jìn)行變異操作，具體包括 根據(jù)預(yù)設(shè)的變異概率，選擇待變異的染色體；從所述待變異的染色體中隨機(jī)選擇待變異的基因片段；對所述待變異的基因片段進(jìn)行翻轉(zhuǎn)操作，以得到變異后的染色體。
8.根據(jù)權(quán)利要求4所述的方法，其特征在于，所述對多個(gè)染色體進(jìn)行重插入操作，具體 包括將所述多個(gè)染色體中最優(yōu)的若干染色體直接加入到下一代的染色體中。
9.一種訂單揀選系統(tǒng)，應(yīng)用于需要在多個(gè)巷道中水平移動的訂單揀選，其特征在于，所 述系統(tǒng)包括服務(wù)器、無線局域網(wǎng)絡(luò)與移動終端；其中，所述服務(wù)器包括制圖單元，根據(jù)倉庫貨架的擺放情況，生成倉庫平面布置圖；計(jì)算出巷道和節(jié)點(diǎn)的信 息；計(jì)算倉庫中各節(jié)點(diǎn)之間的最短路徑；存儲單元，存儲貨物的貨位、大小及重量的信息，以及所述巷道和節(jié)點(diǎn)的信息；存儲倉 庫中各節(jié)點(diǎn)之間的最短路徑；計(jì)算單元，用于從預(yù)存的數(shù)據(jù)中查找所述訂單中所需貨物的貨位、大小及重量；根據(jù)所 述訂單中所需貨物的數(shù)量、以及查找到的貨物的大小及重量計(jì)算所需貨物的需求量；并利 用預(yù)先存儲的各節(jié)點(diǎn)之間的最短路徑計(jì)算任意兩個(gè)所需貨物之間的最短路徑；求解單元，用于根據(jù)揀選設(shè)備的容量、所述任意兩個(gè)所需貨物之間的最短路徑以及所 述訂單中所需貨物的需求量，通過遺傳算法和LK算法求解最佳揀選路徑，以使所述揀選設(shè) 備根據(jù)所述最佳揀選路徑進(jìn)行訂單揀選。
10.根據(jù)權(quán)利要求9所述的系統(tǒng)，其特征在于，所述求解單元具體包括次數(shù)確定單元，用于根據(jù)所述揀選設(shè)備的容量、所述訂單中需求點(diǎn)以及所需貨物的需 求量確定所述訂單的最大揀選次數(shù)，以獲得K-I個(gè)虛擬需求點(diǎn)；其中，K為所述訂單的最大 揀選次數(shù)；路徑產(chǎn)生單元，用于根據(jù)所述虛擬需求點(diǎn)以及所需貨物的貨位隨機(jī)產(chǎn)生多個(gè)初始的染 色體，每個(gè)初始的染色體包括(η+κ-1)個(gè)需求點(diǎn)；其中，η為所述訂單中需求點(diǎn)的數(shù)量；路徑獲取單元，用于利用所述任意兩個(gè)所需貨物之間的最短路徑，通過遺傳算法和LK 算法對所述多個(gè)初始的染色體進(jìn)行多次迭代優(yōu)化，并根據(jù)優(yōu)化后的多個(gè)染色體確定所述最 佳揀選路徑。
全文摘要
本發(fā)明實(shí)施例提供一種訂單揀選方法及系統(tǒng)，該方法包括根據(jù)倉庫貨架的擺放情況，生成倉庫平面布置圖，然后計(jì)算倉庫中各節(jié)點(diǎn)之間的最短路徑；從預(yù)存的數(shù)據(jù)中查找訂單所需貨物的貨位、大小及重量；利用節(jié)點(diǎn)之間最短路徑計(jì)算任意兩個(gè)所需貨物之間的最短路徑和距離；根據(jù)揀選設(shè)備的容量、訂單中所需貨物的需求量求解最佳揀選路徑，以使揀選設(shè)備根據(jù)最佳揀選路徑進(jìn)行訂單揀選。通過本發(fā)明實(shí)施例，可高效地計(jì)算出揀選路徑，降低作業(yè)成本，提高作業(yè)效率；解決在貨架擺放不一、貨架高度相對較小、對同一貨位不同層的貨架上的貨物存取時(shí)所用代價(jià)差異不大、揀選作業(yè)需要優(yōu)化的主要是揀選作業(yè)人員水平移動距離的情況下訂單的揀選問題。
文檔編號G06Q50/00GK101968860SQ201010501229
公開日2011年2月9日 申請日期2010年10月9日 優(yōu)先權(quán)日2010年10月9日
發(fā)明者劉軍, 岳溥庥, 張海軍, 朱杰 申請人:北京物資學(xué)院

  本文關(guān)鍵詞：自動化立體倉庫揀選作業(yè)路徑優(yōu)化問題研究，由筆耕文化傳播整理發(fā)布。