王君

天津財(cái)經(jīng)大學(xué) 商學(xué)院，天津 300222

模糊時(shí)間窗VRP的動(dòng)態(tài)規(guī)劃和禁忌搜索混合算法

王君

天津財(cái)經(jīng)大學(xué) 商學(xué)院，天津 300222

1 引言

帶時(shí)間窗的車輛路徑問題（Vehicle Routing Problem with Time Windows，VRPTW）應(yīng)用到現(xiàn)實(shí)中時(shí)，顧客往往是給出一個(gè)比他們實(shí)際需要更窄的時(shí)間窗，實(shí)際配送服務(wù)中對(duì)時(shí)間窗的一點(diǎn)點(diǎn)違反對(duì)于顧客來說是可以接受的。有時(shí)在滿足所有時(shí)間窗的情況下不一定能找到可行解，所以對(duì)時(shí)間窗約束的放松不僅能提高實(shí)施車輛調(diào)度計(jì)劃的成功率，而且可以降低車輛配送的成本。雖然傳統(tǒng)的軟時(shí)間窗VRP能在一定程度上處理該問題，然而該方法僅僅是對(duì)違反時(shí)間窗時(shí)間的簡單求和，沒有考慮顧客對(duì)時(shí)間窗的主觀偏好。鑒于此種情況，Tang等[1]提出了模糊時(shí)間窗（Fuzzy Time Windows）的概念，給出了管理配送服務(wù)水平的一個(gè)新思路。

應(yīng)用顧客的偏好水平描述時(shí)間窗最早由Cheng等[2]通過對(duì)模糊預(yù)約時(shí)間（Fuzzy Due-Time）的定義提出。作者假定顧客的需求是希望在一個(gè)特定的時(shí)點(diǎn)得到服務(wù)，服務(wù)時(shí)間離該時(shí)點(diǎn)越遠(yuǎn)，顧客的滿意度越低。在確定完車輛的行駛路徑后，還需要對(duì)車輛到達(dá)顧客點(diǎn)后的開始服務(wù)時(shí)間進(jìn)行決策，以提高顧客的總體滿意水平。Tang等[1]采用順序優(yōu)化的方法來求解模糊時(shí)間窗VRP（VRP with Fuzzy Time Windows，VRPFTW），第一階段求解常規(guī)VRPTW，最小化車輛行駛距離的目標(biāo)，第二階段對(duì)具有線性分段函數(shù)和二次凹函數(shù)形式的隸屬度函數(shù)，分別用割平面法或者次梯度投影算法計(jì)算顧客的最優(yōu)開始服務(wù)時(shí)間，提高顧客的滿意度目標(biāo)。Ibaraki等[3]研究了軟時(shí)間VRP，應(yīng)用局部鄰域搜索確定路徑規(guī)劃，并設(shè)違反時(shí)間窗約束的懲罰函數(shù)為線性分段凹函數(shù)的形式，應(yīng)用動(dòng)態(tài)規(guī)劃方法和二叉搜索樹的存儲(chǔ)結(jié)構(gòu)計(jì)算顧客的最優(yōu)開始服務(wù)時(shí)間。VRPFTW需要考慮車輛配送成本、顧客偏好程度、車輛載重限制約束等，所以VRPFTW同樣也是多目標(biāo)最優(yōu)化問題[4]，需要采用多目標(biāo)優(yōu)化方法進(jìn)行求解。

