多車場(chǎng)與多車型車輛路徑問(wèn)題的多染色體遺傳算法

陳呈頻 韓勝軍 魯建廈 陳青豐 王 成

浙江工業(yè)大學(xué)工業(yè)工程研究所，杭州，310014

0 引言

車輛路徑問(wèn)題(vehicle routing problem，VRP)是運(yùn)輸組織優(yōu)化的核心問(wèn)題。從現(xiàn)有研究文獻(xiàn)看，圍繞車輛路徑問(wèn)題的研究比較多，但多數(shù)是從以下三個(gè)方向進(jìn)行研究：?jiǎn)诬囆突蚨嘬囆偷能囕v路徑問(wèn)題[1-2]，單車場(chǎng)或多車場(chǎng)的車輛路徑問(wèn)題[3-4]，帶時(shí)間窗或不帶時(shí)間窗的車輛路徑問(wèn)題[5-6]。這主要是因?yàn)檐囕v路徑問(wèn)題屬于NP難題，該問(wèn)題只有在規(guī)模較小時(shí)才有可能求得其精確解，隨著問(wèn)題規(guī)模的擴(kuò)大，求解難度急劇增加，往往很難求得最優(yōu)解。多車場(chǎng)、多車型車輛路徑問(wèn)題(multiple-depot multiple-type vehicle routing problem，MDMTVRP)既是對(duì)基本車輛路徑問(wèn)題的擴(kuò)展，更是對(duì)多車場(chǎng)車輛路徑問(wèn)題和多車型車輛路徑問(wèn)題的組合，它的求解必然更加復(fù)雜，目前還沒(méi)有成熟的求解算法。

SUREKHA等[7]在研究多車場(chǎng)車輛路徑問(wèn)題時(shí)，根據(jù)C-W節(jié)約算法將客戶就近分配給車場(chǎng)，然后采用遺傳算法安排車輛配送路線。SALHI等[8]研究了帶回程取貨的多車型車輛路徑問(wèn)題并建立其數(shù)學(xué)模型，提出一種基于集合分割的啟發(fā)式算法來(lái)求解該類問(wèn)題。馬建華等[9]采用變異蟻群算法求解MDMTVRP，對(duì)給定的顧客順序劃分車輛和指派車場(chǎng)，把該問(wèn)題轉(zhuǎn)化為尋找最優(yōu)顧客順序問(wèn)題進(jìn)行求解。然而，這種方法最大的缺陷在于，即使每條線路都最優(yōu)，但從問(wèn)題的整體而言，得到的卻未必是全局最優(yōu)解。羅鴻斌[10]將改進(jìn)粒子群算法用于求解MDMTVRP，粒子采用3個(gè)n維向量進(jìn)行編碼的方式，但造成了大量的無(wú)效運(yùn)算，導(dǎo)致求解效率不高。SUNDAR等[11]研究了附加燃料限制的MDMTVRP，通過(guò)比較4種基于節(jié)點(diǎn)和基于弧的模型，設(shè)計(jì)了分支切割算法，不過(guò)該方法很難應(yīng)用于規(guī)模較大的情況。

大量的文獻(xiàn)均表明，多車場(chǎng)、多車型車輛路徑問(wèn)題，特別是規(guī)模較大的多車場(chǎng)、多車型車輛路徑問(wèn)題的求解效率和解的質(zhì)量還遠(yuǎn)未達(dá)到實(shí)用要求。為此，本文提出一種求解MDMTVRP的多染色體遺傳算法。

1 MDMTVRP描述和數(shù)學(xué)模型

1.1 問(wèn)題描述

