畢志升 鄭炯彬 蔡桂艷

（廣州醫(yī)科大學基礎學院廣州511436）

基于高維多目標優(yōu)化的多車場車輛路徑問題?

畢志升 鄭炯彬 蔡桂艷

（廣州醫(yī)科大學基礎學院廣州511436）

車輛路徑問題是運籌學中著名的NP問題，在運輸領域中具有重要的現(xiàn)實意義。多車場車輛路徑問題是其中的一個重要分支，作為單目標優(yōu)化問題和低維多目標優(yōu)化問題被廣泛研究。然而，多車場車輛路徑問題本質上是一個高維多目標優(yōu)化問題。因此，論文針對問題的本質，從物流企業(yè)和客戶兩個不同的角度考察四個優(yōu)化目標，提出了基于高維多目標優(yōu)化的多車場車輛路徑問題，構造了相應的框架MO-MDVRP，并運用NSGA-III和I-DBEA得到了兩個算法實例MD?VRP-NSGAIII和MDVRP-IDBEA。在六個Cordeau數(shù)據(jù)集上進行仿真實驗，實驗表明，運用MDVRP-NSGAIII和MDVRP-ID?BEA求解MO-MDVRP是可行的，MDVRP-NSGAIII的效果顯著優(yōu)于MDVRP-IDBEA。

車輛路徑問題；多車場；高維多目標優(yōu)化

Class NumberTP391

1 引言

電子商務的蓬勃發(fā)展為物流企業(yè)的發(fā)展提供了難得的機遇。然而，機遇背后是巨大的挑戰(zhàn)。物流企業(yè)必須制定科學的運輸路線，高效地滿足客戶的配送需求。這種運輸路線的規(guī)劃，對整個物流系統(tǒng)的運輸效率、成本具有極其重要的影響。運輸路線的規(guī)劃可以抽象為車輛路徑問題（Vehicle Rout?ing Problem，VRP）。VRP是運籌學中著名的NP問題，由Dantzig和Ramser［1］于1959年首次提出。它通過設計合理的車輛行駛路線，實現(xiàn)運輸配送系統(tǒng)的運輸成本最小化。

近年來，VRP受到越來越多國內外學者的關注。然而，已有的研究成果主要針對一個車場即單一配送中心的情況［2］，而現(xiàn)實中許多物流企業(yè)建立了多個配送中心分布在不同的區(qū)域。因而，研究多車場車輛路徑問題（Multiple Depot Vehicle Routing Problem，MDVRP）是十分必要的。

當前對MDVRP的研究主要基于單目標優(yōu)化［2］和低維多目標優(yōu)化［2～3］。然而，MDVRP本質上是一個目標數(shù)大于3的高維多目標優(yōu)化問題。從物流企業(yè)的角度考慮，企業(yè)期望運輸成本低、客戶滿意、各車輛服務工作量均衡或車場服務工作量比例滿足特定要求；從客戶的角度考慮，客戶期望運輸時間短。運輸成本低，除了要求運輸路徑短，還需要車輛少司機少，以減少硬件成本和人工成本。但是，大量貨物依賴少量車輛運輸將導致貨物積壓，延長運輸時間，引起客戶不滿。另一方面，每一件貨物都用專車專人運輸能達到運輸時間短客戶滿意度高的要求，但也必然導致硬件成本和人工成本上升。從物流企業(yè)的生存和發(fā)展考慮，成本低和客戶滿意度高都是不可忽視的。因而，MDVRP中存在三個以上相互矛盾的目標。相比采用加權求和的方式將問題轉化為單目標或低維多目標的求解方法，基于高維多目標優(yōu)化求解MDVRP更符合問題本質和更具有理論意義。另一方面，基于高維多目標優(yōu)化求解MDVRP能同時產生一組均衡解，反映目標間不同的取舍，有利于物流企業(yè)根據(jù)實際情況選擇合適的實施方案。因而，基于高維多目標優(yōu)化求解MDVRP是符合物流企業(yè)利益、具有現(xiàn)實意義的。