采用Pareto技術(shù)的智能算法是求解多目標(biāo)VRP的一種有效方法，如多目標(biāo)遺傳算法[5-7]、多目標(biāo)粒子群算法[8]、多目標(biāo)蟻群算法[9-10]、多目標(biāo)禁忌搜索算法（Multi-Objective Tabu Search，MOTS）[11-13]等。借鑒以上思路，本文提出一種求解VRPFTW的MOTS集成優(yōu)化方法，應(yīng)用了Pareto最優(yōu)方法權(quán)衡多個(gè)目標(biāo)的同時(shí)最優(yōu)化。為了在MOTS算法中優(yōu)化顧客的平均滿意度目標(biāo)，進(jìn)一步在可行路徑規(guī)劃上提出了求最優(yōu)開始服務(wù)時(shí)間的動(dòng)態(tài)規(guī)劃方法，利用階段劃分思想把問題化為基于緊路徑的一維優(yōu)化子問題。對(duì)于模糊時(shí)間窗為線性分段形式的隸屬度函數(shù)，給出一種有限枚舉算法，對(duì)于非線性的凹隸屬度函數(shù)，給出一種次梯度二分迭代算法。最后通過Solomon的標(biāo)準(zhǔn)算例不僅驗(yàn)證了基于動(dòng)態(tài)規(guī)劃方法求最優(yōu)服務(wù)時(shí)間的有效性，而且與目前主流的NSGA-II算法的比較實(shí)驗(yàn)，進(jìn)一步說明了MOTS求解VRPFTW問題的優(yōu)勢。

2 問題描述與數(shù)學(xué)模型的建立

2.1 模糊時(shí)間窗的描述

顧客i的模糊時(shí)間窗包含可以容忍的時(shí)間范圍[EETi，ELTi]和期望服務(wù)時(shí)間范圍[Ei，Li]，如圖1所示。如果顧客i在期望服務(wù)時(shí)間范圍[Ei，Li]內(nèi)得到服務(wù)，顧客會(huì)得到最大的滿意度(μi=1，μi表示顧客i的滿意度，0≤μi≤1)；如果顧客在容忍時(shí)間范圍[EETi，ELTi]外得到服務(wù)，顧客不滿意(μi=0)；如果顧客的開始服務(wù)時(shí)間落在兩個(gè)范圍之間，那么顧客的滿意度會(huì)隨著與區(qū)間[Ei，Li]距離的增大而逐漸降低。模糊時(shí)間窗反映了顧客對(duì)時(shí)間的偏好程度，可以表示為關(guān)于時(shí)間ti的凹模糊數(shù)，ti表示車輛開始服務(wù)顧客i的時(shí)間，顧客的滿意度可以用隸屬度函數(shù)μi(ti)來表示。在實(shí)際問題中，為了建立良好的客戶關(guān)系，一般會(huì)要求對(duì)顧客的服務(wù)水平至少要達(dá)到最低滿意度λi，此時(shí)對(duì)應(yīng)一個(gè)可行的時(shí)間范圍[E^i，L^i]，即車輛必須在該時(shí)間范圍內(nèi)開始對(duì)顧客進(jìn)行服務(wù)。

圖1 模糊時(shí)間窗示意圖

定義1（λ水平時(shí)間窗）使顧客對(duì)開始服務(wù)時(shí)間的偏好水平不低于λ的時(shí)間范圍，稱為λ水平時(shí)間窗。

2.2 模糊時(shí)間窗VRP數(shù)學(xué)模型的建立

一個(gè)VRPFTW描述為：設(shè)G={I，E}為一個(gè)完備的無向圖，其中 I={0，1，…，n}為節(jié)點(diǎn)集，E={i，j}，其中i，j∈I，i≠j為邊集。0代表車庫點(diǎn)，其余為顧客點(diǎn)，一隊(duì)具有有限裝載能力的車輛從車庫點(diǎn)出發(fā)，實(shí)現(xiàn)對(duì)所有顧客點(diǎn)的配送服務(wù)，最終回到車庫。每個(gè)顧客點(diǎn)有固定的需求、固定的服務(wù)時(shí)間和模糊時(shí)間窗，并且只能由一輛車服務(wù)。優(yōu)化目標(biāo)是確定車輛的行駛路線，使得總費(fèi)用最小，車隊(duì)服務(wù)滿意度最高。

標(biāo)號(hào)和參數(shù)變量：

cij表示i點(diǎn)和 j點(diǎn)間的距離；V表示車輛集合；tij，ati，wti，sti分別表示車輛從節(jié)點(diǎn)i到 j的行駛時(shí)間、到達(dá)節(jié)點(diǎn)i的時(shí)間、在服務(wù)節(jié)點(diǎn)i前的等待時(shí)間和服務(wù)點(diǎn)i的持續(xù)服務(wù)時(shí)間；di表示第i個(gè)顧客的配送貨物量；Qv表示車輛v的載重量。

決策變量：

