繆朝煒，蘇瑞澤，張 杰

?

越庫配送車輛調(diào)度問題的自適應(yīng)遺傳算法研究

繆朝煒1，蘇瑞澤1，張 杰2

（1. 廈門大學(xué)管理學(xué)院，福建廈門361005；2. 廣東財(cái)經(jīng)大學(xué)工商管理學(xué)院，廣東廣州510320）

本文研究的是帶有車輛容量限制以及時(shí)間窗口約束的越庫配送車輛調(diào)度問題，該問題旨在通過車輛與倉門的合理分配來實(shí)現(xiàn)越庫內(nèi)部貨物的最優(yōu)調(diào)度從而達(dá)到高效的運(yùn)作目標(biāo)。由于該問題是強(qiáng)NP難的問題，本文基于遺傳算法的思想，設(shè)計(jì)了單點(diǎn)交叉算子和兩點(diǎn)交叉算子，并采用“交叉行為自適應(yīng)選擇機(jī)制”設(shè)計(jì)了一種自適應(yīng)遺傳算法來進(jìn)行求解。在數(shù)值實(shí)驗(yàn)中，本文將該自適應(yīng)遺傳算法與分別采用單種交叉算子的遺傳算法進(jìn)行算法性能的比較，通過大量不同規(guī)模的數(shù)值算例的結(jié)果對(duì)比發(fā)現(xiàn)在這三種算法中，采用自適應(yīng)機(jī)制的遺傳算法在最終解的質(zhì)量上總體表現(xiàn)最好，表明該算法對(duì)于求解此類問題具有良好的性能，同時(shí)也表明該自適應(yīng)機(jī)制對(duì)于提升算法性能上具有顯著的促進(jìn)作用。

遺傳算法；自適應(yīng)機(jī)制；越庫；車輛調(diào)度

0 引言

在今天全球競(jìng)爭(zhēng)日趨激烈的環(huán)境下，如何既能降低物流成本又能夠保證貨物的及時(shí)配送，這是許多企業(yè)都非常關(guān)注的問題。越庫技術(shù)集庫存管理策略與配送策略為一體，被各類企業(yè)應(yīng)用于優(yōu)化物流配送網(wǎng)絡(luò)以達(dá)到降低庫存水平，提高庫存周轉(zhuǎn)率，提升顧客服務(wù)水平的目的，如沃爾瑪、Home Depot, Costco, Canadian Tire以及FedEx等企業(yè)都成功的實(shí)施了越庫技術(shù)?，F(xiàn)如今雖然越庫的使用較為廣泛，但對(duì)其還沒有一個(gè)統(tǒng)一的定義。Gue[1]把越庫當(dāng)成是一種零擔(dān)運(yùn)輸，只具備接發(fā)貨物功能的轉(zhuǎn)運(yùn)中心。Napolitano[2]認(rèn)為越庫是一種幾乎跨越倉儲(chǔ)生命周期的運(yùn)作策略，它通過設(shè)備將收到的貨物和其他將運(yùn)至同一地點(diǎn)的貨物整合一起，盡可能快的運(yùn)送給客戶，不進(jìn)行長(zhǎng)期存儲(chǔ)。對(duì)于越庫的分類，之前文獻(xiàn)已經(jīng)提出了很多方法。如Yan和Tang[3,4]分別研究了前配送越庫與后配送越庫以及它們分別的適用環(huán)境。Shaffe[5]和Napolitano[2]根據(jù)產(chǎn)品所處的階段，將越庫分為制造型越庫，分銷型越庫，零售型越庫及機(jī)會(huì)型越庫。另外，對(duì)于越庫作業(yè)問題的研究范圍較廣，從戰(zhàn)略層面到單個(gè)越庫的運(yùn)作層面，都有相關(guān)的研究成果，如：(1)越庫的選址：Axsater[6,7]研究設(shè)施選址以及相關(guān)的越庫策略（比如如何通過處理貨物達(dá)到快速轉(zhuǎn)運(yùn)的目的）；(2)多越庫的配送網(wǎng)絡(luò)：Lim等人[8]研究了供應(yīng)商和顧客帶有時(shí)間窗口約束的越庫運(yùn)輸網(wǎng)絡(luò)模型；Miao等人[9]研究了帶有時(shí)間窗口的多越庫系統(tǒng)下固定路徑車輛運(yùn)輸調(diào)度問題；(3)越庫的布局：Bartholdi和Gue[10,11]研究了越庫系統(tǒng)的最佳布局，并研究了特定布局下如何減少勞動(dòng)力成本；(4)越庫內(nèi)部資源分配問題：Yu和Egbelu[12]研究了一個(gè)無庫存容量限制的越庫系統(tǒng)中如何調(diào)度進(jìn)出車輛。Miao等人[13]考慮了類似于航空港中登機(jī)口分配的越庫倉門分配問題，考慮了每一到達(dá)越庫的車輛都被賦予一個(gè)服務(wù)的時(shí)間窗口，并給出了該問題的優(yōu)化算法；(5)越庫內(nèi)部貨物調(diào)度作業(yè)：Chen和Lee[14]提出一類需要找到一個(gè)最佳出入口車輛序列以使得總運(yùn)作時(shí)間最少的越庫調(diào)度模型，他們把該問題轉(zhuǎn)化成經(jīng)典的兩臺(tái)機(jī)器兩個(gè)任務(wù)集的最小化最大完工時(shí)間問題，并給出多項(xiàng)式近似算法對(duì)該模型進(jìn)行求解。由于目前不管是企業(yè)界還是學(xué)術(shù)界對(duì)越庫方面的應(yīng)用和研究都十分重視，越庫方面相關(guān)的研究成果豐碩，因此在本文中不再一一贅述，有關(guān)越庫方面的研究成果可以參閱Boysen和Fliedner[15]以及Jan 等人[16]的兩篇關(guān)于越庫研究的非常系統(tǒng)的文獻(xiàn)綜述。

