李 琳，孟 嬌，陳 瑩

(沈陽航空航天大學 理學院，沈陽 110136)

隨著B2C電子商務的不斷發(fā)展，高效的物流服務在客戶的采購決策中發(fā)揮著越來越重要的作用。車輛路徑問題(Vehicle Routing Problem,VRP)是物流行業(yè)發(fā)展過程中的重要組成部分，引起了該領域許多專家的關注。在B2C電子商務環(huán)境下，人們可以通過各種組合方式尋求物流配送過程的優(yōu)化，使貨物在實際運輸過程中達到配送效率最高、配送費用最少、運輸距離最短、配送時間最少的目標?，F(xiàn)實生活中關于VRPMB的應用非常廣泛，如：汽車制造商向供應商提供和回收零部件、半導體供應鏈分銷網(wǎng)絡中晶片的取貨與送貨過程、圖書館圖書的發(fā)送與回館問題等等。實踐證明，降低物流配送費用、提高服務效率及質(zhì)量、提高環(huán)保產(chǎn)業(yè)的市場需求不僅對企業(yè)具有十分重要的意義，對推動人類環(huán)保事業(yè)的發(fā)展同樣也具有重大意義。

混合帶回程取貨的車輛路徑問題(VRPMB)是在傳統(tǒng)的VRP上增加了回程取貨服務，客戶可以是需要送貨的，也可以是需要取貨的，送貨的客戶和取貨的客戶可以是任意的、混合的。許多學者建立了VRP及VRPMB的數(shù)學模型[1-5]，并設計了相關算法求解該問題，如： Florian[1]結合了三種強大的局部搜索算法，三個互補的局部搜索算法使用順序搜索和精簡的想法并以有效的方式實現(xiàn)它們，由此產(chǎn)生的啟發(fā)式算法可在幾秒或幾分鐘內(nèi)為各種基準測試實例計算高質(zhì)量的解決方案，進而解決車輛路徑問題。對于VRPMB問題，Kalayci[2]等人提出一種基于蟻群系統(tǒng)(Ant Colony System,即ACS)和變鄰域搜索(Variable Neighborhood Search,即VNS)的混合元啟發(fā)式算法。VNS是一種功能強大的優(yōu)化算法，可提供密集的局部搜索，但它缺乏內(nèi)存結構，通過利用ACS的長期存儲器結構可以最小化這種弱點。因此可將它們組合在一起克服彼此的缺陷，從而提高算法的整體性能。Belgin[3]等人提出了一種基于混合啟發(fā)式算法的變鄰域下降算法(Variable Neighborhood Descent,即VND)和局部搜索算法(Local Search,即LS)，實驗分析表明，混合啟發(fā)式方法VND_LS對于找到同時取貨和送貨的雙梯車輛路徑問題的良好解是有效且高效的。Ahkamiraad[4]等提出一種基于遺傳算法(Genetic Algorithm,即GA)和粒子群優(yōu)化算法(Particle Swarm Optimization,即PSO)的混合算法，實驗結果表明，在解決VRPMB時所提出的混合算法得到的解均是有效且高效的。

預售模式是以客戶的需求來驅(qū)動商家生產(chǎn)，即利用B2C網(wǎng)絡平臺，提前一段時間發(fā)布產(chǎn)品信息，并在短時間內(nèi)快速聚集單個分散的客戶需求訂單，然后給發(fā)貨中心匯集一個大訂單，發(fā)貨中心可從供應鏈的前端、后端進行優(yōu)化，從而更加精確地鎖定訂單，打包配送貨物，從而大大降低物流成本。簡言之，預售模式就是先收集客戶需求訂單，然后再進行流通和配送。