本文對MDVRP建立高維多目標優(yōu)化模型MO-MDVRP，并運用非劣排序遺傳算III（Nondom?inated Sorting Genetic Algorithm-III，NSGA-III）［4］和增強的基于分解的演化算法（Improved Decomposi?tion-Based Evolutionary Algorithm，I-DBEA）［5］進行求解。實驗表明，NSGA-III和I-DBEA能有效求解MO-MDVRP。

2 多車場車輛路徑問題

一般地，MDVRP可以定義為［6～7］：有M個車場，每個車場擁有K輛容量為Q、最大持續(xù)時間（包括路徑行駛時間和客戶服務時間）為D的車輛。有N個客戶需要貨物配送?？蛻鬷的貨物容量為gi且gi＜Q，該客戶的服務時間為si且si＜D。車場的服務時間為0?？蛻艨梢杂扇我廛噲龅娜我廛囕v服務，但只能被服務一次。在不超出容量和最大持續(xù)時間的情況下，每輛車一次離開車場可以為多個客戶提供服務，服務結束后車輛必須返回原車場。

記節(jié)點{1，2，…，N}為客戶節(jié)點；節(jié)點{N+1，N+2，…，N+M}為車場節(jié)點；mk為車場m的第k輛車；從節(jié)點i到節(jié)點j的距離為dij；R為一組滿足約束的路徑集合，對應問題的一個解。R中每一條路徑都是一條以某一車場為起點，以同一車場為終點的環(huán)路。令

其中，i∈{1，2，…，N+M}，j∈{1，2，…，N+M}，k∈{1，2，…，K}，且i和j不同時大于N。則MD?VRP可形式化描述為

其中，F(xiàn)是目標函數(shù)，通常選擇總持續(xù)時間或在其基礎上結合車輛數(shù)等其他因素構造目標函數(shù)［2］；式（4）是容量限制；式（5）是最大持續(xù)時間約束，這里用路徑長度替代其中的路徑行駛時間；式（6）是保證每個客戶都被服務且僅被服務一次。顯然，若所有客戶的服務時間均為零，總持續(xù)時間等同于路徑總長度。

近十年，MDVRP一直是一個研究熱點。然而，在豐富的MDVRP研究成果中，近九成都把MDVRP作為一個單目標優(yōu)化問題［2］。它們采用精確方法［8］、啟發(fā)式方法［9］或原啟發(fā)式方法［10］對MDVRP及其衍生的如帶時間窗的MDVRP［11］、可拆分需求的MDVRP［12］等問題進行求解。在多目標優(yōu)化方面，原啟發(fā)式算法被普遍采用［2］。但它們都針對低維多目標優(yōu)化，未充分考慮現(xiàn)實中常見的目標，具有一定的局限性。

3 基于高維多目標優(yōu)化的多車場車輛路徑問題

MDVRP本質上是一個高維多目標優(yōu)化問題，從多目標優(yōu)化的角度考察MDVRP是合理而且必要的。本節(jié)從目標函數(shù)設定、問題轉換、編碼、解碼等方面描述基于多目標優(yōu)化的MDVRP及其求解。

3.1 目標函數(shù)

從物流企業(yè)的角度考慮，本文設定總持續(xù)時間、車輛數(shù)、最大容量差各為一個優(yōu)化目標；從客戶的角度考慮，本文設定客戶的等待時間為一個優(yōu)化目標。因此，本文共設置四個目標函數(shù)。其中最大容量差定義為路徑中實際載貨容量的最大值和最小值之差?？蛻舻却龝r間定義如下：

假設當前有一條路徑r：0-3-2-4-0，節(jié)點0為車場，其余節(jié)點為客戶。路徑中第一個客戶的等待時間為節(jié)點0和節(jié)點3之間的路徑長度。相應地，第二個客戶的等待時間為節(jié)點0到節(jié)點3、節(jié)點3到節(jié)點2的路徑長度之和再加上節(jié)點3的服務時間。即，每個客戶的等待時間是沿著路徑從車場到客戶之間的路徑長度再加上之前經過的客戶的服務時間。而優(yōu)化目標則是最小化所有客戶的等待時間之和。記R中路徑數(shù)量為|R|，每一條路徑上的客戶等待時間為wr。則R中客戶等待時間為