本文研究了帶有車輛容量限制以及時(shí)間窗口約束的越庫配送車輛調(diào)度問題，該問題旨在通過車輛與倉門的合理分配來實(shí)現(xiàn)越庫內(nèi)部貨物的最優(yōu)調(diào)度從而達(dá)到高效的運(yùn)作目標(biāo)。與已有的文獻(xiàn)不同的是，本文研究的問題不僅考慮了越庫的容量限制，而且還考慮了車輛裝載容量限制，而以往的研究往往只考慮前者甚至兩者都不考慮，大大降低了研究該問題的實(shí)踐意義，因?yàn)樵趯?shí)際越庫運(yùn)作中，車輛容量是非常重要的限制條件，對(duì)越庫內(nèi)部的優(yōu)化調(diào)度以及運(yùn)作績(jī)效有著直接影響。對(duì)于此類越庫運(yùn)作問題，由于大部分都屬于強(qiáng)NP難題，因此研究的重點(diǎn)在于如何設(shè)計(jì)高效的啟發(fā)式算法來求解，如Miao 等人[13]針對(duì)考慮越庫內(nèi)部作業(yè)時(shí)間的車輛庫門分配問題分別設(shè)計(jì)了GA和TS兩種啟發(fā)式算法。Vahdani和Zandieh[17]針對(duì)越庫車輛調(diào)度問題的不同啟發(fā)式算法的效果進(jìn)行對(duì)比，并且利用數(shù)值實(shí)驗(yàn)證明每種啟發(fā)式算法的穩(wěn)健性。此外，陳峰和宋凱雷[18]、俞亮和陳峰[19]以及強(qiáng)瑞等人[20]也分別針對(duì)幾種不同的越庫物流以及車輛調(diào)度問題設(shè)計(jì)了高效的啟發(fā)式算法進(jìn)行求解。由于本文研究的越庫車輛調(diào)度問題同樣屬于強(qiáng)NP難問題，因此基于遺傳算法的思想，文中設(shè)計(jì)了單點(diǎn)交叉算子和兩點(diǎn)交叉算子，并采用“交叉行為自適應(yīng)選擇機(jī)制”設(shè)計(jì)了一種自適應(yīng)遺傳算法來進(jìn)行求解；最后通過大量不同規(guī)模的數(shù)值算例將該自適應(yīng)遺傳算法與分別采用單種交叉算子的遺傳算法進(jìn)行算法性能的比較，以此來分析不同算法的效率以及這種自適應(yīng)機(jī)制的有效性。

1 問題描述與模型

