考慮客戶偏好的雙目標時間窗指派車輛路徑問題

李嫚嫚 陸 建 安 穎

(東南大學城市智能交通江蘇省重點實驗室， 南京210096)(東南大學現(xiàn)代城市交通技術(shù)江蘇高校協(xié)同創(chuàng)新中心， 南京210096)(東南大學交通學院， 南京210096)

在分撥網(wǎng)絡(luò)中，供應(yīng)商常常需在已知客戶需求量前向客戶許諾一個一段時期內(nèi)每天服務(wù)所遵循的時間窗[1].這個時間窗會顯著地影響配送路徑的選擇，進而影響配送費用[2].同時，許多研究文獻中都假定客戶對配送服務(wù)有時間要求[3-7].由此可知，客戶對配送時間有著特定偏好，不同的配送時間會帶來不一樣的客戶滿意度.現(xiàn)有的研究僅考慮供應(yīng)商利益的單目標時間窗指派問題、時間窗指定后的配送路徑安排以及多目標優(yōu)化.Spliet等[1-2]以最小化期望配送成本為目標，分別研究了不確定需求下連續(xù)時間窗和離散時間窗指派車輛路徑問題；Agatz等[8]以最小化配送成本為目標，研究了給定每個街區(qū)客戶數(shù)量和平均每周需求量下的各街區(qū)服務(wù)時間窗集合指定問題；Campbell等[9]和Ehmke等[10]以最大利潤為目標，分別研究了不同路段行駛時間假設(shè)條件下，實時動態(tài)接受客戶并為其指定服務(wù)時間窗的問題.

為得到一個時間窗指派方案的期望配送成本，需構(gòu)建滿足指定時間窗的每日配送路徑，即時間窗指定后的配送路徑安排問題.Baldacci等[6]總結(jié)了帶時間窗車輛路徑問題的精確解求法；柴獲等[7]將單變量邊緣分布算法用于求解帶時間窗車輛路徑問題.

多目標優(yōu)化方法主要有標量方法、帕累托方法和其他[11]3類.標量方法是通過線性加權(quán)等方法將多目標優(yōu)化問題轉(zhuǎn)化為單目標優(yōu)化問題，從而借用單目標優(yōu)化算法對其求解.該方法使用簡單，但單次運行無法求解出整個非支配解集，而且目標的加權(quán)系數(shù)難以確定.帕累托方法利用支配解概念評價或者比較解質(zhì)量，能夠單次求解出整個非支配解集.其他方法是一些不同的目標處理技術(shù)，主要包括遺傳算法、邏輯策略、蟻群算法機制和特定的啟發(fā)式方法.

本文針對考慮客戶時間窗偏好的雙目標時間窗指派車輛路徑問題進行研究，構(gòu)建了一個混合整數(shù)線性規(guī)劃模型，采用不同約束處理依據(jù)帕累托方法設(shè)計了2個多目標遺傳算法用于問題求解，并通過算例對模型和算法的有效性進行了驗證.

1 問題描述與模型建立

本文考慮客戶時間窗偏好的雙目標時間窗指派車輛路徑問題描述如下：供應(yīng)商需向每一個客戶許諾一個服務(wù)時間窗.一段時間內(nèi)，供應(yīng)商的配送服務(wù)都應(yīng)遵守該時間窗.可供指定的離散時間窗不重疊地覆蓋了一整天，如[8:00—9:00]，[9:00—10:00]，…，[17:00—18:00].每個客戶對其中2個時間窗較為滿意.供應(yīng)商在許諾時間窗時，期望最大化客戶滿意度的同時最小化期望配送成本.配送成本只包含車輛行駛時間成本.

供應(yīng)商所需服務(wù)的所有客戶位置均已知.客戶間的行駛時間均為常量.一段時間內(nèi)，客戶的每日需求量為隨機變量.本文以有限情景集模擬其可能出現(xiàn)情形[1,12].由于客戶的服務(wù)時間可加入行駛時間[13]，這里假定客戶服務(wù)時間為零.供應(yīng)商擁有的車輛數(shù)確定，但車輛的載重量不同.在每日的配送服務(wù)中，可根據(jù)需要使用車輛.