xijv是0-1的決策變量，即

其中，式（2）和（3）表示目標(biāo)函數(shù)，兩個(gè)目標(biāo)分別指最小化車輛行駛總路徑長度和最大化顧客平均滿意度。式（4）和（5）表示每輛車都要從車庫出發(fā)，最終回到車庫。式（6）和（7）表示每個(gè)顧客有且僅有一輛車為其服務(wù)。式（8）表示要貨量不能超過車輛的載重量。式（9）表示車輛服務(wù)相鄰顧客的時(shí)間關(guān)系。式（10）表示至少要達(dá)到顧客的最低滿意度λi。式（11）指決策變量xijv是0-1變量。

3 多目標(biāo)集成優(yōu)化求解方法

VRPFTW需要同時(shí)優(yōu)化車輛行駛總距離和顧客的平均滿意度，本文依據(jù)解的Pareto占優(yōu)關(guān)系來比較解的優(yōu)劣以指導(dǎo)搜索方向，提出一種求解VRPFTW的基于并行多目標(biāo)禁忌搜索的集成優(yōu)化方法。算法首先應(yīng)用隨機(jī)車輛配載方法生成初始解并存儲(chǔ)在一個(gè)候選解池中，然后對(duì)池中的Pareto解進(jìn)行獨(dú)立的禁忌搜索。初始解和鄰域操作得到的候選解需要通過動(dòng)態(tài)規(guī)劃的方法來計(jì)算顧客的最優(yōu)開始服務(wù)時(shí)間以優(yōu)化平均滿意度，并通過Pareto占優(yōu)關(guān)系更新候選解池中的劣解，最終逼近Pareto前沿。

集成優(yōu)化方法主要是把計(jì)算最優(yōu)開始服務(wù)時(shí)間的動(dòng)態(tài)規(guī)劃方法集成到多目標(biāo)禁忌搜索算法中。在MOTS算法本身的流程執(zhí)行過程中，實(shí)際上是以λ水平時(shí)間窗替代傳統(tǒng)時(shí)間窗，然后求解VRPTW問題。而每當(dāng)MOTS中生成一個(gè)可行解，就要對(duì)該可行解進(jìn)一步優(yōu)化每個(gè)顧客的開始服務(wù)時(shí)間。圖2給出的例子描繪了一個(gè)車的配送計(jì)劃，上方時(shí)間軸表示采用MOTS本身流程優(yōu)化的一個(gè)車輛的路徑計(jì)劃，是把λ水平時(shí)間窗看做傳統(tǒng)時(shí)間窗，采用初始解生成方法和鄰域結(jié)構(gòu)得到的解。下方的時(shí)間軸是根據(jù)上方時(shí)間軸的路徑計(jì)劃，用動(dòng)態(tài)規(guī)劃方法對(duì)每個(gè)顧客的開始服務(wù)時(shí)間進(jìn)行優(yōu)化后的結(jié)果。優(yōu)化直接提高了一部分顧客的滿意度，從而提高了總體的滿意度水平。

3.1 初始解與可行鄰域結(jié)構(gòu)

初始解決定了算法搜索的起始點(diǎn)，質(zhì)量優(yōu)的初始解能使算法快速收斂到最優(yōu)解。首先以λ水平時(shí)間窗作為計(jì)算依據(jù)，采用隨機(jī)車輛配載方法[14]生成PN個(gè)初始解，以保證每個(gè)初始解都滿足約束條件。

鄰域結(jié)構(gòu)的選擇對(duì)算法的搜索質(zhì)量和效率影響較大，因?yàn)閂RPFTW不僅需要考慮車輛的載重量約束，還要考慮模糊時(shí)間窗以滿足顧客的最低滿意度水平。如果在鄰域搜索過程中不考慮λ水平時(shí)間窗，會(huì)產(chǎn)生大量的不可行解，即存在顧客i使得 μi(ti)＜λi。為了提高算法性能，本文提出一種λ可行鄰域結(jié)構(gòu)，保證可行解通過鄰域的作用生成的解仍然是可行的，即滿足載重量約束和λ水平時(shí)間窗約束。

