畢志升蔡茗芊

基于多目標(biāo)模擬退火的帶容量限制車輛路徑問題?

畢志升蔡茗芊

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

車輛路徑問題是運籌學(xué)中著名的NP問題。帶容量限制的車輛路徑問題作為最基本的車輛路徑問題，其研究對其它類型的車輛路徑問題具有重要的借鑒作用。論文首先從物流企業(yè)和客戶兩個不同的角度考察4個優(yōu)化目標(biāo)，將帶容量限制的車輛路徑問題推廣到高維多目標(biāo)領(lǐng)域。然后運用基于Pareto支配接受準(zhǔn)則的多目標(biāo)模擬退火算法在單數(shù)組和多數(shù)組兩種不同的編碼方式下進行求解，并通過實驗分析對比兩種編碼方式的優(yōu)劣。在9個Augerat數(shù)據(jù)集上的實驗結(jié)果表明，單數(shù)組編碼方式在IGD和HV指標(biāo)下不如多數(shù)組編碼方式。單數(shù)組編碼方式得到的Pareto解集具有更好的多樣性，而多數(shù)組編碼方式得到的Pareto解集具有更好的收斂性。

車輛路徑問題；容量限制；高維多目標(biāo)優(yōu)化

Class NumberTP391

1引言

車輛路徑問題（Vehicle Routing Problem，VRP）是Dantzig和Ramser［1］于1959年提出的運籌學(xué)領(lǐng)域中著名的NP問題。它通過設(shè)計合理的車輛路線，期望以最小的運輸成本，為不同的客戶配送不同的貨物。時至今日，VRP的研究成果已經(jīng)被廣泛應(yīng)用于現(xiàn)實生活，為物流配送、巴士路線規(guī)劃等［2］現(xiàn)實問題的求解提供理論依據(jù)，具有重要的現(xiàn)實意義。

帶容量限制的車輛路徑問題（Capacitated Ve?hicle Routing Problem，CVRP）是最基本的車輛路徑問題。它僅僅考慮車輛具有載貨量限制。由于這個約束被帶時間窗車輛路徑問題、多車場車輛路徑問題等衍生VRP廣泛采用，使得CVRP成為其它類型VRP的基礎(chǔ)。因而，CVRP的研究成果對其它類型的VRP具有重要的借鑒意義。

近年來，VRP受到越來越多國內(nèi)外學(xué)者的關(guān)注。當(dāng)前對VRP的研究主要基于單目標(biāo)優(yōu)化［3］。然而，VRP本質(zhì)上是一個目標(biāo)數(shù)大于3的高維多目標(biāo)優(yōu)化問題。例如，物流企業(yè)為了減少成本和提高利用率，追求車輛少、運輸路線短、工作量均衡；而客戶期望更快收到貨物，要求等待時間短。這些目標(biāo)之間是存在矛盾的。減少車輛雖然能有效減少由硬件維護和人力資源帶來的成本，卻增加了每輛車需要服務(wù)的客戶數(shù)量，導(dǎo)致客戶需要等待更長的時間。因而，物流企業(yè)需要在諸多目標(biāo)上進行取舍。不同的取舍能產(chǎn)生不同的解決方案，產(chǎn)生一組對應(yīng)不同取舍的均衡解是物流企業(yè)根據(jù)自身情況選擇實施方案的前提。基于多目標(biāo)優(yōu)化能在不固定取舍的前提下同時產(chǎn)生一組均衡解，因此，基于多目標(biāo)優(yōu)化求解CVRP是符合企業(yè)需要、具有現(xiàn)實意義的。

本文通過考察4個優(yōu)化目標(biāo)將CVRP推廣到高維多目標(biāo)領(lǐng)域。然后采用兩種不同的編碼方式對問題進行建模，并運用基于Pareto支配接受準(zhǔn)則的多目標(biāo)模擬退火算法（Multiobjective Simulated An?nealing Using Pareto-Domination Based Acceptance Criterion，PDMOSA）［4］進行求解。最后通過實驗對兩種不同的編碼方式進行對比分析。