本文借鑒文獻[1，14]中的模型，構(gòu)建如下雙目標混合整數(shù)線性規(guī)劃模型.

1) 已知數(shù)據(jù)集合

2) 決策變量

i∈C,j∈C,s∈S

i∈C,k∈K,s∈S

opt：

(1)

(2)

s.t.

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

式(1)和式(2)分別為最小化期望配送成本和最大化客戶滿意度，是問題的2個目標函數(shù).

問題的約束條件有5類：第1類約束為時間窗指派約束(見式(3))，表明每個客戶應(yīng)被指定一個服務(wù)時間窗，且只能指定一個.剩余的約束類在每一個需求情景中都被滿足.第2類約束為客戶服務(wù)約束(見式(4))，表明每個客戶都應(yīng)由一輛車服務(wù)且只能由一輛車服務(wù)；第3類約束為路徑約束(見式(5)～(8))，確保被使用車輛的行駛路徑為Haminton回路，未使用車輛依然留在原處；第4類約束為載重量約束(見式(9)～(11))，確保每輛車不超重；第5類約束為時間窗約束(見式(12)～(15))，指明每個客戶必須在許諾的時間窗內(nèi)被服務(wù).

2 算法設(shè)計

遺傳算法是一類自適應(yīng)、自組織、自學習算法，能夠有效地求解難于解決的各類復(fù)雜問題.由于所研究問題是通過指定客戶時間窗，且僅考慮一種需求情景時轉(zhuǎn)化為帶硬時間窗的車輛路徑問題，故是一個NP完備問題[15].精確解難以求解該類問題的大規(guī)模實例，而且，基于群體搜索機制的算法對于求解多目標優(yōu)化問題的非支配解集有優(yōu)勢，故將遺傳算法作為問題的求解算法.采用不同約束處理依據(jù)帕累托方法設(shè)計了拋棄法約束處理多目標遺傳算法和無參約束處理多目標遺傳算法.

2.1 多目標遺傳算法流程

本文設(shè)計的2個多目標遺傳算法基本流程相同，如圖1所示.初始種群首先被隨機生成.然后，執(zhí)行迭代過程至最大迭代數(shù)G.在每次迭代中，遺傳算子用于生成新解，將適應(yīng)度計算、非支配排序和選擇策略相結(jié)合以產(chǎn)生下一代.

圖1 多目標遺傳算法流程

2.2 拋棄法約束處理多目標遺傳算法

2.2.1 編碼

依據(jù)隨機密鑰編碼思想[14,16]，染色體被編碼如表1所示.由于本文采用有限情景集處理不確定需求，為能同時獲得所有情景下的配送方案，所有客戶首先被復(fù)制s-1份，考慮2種模擬情景(模擬情景1和模擬情景2).接著，針對每個客戶點，以[0, |K|]均勻分布生成一個隨機數(shù)，表示服務(wù)客戶的車輛；在此基礎(chǔ)上，以[0,|W|]均勻分布隨機生成指派給客戶的時間窗.由于多個需求情景中，供應(yīng)商都需遵守同一服務(wù)時間窗，因此，在生成指派給客戶的時間窗時，只針對一種需求情景的所有客戶點生成，其他需求情景通過復(fù)制得到.隨后，生成一個隨機數(shù)用以指定相同服務(wù)車輛、相同時間窗下客戶被服務(wù)的先后順序.為保證車輛配送路徑中，時間窗在前的客戶比時間窗滯后的客戶先被服務(wù)，必須先指定客戶服務(wù)時間窗，再生成指定客戶服務(wù)順序的隨機數(shù)，這樣可以提高滿足客戶時間窗約束的概率.最后，將每一客戶點生成的所有隨機數(shù)擴大加和后作為基因值.擴大倍數(shù)的選擇以兩兩相鄰隨機數(shù)不重疊為標準.

表1 2種模擬情景的編碼