本文研究的越庫的常見結(jié)構(gòu)如圖1所示，該越庫帶有平行的兩排庫門，分別為貨物的入庫門與出庫門，貨物由入庫車輛運(yùn)送到越庫，然后根據(jù)不同客戶的需求，在操作區(qū)將貨物進(jìn)行重新分配，最后由出庫車輛進(jìn)行物流配送，在越庫內(nèi)部操作會(huì)引發(fā)相關(guān)的運(yùn)作費(fèi)用。實(shí)際問題中常會(huì)遇到由于庫門資源以及車輛運(yùn)輸容量的制約，導(dǎo)致有些貨物無法及時(shí)配送，這些貨物將會(huì)短暫存儲(chǔ)在越庫中具有一定容量的臨時(shí)存儲(chǔ)區(qū)，此時(shí)將會(huì)帶來額外的成本，比如倉儲(chǔ)費(fèi)用以及延遲發(fā)貨成本等等，根據(jù)此類問題建模的常用方法，將其統(tǒng)一定義為懲罰成本。此外，實(shí)際操作中常會(huì)給每輛車輛分配特定的時(shí)間窗口，該做法可以有效的提高越庫的利用率，但是也大大增加了實(shí)際工作的復(fù)雜性。本文采用的時(shí)間窗口由車輛的到達(dá)與離開時(shí)間來定義，要求每一輛入庫（出庫）車輛只能在給定的到達(dá)和離開時(shí)間內(nèi)占用一個(gè)入（出）庫門。同時(shí)，文中考慮了越庫內(nèi)轉(zhuǎn)運(yùn)、分揀、包裝所需的越庫內(nèi)部操作總時(shí)間，并假設(shè)這個(gè)時(shí)間與入庫門與出庫門的相對(duì)位置有關(guān)，因?yàn)橄鄬?duì)位置離的越遠(yuǎn)，則時(shí)間消耗越長(zhǎng)，而且越庫內(nèi)部操作時(shí)間約束會(huì)影響內(nèi)部調(diào)度轉(zhuǎn)運(yùn)方案的可行性，例如出庫車輛A?？吭诔鰩扉Ta，要求配送?？吭谌霂扉Tb的入庫車輛B上面的部分貨物，那么出庫車輛A的離開時(shí)間必須晚于入庫車輛B的到達(dá)時(shí)間和從入庫門b到出庫門a的越庫內(nèi)部操作總時(shí)間之和，這樣入庫車輛B才可能將貨物裝配到出庫車輛A上，否則就會(huì)導(dǎo)致貨延遲配送，同樣會(huì)引發(fā)相應(yīng)的懲罰成本。綜上所述，在庫門資源有限、車輛運(yùn)載能力以及時(shí)間窗口限制等諸多實(shí)際限制條件下，研究如何合理的進(jìn)行車輛庫門分配以及貨物調(diào)度，使得包括越庫內(nèi)部貨物調(diào)度引發(fā)的運(yùn)作成本以及由于延遲配送而引發(fā)的懲罰成本在內(nèi)的總成本最小化問題是非常具有實(shí)踐意義的。

圖1 越庫結(jié)構(gòu)

針對(duì)上述問題本文構(gòu)建了0-1整數(shù)規(guī)劃模型，首先介紹模型的參數(shù)符號(hào)如下：

決策變量定義如下：

目標(biāo)是為了使總成本最小化，即運(yùn)作成本與懲罰成本的總和最小。具體線性規(guī)劃模型如下：

其中

(2)

因此目標(biāo)函數(shù)可以被改寫成為下式：

(4)

(6)

(7)

(9)

(10)

(12)

(13)

在上述模型中，約束條件（5）和（6）保證了每輛車至多只能分配一個(gè)庫門；約束條件（7）和（8）表示每個(gè)庫門在每一個(gè)時(shí)間點(diǎn)至多被一輛車占用；約束條件（9）給出了決策變量間內(nèi)在的邏輯關(guān)系；約束條件（10）和（11）分別給出了出庫車輛的運(yùn)載容量限制以及越庫臨時(shí)存儲(chǔ)區(qū)的容量限制條件；約束條件（12）給出了當(dāng)車輛間貨物轉(zhuǎn)運(yùn)可行時(shí)越庫內(nèi)部操作時(shí)間與車輛時(shí)間窗口之間需滿足的條件；約束條件（13）給出了決策變量的取值范圍。

2 自適應(yīng)遺傳算法設(shè)計(jì)

2.1 解結(jié)構(gòu)設(shè)計(jì)

2.2 初始解生成

初始解對(duì)啟發(fā)式算法的求解效果有很大的影響，質(zhì)量高的初始解能夠極大地提升搜索速度，因此在本文中，我們不采用隨機(jī)產(chǎn)生初始解的方法，而是通過啟發(fā)式策略分階段產(chǎn)生初始解。由于入庫車輛的入庫門分配策略與出庫車輛的出庫門分配策略有著緊密的聯(lián)系，因此在生成初始解時(shí)我們制定了以下5條規(guī)則：①先分配入庫車輛的庫門，后分配出庫車輛的庫門；②盡可能使每一輛車都能分配到庫門；③盡可能較早的給所載貨物總的懲罰成本較高的入庫車輛分配庫門；④盡可能降低批量大的貨物的轉(zhuǎn)運(yùn)成本；⑤入庫車輛庫門分配完成后，盡可能先給所載貨物總量較大的出庫車輛分配庫門。在給出具體初始解的生成步驟之前，先介紹相關(guān)參數(shù)如下：