定義2（λ可行鄰域結(jié)構(gòu)）任意一個(gè)滿足載重量約束和λ水平時(shí)間窗約束的路徑計(jì)劃，經(jīng)過鄰域結(jié)構(gòu)的作用后，生成的新路徑計(jì)劃仍然滿足載重量約束和λ水平時(shí)間窗約束，則稱該鄰域結(jié)構(gòu)為λ可行鄰域結(jié)構(gòu)。根據(jù)不同的鄰域操作，可以定義不同的λ可行鄰域結(jié)構(gòu)。

定義3（插入λ可行鄰域）由插入操作作用的λ可行鄰域結(jié)構(gòu)稱為插入λ可行鄰域。對(duì)于一個(gè)可行的單車輛路徑，判斷一個(gè)顧客插入到該路徑的各個(gè)位置是否滿足載重量約束和λ水平時(shí)間窗約束，如果滿足，則將該顧客插入到可行位置。

定義4（2-Optλ可行鄰域）由2-Opt操作作用的λ可行鄰域結(jié)構(gòu)稱為2-Optλ可行鄰域。2-Optλ可行鄰域是將兩條單車輛路徑從中間斷開再交叉組合生成兩個(gè)新的路徑，或是把兩個(gè)路徑尾首相接，由一輛車單獨(dú)進(jìn)行配送服務(wù)。

3.2 動(dòng)態(tài)規(guī)劃方法計(jì)算最優(yōu)開始服務(wù)時(shí)間

通過隨機(jī)車輛配載方法生成的初始解和λ可行鄰域結(jié)構(gòu)生成的候選解，每個(gè)顧客的開始服務(wù)時(shí)間都是其最早的可以開始服務(wù)的時(shí)間。為了讓候選解得到最大的服務(wù)滿意度，在不改變路徑計(jì)劃的前提下，需要對(duì)每個(gè)顧客的開始服務(wù)時(shí)間進(jìn)行調(diào)整。對(duì)某車輛配送的路徑(s1，s2，…，sp，…，sP)，sp∈I，根據(jù)文獻(xiàn)[14]的緊路徑定義，下面以緊路徑優(yōu)化子問題為計(jì)算單元，給出計(jì)算最優(yōu)開始服務(wù)時(shí)間的動(dòng)態(tài)規(guī)劃方法。

圖2 計(jì)算顧客最優(yōu)開始服務(wù)時(shí)間的示意圖

對(duì)于每輛車給定的路徑計(jì)劃，可以按照服務(wù)的順序?qū)個(gè)顧客劃分成P個(gè)階段，每個(gè)階段需要對(duì)相應(yīng)顧客的開始服務(wù)時(shí)間進(jìn)行決策。對(duì)當(dāng)前顧客的決策會(huì)影響相鄰的顧客，當(dāng)每個(gè)顧客的開始服務(wù)時(shí)間確定以后，就組成了一個(gè)決策序列。顯然，最優(yōu)服務(wù)時(shí)間的確定是一種多階段最優(yōu)決策問題，而動(dòng)態(tài)規(guī)劃正是解決多階段最優(yōu)決策問題的有效方法。

階段劃分：如前所述，根據(jù)車輛對(duì)顧客的服務(wù)順序劃分P個(gè)顧客為P個(gè)階段，p為階段變量，p=1，2，…，P。

狀態(tài)變量：車輛到達(dá)顧客點(diǎn)sp的時(shí)間atsp為狀態(tài)變量，這里狀態(tài)變量是連續(xù)的。

決策變量：車輛開始服務(wù)顧客點(diǎn)sp的時(shí)間tsp為決策變量，允許決策集合為max{，atsp}≤tsp≤L^sp。

狀態(tài)轉(zhuǎn)移方程：確定階段 p的決策變量tsp之后，車輛對(duì)顧客sp進(jìn)行服務(wù)，然后行駛一段路程后才能到達(dá)下一個(gè)顧客sp+1，故狀態(tài)轉(zhuǎn)移方程為atsp+1=(tsp+stsp+tspsp+1)。

一個(gè)狀態(tài)為atsp階段 p的優(yōu)化問題，可以轉(zhuǎn)化為下面的階段優(yōu)化問題：