此種編碼方式既可方便遺傳算子的使用，又可保證隨機生成的染色體滿足時間窗指定、客戶服務(wù)以及路徑三大類約束，縮小了算法探索空間，提高了算法的求解性能.

2.2.2 解碼

在適應(yīng)度計算和約束檢查時，需對染色體進行解碼.解碼為編碼的逆過程，具體步驟如下：

① 對每種需求情景，按升序排序基因值大??；

② 解碼服務(wù)客戶的車輛；

③ 解碼指定給每個客戶的時間窗.

上述染色體的解碼結(jié)果如表2所示.指派給客戶1～客戶5的時間窗分別為時間窗9,6,7,6,4.模擬情景1中，車輛1從供應(yīng)點出發(fā)，服務(wù)完客戶5后，接著服務(wù)客戶2和客戶1，最后返回供應(yīng)點；車輛2從供應(yīng)點出發(fā)，服務(wù)完客戶4和客戶3后，返回供應(yīng)點；需求情景2中，車輛配送路徑分別為0—客戶5—客戶4—客戶2—0和0—客戶3—客戶1—0，其中，0代表供應(yīng)點.

表2 2種模擬情景的解碼

2.2.3 交叉算子

本文中設(shè)計的編碼方式可以方便地使用標準遺傳算子，故使用兩點交叉算子[14,16].但為了保證多需求情景中指派給客戶的時間窗一致，在選擇交叉點時，將其限定在[1,|U|]之間，如基因位2和4.然后，將2個父代染色體中不同需求情景的相應(yīng)位置進行交叉操作，如基因位2～基因位4和基因位7～基因位9，結(jié)果如表3所示.

表3 2種模擬情景的交叉算子

2.2.4 變異算子

交叉操作后，解的樣本空間被擴大.對擴大后樣本空間的每個染色體進行變異操作.使用均勻變異算子，過程如下：以一定概率對染色體的每個基因位進行變異；每個基因位變異時，將其基因值更新為由新生成的服務(wù)車輛和時間窗計算所得值(如基因位2)；同樣，為保證多需求情景中客戶時間窗指定的一致性，其他需求情景中對應(yīng)客戶的時間窗也需替換為新生成值，結(jié)果如表4所示.

表4 2種模擬情景變異結(jié)果

2.2.5 約束檢查

為了保證求解的可行性，對隨機生成的初始解、交叉和變異產(chǎn)生的新解進行時間窗約束和載重量約束檢查.當其不可行時，將其拋棄.由于剩余約束在算法中一直被滿足，所以只檢查載重量約束和時間窗約束.

2.2.6 適應(yīng)度

染色體的適應(yīng)度為2個目標函數(shù)值所組成的兩維向量.

2.2.7 非支配排序

與單目標優(yōu)化不同的是，多目標優(yōu)化的解以權(quán)衡形式存在，這就是著名的帕累托優(yōu)化集.優(yōu)化集中任何一個解都不支配其他解.為了能提供給決策者全部的解信息，方便決策者選擇自己偏好的方案.本文采用快速非支配排序策略比較解質(zhì)量[17].該策略通過邏輯將種群組織成一系列子種群，每個種群中的個體有相同的排序且不相互支配對方，但個體被低排序值的種群所支配.快速非支配排序的偽代碼如下：

Si=?,npi=0,Fi=?,i∈P∥初始化

Fori,i∈P∥解間支配關(guān)系

Forj,j∈P

IfpjpithenSi=Si∪{pj};

Else Ifpipjthennpi=npi+1

Fori,i∈P∥子種群劃分

Ifnpi=0 thenF1=F1∪pi;

n=1

WhileFn～=?

Fori,i∈Fn

npi=npi-1

Ifnpi=0 thenFn+1=Fn+1∪pi;

n=n+1

2.2.8 選擇

將父代和交叉、變異產(chǎn)生的子代作為樣本空間.為了防止解質(zhì)量退化，首先采用精英策略，將每代非支配解直接傳遞給下一代.當其數(shù)量多于種群數(shù)時，隨機從中選擇出相應(yīng)數(shù)量的解.剩余的個體采用二元錦標法從整個樣本空間中選出.