：入庫車輛；

：出庫車輛；

：分配給入庫車輛的入庫門；

：分配給出庫車輛的出庫門；

此外，入庫車輛庫門優(yōu)先選擇概率和出庫車輛庫門優(yōu)先選擇概率分別由（14）和（15）式確定，從式(14)可以看出，入庫車輛所載貨物總的懲罰成本越高，其優(yōu)先選擇庫門的概率越大。從式(15)可以看出，當(dāng)入庫車輛確定時(shí)，越大，相應(yīng)的出庫車輛的優(yōu)先選擇庫門的概率越大。

(15)

通過（14）和（15）式選定入庫車輛和出庫車輛以后，根據(jù)（16）和（17）式給出的概率確定入庫門和出庫門。

(17)

(19)

(20)

圖1 入庫車輛庫門分配流程圖

圖2 出庫車輛庫門分配流程圖

具體的入庫車輛和出庫車輛的庫門分配流程如圖2與圖3所示。當(dāng)庫門分配結(jié)束后，還無法得到該問題的最終可行解，因?yàn)檫€必須制定內(nèi)部貨物的轉(zhuǎn)運(yùn)方案?；谪澙匪惴ǖ乃枷?，采用單位價(jià)值貪婪策略，按的值對(duì)已分配庫門的入庫車輛的貨物進(jìn)行降序排列并依次分配給出庫車輛，從而得到最終的可行解。

2.3 交叉算子

（1）單點(diǎn)交叉（SPCO）

單點(diǎn)交叉是遺傳算法中最基本也是最常用的交叉算子，若個(gè)體基因位之間的聯(lián)系較為緊密，并能提供較好的個(gè)體性狀，那么單點(diǎn)交叉對(duì)個(gè)體模式的破壞較小，但其產(chǎn)生的新個(gè)體與父代的個(gè)體相似性較強(qiáng)，不易于維持種群的多樣性。其步驟就是隨機(jī)選取兩個(gè)染色體作為父代，并隨機(jī)生成一個(gè)交叉點(diǎn)，互換兩個(gè)基因片段，形成兩個(gè)新的個(gè)體[13]。具體如下所示，比如隨機(jī)生成的交叉點(diǎn)是4。

隨機(jī)選取兩個(gè)染色體：

Parent1: X1 X2 X3 X4 X5 X6 X7 X8 X9

Parent2: Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9

生成新的個(gè)體：

Child1: Y1 Y2 Y3 Y4 X5 X6 X7 X8 X9

Child2: X1 X2 X3 X4 Y5 Y6 Y7 Y8 Y9

（2）兩點(diǎn)交叉(DPCO)

兩點(diǎn)交叉與單點(diǎn)交叉相比，在交叉過程中，所交叉的基因片段選擇更大。其步驟是隨機(jī)選取兩個(gè)染色體作為父代，隨機(jī)生成為兩個(gè)交叉點(diǎn)，互換兩個(gè)交叉點(diǎn)之點(diǎn)的基因片段，形成兩個(gè)新的個(gè)體[20]。比如隨機(jī)生成的交叉點(diǎn)是3和7，則

隨機(jī)選取兩個(gè)染色體：

Parent1: X1 X2 X3 X4 X5 X6 X7 X8 X9

Parent2: Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9

生成新的個(gè)體：

Child1: X1 X2 X3 Y4 Y5 Y6 X7 X8 X9

Child2: Y1 Y2 Y3 X4 X5 X6 Y7 Y8 Y9

但由于本文問題的特殊性，即分為入口車輛和出口車輛兩部分，所以對(duì)兩點(diǎn)交叉增加一個(gè)限制條件，即兩個(gè)交叉點(diǎn)必須一個(gè)在入口車輛部分的基因段，而另一個(gè)必須在出口車輛的基因段。

2.4 變異算子

變異算子能為個(gè)體進(jìn)化提供新的基因，使整個(gè)算法搜索能夠探查到之前沒有搜索的區(qū)域，是保持群體多樣性、防止出現(xiàn)“早熟”的重要手段，是提高使算法跳出局部最優(yōu)解的有效方法。

本文采用車輛的庫門互換的變異方法[13, 20]，即對(duì)每個(gè)個(gè)體以給定的變異概率進(jìn)行選取，然后對(duì)選中需要變異的個(gè)體，隨機(jī)選取兩個(gè)入（出）庫門a和b，將分配給庫門a的車輛分配給庫門b，將原本分配給庫門b的車輛分配給庫門a。需要特別注意的是隨機(jī)選取的庫門必須是同一種庫門，即都是入庫門或者都是出庫門，否則無法互換。