次梯度投影方法要求對(duì)每次遞推的自變量求其在可行域上的歐式投影，這本身又是一個(gè)多維優(yōu)化問題。為了能夠簡化該方法，應(yīng)用動(dòng)態(tài)規(guī)劃方法可以逐步對(duì)緊路徑進(jìn)行優(yōu)化，從而把多維優(yōu)化問題轉(zhuǎn)化為一維優(yōu)化問題，降低處理問題的難度。

即轉(zhuǎn)化為一維的約束優(yōu)化問題，其中μ⌒(·)是一個(gè)分段的凹函數(shù)。

（1）如果隸屬度函數(shù)μ(·)是線性的，則μ⌒(·)是一個(gè)分段的線性函數(shù)，緊路徑優(yōu)化問題可以用有限枚舉算法來優(yōu)化。

（2）如果隸屬度函數(shù)μ(·)是非線性的，則μ⌒(·)是一個(gè)分段的凹函數(shù)，本文提出次梯度二分迭代方法求解緊路徑優(yōu)化問題。

次梯度：

步驟2確定由sp開始的最長緊路徑(sp,sp+1,…,sq)。若q=P并且wtsq+1=0，階段優(yōu)化完畢；否則，繼續(xù)步驟3。

步驟3優(yōu)化緊路徑(sp，sp+1，…，sq)，若優(yōu)化后wtsq+1＞0，階段優(yōu)化完畢；否則，返回步驟2。

3.3 MOTS總體流程

圖3 MOTS流程示意圖

MOTS的總體流程如圖3所示，解的評(píng)價(jià)方法、適應(yīng)度函數(shù)、禁忌對(duì)象、禁忌表、特赦準(zhǔn)則、停止規(guī)則和長期表的設(shè)置與文獻(xiàn)[14]相同。MOTS采用一個(gè)候選解池的存儲(chǔ)結(jié)構(gòu)和Pareto排序機(jī)制實(shí)現(xiàn)對(duì)全局搜索的控制。虛線所框部分描述了每個(gè)獨(dú)立的搜索過程，每個(gè)搜索有獨(dú)立的禁忌表和一個(gè)Pareto候選解列表，以記錄其找到的局部Pareto解。在生成初始解和用鄰域結(jié)構(gòu)產(chǎn)生候選解之后，已經(jīng)確定了目標(biāo) f1，需要進(jìn)一步計(jì)算顧客的最優(yōu)開始服務(wù)時(shí)間來優(yōu)化目標(biāo) f2，所以MOTS算法中嵌入了3.2節(jié)提出的動(dòng)態(tài)規(guī)劃方法以綜合評(píng)價(jià)解的優(yōu)劣。

4 仿真實(shí)驗(yàn)與討論

測試采用國際上通用Solomon的標(biāo)準(zhǔn)算例rc101，該算例包含100個(gè)顧客，顧客在地理位置或者服務(wù)時(shí)間窗上部分具有聚集特征，部分為隨機(jī)生成。rc101的整個(gè)計(jì)劃時(shí)間窗較短，每條線路中只能安排幾個(gè)顧客。算法用VC++6.0進(jìn)行編程，在Inter Pentium Dual T2410 CPU 2 GHz，1 GB內(nèi)存，Windows XP SP3的主機(jī)上運(yùn)行。實(shí)驗(yàn)主要包括兩部分，首先比較本文提出的計(jì)算最優(yōu)開始服務(wù)時(shí)間的動(dòng)態(tài)規(guī)劃方法和文獻(xiàn)[1]提出的次梯度投影方法（記為PSM）的優(yōu)劣，然后對(duì)本文提出的MOTS集成算法和目前比較主流的成熟多目標(biāo)求解算法NSGA-II進(jìn)行對(duì)比分析。

4.1 模糊時(shí)間窗的實(shí)驗(yàn)設(shè)定

4.2 計(jì)算最優(yōu)開始服務(wù)時(shí)間方法的對(duì)比