2.3 無參約束處理多目標遺傳算法

無參約束處理多目標遺傳算法與拋棄法約束處理多目標遺傳算法的基本流程和所用方法一致.不同之處在于：

1) 無約束檢查.

2) 適應(yīng)度向量的維度被改變.對于可行解，適應(yīng)度向量為由可行解標識及2個目標函數(shù)值組成的三維向量；對于不可行解，適應(yīng)度向量為由不可行解標識、2個目標函數(shù)值以及總約束違反度組成的四維向量.總約束違反度為標準化后的各約束違反度的加和值，即

(16)

(17)

(18)

3) 非支配排序中，支配的定義被修改[17].修改后的定義如下：

① 可行解間的支配仍采用Pareto支配定義；

② 可行解支配不可行解；

③ 2個不可行解中總約束違反度小的不可行解支配總約束違反度大的不可行解.

3 數(shù)值試驗

在Matlab R2012b中將拋棄法約束處理多目標遺傳算法和無參約束處理多目標遺傳算法進行編程，在Intel Core I5 CPU 2.6 GHz計算機上運行.算法參數(shù)分別為：迭代次數(shù)G=200，種群數(shù)N=300，交叉概率Pc=0.9和變異概率Pm=0.01.

3.1 算例設(shè)計

隨機生成案例以測試2個多目標遺傳算法的有效性.案例的客戶數(shù)分別為10，20，30，40，50和60.每個案例有2個實例(實例1和實例2).每個實例中，供應(yīng)商被置于10×10網(wǎng)格中心點(5,5)，其余客戶被均勻、不重復(fù)地分布在其他網(wǎng)格點(x,y).客戶點間的距離為歐幾里德距離.客戶的隨機需求以低、中、高3種需求情景模擬(即分別為情景1、情景2和情景3)，每種需求情景的概率為1/3，這與冰激凌零售商的需求行為類似[1].每個客戶的需求量等于基本需求量與需求情景乘子的乘積.以[5,1.5]正態(tài)分布生成每個客戶的基本需求量；以[0.7,0.8]，[0.95,1.05]，[1.2,1.3]均勻分布分別生成低、中、高需求的情景乘子[1].供應(yīng)商開始服務(wù)時間為8:00.以1 h為間隔構(gòu)造10個離散時間窗：[8:00,9:00]，[9:00,10:00]，…，[17:00,18:00].每個客戶對其中2個時間窗的滿意度為3；其余的滿意度為1.這2個時間窗以[1,10]均勻分布隨機選擇.車輛額定載重量為30，行駛速度為20.每增加10個客戶，供應(yīng)商則增加3輛車，以保證車輛額定載重量總額大于高需求情景中客戶需求總量.

3.2 模型驗證

為了驗證所建模型的正確性，使用Cplex12.7.1以默認設(shè)置對客戶規(guī)模為5的案例進行求解.由于Cplex無法直接求解多目標問題，在使用其求解時，將最大化客戶滿意度作為主目標，將最小化期望配送成本作為次目標，進而將雙目標加權(quán)處理為單目標.求解得到3種情景下的配送路徑分別如表5、表6和表7所示.

客戶的時間窗指派方案在所有情景中都相同.

表5 情景1的配送路徑

表6 情景2的配送路徑

表7 情景3的配送路徑

每條路徑也都滿足客戶服務(wù)約束、路徑約束、時間窗約束和載重量約束.這證明了本文中所建模型的正確性.

3.3 數(shù)值結(jié)果

表8為客戶規(guī)模為30的一個案例的求解結(jié)果.從中可以看出，本文設(shè)計的2個多目標遺傳算法都能夠求解出有效的非支配解集，為供應(yīng)商提供了多種時間窗指派方案，增加了供應(yīng)商的選擇.

3.4 算法比較

從表8還可觀察到，拋棄法約束處理多目標遺傳算法的求解質(zhì)量優(yōu)于無參約束處理多目標遺傳算法.為了進一步證實這一結(jié)論，采用覆蓋度量[18]來比較2個多目標算法的性能，覆蓋度量定義為