2帶容量限制的車輛路徑問題

一般地，CVRP可以定義為［2］：有1個擁有K輛車的車場，每輛車容量為Q。有N個客戶需要貨物配送?？蛻鬷的貨物容量為gi且gi＜Q。客戶可以由任意車輛服務(wù)，但只能被服務(wù)一次。在不超出容量限制的情況下，每輛車離開車場可以為多個客戶提供服務(wù)。服務(wù)結(jié)束后車輛返回車場。

記節(jié)點0為車場節(jié)點；節(jié)點{1，2，…，N}為客戶節(jié)點；k為車場的第k輛車；從節(jié)點i到節(jié)點j的距離為dij；R為一組滿足約束的路徑集合，對應(yīng)問題的一個解。R中每一條路徑都是一條以車場為起點、以車場為終點的環(huán)路，由一輛車提供服務(wù)。令

則CVRP可形式化描述為

其中，i∈{1，2，…，N}，k∈{1，2，…，K}，F(xiàn)是目標(biāo)函數(shù)，通常選擇路徑長度或在其基礎(chǔ)上結(jié)合車輛數(shù)等其他因素構(gòu)造目標(biāo)函數(shù)［5］；式（4）是容量限制；式（5）是保證每個客戶都被服務(wù)且僅被服務(wù)一次。

近五十年，CVRP一直是一個研究熱點［2，5］。然而，CVRP的求解還遠(yuǎn)遠(yuǎn)沒有達(dá)到令人滿意的程度［2］。由于CVRP是VRP中最基礎(chǔ)的問題，而VRP在現(xiàn)實生活中的應(yīng)用也越發(fā)廣泛，其研究還將長期持續(xù)。

3基于高維多目標(biāo)優(yōu)化的帶容量限制車輛路徑問題

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

3.1基于Pareto支配接受準(zhǔn)則的多目標(biāo)模擬退火算法

本文選擇PDMOSA求解CVRP。PDMOSA是一種單點搜索算法。相比基于種群的搜索算法，單點搜索算法立足于鄰域搜索，在求解VRP問題上具有優(yōu)勢［6］。

PDMOSA是Suman［4］在2004年提出的多目標(biāo)模擬退火算法。不同于其它利用目標(biāo)函數(shù)值計算接受概率的模擬退火算法，該算法提出了基于Pa?reto支配的適應(yīng)度用于計算接受概率。Pareto支配的適應(yīng)度等于支配當(dāng)前解的非劣解個數(shù)加1。顯然，適應(yīng)度越大解越差。PDMOSA算法如算法1所示。

關(guān)于多目標(biāo)優(yōu)化算法的詳細(xì)描述可參見文獻［7］，這里不再詳述。

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

本文分別從物流企業(yè)和客戶的角度設(shè)定4個優(yōu)化目標(biāo)：1）從物流企業(yè)的角度考慮，考察路徑總長度、車輛數(shù)、最大容量差。其中最大容量差為各車輛實際容量的最大值與最小值之差。2）從客戶的角度考慮，考察客戶的等待時間。客戶等待時間定義為沿著路徑從車場到客戶之間的路徑長度。例如路徑0-6-2-0，第一個客戶節(jié)點6的等待時間是節(jié)點0到節(jié)點6之間的距離，第二個客戶節(jié)點2的等待時間是節(jié)點0到節(jié)點6再到節(jié)點2的總距離，如此類推。記R中路徑數(shù)量為|R|，每一條路徑上的客戶等待時間為wr。則，R中客戶等待時間為

故，該CVRP可形式化描述為

其中，i∈{1，2，…，N}，k∈{1，2，…，K}，wr是R中第r條路徑的等待時間；式（6）是最小化總路徑長度；式（7）是最小化車輛數(shù)；式（8）是最小化最大容量差；式（9）是最小化客戶等待時間。問題約束如第2節(jié)所述。

3.3染色體編碼