本文在傳統(tǒng)的物流配送模式下引入了預售模式的概念，在預售期結束后某一時刻對訂單進行打包配送，進而節(jié)省物流成本。建立了相應的數(shù)學模型，目標函數(shù)是為每輛車尋找一條合適的行駛路線，以便盡可能降低物流成本來滿足客戶取貨和送貨的要求。本文將K-均值聚類算法(K-means)和禁忌搜索算法(TS)相結合求解VRPMB，并與文獻中的結果進行比較，實驗結果驗證了該混合算法的有效性。

1 VRPMB數(shù)學模型

VRPMB可描述為一個配送中心最多可用m輛車訪問n個客戶。每個客戶必須被訪問，目標是尋找起止配送中心且滿足車輛容量限制的服務路徑，以便最小化費用函數(shù)。0表示配送中心，可用車輛集合K={1,2，…，m}，所有客戶點和配送中心的集合V={0,1,2…,n}，邊集合E={(i,j)|i,j∈V}，客戶i送貨需求為di，客戶i取貨需求為pi，車輛容量限制為CK，車輛的初始容量為b0k，服務顧客i之后的車輛剩余容量為bi+1，兩點間的配送距離為cij，車輛均為同質(zhì)型車輛，故設單位車輛固定使用成本為F。

數(shù)學模型為

(1)

s.t.

(2)

(3)

(4)

(5)

bi+1=bi-di+piCK,?i∈V/{0}

(6)

yik∈{0,1},?i∈V/{0},?k∈K

不同融資渠道分別可以用于建設、運營、規(guī)劃，且彼此不能混同。對于特定融資渠道用于再生水項目的融資份額一般也規(guī)定上限。對于基金的資金回收和持續(xù)運行實行謹慎的管理，對于各類融資適用于再生水項目的條件、申請程序等都有嚴格的法律規(guī)定。

(7)

xijk∈{0,1},?i,j∈V,?k∈K

(8)

決策變量為

xijk=

式(1)為目標函數(shù)，即最小化車輛行駛成本與車輛固定成本之和，約束(2)為車輛從配送中心出發(fā)的送貨容量約束，約束(3)是每個客戶只能被一輛車服務，約束(4)是車輛k從配送中心出發(fā)時的初始載重，為路徑上所有客戶的需求量之和，約束(5)是保證進入和駛出每個客戶的車輛數(shù)相同，約束(6)是服務完客戶i之后，車輛剩余載重量不能超過車輛的容量限制，式(7)和式(8)為決策變量。

2 求解VRPMB的算法設計

VRP是一個NP-hard問題，VRPMB亦是一個NP-hard問題，很難在較短的時間內(nèi)獲得全局最優(yōu)解，本文采用啟發(fā)式算法進行求解。禁忌搜索算法是一種元啟發(fā)式算法，是對局部搜索算法的擴展，它是解決復雜車輛路徑問題的一種非常有效的方法。Qiu[6]、符卓[7]等人利用禁忌算法求解VRPMB，并取得了一些研究成果。邱萌[8]對于需求可離散拆分的問題，采用禁忌搜索算法求解，取得了很好的搜索性能。殷佳林[9]等人提出一種蟻群算法與禁忌搜索算法的新混合算法，提高了全局搜索能力，加快了收斂速度。禁忌搜索算法的基本思想是防止重復并禁止或懲罰下一步驟中的重復。禁忌搜索算法的基本組成部分是一個起始解、移動機制、鄰域、禁忌表長度、禁忌列表、禁忌特赦準則和終止準則。

2.1 初始解的設定