MDMTVRP可以描述為：擁有多種車型車輛的多個(gè)車場(chǎng)需要對(duì)服務(wù)區(qū)內(nèi)的眾多客戶提供配貨服務(wù)，要求通過(guò)合理地調(diào)度車輛并選擇適當(dāng)?shù)男熊嚶肪€，使總配送費(fèi)用最低。該問(wèn)題有如下幾個(gè)基本假設(shè)[12]：①多個(gè)車場(chǎng)擁有多種車型的車輛；②車型不同，車輛的裝載量可能不同；③車型不同，車輛的成本(固定成本和可變成本)可能不同；④一輛車最多被調(diào)度一次，從車場(chǎng)出發(fā)并最終返回原車場(chǎng)；⑤一輛車至少可以服務(wù)一個(gè)客戶，即一個(gè)客戶的需求量不會(huì)大于一輛車的裝載量；⑥一個(gè)客戶被且僅被一輛車服務(wù)。

1.2 數(shù)學(xué)模型

無(wú)論是MDMTVRP，還是基本車輛路徑問(wèn)題，一輛車必然屬于某個(gè)車場(chǎng)，同時(shí)也必然屬于某個(gè)車型。因此，本文直接為客戶和所有車輛進(jìn)行統(tǒng)一編號(hào)，從而能夠利用只包含3個(gè)角標(biāo)的變量建立MDMTVRP的數(shù)學(xué)模型(傳統(tǒng)的建模方式中，變量需要使用4個(gè)角標(biāo)表示)，有效地簡(jiǎn)化了模型。

設(shè)多個(gè)車場(chǎng)擁有不同型號(hào)的車輛共H輛，每輛車的坐標(biāo)位置反映其所屬車場(chǎng)信息，裝載量和成本反映其所屬車型信息，車的裝載量為Qh(h=1，2，…，H)，固定成本為c1h，行駛單位距離的可變成本為c2h，客戶n的需求量為gn(n=1，2，…，N)。MDMTVRP可以用一個(gè)加權(quán)圖G(V，E)來(lái)表示，其中，節(jié)點(diǎn)集V={1，2，…，N+H}，V的前N個(gè)節(jié)點(diǎn)表示客戶，后H個(gè)節(jié)點(diǎn)表示車輛；路徑集E={dij|i，j∈V}表示從節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離集合。問(wèn)題的目標(biāo)是要在滿足約束條件下找到一個(gè)車輛集和路徑集，使總配送費(fèi)用最低。

引入決策變量：

(1)

基于上述條件，MDMTVRP的數(shù)學(xué)模型可表示如下：

目標(biāo)函數(shù)

(2)

約束條件

(3)

(4)

(5)

(6)

(7)

(8)

上述模型中，式(2)表示最低配送成本，前半部分為固定成本，后半部分為可變成本；式(3)表示調(diào)度車輛數(shù)不超過(guò)車輛總數(shù)；式(4)、式(5)表示一個(gè)客戶僅被一輛車配送一次；式(6)表示每輛車的配送總量不超過(guò)其最大裝載量；式(7)表示車輛從車場(chǎng)出發(fā)并返回原車場(chǎng)；式(8)表示車輛不能從一個(gè)車場(chǎng)行駛到另一個(gè)車場(chǎng)。

需要說(shuō)明的是，本文建立的三角標(biāo)變量的數(shù)學(xué)模型基礎(chǔ)性和通用性較強(qiáng)。實(shí)際上，許多MDMTVRP的擴(kuò)展問(wèn)題也能通過(guò)上面的模型進(jìn)行求解，例如約束條件中考慮客戶優(yōu)先順序、車輛行駛時(shí)間、貨物成本因素，以及優(yōu)化目標(biāo)為車輛數(shù)最少、行駛路徑最短、客戶等待時(shí)間最短等多車場(chǎng)、多車型車輛路徑問(wèn)題。

2 多染色體遺傳算法

雖然遺傳算法傳統(tǒng)的單染色體(單鏈)編碼方式在求解基本的單車場(chǎng)單車型車輛路徑問(wèn)題上有著較好的效果，但對(duì)于MDMTVRP，由于添加“多車場(chǎng)”和“多車型”兩個(gè)重要約束，往往會(huì)導(dǎo)致解的質(zhì)量不高，還會(huì)產(chǎn)生大量的不可行解甚至非法解，大大降低了求解效率。