故，該MDVRP可形式化描述如下：

其中，Km≤K是第m個車場實際派出的車輛數(shù)；式（7）是最小化總持續(xù)時間；式（8）是最小化車輛數(shù)；式（9）是最小化最大容量差；式（10）是最小化客戶等待時間。問題約束如第2節(jié)所述。

3.2 問題轉換

鑒于傳統(tǒng)單車場VRP的豐碩成果，求解MD?VRP可以先采用特殊的轉換方法把問題轉化為單車場VRP，然后用單車場VRP的求解方法進行求解。轉換方法通常有兩類［13］：聚類和虛擬車場。前者通過對車場和客戶進行聚類，將一個車場和部分客戶劃分到一個聚類中，然后在聚類內求解VRP。后者使用一個虛擬車場代替實際車場進行路徑規(guī)劃，并在路徑規(guī)劃結束后，將路徑劃分到使路徑總長度最小的實際車場中。

在高維多目標背景下，總持續(xù)時間已經不是唯一的目標，而聚類的劃分蘊含了距離的因素，偏向于優(yōu)化總持續(xù)時間。由于目標間存在矛盾，這種偏向不利于其它目標的優(yōu)化。因此，本文選擇虛擬車場的方式進行問題轉換。

根據(jù)文獻［14］，采用設置虛擬車場的方式將MDVRP轉換為單車場VRP。具體方法是：先設置一個虛擬車場，讓所有車輛都從虛擬車場出發(fā)并在服務結束后回到虛擬車場。如此，MDVRP被轉換成單車場VRP。然后采用針對單車場VRP的方法求解。如圖1所示，假設有15個客戶和4個車場，在增加虛擬車場O后轉換成單車場VRP并進行路徑規(guī)劃。

圖1轉化后進行路徑規(guī)劃

在路徑劃分之后需要把實際車場添加到各條路徑中。添加的方法是：遍歷每條路徑，在尚有空余車輛的車場中選擇令總持續(xù)時間最小的車場替換虛擬車場。這是一種貪心策略，在所有車場都有空余車輛的情況下，這種方法保證添加后總持續(xù)時間最小；當存在個別車場沒有空余車輛時，可能陷入局部最優(yōu)。而且，這種替換方法對路徑的替換順序敏感。

3.3 染色體編碼

本文采用長度為N的整型數(shù)組對染色體進行編碼。數(shù)組以客戶的編號作為數(shù)組的元素，每個編號出現(xiàn)且僅出現(xiàn)一次。記chrom為一條長度為N的染色體，chrom［i］為其中的第i個元素。直觀地，這種編碼的染色體可以通過將各個路徑中的客戶按路徑順序連接后得到。如圖1所示的路徑可以通過chrom=｛13，2，15，5，14，4，8，3，10，9，6，7，12，11，1｝表示。因而，一條染色體就是問題的一個解。由于沒有參雜車場節(jié)點，對任意給定的MD?VRP，其染色體長度固定，為算法的搜索帶來便利。然而，這種編碼方式并沒有記錄車場和路徑劃分信息，因而需要額外的解碼技術，以便將染色體重新劃分為一組路徑。

3.4 染色體解碼

本文在文獻［13］的Plot算法基礎上添加持續(xù)服務時間約束，得到Plot+算法，以滿足MDVRP的問題約束。本文采用Plot+算法對染色體進行解碼，算法如圖2所示。