禁忌搜索算法対初始解有一定的依賴性，一個高質(zhì)量的初始解[10]能夠幫助禁忌搜索算法在解空間中找到一個最終的高質(zhì)量解決方案，提升禁忌搜索算法的收斂速度?？梢允褂貌煌慕鉀Q方法來獲得初始解決方案。這些結果是可以隨機得到的，也可以用啟發(fā)式方法得到一個初始解。本文采用K-means算法得到了有效的初始解。經(jīng)典的K-means算法[11]是給定一個數(shù)據(jù)點集合和需要的聚類數(shù)目，由用戶指定，根據(jù)某個距離函數(shù)反復把數(shù)據(jù)分入幾個聚類中，但K-means算法是不帶約束的算法，因而不能直接將其應用于VRPMB。本文設計的K-means算法，在對客戶點進行聚類時，需要考慮客戶點的需求總量不能超過車輛的最大運載容量。若某一簇的客戶需求總量達到車輛最大運載容量時，其他客戶便選擇次近的簇加入其中，目的是將距離相近的客戶規(guī)劃在同一條路線上，由一輛車服務，以達到節(jié)約運輸成本的目的。

假設給定數(shù)據(jù)樣本X，包含了n個對象X={X1,X2,…,Xn}，其中每個對象都具有m個維度的屬性。Xi表示第i個對象(1≤i≤n)，Oj表示第j個聚類中心(1≤j≤k)，Xit表示第i個對象的第t個屬性(1≤t≤m)，Ojt表示第j個聚類中心的第t個屬性。|Sj|表示第j個類簇中對象的個數(shù)，Xij表示第j個類簇中第i個對象(1≤i≤|Sj|)。

具體算法步驟如下：

(1)從數(shù)據(jù)集pi=0中隨機選取k個元素，作為k個簇的初始聚類中心；

(4)將數(shù)據(jù)集D中全部元素在容量限制的條件下，按照新的中心重新聚類；

(5)重復(4)，直到聚類結果不再變化；

(6)輸出結果。

2.2 鄰域操作及候選集的確定

本文采用兩交換法[12]得到鄰域解。兩交換法是指隨機地交換兩個客戶點的基本信息。交換可以是一條路徑內(nèi)兩個客戶點的交換，2-交換法路徑內(nèi)交換方式如圖1所示。也可以是兩條不同路徑的兩個客戶點之間的交換，2-交換法路徑間交換方式如圖2所示，并且由此可以設置出候選集。

圖1 2-交換法，路徑內(nèi)交換示意圖

圖2 2-交換法，路徑間交換示意圖

2.3 確定禁忌對象和禁忌表長度

禁忌對象是指禁忌表中被禁的局部最優(yōu)解，本文將每次迭代之后的最優(yōu)解作為禁忌對象放入禁忌表中，用禁忌表記錄已搜索的局部最優(yōu)解的歷史信息，使算法在一定程度上避免陷入局部最優(yōu)，開辟新的搜索區(qū)域。禁忌表長度是指禁忌對象在不考慮特赦準則的情況下，禁止被選取的最大次數(shù)。禁忌表長度太短會造成搜索的循環(huán)，禁忌表長度太長又會導致計算時間過長，所以禁忌表長度應該根據(jù)問題的規(guī)模與特征進行選取。

2.4 終止準則

本文采用的終止準則是目標控制原則：如果在一個給定迭代步數(shù)內(nèi)當前最優(yōu)值沒有變化，可終止計算。

3 實驗結果與分析

B2C電子商務環(huán)境下的訂單具有多批次、小批量、多種類等特點，且實驗數(shù)據(jù)不易獲得，因此本文采用已有文獻[13]-[18]的數(shù)據(jù)來驗證算法的有效性。算法是用Python實現(xiàn)，在環(huán)境為Windows 7、內(nèi)存為8GB的Dell Optiplex 3046的計算機上運行。

3.1 VRPMB問題特例

實驗1是8個客戶的問題，實驗2是20個客戶的問題，是本文的VRPMB模型中的取貨需求的特殊實例，車輛的最大載重量均為8t，車輛的固定成本忽略不計。具體數(shù)據(jù)見文獻[13]-[14]。設置總迭代次數(shù)N=50，聚類中心=3，禁忌表長度T=10。實驗1計算比較結果見表1。