針對(duì)上述問(wèn)題，本文從遺傳算法設(shè)計(jì)的本源出發(fā)，對(duì)遺傳算法進(jìn)行了重新設(shè)計(jì)。為此，聯(lián)系到MDMTVRP，本文從更加貼近生物遺傳進(jìn)化規(guī)律的角度，提出了求解該問(wèn)題的多染色體編碼方式，即一個(gè)個(gè)體包含多條染色體，染色體的數(shù)量與車輛總數(shù)相等，每條染色體恰好完全表示一輛車的行駛路線，既方便了染色體的交叉，又能避免不可行解甚至非法解的產(chǎn)生。由于該算法的設(shè)計(jì)思想與傳統(tǒng)的一個(gè)個(gè)體只含有一條染色體的遺傳算法不同，所以，本文把該種求解MDMTVRP的遺傳算法命名為多染色體遺傳算法。

2.1 染色體的編碼

遺傳算法求解MDMTVRP時(shí)，染色體的編碼是一項(xiàng)非常重要的工作，它直接決定了算法性能的優(yōu)劣。由于一輛車必然對(duì)應(yīng)某個(gè)車場(chǎng)和車型，也必然對(duì)應(yīng)一條配送路線，所以，本文設(shè)計(jì)種群個(gè)體染色體數(shù)量等于車輛數(shù)量的多染色體編碼方式。對(duì)于一個(gè)包含N個(gè)客戶、H輛車的MDMTVRP，將客戶編號(hào)為自然數(shù)1～N，車輛編號(hào)為自然數(shù)N+1～N+H，每個(gè)自然數(shù)表示一個(gè)基因。種群中每個(gè)個(gè)體包含H條染色體，每一條染色體的第一個(gè)基因代表車輛(稱為車輛基因)，其他基因代表客戶(稱為客戶基因)，基因的順序代表被服務(wù)的先后。

例如，如圖1所示，有兩種車型(Ⅰ型、Ⅱ型)的5輛車(編號(hào)11～15)分別屬于3個(gè)車場(chǎng)(編號(hào)A、B、C)，要為10個(gè)客戶(編號(hào)1～10)提供配送服務(wù)。個(gè)體設(shè)計(jì)為與車輛數(shù)相等的5條染色體，編碼為：11，9，1，3；12，6，8；13，10，7；14；15，5，4，2。

染色體表示意義如下：車輛11從車場(chǎng)出發(fā)依次為客戶9、1、3提供服務(wù)，然后返回原車場(chǎng)；車輛12從車場(chǎng)出發(fā)依次為客戶6、8提供服務(wù)，然后返回原車場(chǎng)；車輛13從車場(chǎng)出發(fā)依次為客戶10、7提供服務(wù)，然后返回原車場(chǎng)；車輛14未被調(diào)用；車輛15從車場(chǎng)出發(fā)依次為客戶5、4、2提供服務(wù)，然后返回原車場(chǎng)。

圖1 車輛配送示意圖Fig.1 Schematic diagram of vehicle distribution

2.2 初始種群的確定

隨機(jī)產(chǎn)生一個(gè)種群規(guī)模為S的初始種群，具體過(guò)程如下：隨機(jī)打亂序列{1、2、…、N}的順序，然后隨機(jī)選擇編號(hào)N+1～N+H中的一個(gè)編號(hào)(代表車輛)，序列的第一個(gè)編號(hào)對(duì)應(yīng)的客戶“試分配”給這輛車，如果不超載，則此客戶確定被分配給這輛車，否則在其余車輛中隨機(jī)選擇一輛并再次判斷是否超載；以此類推，直至將此客戶分配給某輛車。按上述過(guò)程依次將新序列的剩余客戶分配給車輛?？蛻舯环峙浣o車輛的先后順序作為被服務(wù)的次序。

2.3 適應(yīng)度函數(shù)