用隨機(jī)車輛配載方法分別對(duì)模糊時(shí)間窗的兩類隸屬度函數(shù)分別生成800個(gè)可行解，然后對(duì)每個(gè)可行解分別應(yīng)用次梯度投影方法和基于動(dòng)態(tài)規(guī)劃的方法（記為DP）來計(jì)算最優(yōu)開始服務(wù)時(shí)間。參數(shù)設(shè)置為：η=0.001，PSM方法如果在迭代過程中得到最大滿意度1，則停止，且最大迭代次數(shù)設(shè)定為100。

表1的左半部分統(tǒng)計(jì)了PSM和DP的平均運(yùn)算時(shí)間，Mean time是指計(jì)算每個(gè)解的最優(yōu)開始服務(wù)時(shí)間所消耗的計(jì)算機(jī)平均運(yùn)行時(shí)間；右半部分給出了在SPSS軟件中做Wilcoxon signed ranks檢驗(yàn)的統(tǒng)計(jì)分析結(jié)果，根據(jù)Z值可以判定兩種方法在統(tǒng)計(jì)意義上存在顯著性差異。對(duì)于線性的隸屬度函數(shù)，DP方法的計(jì)算結(jié)果要明顯優(yōu)于PSM，并且計(jì)算時(shí)間還縮短了18.038%；而對(duì)于非線性的隸屬度函數(shù)，DP方法計(jì)算結(jié)果的優(yōu)勢雖然不明顯，但是計(jì)算時(shí)間縮短了74.150%。因?yàn)殡m然從直觀來看，階段的劃分使DP方法需要大量的計(jì)算子單元，但是其每個(gè)計(jì)算單元相比PSM要簡單許多。PSM的逐步迭代和漸進(jìn)尋優(yōu)的策略，其收斂速度受步長的限制，而次梯度二分迭代算法能更快地收斂到最優(yōu)解。由對(duì)比結(jié)果可以肯定，本文提出的DP方法要顯著優(yōu)于PSM。

表1 PSM和DP的運(yùn)算時(shí)間及Wilcoxon signed ranks檢驗(yàn)（SPSS軟件）

4.3 MOTS算法和NSGA-II算法的對(duì)比

為了證明本文提出MOTS集成算法的有效性，與目前比較主流的成熟多目標(biāo)求解算法NSGA-II進(jìn)行對(duì)比。NSGA-II對(duì)父代和子代的群體混合并采用基于Pareto排序和擁擠度的選擇方式，這里采用父代個(gè)體兩兩配對(duì)進(jìn)行交叉，交叉算子采用BCRC交叉算子[15]，并結(jié)合插入λ可行鄰域，變異算子采用2-Optλ可行鄰域，變異概率0.2，種群數(shù)量400。MOTS算法參數(shù)設(shè)置如下：NMAX= 9，候選解數(shù)量=80，候選解池容量=800。MOTS達(dá)到最大迭代數(shù)1 000或者最優(yōu)解在迭代200次不變，算法終止。

表2列出了MOTS和NSGA-II運(yùn)行結(jié)果得到的Pareto解的個(gè)數(shù)和平均求得每個(gè)Pareto解的運(yùn)行時(shí)間。數(shù)據(jù)表明MOTS不僅比NSGA-II取到更多的Pareto解，并且MOTS求解每個(gè)解消耗的時(shí)間明顯低于NSGA-II，尤其在隸屬度函數(shù)為非線性形式時(shí)縮短了62.853%，所以MOTS的優(yōu)勢很大。圖4和圖5分別顯示了線性和非線性的隸屬度函數(shù)下MOTS和NSGA-II最終求得的Pareto前沿，對(duì)比表明MOTS計(jì)算得到的Pareto解集明顯優(yōu)于NSGA-II。因?yàn)镹SGA-II得到的Pareto解個(gè)數(shù)與種群規(guī)模相關(guān)，如果要得到更多的Pareto解，必須擴(kuò)大種群規(guī)模。實(shí)驗(yàn)表明在占用相同存儲(chǔ)空間的情況下，MOTS通過候選解的持續(xù)生成，既能擴(kuò)大搜索區(qū)域，又能提高搜索的密度。

表2 NSGA-II和MOTS運(yùn)行結(jié)果統(tǒng)計(jì)

圖4 線性隸屬度函數(shù)NSGA-II和MOTS計(jì)算結(jié)果對(duì)比圖