在解碼前，首先在chrom首位插入一個0節(jié)點。在Plot+中，v［i-1］保存的是從車場開始到客戶chrom［i-1］為止路徑的總長度（Line 7）。chrom［i-1］是上一路徑的最后一個客戶節(jié)點。cost對應的是以客戶chrom［i］為第一個客戶、以客戶chrom［j］為最后一個客戶的路徑長度，是當前嘗試構造的路徑（Line 5）。這種嘗試直到不滿足約束或沒有客戶為止（Line 13）。Line 8中if為真，則構造一條以客戶chrom［i］作為第一個客戶節(jié)點，以客戶chrom［j］為最后一個客戶節(jié)點的路徑。此時意味著新路徑較原方案（對應v［j］）的總持續(xù)時間更小，或路徑等長但能使前一條路徑服務更多的客戶，即車輛容量的利用更充分。如果if為假，意味著原方案更優(yōu)，并在下一次循環(huán)（Line 4-Line 13）中嘗試構造以chrom［j+1］作為最后一個客戶節(jié)點的路徑。pred保存當前節(jié)點的路徑是從chrom中哪一個客戶開始的（Line 9）。若pred［j］=x，說明客戶chrom［j］所在的路徑是從客戶chrom［x+1］開始的。因此，當算法結束時，從后向前讀取數(shù)組pred，就可以實現(xiàn)路徑的劃分。例如chrom=｛0，2，5，1，3，4｝，pred=｛0，0，0，1，1，2｝。從后向前讀取數(shù)組pred，pred［5］=2，即當前最后一個客戶chrom［4］所在的路徑是從chrom［2+1］開始，即得到路徑0-1-3-4-0，0為虛擬車場。繼續(xù)讀取pred，pred［2］=0，即當前最后一個客戶chrom［2］所在的路徑是從chrom［0+1］開始的，得到路徑0-2-5-0。至此，解碼結束。

算法1：Plot+算法

輸入：待解碼的染色體chrom，客戶數(shù)量N.

1.chrom插入0節(jié)點，新建數(shù)組v，其中v[0]=0，其余元素賦值為正無窮，新建前綴數(shù)組pred，每一個元素賦值為0；

2.fori=1 to N

3.j=i，令當前容量load為0，持續(xù)服務時間cost為0；

4.do

5.讀取chrom[j]，更新load和cost；

6.if load和cost不違反約束

7.vNew=v[i-1]+cost；

8.if vNew＜v[j]或((vNew=v[j])

且(pred[i-1]+1＜pred[j]))

9.更新v[j]=vNew，pred[j]=i-1;

10.end if

11.j=j+1；

12.end if

13.while load和cost滿足約束且j≤N；

14.end for

輸出：前綴數(shù)組pred．

對解碼后得到的每一條路徑，嘗試在當前尚有空余車輛的車場中選擇令總持續(xù)時間最小的車場替換虛擬車場。

3.5 基于高維多目標優(yōu)化算法求解多車場車輛路徑問題

基于高維多目標優(yōu)化算法求解MDVRP的框架如圖3所示。

MO-MDVRP對高維多目標優(yōu)化算法的選擇并不敏感，除了極其有限的額外操作（Line 4），并沒有對所選的算法有任何修改。因此，MO-MDVRP是一個通用的基于高維多目標優(yōu)化求解MDVRP的框架。

算法2：MO-MDVRP

輸入：客戶集合Cus，車場集合Dep，算法終止條件condition．

1.生成初始解集，形成初始種群；

2.dO

3.運用選定的高維多目標優(yōu)化算法對當前種群進行演化；

4.對演化得到的個體進行解碼、評價；

5.根據(jù)所選的高維多目標優(yōu)化算法和上一步的評價結果，生成下一代種群；

6.until滿足condition

輸出：最后一代種群．

本文采用NSGA-III［4］和I-DBEA［5］求解MO-MDVRP。NSGA-III是經典的高維多目標優(yōu)化算法，而I-DBEA是近期發(fā)表的高維多目標優(yōu)化算法。兩者在求解高維多目標優(yōu)化問題上都有出色的效果。關于多目標優(yōu)化算法的詳細描述可參見文獻［14］，這里不再詳述。

4 仿真實驗

本節(jié)選擇NSGA-III［4］和I-DBEA［5］構造MOMDVRP的實例，分別命名為MDVRP-NSGAIII和MDVRP-IDBEA，并進行仿真實驗測試算法效果。

4.1 測試平臺

本文以MOEAFramework為實驗平臺，它是一個用于開發(fā)和測試多目標優(yōu)化算法的開源平臺，提供了豐富的算法和測試接口。本實驗在平臺上對MO-MDVRP進行編碼并調用平臺的NSGA-III和I-DBEA進行問題求解。由于染色體的整型數(shù)組編碼和客戶編號不可遺漏不可重復，NSGAIII和ID?BEA均選用PMX［15］作為交叉算子，并使用隨機插入算子和隨機交換算子作為變異算子。