遺傳算法用適應(yīng)度來(lái)評(píng)價(jià)個(gè)體的優(yōu)劣程度，對(duì)于極大值問(wèn)題，適應(yīng)度越大的個(gè)體越好；對(duì)于極小值問(wèn)題，適應(yīng)度越小的個(gè)體越好。由于種群中不存在不可行解和非法解，所以直接根據(jù)式(2)計(jì)算對(duì)應(yīng)的目標(biāo)函數(shù)值z(mì)i(i=1，2，…，S)，并將其作為個(gè)體i的適應(yīng)度。

2.4 交叉操作

由于不定點(diǎn)交叉或多點(diǎn)交叉可能會(huì)導(dǎo)致車輛超載，從而產(chǎn)生非法解，所以本文采用定點(diǎn)單點(diǎn)交叉，交叉點(diǎn)設(shè)定在第一個(gè)基因(車輛基因)之后。根據(jù)交叉概率Pc隨機(jī)選擇個(gè)體A、B，對(duì)其進(jìn)行交叉操作的具體步驟如下：

(1)隨機(jī)產(chǎn)生一個(gè)介于1～H之間的自然數(shù)，代表要進(jìn)行交叉操作的兩個(gè)個(gè)體的同一染色體編號(hào)(個(gè)體A編號(hào)設(shè)為a，個(gè)體B編號(hào)設(shè)為b，且a=b)；

(2)取出a、b兩條染色體相同的客戶基因存入基因庫(kù)Fab中，不同的客戶基因分別存入基因庫(kù)Fa、Fb中；

(3)交換2條染色體的客戶基因(保持客戶基因的順序不變)；

(4)將個(gè)體A中除染色體a以外的其他染色體的客戶基因與Fb的基因逐一進(jìn)行比對(duì)，并將所有相同的基因刪除，同樣，對(duì)個(gè)體B進(jìn)行類似操作；

(5)將Fa中的基因逐一隨機(jī)插入個(gè)體A任意染色體的首基因之后的任意位置。之后，判斷車輛是否超載：如果超載，則隨機(jī)插入下一條染色體并再次判斷是否超載，以此類推，直至將Fa中的基因全部分配出去為止。對(duì)個(gè)體B進(jìn)行類似操作。

2.5 變異操作

設(shè)變異概率Pe，個(gè)體每條染色體第一個(gè)基因不產(chǎn)生變異，對(duì)于其他的每個(gè)基因i，在區(qū)間0～1之間隨機(jī)產(chǎn)生浮點(diǎn)數(shù)ri與基因i對(duì)應(yīng)。如果ri

2.6 選擇

傳統(tǒng)的正比選擇法(選擇概率正比于個(gè)體的適應(yīng)度)有一些不好的性質(zhì)：迭代早期，一些適應(yīng)度很高的超級(jí)個(gè)體會(huì)霸占選擇過(guò)程，導(dǎo)致選擇壓力過(guò)大；迭代晚期，個(gè)體間的適應(yīng)度差距較小，導(dǎo)致選擇壓力過(guò)小。CHENG等[13]提出的正規(guī)化技術(shù)彌補(bǔ)了上述不足，它的形式如下(對(duì)于極小化問(wèn)題)：

(9)

2.7 精英選擇

設(shè)計(jì)第S+1個(gè)個(gè)體，最初用來(lái)保存初始種群中的最優(yōu)個(gè)體。之后，如果第S+1個(gè)個(gè)體的適應(yīng)度優(yōu)于所有子代個(gè)體，則用它替換掉子代中的最差個(gè)體；否則，它被子代中的最優(yōu)個(gè)體取代。精英選擇一方面可以保證優(yōu)秀個(gè)體的基因在進(jìn)化選擇過(guò)程中不被丟失，從而加速收斂；另一方面確保了子代種群中的最優(yōu)個(gè)體不會(huì)比父代種群差，從而使進(jìn)化曲線單調(diào)下降。

3 算例分析

3.1 算例驗(yàn)證