圖5 非線性隸屬度函數(shù)NSGA-II和MOTS計(jì)算結(jié)果對(duì)比圖

5 結(jié)束語

模糊時(shí)間窗VRP考慮了顧客對(duì)時(shí)間窗的偏好，相比傳統(tǒng)硬時(shí)間窗VRP，雖然顧客的滿意度有一點(diǎn)下降，但是在顧客容忍的范圍內(nèi)，會(huì)大大節(jié)約物流配送成本。本文提出的基于λ可行鄰域結(jié)構(gòu)的多目標(biāo)集成優(yōu)化方法，在MOTS中嵌入了優(yōu)化顧客滿意度的動(dòng)態(tài)規(guī)劃方法，運(yùn)用階段劃分，把原問題分解為關(guān)于緊路徑的優(yōu)化子問題。對(duì)模糊時(shí)間窗為線性分段函數(shù)形式和非線性凹函數(shù)形式的隸屬度函數(shù)，分別提出了有限枚舉算法和次梯度二分迭代算法來優(yōu)化顧客的最優(yōu)開始服務(wù)時(shí)間。集成方法求得的一組Pareto解，能有效幫助決策者權(quán)衡不同的決策目標(biāo)，做出正確的管理決策。對(duì)比仿真實(shí)驗(yàn)表明，基于動(dòng)態(tài)規(guī)劃的方法能有效優(yōu)化模糊時(shí)間窗VRP的顧客滿意度，MOTS集成算法對(duì)比NSGA-II方法在求解精度和計(jì)算速度上都具有明顯的優(yōu)勢。

[1]Tang J F，Pan Z D，F(xiàn)ung R Y K，et al.Vehicle routing problem with fuzzy time windows[J].Fuzzy Sets and Systems，2009，160（5）：683-695.

[2]Cheng R，Gen M，Tozawa T.Vehicle routing problem with fuzzy due-time using genetic algorithms[J].Japanese Journal of Fuzzy Theory and Systems，1995，7：665-679.

[3]Ibaraki T，Imahori S，Nonobe K，et al.An iterated local search algorithm for the vehicle routing problem with convex time penalty functions[J].Discrete Applied Mathematics，2008，156（11）：2050-2069.

[4]Jozefowiez N，Semet F，Talbi E G.Multi-objective vehicle routing problems[J].European Journalof Operational Research，2008，189（2）：293-309.

[5]Tan K C，Chew Y H，Lee L H.A hybrid multi-objective evolutionary algorithm for solving truck and trailer vehicle routing problems[J].European Journalof Operational Research，2006，172（3）：855-885.

[6]Jozefowiez N，Semet F，Talbi E G.An evolutionary algorithm for the vehicle routing problem with route balancing[J].European Journal of Operational Research，2009，195（3）：761-769.

[7]Jozefowiez N，Semet F，Talbi E G.Target aiming Pareto search and its application to the vehicle routing problem with route balancing[J].Journal of Heuristics，2007，13（5）：455-469.

[8]趙燕偉，李川，張景玲，等.一種新的求解多目標(biāo)隨機(jī)需求車輛路徑問題的算法[J].計(jì)算機(jī)集成制造系統(tǒng)，2012，18（3）：523-530.

[9]李琳，劉士新，唐加福.B2C環(huán)境下帶預(yù)約時(shí)間的車輛路徑問題及多目標(biāo)優(yōu)化蟻群算法[J].控制理論與應(yīng)用，2011，28（1）：87-93.

[10]李世威，王建強(qiáng)，曾俊偉.求解VRPTW問題的多目標(biāo)模糊偏好蟻群算法[J].計(jì)算機(jī)應(yīng)用研究，2011，28（12）：4495-4499.

[11]Choobineh F F，Mohebbi E，Khoo H.A multi-objective tabu search for a single-machine scheduling problem with sequence-dependent setup times[J].European Journal of Operational Research，2006，175（1）：318-337.

[12]Belfares L，Klibi W，Lo N，et al.Multi-objectives Tabu search based algorithm for progressive resource allocation[J].European Journal of Operational Research，2007，177（3）：1779-1799.