本實驗的實驗環(huán)境是MOEA Framework 2.11；JDK 8；CPU 2.3GHz；16GB RAM。

4.2 數(shù)據(jù)集及參數(shù)設置

本實驗的數(shù)據(jù)集來自University of Malaga的Networking and Emerging Optimization研究組。該研究組持續(xù)研究各種VRP，并提供了一系列MD?VRP數(shù)據(jù)集。實驗在6個Cordeau數(shù)據(jù)集上進行，數(shù)據(jù)集的基本參數(shù)如表1所示。

實驗中，MDVRP-NSGAIII和MDVRP-IDBEA的最大評價次數(shù)均為106，PMX的交叉分布指數(shù)（Distribution Index）為20，隨機插入算子和隨機交換算子的概率均為0.3，其余參數(shù)取建議值［4～5］。

4.3 性能指標

本文選擇了2個常用的性能指標對MD?VRP-NSGAIII和MDVRP-IDBEA的運算結果進行比較。

表1 測試集的基本參數(shù)

1）逆世代距離（Inverted Generational Dis?tance，IGD）［16］：IGD通過度量算法求得的Pareto前沿與真實Pareto前沿的距離評價算法的優(yōu)劣，是一個同時度量Pareto最優(yōu)解集的收斂性和多樣性的指標。指標值越小越好。

2）超體積（Hypervolume，HV）［17］：HV通過Pa?reto最優(yōu)解集在空間中與參考點圍成的空間大小度量算法的優(yōu)劣，同樣是一個同時度量Pareto最優(yōu)解集的收斂性和多樣性的指標。指標值越大越好。

對算法的各性能指標值進行顯著性檢驗，顯著性水平為0.05。

4.4 實驗結果

實驗中，每個算法在每個數(shù)據(jù)集上獨立運行30次，運行后的結果如表2、表3及圖2～圖7所示。加粗底紋表示該結果顯著優(yōu)于其它對比算法。

表2 各算法在p01-p06上運行30次IGD和HV比較

表3 在p01-p06上運行30次的f1最小值與已知最優(yōu)解比較

從表2可知，在IGD指標上，MDVRP-NSGAIII較MDVRP-IDBEA有明顯的優(yōu)勢，在2/3的數(shù)據(jù)集上顯著地優(yōu)于后者。而在HV指標上，除了p02上MDVRP-NSGAIII更優(yōu)以及p03、p05上MD?VRP-IDBEA更優(yōu)，其余數(shù)據(jù)集上兩者并沒有顯著的差異。從p03可以看出，不同的指標可能對Pare?to最優(yōu)解集的優(yōu)劣給出截然不同甚至矛盾的評價。因而，通過多個指標考察算法性能是十分必要的。圖2～圖7給出了p01-p06目標間兩兩組組合的Pareto前沿。直觀地，在多數(shù)情況下MD?VRP-NSGAIII（灰色）比MDVRP-IDBEA（黑色）更靠近坐標系左下角，意味著MDVRP-NSGAIII較MDVRP-IDBEA更優(yōu)。這與表2的結果一致。

圖2p01的Pareto前沿

圖3p02的Pareto前沿

圖4p03的Pareto前沿

圖5p04的Pareto前沿

圖6p05的Pareto前沿

圖7p06的Pareto前沿