為了驗(yàn)證多染色體遺傳算法的可行性及有效性，對(duì)一個(gè)隨機(jī)生成的算例進(jìn)行求解驗(yàn)證。算例中采用直線距離，便于更直觀地說(shuō)明問(wèn)題，系統(tǒng)內(nèi)的車場(chǎng)和客戶的位置隨機(jī)分布在100 km×100 km的區(qū)域內(nèi)。設(shè)有3個(gè)車場(chǎng)、3個(gè)類型的車輛(共10輛)為30位客戶配送貨物，其信息分別見(jiàn)表1和表2。要求安排適當(dāng)?shù)能囕v及其行駛路線，使配送任務(wù)的總費(fèi)用最少。

需要指出的是，車輛服務(wù)客戶的數(shù)量可能不同，如果使用染色體編碼常用的數(shù)組結(jié)構(gòu)表示染色體，則必須根據(jù)染色體的最大長(zhǎng)度設(shè)定數(shù)組長(zhǎng)度，這必然會(huì)造成大量的無(wú)效運(yùn)算和資源浪費(fèi)。為了解決這個(gè)問(wèn)題，本文采用鏈表結(jié)構(gòu)表示染色體，染色體中基因的順序通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)，從而方便基因的插入和刪除操作，其時(shí)間復(fù)雜度達(dá)到O(1)，數(shù)組結(jié)構(gòu)進(jìn)行同樣操作的時(shí)間復(fù)雜度為O(n)。

表1 客戶信息表

表2 車場(chǎng)/車輛信息表

遺傳算法參數(shù)設(shè)置如下：種群規(guī)模S=400，迭代次數(shù)T=1000，交叉概率Pc=0.5，變異概率Pm=0.03。算法通過(guò)VC++6.0編程實(shí)現(xiàn)，在Win7操作系統(tǒng)的計(jì)算機(jī)上運(yùn)行。運(yùn)算結(jié)果如表3所示，其中，總費(fèi)用為8306元；車輛路徑如圖2所示，適應(yīng)度隨遺傳迭代次數(shù)變化的進(jìn)化曲線如圖3所示。

表3 車輛調(diào)度方案

圖2 車輛路徑示意圖Fig.2 Schematic diagram of vehicle path

圖3 進(jìn)化曲線Fig.3 Evolution curve

圖2中，小圓點(diǎn)表示客戶，大圓點(diǎn)表示車場(chǎng)，數(shù)字為客戶編號(hào)，連線表示車輛的行駛路線；“A，31，3”表示A車場(chǎng)第1輛車起始編號(hào)為31，共有3輛車，“B，34，3”和“C，37，4”含義類推。

客戶平均需求量為28，車輛的平均最大裝載量為131，一個(gè)客戶僅被一輛車服務(wù)，這直接限制了車輛的裝載率。所以，由表3可以看出，被派出車輛的裝載率已經(jīng)達(dá)到了較高的水平，平均裝載率為80%。由圖2可以看出，每輛車的配送路徑所形成的環(huán)路沒(méi)有出現(xiàn)交叉的情況，說(shuō)明解的質(zhì)量較高。由圖3的進(jìn)化曲線可以看出，隨著迭代次數(shù)的增加，種群最優(yōu)個(gè)體的適應(yīng)度迅速減小，種群在300代左右產(chǎn)生的最優(yōu)個(gè)體的質(zhì)量已經(jīng)較高，之后進(jìn)化速度減緩，進(jìn)化曲線在第591代收斂，最優(yōu)適應(yīng)度為8 306。程序運(yùn)行速度快，消耗總時(shí)間為6.515 s。

3.2 對(duì)比分析

為了進(jìn)一步驗(yàn)證多染色體遺傳算法的性能，將其測(cè)試結(jié)果與傳統(tǒng)的單染色體遺傳算法和標(biāo)準(zhǔn)的粒子群算法的測(cè)試結(jié)果進(jìn)行對(duì)比分析。傳統(tǒng)的單染色體遺傳算法的遺傳算子參考馬宇紅等[15]的研究成果設(shè)計(jì)。為便于對(duì)比分析，統(tǒng)一設(shè)定迭代次數(shù)為1 000，種群規(guī)模(或粒子數(shù))設(shè)計(jì)為100，統(tǒng)計(jì)3種算法分別運(yùn)行100次解的均值和標(biāo)準(zhǔn)差，并輸出其運(yùn)行100次的平均進(jìn)化曲線。統(tǒng)計(jì)結(jié)果如表4所示，平均進(jìn)化曲線如圖4所示。

