倉內(nèi)揀貨路程優(yōu)化問題研究

謝曉敏，李 琳

（川北幼兒師范高等?？茖W(xué)校 初等教育系，四川 廣元 628017）

1 問題的提出

隨著物流業(yè)的迅速發(fā)展，越來越多的企業(yè)構(gòu)建屬于自己的倉儲(chǔ)體系。在整個(gè)倉儲(chǔ)體系中，揀貨作業(yè)是其核心，且涉及的計(jì)算復(fù)雜。因此，揀貨作業(yè)的優(yōu)化設(shè)計(jì)與綜合控制至關(guān)重要。某電商公司的雙區(qū)型[1]倉庫中有13個(gè)復(fù)核臺(tái)，4排（行）貨架，每排25組貨架，每組2個(gè)貨架，共200個(gè)貨架，每個(gè)貨架包含15個(gè)貨格。貨架與復(fù)核臺(tái)分布如圖1所示。相鄰貨架間的垂直過道寬1 500 mm，水平過道寬2 000 mm，貨格長寬均為800 mm，復(fù)核臺(tái)長寬均為1 000 mm。13個(gè)復(fù)核臺(tái)用F01～F13標(biāo)記，其中：F01～F08在最下面，處于同一行，從左至右排列，橫坐標(biāo)以4 500 mm的量增加；F09～F13在最左面，處于同一列，從下至上排列，縱坐標(biāo)以4 500 mm的量增加。每個(gè)貨架中的15個(gè)貨格從下至上縱向排列。圖2為1號(hào)、2號(hào)貨架上貨格的分布情況，其中字母S代表“貨格”，數(shù)字編號(hào)的前三位表示貨架號(hào)，后兩位表示貨格號(hào)。3000個(gè)貨格和13個(gè)復(fù)核臺(tái)的左下角坐標(biāo)都已給定。貨架和復(fù)核臺(tái)為障礙物，不可通行，其余位置均可通行，不用考慮揀貨車尺寸、貨架和復(fù)核臺(tái)高度。當(dāng)揀貨員在倉庫中揀貨時(shí)，要在貨格與復(fù)核臺(tái)之間行走，通常需繞過障礙物，不能直接采用坐標(biāo)計(jì)算歐幾里得路程[2]。要求設(shè)計(jì)一種方法，計(jì)算3 000個(gè)貨格和13個(gè)復(fù)核臺(tái)（共3 013個(gè)元素）之間的最短路程，并滿足如下要求：

圖1 貨格與復(fù)核臺(tái)的分布

圖2 貨架上貨格的分布

（Ⅰ）當(dāng)繞障礙物折線行走時(shí)橫向和縱向偏移均取d=750 mm；

（Ⅱ）奇數(shù)號(hào)貨架上的貨格從左邊中點(diǎn)出發(fā)，偶數(shù)號(hào)貨架上的貨格從右邊中點(diǎn)出發(fā)；

（Ⅲ）復(fù)核臺(tái)F01～F08的出發(fā)點(diǎn)是上邊中間位置，復(fù)核臺(tái)F09～F13的出發(fā)點(diǎn)是右邊中間位置。

2 標(biāo)識(shí)點(diǎn)及其坐標(biāo)變換

編號(hào)為n的貨格標(biāo)記為S n，五位數(shù)n的前三位表示其所在的貨架號(hào)，記作i（n），也可用算式表示為

如圖3所示，從貨格S n的邊線中點(diǎn)出發(fā)，先要偏移距離d=750 mm，偏移后的點(diǎn)Bn稱為S n的標(biāo)識(shí)點(diǎn)，An為給定原始坐標(biāo)的點(diǎn)。

圖3 貨格的標(biāo)識(shí)點(diǎn)

將所有貨格的原始縱坐標(biāo)都加400 mm；當(dāng)i（n）為奇數(shù)時(shí)，將貨格S n的原始橫坐標(biāo)減d；當(dāng)i（n）為偶數(shù)時(shí)，將貨格S n的原始橫坐標(biāo)加（d+800）mm。經(jīng)坐標(biāo)變換得到貨格標(biāo)識(shí)點(diǎn)Bn的坐標(biāo)，記為（xn，yn）。

如圖4所示，編號(hào)為j的復(fù)核臺(tái)標(biāo)記為F j（j=01~13），字母F代表“復(fù)核臺(tái)”。F j也有標(biāo)識(shí)點(diǎn)，記做Qj，Pj為給定原始坐標(biāo)的點(diǎn)。

圖4 復(fù)核臺(tái)的標(biāo)識(shí)點(diǎn)