表8 多目標遺傳算法求解結(jié)果

(19)

式中，X′和X″為一對多目標算法求解的非支配解集；|X″/為解集X″中解的個數(shù)；a′?=a″為解a′支配解a″或者與解a″相等.

C(X′,X″)∈(0,1)，其值越大，表示X″中的解被X′覆蓋的比例越高.但由于C(X′,X″)和C(X″,X′)沒有直接關(guān)系，因此，在比較不同算法時，應(yīng)都被考慮.

對隨機生成的6個不同客戶規(guī)模的案例分別求解10次，得到的平均覆蓋度量和運行時間如圖2所示.對于不同客戶規(guī)模的案例，C(A1,A2)>C(A2,A1).而且，C(A1,A2)和C(A2,A1)的差距明顯.這表明拋棄法約束處理多目標遺傳算法(A1)的求解結(jié)果顯著地優(yōu)于無參約束處理多目標遺傳算法(A2)的求解結(jié)果.這也證實了由表8所得的結(jié)論.但是，A1所需運行時間隨問題規(guī)模增大而快速增加，尤其當客戶數(shù)從50增加到60時.這主要是因為隨客戶規(guī)模增加，解空間急劇擴大，為獲得相同數(shù)量的初始可行解，A1所需探索解空間的次數(shù)顯著地增加.因而，在未來研究中應(yīng)混合局部啟發(fā)式算法獲取初始可行解以減少A1的求解時間.A2的求解時間隨著客戶規(guī)模增大而緩慢增加，這主要由于A2探索解空間的次數(shù)是常量.因此，提高A2的求解質(zhì)量是未來的另一個工作重點.

(a) 實例1

(b) 實例2圖2 覆蓋度量和運行時間

3.5 目標分析

圖3展示了客戶規(guī)模為30的案例全部非主支配解，表9為6個不同客戶規(guī)模案例的2個極端解.每個案例的非支配解為拋棄法約束處理多目標遺傳算法求解10次所獲非支配解的匯總.由圖3可知，隨著期望配送成本的下降，客戶滿意度也呈下降趨勢.這表明期望配送成本與客戶滿意度之間存在著制約關(guān)系.對于客戶規(guī)模為30的案例，當期望配送成本從5.27增加到5.81(增加10%)時，客戶滿意度從68提高到90，提高了32%.客戶滿意度的提升率α遠高于期望成本提升率β，比值為3.19.對于其余規(guī)模的案例來說，α與β的比值也都大于1.這意味著供應(yīng)商多付出的成本總能收到更好的回報.供應(yīng)商應(yīng)在其成本額可承受范圍內(nèi)，盡可能提升客戶滿意度.

圖3 目標關(guān)系

表9 不同客戶規(guī)模的極端解

4 結(jié)論

1) 2種算法都能求解得到非支配解集，為供應(yīng)商提供了多種時間窗指派方案.

2) 拋棄法約束處理多目標遺傳算法的求解質(zhì)量顯著地優(yōu)于無參約束處理多目標遺傳算法.但拋棄法約束處理多目標遺傳算法的求解時間隨客戶規(guī)模增加而快速增加.因此，未來可進一步研究將拋棄法約束處理多目標遺傳算法與傳統(tǒng)啟發(fā)式算法混合以提升算法的性能.

3) 客戶滿意度與期望配送成本間存在著制約關(guān)系.客戶滿意度從最小到最大的提升率高于期望配送成本提升率.

然而，現(xiàn)實中還有更多不確定因素，如行駛時間等，因此，未來可擴展問題進行研究.

參考文獻(References)

[1] Spliet R, Desaulniers G. The discrete time window assignment vehicle routing problem [J].EuropeanJournalofOperationalResearch， 2015,244(2): 379-391. DOI:10.1016/j.ejor.2015.01.020.

[2] Spliet R, Gabor A F. The time window assignment vehicle routing problem [J].TransportationScience，2015,49(4): 721-731. DOI:10.1287/trsc.2013.0510.