表4 測(cè)試結(jié)果統(tǒng)計(jì)

圖4 平均進(jìn)化曲線Fig.4 Average evolution curve

由表4可以看出，多染色體遺傳算法的均值和標(biāo)準(zhǔn)差都大幅度優(yōu)于單染色體遺傳算法和粒子群算法。由圖4還可以看出，粒子群算法雖然收斂較快，但易陷入局部最優(yōu)；單染色體遺傳算法收斂較慢，且收斂值較大；多染色體遺傳算法無(wú)論是收斂速度，還是收斂值均優(yōu)于其他兩種算法。另外，多染色體遺傳算法的進(jìn)化曲線在100代左右已經(jīng)達(dá)到了粒子群算法和單染色體遺傳算法的進(jìn)化曲線的收斂值。所以，求解MDMTVRP時(shí)，在解的質(zhì)量和搜索效率方面，多染色體遺傳算法都體現(xiàn)出良好的性能。

4 結(jié)語(yǔ)

多車場(chǎng)、多車型車輛路徑問(wèn)題相對(duì)于單車場(chǎng)、單車型車輛路徑問(wèn)題而言，是一種更加通用且貼近實(shí)際的車輛路徑問(wèn)題。本文針對(duì)多車場(chǎng)、多車型車輛路徑問(wèn)題，首先建立其變量用三角標(biāo)形式表示的整數(shù)規(guī)劃模型，然后在此基礎(chǔ)上設(shè)計(jì)了個(gè)體染色體數(shù)量與總車輛數(shù)量相等的多染色體遺傳算法，根據(jù)配送任務(wù)的基本單位——車輛來(lái)設(shè)計(jì)染色體，從而使多車場(chǎng)、多車型車輛路徑問(wèn)題與基本的單車場(chǎng)、單車型車輛路徑問(wèn)題有效地統(tǒng)一起來(lái)；染色體采用鏈表結(jié)構(gòu)表示，相比于傳統(tǒng)的數(shù)組結(jié)構(gòu)，算法很好地避免了大量無(wú)效運(yùn)算；選擇過(guò)程中，對(duì)適應(yīng)度采用正規(guī)化技術(shù)進(jìn)行處理，確保了整個(gè)遺傳過(guò)程始終保持適度的選擇壓力；精英選擇的應(yīng)用保證了種群優(yōu)良基因的延續(xù)。實(shí)驗(yàn)結(jié)果表明，本文所設(shè)計(jì)的多染色體遺傳算法不僅具有很高的搜索效率與較高的收斂速度，而且解的質(zhì)量和穩(wěn)定性也很高。

進(jìn)一步的研究擬考慮加入“時(shí)間窗”約束，將此算法應(yīng)用于帶時(shí)間窗的多車場(chǎng)、多車型車輛路徑問(wèn)題，從而使研究對(duì)象更加切合實(shí)際，使算法更加具有通用性。

[1] 葉志堅(jiān), 葉懷珍, 周道平, 等. 多車型車輛路徑問(wèn)題的算法[J]. 公路交通科技, 2005, 22(5): 147-151.

YE Zhijian, YE Huaizhen, ZHOU Daoping, et al. Heuristics for the Fleet Size and Mix Vehicle Routing Problem[J]. Journal of Highway and Transportation Research and Development, 2005, 22(5): 147-151.

[2] GENDREAU M, LAPORTE G, MUSARAGANYI C. A Tabu Search Heuristic for the Heterogenous Fleet Vehicle Routing Problem[J]. Computers & Operations Research, 1999, 26(12): 1153-1173.

[3] FISHER M L, TANG B X, ZHENG Z. A Network Flow Based Heuristic for Bulk Pickup and Delivery Routing[J]. Transportation Science, 1995, 29(1): 45-55.