表3給出了算法在f1（即路徑總長度）上找到的最小值、數(shù)據(jù)集給出的已知最優(yōu)解以及兩者的比值。首先，數(shù)據(jù)集并沒有說明已知最優(yōu)解的來源，而不同類算法的結果直接比較是不合適的。此外，MDVRP-NSGAIII和MDVRP-IDBEA并沒有單獨優(yōu)化f1，而是同時優(yōu)化四個目標函數(shù)，得到的是目標間的均衡。因此不能因為沒有得到已知最優(yōu)解而否定MDVRP-NSGAIII和MDVRP-IDBEA。雖然不能直接比較，但是依然可以通過已知最優(yōu)解對MD?VRP-NSGAIII和MDVRP-IDBEA的搜索能力進行討論。在規(guī)模較小的p01，MDVRP-NSGAIII和MD?VRP-IDBEA得到非常接近已知最優(yōu)解的結果。隨著車輛數(shù)、客戶數(shù)的增加，兩種算法的結果與已知最優(yōu)解的差距都有一定程度的上升。這說明，MD?VRP-NSGAIII和MDVRP-IDBEA具有一定的求解高維多目標MDVRP的能力。但是，當問題越發(fā)復雜，算法至少在f1極端解的搜索上會顯得不足。這是因為，無論是NSGAIII還是IDBEA都沒有專門的搜索機制對問題的極端解進行搜索。而對多目標優(yōu)化問題而言，表3中的已知最優(yōu)解就是問題的極端解。這意味著，要得到更接近已知最優(yōu)解的結果，不能單獨依靠高維多目標優(yōu)化算法自己的搜索能力。局部搜索算子，甚至是針對特定目標函數(shù)的局部搜索算子會變得不可或缺。事實上，極端解的更新是有可能推動整個種群的進化、促進Pareto前沿推進的。因此，通過引入局部搜索算子提高算法搜索能力是值得嘗試的。由于數(shù)據(jù)集并未給出其它目標上的已知最優(yōu)解，因此沒有對其它目標值進行比較。

5 結語

針對MDVRP的高維多目標本質，本文構造了基于高維多目標優(yōu)化的MDVRP框架MO-MDVRP，并運用NSGA-III和I-DBEA得到兩個算法實例MDVRP-NSGAIII和MDVRP-IDBEA。實驗表明，MDVRP-NSGAIII和MDVRP-IDBEA求解MO-MD?VRP是可行的；在IGD指標上，MDVRP-NSGAIII較MDVRP-IDBEA具有明顯的優(yōu)勢。

MO-MDVRP并沒有引入任何的局部搜索算子。通過引入局部搜索算子提高算法搜索能力是值得嘗試的。然而，正如不同的性能指標對算法評價不同，不同的局部搜索算子對各個目標函數(shù)的影響可能也大相徑庭。如何設計局部搜索算子以便最大限度地提高算法的搜索能力是后續(xù)研究中需要解決的問題。

［1］G Dantzig，J Ramser.The truck dispatching problem［J］. Management Science，1959，6（8）：80-91.

［2］J R Montoya-Torres，J L Franco，S N Isaza，H F Jiménez，N Herazo-Padilla.A literature review on the vehicle rout?ing problem with multiple depots［J］.Computers&Indus?trial Engineering，2015，79：115-129.

［3］R Tavakkoli-Moghaddam，A Makui，Z Mazloomi.A new integrated mathematical model for a bi-objective multi-de?pot location-routing problem solved by a multi-objective scatter search algorithm［J］.Journal of Manufacturing Sys?tems，2010，29（2）：111-119.

［4］K Deb，H Jain.An evolutionary many-objective optimiza?tion algorithm using reference-point-based nondominated sorting approach，part I：Solving problems with box con?straints［J］.IEEE Transactions on Evolutionary Computa?tion，2014，18（4）：577-601.

［5］M Asafuddoula，T Ray，R Sarker.A decomposition-based evolutionary algorithm for many-objective optimization［J］.IEEE Transaction on Evolutionary Computation，2015，19（3）：445-460.

［6］L Calvet，A Ferrer，M I Gomes，A A Juan，D Masip.Com?bining statistical learning with metaheuristics for the multi-depot vehicle routing problem with market segmen?tation［J］.Computers&Industrial Engineering，2016，94：93-104.

［7］J W Escobar，R Linfati，P Toth，M G Baldoquin.A hybrid granular tabu search algorithm for the multi-depot vehicle routing problem［J］.Journal of Heuristics，2014，20（5）：483-509.

［8］S Ray，A Soeanu，J Berger，M Debbabi.The multi-depot split-delivery vehicle routing problem：Model and solu?tion algorithm［J］.Knowledge-Based Systems，2014，71：238-265.