[13]Carcangiu S，F(xiàn)anni A，Montisci A.Multiobjective tabu search algorithms for optimal design of electromagnetic devices[J].IEEE Transactions on Magnetics，2008，44（6）：970-973.

[14]王君，李波.帶模糊預(yù)約時(shí)間的車輛路徑問題的多目標(biāo)禁忌搜索算法[J].計(jì)算機(jī)集成制造系統(tǒng)，2011，17（4）：858-866.

[15]Ombuki B，Ross B J，Hanshar F.Multi-objective genetic algorithms for vehicle routing problem with time windows[J].Applied Intelligence，2006，24（1）：17-30.

WANG Jun

School of Business,Tianjin University of Finance&Economics,Tianjin 300222,China

The Vehicle Routing Problem with Fuzzy Time Windows is addressed.A multi-objective mathematical model is designed with the objectives of logistics cost and average customer satisfaction.Based on Pareto dominance theory,a multiobjective tabu search algorithm is proposed to solve multi-objective optimization problems.Moreover,a dynamic programming method is embedded in the algorithm to optimize the customer satisfaction,which simplifies the original problem into tight path optimization sub-problems with the use of phasing.While fuzzy time windows are in piecewise linear and nonlinear convex membership function forms,customer beginning service time is optimized by proposed limited iteration subgradient algorithm and median iteration subgradient algorithm,respectively.Computational experiments on Solomon’s benchmark not only verify that the dynamic programming is more effective than projected subgradient methods to optimize the service level,but also show the advantages of the proposed multi-objective tabu search approach when compared with the well-known NSGA-II method.

vehicle routing problem;fuzzy time windows;dynamic programming;multi-objective tabu search;Pareto optimization

為優(yōu)化具有模糊時(shí)間窗的車輛路徑問題，以物流配送成本和顧客平均滿意度為目標(biāo)，建立了多目標(biāo)數(shù)學(xué)規(guī)劃模型?；赑areto占優(yōu)的理論給出了求解多目標(biāo)優(yōu)化問題的并行多目標(biāo)禁忌搜索算法，算法中嵌入同時(shí)優(yōu)化顧客滿意度的動(dòng)態(tài)規(guī)劃方法，運(yùn)用階段劃分，把原問題分解為關(guān)于緊路徑的優(yōu)化子問題。對(duì)模糊時(shí)間窗為線性分段函數(shù)形式和非線性凹函數(shù)形式的隸屬度函數(shù)，分別提出了次梯度有限迭代算法和次梯度中值迭代算法來優(yōu)化顧客的最優(yōu)開始服務(wù)時(shí)間。通過Solomon的標(biāo)準(zhǔn)算例，與次梯度投影算法的比較驗(yàn)證了動(dòng)態(tài)規(guī)劃方法優(yōu)化服務(wù)水平的有效性，與主流的NSGA-II算法的對(duì)比實(shí)驗(yàn)表明了該研究提出的多目標(biāo)禁忌搜索算法的優(yōu)越性。

車輛路徑問題；模糊時(shí)間窗；動(dòng)態(tài)規(guī)劃；多目標(biāo)禁忌搜索；Pareto最優(yōu)

A

TP29；N945.25

10.3778/j.issn.1002-8331.1303-0092

WANG Jun.Dynamic programming and tabu search hybrid algorithm for Vehicle Routing Problem with fuzzy time windows.Computer Engineering and Applications,2014,50（24）：58-64.

國家社科基金資助項(xiàng)目（No.11CGL102）；教育部人文社科青年項(xiàng)目（No.13YJC630195）；天津市科技發(fā)展戰(zhàn)略研究計(jì)劃項(xiàng)目（No.13ZLZLZF04600）；天津財(cái)經(jīng)大學(xué)科研發(fā)展基金資助項(xiàng)目（No.Q1208）。

王君（1983—），男，博士，講師，研究領(lǐng)域?yàn)槲锪鞴こ?，智能?yōu)化等。E-mail：woosuny@163.com

2013-03-08

2013-06-13

1002-8331（2014）24-0058-07

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-06-26，http∶//www.cnki.net/kcms/detail/11.2127.TP.20130626.1539.007.html

◎網(wǎng)絡(luò)、通信、安全◎