舉個(gè)實(shí)例，假如交叉完后產(chǎn)生的新個(gè)體的入庫門分配如下：

Child: 1 3 2 3 4 5 3 4 5

對(duì)其進(jìn)行變異，假設(shè)隨機(jī)選取的兩入庫門為3和4，那么對(duì)其他進(jìn)行變異之后：

New Child: 1 4 2 4 3 5 4 3 5

采用該變異方法是考慮模型的特點(diǎn)，即對(duì)車輛進(jìn)行庫門分配時(shí)，受到車輛時(shí)間窗口的影響，采用庫門互換的變異方法不但達(dá)到了變異的效果，而且可以保證變異后的新個(gè)體仍是可行解。

2.5 自適應(yīng)機(jī)制

遺傳算法中的各種算子的選擇等對(duì)算法本身的效果影響很大，如交叉算子，雖然很多學(xué)者對(duì)單點(diǎn)交叉、多點(diǎn)交叉等算子的性能做了分析，但并不能有效的預(yù)測(cè)各種交叉算子使用的效果，因此Spears[21]認(rèn)為采用自適應(yīng)機(jī)制是最好的選擇。本文采用的自適應(yīng)機(jī)制屬于對(duì)交叉行為的自適應(yīng)選擇，即采用何種交叉算子的選擇。

單點(diǎn)交叉算子能夠較好的保存父代的優(yōu)良模式，但也因此降低了進(jìn)化能力。兩點(diǎn)交叉與單點(diǎn)交叉相比，在交叉過程中，所交叉的基因片段選擇更大，對(duì)父代的基因結(jié)構(gòu)破壞相對(duì)更大，但卻可以提高尋找新優(yōu)良模式的能力。因此可以考慮采用自適應(yīng)機(jī)制，讓算法自動(dòng)選擇交叉算子，盡可能的保留這兩種交叉算子的優(yōu)點(diǎn)。該自適應(yīng)算子設(shè)計(jì)思路是根據(jù)單點(diǎn)交叉及兩點(diǎn)交叉的特點(diǎn)，當(dāng)交叉的父代個(gè)體適應(yīng)度值大時(shí)，采用單點(diǎn)交叉的概率大；當(dāng)交叉的父代個(gè)體適應(yīng)度值小時(shí)采用兩點(diǎn)交叉的概率大。因此本文結(jié)合神經(jīng)網(wǎng)絡(luò)中的神經(jīng)元激活函數(shù)sigmoid函數(shù)[22]，采用一種反饋學(xué)習(xí)策略，如式(21)和(22)所示，其中、分別指每次采用兩點(diǎn)交叉與單點(diǎn)交叉的概率；A取值9.903438；、、分別指群體中適應(yīng)度的最大值、平均值以及當(dāng)前個(gè)體的適應(yīng)度值。對(duì)系數(shù)做多次實(shí)驗(yàn)，發(fā)現(xiàn)取值0.5的效果相對(duì)較好。

(22)

3 數(shù)值實(shí)驗(yàn)

本文通過隨機(jī)生成數(shù)據(jù)的方法對(duì)不同規(guī)模的問題進(jìn)行了大量的數(shù)值實(shí)驗(yàn)，主要目的是通過數(shù)值實(shí)驗(yàn)結(jié)果對(duì)比自適應(yīng)遺傳算法與分別采用單種交叉算子的遺傳算法的性能，分析這三種算法的效率以及該自適應(yīng)機(jī)制的有效性。實(shí)驗(yàn)在MS-Windows XP，Pentium 4 2.93GHz，1G內(nèi)存的環(huán)境下測(cè)試。

3.1 數(shù)據(jù)生成與參數(shù)設(shè)定

數(shù)值實(shí)驗(yàn)中將算例分為三類，分別是小規(guī)模、中規(guī)模和大規(guī)模，算例的規(guī)模由入庫車輛的數(shù)量、入庫門的數(shù)量、出庫車輛的數(shù)量以及出庫門的數(shù)量來區(qū)分。入庫車輛的服務(wù)時(shí)間窗口的開始時(shí)間，結(jié)束時(shí)間。對(duì)于出庫車輛，，。庫門與庫門之間的運(yùn)作時(shí)間是根據(jù)它們之間的相對(duì)距離來設(shè)置的，將正對(duì)的兩個(gè)庫門之間的運(yùn)作時(shí)間設(shè)為2，相鄰的庫門之間運(yùn)作時(shí)間設(shè)為1。運(yùn)作成本，懲罰成本，車輛之間的需要運(yùn)送的貨物量，出口車輛的載重量限制，，越庫臨時(shí)庫存容量限制，其中。遺傳算法的參數(shù)設(shè)定如下：總的迭代次數(shù)104，最優(yōu)解最大的重復(fù)代數(shù)100，種群規(guī)模400，每一代的交叉次數(shù)800，變異概率取0.1。