染色體編碼是求解CVRP的過程中對解的一種表示方式，每一個編碼代表一個解。通常采用數(shù)組和節(jié)點的編號進行編碼。常用的編碼方式有兩種：單數(shù)組編碼和多數(shù)組編碼。

1）單數(shù)組編碼

采用長度為N的整型數(shù)組對染色體進行編碼，N為客戶的數(shù)量。數(shù)組以客戶的編號作為數(shù)組的元素，每個編號出現(xiàn)且僅出現(xiàn)一次。以一個有15個客戶的CVRP的解為例，如圖1。采用單一數(shù)組編碼可以表示為chrom=｛13，2，15，5，14，4，8，3，10，9，6，7，12，11，1｝。由于僅僅采用1個數(shù)組，而解由多個路徑組成，因此編碼時需要將各個路徑拼接起來。這種編碼的優(yōu)點在于編碼長度是一個僅與客戶數(shù)量有關(guān)的定值，為算法的搜索提供了便利。然而，這種編碼并未記錄路徑的劃分情況，因而需要額外的路徑劃分技術(shù)，將染色體重新劃分為路徑。

圖1 CVRP的一個解

2）多數(shù)組編碼

多數(shù)組編碼與單數(shù)組編碼的區(qū)別在于，對每一條路徑，多數(shù)組編碼采用一個數(shù)組單獨表示。數(shù)組的數(shù)量等于路徑的數(shù)量，數(shù)組的長度等于該路徑服務(wù)的客戶的數(shù)量。例如，圖2所示的解將被4個數(shù)組表示，分別是｛13，2，15，5，14｝、｛4，8｝、｛3，10，9，6｝和｛7，12，11，1｝（此處不記錄車場）。相比單數(shù)組編碼，該方法能有效區(qū)分各個不同的路徑，無須額外的路徑分割技術(shù)。然而，不同的解可能擁有不同的數(shù)組數(shù)量和長度，導(dǎo)致解集中同時存在多種不同的結(jié)構(gòu)，算法的搜索也因此不如單數(shù)組便利。

3.4鄰域搜索策略

不同的編碼方式采用不同的鄰域搜索策略。

1）單數(shù)組編碼的鄰域搜索

在染色體中隨機選擇一個客戶，并插入到另一個隨機選擇的位置中。

鄰域搜索之后要將染色體重新劃分成路徑。本文采用Plot算法［8］對染色體進行解碼，見算法2所示。

在解碼前，首先在染色體前插入一個0節(jié)點。在Plot中，采用以下策略構(gòu)造路徑：嘗試構(gòu)造一條從客戶chrom［i］開始的路徑。如果不違反容量限制，則嘗試將下一個客戶節(jié)點納入當(dāng)前路徑，直到違反約束或沒有剩余客戶節(jié)點（Line 13）。若違反容量約束，則嘗試構(gòu)造從客戶chrom［i］開始的路徑。到客戶chrom［i-1］為止的路徑長度由v［i-1］保存（Line 7）。在構(gòu)造過程中，cost對應(yīng)的是以客戶chrom［i］為第一個客戶、以客戶chrom［j］為最后一個客戶的路徑長度，是當(dāng)前正在構(gòu)造的路徑（Line 6）。Line 8中if為真，則將當(dāng)前客戶chrom［j］添加到當(dāng)前路徑，即構(gòu)造了一條以chrom［i］為第一個客戶節(jié)點、以chrom［j］為最后一個客戶節(jié)點的路徑。該方案較原方案（對應(yīng)v［j］）的總路徑更短，或路徑等長但能使前一條路徑服務(wù)更多的客戶，即車輛容量的利用更充分。如果if為假，意味著原方案更優(yōu)，并在下一次循環(huán)中（Line 4～Line 13）嘗試構(gòu)造以chrom［i］為第一個客戶節(jié)點、以chrom［j+1］為最后一個客戶節(jié)點的路徑。路徑的第一個客戶節(jié)點信息由數(shù)組pred保存。若pred［j］=x，說明客戶chrom［j］所在的路徑是以客戶chrom［x+1］開始。當(dāng)路徑劃分完畢，最后一個客戶所在的路徑以chrom［pred［N］+1］為第一個客戶。而以chrom［pred［N］］為最后一個客戶的路徑以chrom［pred［pred［N］］+1］為第一個客戶。如此向前構(gòu)造路徑，直到chrom的第一個客戶節(jié)點。例如chrom=｛0，2，5，4， 1，3｝，pred=｛0，0，0，0，1，2｝。從后向前讀取數(shù)組pred，pred［5］=2，即當(dāng)前最后一個客戶chrom［5］所在的路徑是以chrom［2+1］為第一個客戶，即得到路徑0-4-1-3-0，0為車場。繼續(xù)讀取pred。當(dāng)前最后一個客戶節(jié)點是chrom［2］。pred［2］=0，即客戶chrom［2］所在的路徑是以chrom［0+1］為第一個客戶的，得到路徑0-2-5-0。至此，解碼結(jié)束。