［9］A Rahimi-Vahed，T G Crainic，M Gendreau，W Rei. Fleet-sizing for multi-depot and periodic vehicle routing problems using a modular heuristic algorithm［J］.Comput?ers&Operations Research，2015，53：9-23.

［10］T Vidal，T G Crainic，M Gendreau，C Prins.Implicit de?pot assignments and rotations in vehicle routing heuristics［J］.European Journal of Operational Research，2014，237（1）：15-28.

［11］J Li，Y Li，P M Pardalos.Multi-depot vehicle routing problem with time windows under shared depot resources［J］.Journal of Combinatorial Optimization，2014，31（2）：515-532.

［12］R Liu，Z Jiang，R Y K Fung，F(xiàn) Chen，X Liu.Two-phaseheuristic algorithms for full truckloads multi-depot ca?pacitated vehicle routing problem in carrier collaboration［J］.Computers&Operations Research，2010，37（5）：950-959.

［13］鄧欣.基于遺傳算法的多車場車輛路徑問題研究［D］.重慶：重慶大學，2007. GENG Xin.Research on Multiple Depot Vehicle Routing Problem Based on Genetic Algorithm［D］.Chongqing：Chongqing University，2007.

［14］公茂果，焦李成，楊咚咚，等.進化多目標優(yōu)化算法研究［J］.軟件學報，2009，20（2）：271-289. GONG Maoguo，JIAO Licheng，YANG Dongdong，et al. Research on Evolutionary Multi-Objective Optimization Algorithms［J］.Journal of Software，2009，20（2）：271-289.

［15］D E Goldberg，Jr R Lingle.Alleles，loci，and the travel?ing salesman problem［C］//Proceedings of the 1st Interna?tional Conference on Genetic Algorithms，154-159.

［16］Q Zhang，H Li.MOEA/D：A multiobjective evolutionary algorithm based on decomposition［J］.IEEE Trans.on Evolutionary Computation，2007，11（6）：712-731.

［17］M L E，Zitzler，L Thiele.SPEA2：Improving the strength pareto evolutionary algorithm［C］//Evolutionary Methods for Design，Optimization and Control with Applications to Industrial Problems，K Giannakoglou，D T Tsahalis，J Periaux，K D Papailiou，T Fogarty，Eds.，2002，95-100.

Multiple Depot Vehicle Routing Problem Based on Many-Objective Optimization

BI ZhishengZHENG JiongbinCAI Guiyan
（School of Basic Science，Guangzhou Medical University，Guangzhou511436）

Vehicle routing problem is a well-known NP problem in operations research，which has important practical signifi?cance in transportation field.As one of the important branches，multi-depot vehicle routing problem has been widely studied as a single-objective optimization problem and a multi-objective optimization problem.However，multi-depot vehicle routing problem is essentially a many-objective optimization problem.Therefore，in view of the nature of the problem，four optimization functions are inspected from the view of logistics enterprise and customer.Next，multi-depot vehicle routing problem based on many-objective op?timization is proposed.Then，a framework called MO-MDVRP is constructed for this problem.After that，instances of this frame?work based on NSGA-III and I-DBEA are proposed，namely MDVRP-NSGAIII and MDVRP-IDBEA.The algorithms are tests on six Cordeau datasets.The experiments show that MDVRP-NSGAIII and MDVRP-IDBEA are feasible in solving MO-MDVRP.And MDVRP-NSGAIII is more effective than MDVRP-IDBEA in these datasets.

vehicle routing problem，multi-depot，many-objective optimization

TP391

10.3969/j.issn.1672-9722.2017.07.013

2017年1月5日，

2017年2月11日

國家自然科學基金（編號：61603106）；廣州市市屬高校科研項目（編號：1201630320）；廣州市教育科學規(guī)劃課題（編號：1201553242）；廣州醫(yī)科大學科學科研項目（編號：L135042）資助。

畢志升，男，博士，講師，研究方向：計算智能和數(shù)據(jù)挖掘。鄭炯彬，男，碩士研究生，研究方向：數(shù)據(jù)挖掘。蔡桂艷，女，碩士，講師，研究方向：數(shù)據(jù)挖掘。