3.2 實(shí)驗(yàn)結(jié)果

數(shù)值實(shí)驗(yàn)分兩個(gè)部分，首先驗(yàn)證本文設(shè)計(jì)的啟發(fā)式策略分段產(chǎn)生初始解的方法相對(duì)于隨機(jī)初始解生成方法的有效性，然后對(duì)比采用不同交叉算子的遺傳算法的性能，以此驗(yàn)證自適應(yīng)機(jī)制對(duì)提升算法性能的有效性。

為了驗(yàn)證本文設(shè)計(jì)的啟發(fā)式初始解生成方法相對(duì)于隨機(jī)初始解生成方法的有效性，本文按照車輛與倉門的不同數(shù)量選取了三個(gè)組合，每個(gè)組合含3個(gè)算例，每個(gè)算例分別采用上述兩種初始解生成方法各產(chǎn)生1000個(gè)初始解，通過比較這些初始解的平均適應(yīng)度值來分析兩種方法的有效性。表1給出了具體的實(shí)驗(yàn)結(jié)果，雖然在問題規(guī)模很小的時(shí)候，隨機(jī)生成初始解的方法的表現(xiàn)相對(duì)優(yōu)于啟發(fā)式方法，這主要是因?yàn)榇藭r(shí)解空間小，隨機(jī)生成方法有較大的概率選取到較優(yōu)的初始解；然而隨著問題規(guī)模的增大，解空間以幾何級(jí)數(shù)擴(kuò)大（這也是此類組合優(yōu)化問題的一大特點(diǎn)），此時(shí)隨機(jī)方法的劣勢(shì)突顯，而啟發(fā)式方法由于采取了特定的選取規(guī)則，能夠在眾多的解中尋找到質(zhì)量更好的初始解，對(duì)于此類組合優(yōu)化問題具有良好的適用性，從數(shù)值實(shí)驗(yàn)結(jié)果也能夠看出總體而言啟發(fā)式方法優(yōu)于隨機(jī)方法。此外，在越庫實(shí)踐中，車輛和倉門的數(shù)量往往較多，問題規(guī)模也較大，因此啟發(fā)式初始解生成方法在實(shí)踐中也更加適用。

下面為了對(duì)比采用不同交叉算子的遺傳算法的性能，生成三類不同規(guī)模的算例，每一類同樣按照車輛與倉門的不同數(shù)量分成6組，每組各做10次隨機(jī)實(shí)驗(yàn)。表2～表4給出了每組10次隨機(jī)實(shí)驗(yàn)分別采用自適應(yīng)機(jī)制、單點(diǎn)交叉以及兩點(diǎn)交叉的遺傳算法求解得到的平均實(shí)驗(yàn)結(jié)果，包括平均目標(biāo)函數(shù)值以及平均求解時(shí)間（以秒為單位）。從表2～表4可以看出，對(duì)于不同規(guī)模的問題，算法的表現(xiàn)對(duì)比結(jié)果是一致的，都是自適應(yīng)算法優(yōu)于單點(diǎn)交叉，單點(diǎn)交叉優(yōu)于兩點(diǎn)交叉。因此，自適應(yīng)遺傳算法對(duì)于求解該問題是有效的，而且自適應(yīng)機(jī)制對(duì)于提升算法性能有顯著的效果。

表1 啟發(fā)式初始解與隨機(jī)法初始解的平均適應(yīng)度值對(duì)比

表2 小規(guī)模問題數(shù)值實(shí)驗(yàn)結(jié)果

表3 中規(guī)模問題數(shù)值實(shí)驗(yàn)結(jié)果

表4 大規(guī)模問題數(shù)值實(shí)驗(yàn)結(jié)果

4 結(jié)論

本文研究了帶有車輛容量限制以及時(shí)間窗口約束的越庫配送車輛調(diào)度問題，該問題旨在通過車輛與庫門的合理分配來實(shí)現(xiàn)越庫內(nèi)部貨物的最優(yōu)調(diào)度從而達(dá)到高效的運(yùn)作目標(biāo)。本文基于遺傳算法的思想，采用了單點(diǎn)交叉算子和兩點(diǎn)交叉算子的 “交叉行為自適應(yīng)選擇機(jī)制”設(shè)計(jì)了一種自適應(yīng)遺傳算法來進(jìn)行求解。數(shù)值實(shí)驗(yàn)結(jié)果表明，采用自適應(yīng)機(jī)制的遺傳算法在最終解的質(zhì)量上的表現(xiàn)要優(yōu)于單獨(dú)采用單點(diǎn)交叉算子或者兩點(diǎn)交叉算子，說明自適應(yīng)遺傳算法對(duì)解決該問題的高效性，同時(shí)也表明該自適應(yīng)機(jī)制對(duì)于提升遺傳算法性能上具有顯著的促進(jìn)作用。