顯然，這種鄰域搜索算法雖然僅僅改變了一個客戶節(jié)點的位置，但由于解碼算法的作用，插入的客戶節(jié)點不僅僅改變當(dāng)前路徑的貨物總?cè)萘亢烷L度，還有可能由于部分客戶節(jié)點被順延到下一條路徑，使得后續(xù)路徑也發(fā)生變化。因而，鄰域搜索的力度較大。另一方面，解碼算法追求路徑最短的同時追求車輛容量的最大化，因此有利于最小化路徑總長度和車輛數(shù)，但不利于最小化最大容量差。

2）多數(shù)組編碼的鄰域搜索

在多數(shù)組編碼中，每個數(shù)組代表一條路徑。隨機選擇一條路徑中的一個客戶，插入到隨機選擇的另一條路徑的一個隨機位置。

這種鄰域搜索不能保證被插入客戶的路徑依然滿足容量約束。若約束無法滿足，采用以下策略進行修補：對該路徑中的每一個客戶節(jié)點，若刪除該節(jié)點后車輛容量滿足約束，則計算刪除該節(jié)點帶來的路徑長度變化，按變化從大到小排序，得到序列ListN。對其余路徑，計算剩余容量，按剩余容量從大到小進行排序，得到序列ListR。選擇ListN中第1個客戶節(jié)點，嘗試添加到ListR的第1條路徑中。如果客戶節(jié)點的貨物超過路徑的剩余容量，不允許插入，嘗試下一條路徑；若所有路徑均插入失敗，選擇ListN中第2個客戶節(jié)點，繼續(xù)上述嘗試，直到允許插入。若允許插入，計算所有可能的插入點，選擇插入后路徑最短的插入位置。若所有節(jié)點對于所有路徑均不允許插入，新建一條路徑，該路徑僅有ListN中的第1個客戶節(jié)點。

在無須修補的情況下，該鄰域搜索僅僅改變兩條路徑，其余路徑不受影響。即使需要修補，受影響的路徑也僅有3條。因而，相比單數(shù)組編碼，鄰域搜索的力度較小。另一方面，除了修補時新建路徑，路徑的數(shù)量不會增加。而短路徑有可能在鄰域搜索的隨機選擇中被選中移出客戶節(jié)點，最終越來越短并消失。故該算法有利于最小化車輛數(shù)，車輛數(shù)的變化也相對穩(wěn)定。但是，這也導(dǎo)致車輛數(shù)的多樣性不足。此外，這種鄰域搜索方法對路徑長度的考量僅僅局限于超重路徑和超重后被插入節(jié)點的路徑，因而在優(yōu)化路徑長度上缺乏全局性。

4仿真實驗

本節(jié)運用PDMOSA［4］求解CVRP。針對單數(shù)組編碼方式，構(gòu)造算法實例CVRP-S；針對多數(shù)組編碼方式，構(gòu)造算法實例CVRP-M。