[4] GIOSA I D, TANSINI I L, VIERA I O. New Assignment Algorithms for the Multi-depot Vehicle Routing Problem[J]. Journal of the Operational Research Society, 2002, 53(9): 977-984.

[5] 劉瓊, 劉秀城, 張超勇, 等. 基于改進(jìn)蟻群算法的帶時(shí)間窗廢品收集車輛路徑問(wèn)題[J]. 中國(guó)機(jī)械工程, 2015, 26(2): 247-254.

LIU Qiong, LIU Xiucheng, ZHANG Chaoyong, et al. Waste Collection Vehicle Routing Problem with Time Windows Based on Improved Ant Colony Optimization[J]. China Mechanical Engineering, 2015, 26(2): 247-254.

[6] DAN Z G, CAI L N, ZHENG L. Improved Multi-agent System for the Vehicle Routing Problem with Time Windows[J]. Tsinghua Science and Technology, 2009, 14(3): 407-412.

[7] SUREKHA P, SUMATHI S. Solution to Multi-depot Vehicle Routing Problem Using Genetic Algorithms[J]. World Applied Programming, 2011, 1(3): 118-131.

[8] SALHI S, WASSAN W, HAJARAT M. The Fleet Size and Mix Vehicle Routing Problem with Backhauls: Formulation and Set Partitioning-based Heuristics[J]. Transportation Research, 2013, 56: 22-35.

[9] 馬建華, 房勇, 袁杰. 多車場(chǎng)、多車型最快完成車輛路徑問(wèn)題的變異蟻群算法[J]. 系統(tǒng)工程理論與實(shí)踐, 2011, 31(8): 1508-1516.

MA Jianhua, FANG Yong, YUAN Jie. Mutation Ant Colony Algorithm for Multiple-depot Multiple-types Vehicle Routing Problems with Shortest Finish Time[J]. Systems Engineering Theory & Practice, 2011, 31(8): 1508-1516.

[10] 羅鴻斌. 多車場(chǎng)、多車型車輛調(diào)度問(wèn)題的改進(jìn)粒子群算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2014, 50(7): 251-253.

LUO Hongbin. Study on Multi-depots and Multi-vehicles Vehicle Scheduling Problem Based on Improved Particle Swarm Optimization[J]. Computer Engineering and Applications, 2014, 50(7): 251-253.

[11] SUNDAR K, VENKATACHALAM S, RATHINAM S. Formulations and Algorithms for the Multiple Depot, Fuel-constrained, Multiple Vehicle Routing Problem[C]// American Control Conference 2016. Boston, 2016: 10.1109/ACC. 2016. 7526691.

[12] 田冉, 孫林夫, 唐慧佳, 等. 多車場(chǎng)物流協(xié)同運(yùn)輸調(diào)度問(wèn)題研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 2015, 51(21): 230-236.

TIAN Ran, SUN Linfu, TANG Huijia, et al. Research on Vehicle Logistics Transportation Scheduling Problem[J]. Computer Engineering and Applications, 2015, 51(21): 230-236.

[13] CHENG R, GEN M. Evolution Program for Resource Constrained Project Scheduling Problem[J]. Evolutionary Computation, 1994, 11(3): 274-287.

[14] 米凱利維茨Z. 演化程序——遺傳算法和數(shù)據(jù)編碼的結(jié)合[M]. 北京: 科學(xué)出版社, 2000: 24-33.

MICHALEWICZ Z. Genetic Algorithms + Data Structures = Evolution Programs[M]. Beijing: Science Press, 2000: 24-33.

[15] 馬宇紅, 姚婷婷, 張芳芳. 多車場(chǎng)、多車型車輛調(diào)度問(wèn)題及其遺傳算法[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí), 2014, 44(2): 107-114.

MA Yuhong, YAO Tingting, ZHANG Fangfang. Multi-depot Multi-type Vehicle Scheduling Problem and Its Genetic Algorithm[J]. Mathematics in Practice and Theory, 2014, 44(2): 107-114.