[1] Gue, K.R., The effect of trailer scheduling on the layout of freight terminals [J]. Transportation Science 1999, 33(4): 419–28.

[2] Napolitano, M., Making the move to cross docking-a practical guide [M]. Warehousing Education and Research Council, 2002.

[3] Yan, H., Tang, S. L., Pre-distribution and post-distribution crossdocking operations [J]. Transportation Research Part E, 2009, 45(6): 843-859.

[4] Yan, H., Tang, S. L., Pre-distribution vs. post-distribution crossdocking with transshipments [J]. Omega, 2010, 38(34):192-202.

[5] Shaffer, B.. Implementing the crossdocking operation [J]. IIE Transaction, 2000, 30(5):20-23.

[6] Axsater, S., New decision rule for lateral transshipments in inventory systems [J]. Management Science, 2003, 49(9):1168–1179.

[7] Axsater, S., Evaluation of unidirectional lateral transshipments and substitutions in inventory systems [J]. European Journal of Operational Research, 2003, 149(2):438–447.

[8] Lim, A., Miao, Z., Rodrigues, B., Xu, Z. Transshipment through crossdocks with inventory and time windows [J]. Naval Research Logistics Quarterly, 2005, 52 (8):724–733.

[9] Miao, Z.W., Yang, F., Fu, K., Transshipment service through crossdocks with both soft and hard time windows constraints [J]. Annals of Operations Research, 2012, 192: 21-47.

[10] Bartholdi, J.J., Gue, K.R., The Best Shape for a Crossdock [J]. Transportation Science, 2004, 38(2):235-224.

[11] Bartholdi, J.J., Gue, K.R., Reducing labor costs in an LTL crossdocking terminal [J]. Operation Rearch, 2000, 48(6):823-832.

[12] Yu, W., Egbelu, P.J., Scheduling of inbound and outbound trucks in cross docking systems with temporary storage. European Journal of Operational Research, 2008, 184(1):377–396.

[13] Miao, Z.W., Lim, A., Ma, H., Truck dock assignment problem with operational time constraint within crossdocks [J]. European Journal of Operational Research, 2009, 192(1): 105-115.

[14] Chen, F., Lee, C.Y., Minimizing the make span in two-machine crossdocking scheduling [J]. European Journal of Operations Research, 2009, 193(1):59-72.

[15] Boysen, N., Fliedner, M., Cross dock scheduling: Classification, literature review and research agenda [J]. Omega, 2010, 38(6):413-422.

[16] Jan, V.B., Paul, V., & Dirk, C., Cross-docking: State of the art [J], Omega, 2012, 40: 827-846.

[17] Vahdani, B., Zandieh, M., Scheduling trucks in cross-docking systems: Robust meta-heuristics [J]. Computers and Industrial Engineering, 2010, 58(1):12-24.

[18] 陳峰, 宋凱雷, 越庫物流調(diào)度問題及其近似與精確算法 [J], 工業(yè)工程與管理, 2006, (6): 53-58.

[19] 俞亮, 陳峰, 最小化誤工個(gè)數(shù)的越庫調(diào)度模型與啟發(fā)式算法 [J], 上海交通大學(xué)學(xué)報(bào), 2009, (12): 1984-1988.

[20] 強(qiáng)瑞, 繆朝煒, 吳為民, 供應(yīng)網(wǎng)絡(luò)中越庫轉(zhuǎn)運(yùn)中心倉門分配問題研究 [J], 管理工程學(xué)報(bào)，2011, (1): 209-215.

[21] Spears, W.M., Adapting crossover in evolutionary algorithms [C]. In: McDonnell, J.R., Reynolds, R.G., Fogel, D.B. (Eds.), Proceedings of the Fourth Annual Conference on Evolutionary Programming. MIT Press, Cambridge, MA, 1995: 367–384.

[22] 鄺航宇, 金晶, 蘇勇, 自適應(yīng)遺傳算法交叉變異算子的改進(jìn) [J]. 計(jì)算機(jī)工程與應(yīng)用, 2006,42(12): 93-96.

An Adaptive Genetic Algorithm for the Truck Scheduling Problem in the Crossdock Distribution Center

MIAO Zhao-wei1, SU Rui-ze1, ZHANG Jie2