4.1測試平臺

本文以MOEAFramework（http：//moeaframe?work.org/index.html）為實驗平臺，它是一個用于開發(fā)和測試多目標(biāo)優(yōu)化算法的開源平臺，提供了豐富的測試接口。

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

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

本實驗的數(shù)據(jù)集來自University of Malaga的Networking and Emerging Optimization研究組（http：//neo.lu.uma.es/vrp/vrp-instances）。該研究組持續(xù)研究各種VRP，并提供了一系列CVRP數(shù)據(jù)集。實驗在9個Augerat數(shù)據(jù)集進行，數(shù)據(jù)集的基本參數(shù)如表1所示。

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

參照文獻［4］的建議值，實驗中PDMOSA的初溫為3000，降溫系數(shù)為0.98，內(nèi)循環(huán)次數(shù)為50次，外循環(huán)次數(shù)為3000次。

4.3性能指標(biāo)

本文選擇了2個常用的性能指標(biāo)對算法的運算結(jié)果進行比較：

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

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

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

4.4實驗結(jié)果

實驗中，每個算法在每個數(shù)據(jù)集上獨立運行30次，運行結(jié)果如表2和圖2所示。加粗底紋表示算法在該指標(biāo)下顯著優(yōu)于其它對比算法。

從表2可知，CVRP-S除了在A-n32-k5和A-n55-k9上IGD指標(biāo)下較優(yōu)，B-n31-k5上IGD指標(biāo)下沒有顯著差異，其余情況均不如CVRP-M。這意味著，從總體而言，CVRP-S不如CVRP-M。由于IGD和HV同時度量收斂性和多樣性，表2無法對收斂性和多樣性作更深入的分析。本文通過每個目標(biāo)函數(shù)值的盒圖，從另一個角度分析算法的結(jié)果。通過圖3中A-n55-k9實驗結(jié)果在各目標(biāo)函數(shù)上的盒圖可以發(fā)現(xiàn)，CVRP-S的Pareto解集在各個目標(biāo)上的四分位數(shù)極差均大于CVRP-M。特別地，CVRP-M在車輛數(shù)（f2）上幾乎所有Pareto解均得到同樣的函數(shù)值。雖然兩個算法在各目標(biāo)函數(shù)取得極值的數(shù)量差不多，但CVRP-S在其極值附近的分布明顯比CVRP-M密集。其它數(shù)據(jù)集的盒圖也反映出類似的結(jié)果。這意味著，在Pareto解集的多樣性上CVRP-S優(yōu)于CVRP-M。CVRP-S在IGD和HV指標(biāo)上不如CVRP-M更多的是因為其Pareto解集的收斂性弱。

表2 各算法在9個數(shù)據(jù)集上運行30次IGD和HV比較

圖2 A-n32-k5上各目標(biāo)函數(shù)值的盒圖

5結(jié)語

本文通過考察4個與物流企業(yè)和客戶密切相關(guān)的目標(biāo)函數(shù)，將CVRP推廣到的高維多目標(biāo)領(lǐng)域，并運用PDMOSA進行求解。在求解過程中，采用了單數(shù)組和多數(shù)組兩種不同的編碼方式，并給出了相應(yīng)的鄰域搜索策略。實驗分析表明，在IGD和HV指標(biāo)上，采用單數(shù)組編碼的CVRP-S不如采用多數(shù)組編碼的CVRP-M。CVRP-S能獲得多樣性更好的Pareto解集，而CVRP-M能獲得收斂性更好的Pareto解集。

本文采用的鄰域搜索策略對目標(biāo)函數(shù)具有較明顯的偏向。例如多數(shù)組編碼下，車輛數(shù)的多樣性很差。這在實際應(yīng)用中將影響物流企業(yè)對最終實施方案的選擇。后續(xù)的研究需要提出更為有效的局部搜索策略，在提高Pareto解集收斂性的同時，減少搜索策略的偏向，以期獲得多樣性更好的Pa?reto解集。