當(dāng)j=01~08時(shí)，將F j的原始縱坐標(biāo)加（d+1 000）mm，原始橫坐標(biāo)加500 mm；當(dāng)j=09~13時(shí)，將F j的原始縱坐標(biāo)加500 mm，原始橫坐標(biāo)加（d+1 000）mm。經(jīng)坐標(biāo)變換得到復(fù)核臺(tái)標(biāo)識(shí)點(diǎn)Qj的坐標(biāo)，記為（Xj，Yj）。

引入標(biāo)識(shí)點(diǎn)及其坐標(biāo)，可消弭奇數(shù)號(hào)貨架上貨格與偶數(shù)號(hào)貨架上貨格偏移方式的差異，同時(shí)也消除了橫排復(fù)核臺(tái)與縱列復(fù)核臺(tái)偏移方式的差異，大大降低了計(jì)算的復(fù)雜程度，使得所建模型簡潔明了。

因?yàn)橐@過障礙物，有時(shí)需在貨架下方或上方的水平過道行走，所以還要引入貨格S n所在貨架的下沿縱坐標(biāo)gn和上沿縱坐標(biāo)hn。gn等于該貨架第1個(gè)貨格（最下方貨格）的原始縱坐標(biāo)，而hn=gn+2c，2c=15×800＝12 000 mm是貨架的縱向長度，gn和hn都是已知數(shù)據(jù)，共只有4對(duì)不同的數(shù)值。

3 問題的求解

3013個(gè)元素之間的路程存儲(chǔ)在路程矩陣中，該矩陣是一個(gè)方陣，對(duì)角線上元素都為0，對(duì)稱位置的元素相等，總共有9 078169個(gè)元素。由于數(shù)量龐大，需分成貨格與貨格、貨格與復(fù)核臺(tái)、復(fù)核臺(tái)與復(fù)核臺(tái)三個(gè)部分來求解[3]。

3.1 貨格與貨格之間的路程計(jì)算

貨格S m與貨格S n（m≠n）之間的路程用dmn表示。當(dāng)S m與S n所處貨架不同行時(shí)，其標(biāo)識(shí)點(diǎn)Bm和Bn之間有水平過道，無須繞行，如圖5所示。計(jì)算dmn只需先算得Bm和Bn之間的路程，再加上圖中的虛線段偏移即可：

圖5 不同行貨架中貨格之間的路徑

若S m與S n所處貨架雖在同行，但它們的標(biāo)識(shí)點(diǎn)處于同一垂直過道，則無須借助水平過道行走，dmn仍可按式（1）計(jì)算，例如S00202和S00913、S01312和S01303、S01605和S01614等等。

若S m與S n所處貨架在同行，且標(biāo)識(shí)點(diǎn)Bm和Bn未處于同一垂直過道，則行走路線需經(jīng)貨架下方或上方繞行，如圖6所示。路程計(jì)算取下行路程d′mn和d″mn上行路程中的較小者，即：

圖6 同行貨架中不共過道貨格之間的路徑

其中：d′mn=xm-xn+（ym-gm）+（yn-gn）+4d，d″mn=xm-xn+（hm-ym）+（hn-yn）+4d，并且對(duì)于同行貨架的上、下沿，有g(shù)m=gn，hm=hn。

3.2 貨格與復(fù)核臺(tái)之間的路程計(jì)算

貨格S n與復(fù)核臺(tái)F j間的路程用dnj表示。

當(dāng)j=01~08時(shí)，復(fù)核臺(tái)F j處于所有貨格的下方，標(biāo)識(shí)點(diǎn)Bn和Qj之間必有水平過道，無須繞行，路程計(jì)算可仿照式（1），有：

3.3 復(fù)核臺(tái)與復(fù)核臺(tái)之間的路程計(jì)算

復(fù)核臺(tái)F j與復(fù)核臺(tái)F k（j≠k）之間的路程用djk表示。由于標(biāo)識(shí)點(diǎn)Qj和Qk之間總有水平過道或者處于同一垂直過道，所以路程計(jì)算可仿照式（1），有：

4 模型的評(píng)價(jià)與推廣

模型通過針對(duì)性的坐標(biāo)變換，引入標(biāo)識(shí)點(diǎn)并進(jìn)行分類歸納，大大降低了復(fù)雜距離的計(jì)算難度。

本文的坐標(biāo)變換方法和路程計(jì)算方法在揀貨模型[4]和路徑問題中都可以應(yīng)用，能有效降低揀貨路徑分析的復(fù)雜程度。