(1. School of Management, Xiamen University, Xiamen 361005, China;2. School of Business Administration, Guangdong University of Finance and Economics, Guangzhou 510320, China)

As a just-in-time (JIT) logistics technology, crossdock refers to the operation of pickup-delivery and order-dealt activities at any intermediate points between upstream suppliers and downstream customers. Those intermediate points include transshipment warehouse or distribution center. They are used to achieve the elimination of goods storage, which can be temporarily stored and generally not more than one or two days, and can greatly reduce response time and inventory cost as well. Crossdock is increasingly being used to optimize the distribution network of supply chain, which can significantly reduce company's inventory levels by integrating inventory management strategy and distribution strategy. Thus, crossdock can reduce not only inventory management cost and cargo loss rate, but also speed up cash flow. It is reported that many well-known multi-national companies, such as Wal-Mart, Unilever, Dell, and Cisco, have implemented this technique successfully. The truck scheduling strategy plays a very important role in operations within the crossdock distribution center, which has a significant impact on the operational efficiency of crossdock. A good truck scheduling strategy can increase operational efficiency, improve customer service level, and reduce the total cost.

Because crossdock-related problems are a hot topic in both academic and industrial areas nowadays, there is a lot of related research works in the previous literatures, which can be mainly divided into five categories: (1) the facility location problem of crossdocks; (2) the network flow problem in a multiple-crossdock distribution system; (3) the layout design problem within a crossdock; (4) the resource allocation problem within a crossdock; (5) the scheduling problem within a crossdock. In this paper, we try to extend the truck scheduling problem in a crossdock and consider the capacity constraint of outbound trucks as well as that of the crossdock. In reality, the number of inbound/outbound docks is limited, and the distance between inbound and outbound docks is different, and the amount of transshipment cargos and the time window for each inbound/outbound truck is different. Therefore, it is important to schedule these trucks to guarantee the number of trucks assigned to a door as many as possible so that cargos can be transshipped as many as possible and the transfer distance inside the crossdock can be minimum. These considerations will have a great impact on the efficiency and cost of crossdock operations. This paper tries to find a truck scheduling with a minimum cost under the time windows and capacity constraints of outbound truck and crossdock in order to increase the efficiency of crossdock operations.

In the first part, we introduce this truck scheduling problem including constraints, assumptions, notations as well as decision variables, by which we propose a 0-1 Integer Programming Model. This kind of optimization problem is NP-hard in the strong sense. As a result, we try to develop a genetic algorithm by adopting single-point crossover (SPCO) and double-point crossover (DPCO) adaptively to solve it.

In the second part, we introduce the steps of designing our adaptive genetic algorithm. We design the chromosome and adopt heuristic method to obtain a group of initial solutions at first rather than generate them randomly in order to obtain good quality ones because the quality of the initial solutions will influence the efficiency of the genetic algorithm greatly. SPCO and DPCO are developed as well as probability mutation operator. After that, an adaptive scheme is proposed to adopt the two crossover operators adaptively.

The third part is numerical experiments, where we compare the performance of the adaptive genetic algorithm with those adopting SPCO and DPCO, respectively. We not only show the generation procedure of those parameters, but also develop three categories experiments including large, medium and small scale instances respectively. The results show that the adaptive genetic algorithm has the best performance in terms of final near-optimal solution quality in all scenarios. These findings mean that the proposed adaptive genetic algorithm is a good way to solve this kind of truck scheduling problem. Moreover, it shows that this adaptive scheme can improve the efficiency of the genetic algorithm for this problem.

In summary, this paper tries to resolve the truck scheduling problem with the time windows and capacity constraints of outbound truck and crossdock, and develops an adaptive genetic algorithm to solve it. The numerical experiments show that our algorithm outperforms the others with a single crossover operator. This suggests that this adaptive genetic algorithm is an efficient way to solve this kind of problem.

genetic algorithm; adaptive scheme; crossdock; truck scheduling

中文編輯：杜 健；英文編輯：Charlie C. Chen

F224.3

A

1004-6062(2016)04-0166-07

10.13587/j.cnki.jieem.2016.04.021

2013-12-28

2014-05-26

國家自然科學(xué)基金資助項(xiàng)目（71371158，71301032）；教育部“新世紀(jì)優(yōu)秀人才支持計(jì)劃”資助項(xiàng)目（NCET-10-0712）；中央高?；究蒲袠I(yè)務(wù)費(fèi)資金資助項(xiàng)目（2012221011）。

繆朝煒（1980—），男，福建福州人；廈門大學(xué)管理學(xué)院教授，研究方向：物流與供應(yīng)鏈管理。