［1］G Dantzig，J Ramser.The Truck Dispatching Problem［J］. ManagementScience，1959，6（8）：80-91.

［2］S Akpinar.Hybrid Large Neighbourhood Search Algorithm for Capacitated Vehicle Routing Problem［J］.Expert Sys?tems with Applications，2016，61：28-38.

［3］T Sooktip，N Wattanapongsakorn.Identifying Preferred Solutions for Multi-Objective Optimization：Application to Capacitated Vehicle Routing Problem［J］.Cluster Com?puting，2015，18（4）：1435-1448.

［4］B Suman.Study of Simulated Annealing Based Algorithms for Multiobjective Optimization of a Constrained Problem［J］.Computers&Chemical Engineering，2004，28（9）：1849-1871.

［5］K Braekers，K Ramaekers，IVan Nieuwenhuyse.The Ve?hicle Routing Problem：State of The Art Classification and Review［J］.Computers&Industrial Engineering，2016，99：300-313.

［6］J Wang，Y Zhou，Y Wang，J Zhang，C L P Chen，Z Zheng.Multiobjective Vehicle Routing Problems with Si?multaneous Delivery and Pickup and Time Windows：For?mulation，Instances，and Algorithms［J］.IEEE Transac?tions on Cybernetics，2016，46（3）：582-594.

［7］公茂果，焦李成，楊咚咚，等.進化多目標(biāo)優(yōu)化算法研究［J］.軟件學(xué)報，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.

［8］鄧欣.基于遺傳算法的多車場車輛路徑問題研究［D］.重慶：重慶大學(xué)，2007.

GENG Xin.Research on Multiple Depot Vehicle Routing Problem Based on Genetic Algorithm［D］.Chongqing：Chongqing University，2007.

［9］Q Zhang，H Li.MOEA/D：A Multiobjective Evolutionary Algorithm Based on Decomposition［J］.IEEE Transac?tions on Evolutionary Computation，2007，11（6）：712-731.

［10］E Zitzler，M Laumanns，L Thiele.SPEA2：Improving the Strength Pareto Evolutionary Algorithm［C］//Evolution?ary Methods for Design，Optimization and Control with Applications to Industrial Problems（EUROGEN 2001）. K Giannakoglou，D T Tsahalis，J Periaux，K D Papail?iou，T Fogarty，Eds.，Athens，Greece：International Center for Numerical Methods in Engineering，2002，95-100.

Capacitated Vehicle Routing Problem Based on Multi-Objective Simulated Annealing

BI Zhisheng CAI Mingqian
（Schoolof Basic Science，Guangzhou MedicalUniversity，Guangzhou 511436）

Vehicle routing problem is a well-known NP problem in operations research.As the mostbasic vehicle routing prob?lem，the research of capacitated vehicle routing problem has important reference for other types of vehicle routing problems.In this paper，four optimization functions are firstly inspected from the view oflogistics enterprise and customer，which extends the capaci?tated vehicle routing problem to many-objective field.Then，the multiobjective simulated annealing using Pareto-domination based acceptance criterion is used to solve this problem under single-array encoding and multi-array encoding.The advantages and disad?vantages ofthese two methods are analyzed with experiment.The experiments on nine Augeratdatasets show thatthe single-array en?coding method is better than the multi-array encoding method with the measure of IGD and HV.The Pareto setobtained by the sin?gle-array encoding method has better diversity and worse convergence than thatobtained by the multi-array encoding method.

vehicle routing problem，capacitated，many-objective optimization

TP391

10.3969/j.issn.1672-9722.2017.08.012

2017年3月17日，

2017年4月21日

國家自然科學(xué)基金（編號：61603106）；廣州市市屬高校科研項目（編號：1201630320）；廣州醫(yī)科大學(xué)科學(xué)科研項目（編號：L135042）資助。

畢志升，男，博士，講師，研究方向：計算智能和數(shù)據(jù)挖掘。蔡茗芊，女，研究方向：數(shù)據(jù)挖掘。