從表1可以看出，本文設計的算法得出的結果與文獻[13-14]的結果相同，但是總耗時更少，為0.04 s。得出3輛車配送方案的具體配送路線分別為：車輛1：0-4-7-8-0；車輛2：0-5-3-1-2-0；車輛3：0-6-0。

實驗2隨機求解10次，取總迭代步數(shù)N=100，聚類中心=5，禁忌表長度T=20，得到的計算結果見表2。

表1 實驗1結果比較

由表2可以看出：隨機求解10次的結果均為高質(zhì)量的解決方案，平均使用車輛為5輛，平均車輛運行距離為875.36 km，其中最好的解是864.94 km，最差解的運行距離僅比最好解高2.96%({(最差的解-最好的解)/最好的解}×100%)。從運行時間上看，10次求解的平均計算時間為0.562 s，計算效率較高。實驗2得到的最好配送方案為第8次的運行結果，5輛車的具體配送路徑分別為：車輛1：0-9-11-13-16-2-8-0；車輛2：0-1-4-17-14-15-3-0；車輛3：0-6-5-20-0；車輛4：0-10-7-19-0；車輛5：0-18-12-0。

表3 實驗2結果與文獻[13]-[15]結果比較

表3給出實驗2中本文計算結果與文獻[13]-[15]的結果比較，求得的最好解為864.94 km，遠遠優(yōu)于其它文獻的最好結果，所需車輛數(shù)為5輛，比文獻[14]-[15]的用車數(shù)量更少，在運算時間上具有較高的效率。

3.2 VRPMB問題

實驗3的數(shù)據(jù)取自文獻[16]-[18]，是20個客戶點的VRPMB問題，車輛的最大載重量均為8 t，車輛一次配送的最大行駛距離都為50 km，車輛的固定成本忽略不計。實驗3隨機求解10次，設置總迭代步數(shù)N=100，聚類中心k=5，禁忌表長度T=20，得到的計算結果見表4。

從表4可以看出：在對實驗3進行的10次求解中都得到了質(zhì)量很高的解，平均使用車輛數(shù)為3輛，其解的平均值為103.19 km，優(yōu)于文獻[17]的最好結果，其中有兩次解的質(zhì)量最好，其運行總距離均為100.66 km。對應的配送方案為：車輛1：0-9-18-11-10-3-2-8-0；車輛2：0-19-17-16-4-5-13-15-0；車輛3：0-14-6-1-20-7-12-0。求解算法的計算結果也比較穩(wěn)定，在10次求解結果中，最差解的運行距離僅比最好解高5.42%({(最差的解-最好的解)/最好的解}×100%)。從運行時間上看，10次求解的平均計算時間為0.544 s，計算效率較高。

表4 實驗3求解結果

表5 實驗3結果與文獻[16]結果比較

表5是與文獻[17]以及文獻[18]的總費用進行比較，可以看出本文的運算結果較好，驗證了算法的有效性。

4 結論

物流配送智能化已經(jīng)成為電子商務環(huán)境下物流發(fā)展的一個新趨勢，專家們致力于物流配送優(yōu)化的研究，旨在能夠節(jié)省物流成本，節(jié)約車輛資源。預售模式不僅可以應用到B2C電商平臺，還可以引入到物流配送中，提前收集客戶需求訂單，然后打包配送貨物，進而大大降低物流成本。本文提出了基于禁忌搜索算法(TS)和K-均值聚類算法(K-means)的混合啟發(fā)式算法，建立了VRPMB的數(shù)學模型，并進行實驗求解。仿真實驗結果表明，所提出的算法在解決方案質(zhì)量和運行時間方面都是穩(wěn)定且有效的，可得到高質(zhì)量的解決方案。本文研究了靜態(tài)條件下模型求解問題，未來的研究可以在動態(tài)條件下進行討論，如考慮車輛運行時間的不確定、客戶服務時間的不確定以及客戶需求的不確定等多種不確定信息，也可在算法方面進一步探索，如考慮初始聚類中心的選取、鄰域改進策略等。