[3] Solomon M M. Algorithms for the vehicle routing and scheduling problems with time window constraints [J].OperationsResearch， 1987,35(2): 254-265. DOI:10.1287/opre.35.2.254.

[4] Lau H C, Sim M, Teo K M. Vehicle routing problem with time windows and a limited number of vehicles [J].EuropeanJournalofOperationalResearch，2003,148(3): 559-569. DOI:10.1016/S0377-2217(02)00363-6.

[5] Hashimoto H, Yagiura M, Ibaraki T. An iterated local search algorithm for the time dependent vehicle routing problem with time windows [J].DiscreteOptimization, 2008,5(2): 434-456. DOI: 10.1016/j.disopt.2007.05.004.

[6] Baldacci R, Mingozzi A, Roberti R. Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints [J].EuropeanJournalofOperationalResearch, 2012,218(1): 1-6. DOI: 10.1016/j.ejor.2011.07.037.

[7] 柴獲, 何瑞春, 馬昌喜,等. 求解帶硬時間窗車輛路徑問題的改進UMDA算法 [J]. 交通運輸系統(tǒng)工程與信息, 2016, 16(2): 176-182. DOI: 10.16097/j.cnki.1009-6744.2016.02.027.

Chai Hou, He Ruichun, Ma Changxi, et al. A univariate marginal distribution algorithm hybridized with insertion heuristics for the vehicle routing problem with hard time window [J].JournalofTransportationSystemEngineeringandInformationTechnology，2016,16(2):176-182. DOI: 10.16097/j.cnki.1009-6744.2016.02.027.(in Chinese)

[8] Agatz N, Campbell A, Savelsbergh M. Time slot management in attended home delivery [J].TransportationScience， 2011,45(3): 435-449. DOI:10.1287/trsc.1100.0346.

[9] Campbell A M, Savelsbergh M. Decision support for consumer direct grocery initiatives [J].TransportationScience, 2005,39(3): 313-327. DOI:10.1287/trsc.1040.0105.

[10] Ehmke J F, Campbell A M. Customer acceptance mechanisms for home deliveries in metropolitan areas [J].EuropeanJournalofOperationalResearch, 2014,233(1): 193-207. DOI:10.1016/j.ejor.2013.08.028.

[11] Jozefowieza N, Semetb F, Talbia E G. Multi-objective vehicle routing problems [J].EuropeanJournalofOperationalResearch, 2008,189(2): 293-309. DOI:10.1016/j.ejor.2007.05.055.

[12] Huang Y, Zhao L, Woensel T V, et al. Time-dependent vehicle routing problem with path flexibility [J].TransportationResearchPartB:Methodological, 2017,95: 169-195. DOI:10.1016/j.trb.2016.10.013.

[13] Pillac V, Gendreau M, Guéret C, et al. A review of dynamic vehicle routing problems [J].EuropeanJournalofOperationalResearch, 2013,225(1): 1-11. DOI:10.1016/j.ejor.2012.08.015.

[14] Jung S, Haghani A. Genetic algorithm for the time-dependent vehicle routing problem [J].TransportationResearchRecord, 2001,1771: 164-171. DOI:10.3141/1771-21.

[15] Pierre D M, Zakaria N. Stochastic partially optimized cyclic shift crossover for multi-objective genetic algorithms for the vehicle routing problem with time-windows [J].AppliedSoftComputing, 2017,52: 863-876. DOI:10.1016/j.asoc.2016.09.039.

[16] Bean J C. Geneticalgorithms and random keys for sequencing and optimization [J].ORSAJournalonComputing, 1994,6(2): 154-160. DOI:10.1287/ijoc.6.2.154.

[17] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multi-objective genetic algorithm: NSGA-Ⅱ[J].IEEETransactionsonEvolutionaryComputation, 2002,6(2): 182-197. DOI:10.1109/4235.996017.

[18] Zitzler E, Thiele L. Multi-objective evolutionary algorithms: A comparative case study and the strength pareto approach [J].IEEETransactionsonEvolutionaryComputation, 1999,3(4): 257-271. DOI:10.1109/4235.797969.