交通限制和軟時間窗條件下的車輛路徑問題及其蟻群算法改進(jìn)

劉 瀾，吳金卓，胡 鴻

（1.湖南工學(xué)院 安全與環(huán)境工程學(xué)院，湖南 衡陽 421002；2.東北林業(yè)大學(xué) 工程技術(shù)學(xué)院，黑龍江 哈爾濱 150040）

交通限制和軟時間窗條件下的車輛路徑問題及其蟻群算法改進(jìn)

劉 瀾1，吳金卓2，胡 鴻1

（1.湖南工學(xué)院 安全與環(huán)境工程學(xué)院，湖南 衡陽 421002；2.東北林業(yè)大學(xué) 工程技術(shù)學(xué)院，黑龍江 哈爾濱 150040）

根據(jù)城市交通限制和客戶軟時間窗要求對快遞配送業(yè)務(wù)的影響，提出交通懲罰成本和時間懲罰成本兩個概念，將這兩項成本與VRP問題相結(jié)合，提出VRPTRSTW問題。根據(jù)VRPTRSTW問題描述構(gòu)建VRPTRSTW數(shù)學(xué)模型，該模型包含固定成本、距離成本、交通懲罰成本和時間懲罰成本四項優(yōu)化目標(biāo)。依據(jù)VRPTRSTW模型求解要求，改進(jìn)蟻群系統(tǒng)的螞蟻轉(zhuǎn)移概率公式和信息素更新規(guī)則。通過實際案例對改進(jìn)的蟻群算法求解VRPTRSTW問題的有效性加以驗證。

車輛路徑問題；交通限制；軟時間窗；交通懲罰成本；時間懲罰成本；VRPTRSTW；蟻群算法

1 引言

近年來由于國內(nèi)B2C電商模式逐步發(fā)展成熟，商品網(wǎng)絡(luò)交易已經(jīng)成為商品零售交易的一種重要方式，與之配套的快遞行業(yè)也得到快速發(fā)展［1］。然而，快遞配送業(yè)務(wù)劇增也在一定程度上提高了快遞行業(yè)的運(yùn)營成本，加劇了城鎮(zhèn)交通擁堵和交通管制難度［2］。同時，部分居民由于工作需要或作息時間等原因限制，并不能隨時簽收快遞，因此對快遞簽收往往有時間窗要求［3］。在這一背景下，優(yōu)化快遞公司的配送路徑，合理安排配送時間和配送路線，以緩解城鎮(zhèn)交通擁堵狀況，滿足居民簽收快遞的時間窗要求，同時幫助快遞公司節(jié)約配送成本，已經(jīng)成為物流行業(yè)亟需解決的問題。

車輛路徑問題（Vehicle Routing Problem，VRP）是指

在已知客戶需求和位置的前提下，確定車輛在各客戶間的行駛路線，以使運(yùn)輸路線最短或運(yùn)輸成本最低的系統(tǒng)優(yōu)化問題［4-5］。目前，國內(nèi)外關(guān)于VRP問題的研究大多集中在車輛行駛距離優(yōu)化方面，即以車輛行駛總里程最短作為第一優(yōu)化目標(biāo)［6-8］；此外，Ghoseiri和Fu等在研究這一問題時引入了時間窗約束，即在優(yōu)化車輛行駛路線的同時考慮了客戶時間窗要求［9-10］；而在路徑優(yōu)化過程中考慮到目標(biāo)城市實際交通狀況的研究則較少?；谶@一研究現(xiàn)狀，同時結(jié)合快遞行業(yè)物流配送業(yè)務(wù)的實際情況，本文提出交通限制和軟時間窗條件下的車輛路徑問題（Vehicle Routing Problem with Traffic Restrictions and Soft Time Windows，VRPTRSTW），并對傳統(tǒng)的蟻群算法加以改進(jìn)，以適應(yīng)VRPTRSTW問題的求解。

2 VRPTRSTW影響條件分析

2.1 交通限制影響條件

與長途交通相比，城市交通相對密集，且不同道路等級和運(yùn)輸時段的道路交通量存在顯著差異，其中快速路和主干路的交通量明顯高于次干路和支路，高峰期道路交通量明顯高于其他時段交通量［2,11］?；诔鞘薪煌ǖ倪@一特點，本文提出在交通高峰期，快遞配送優(yōu)先選擇低等級道路，以減緩城市交通壓力的思想。為將該思想融入到車輛路徑優(yōu)化問題中，引出交通懲罰系數(shù)這一參數(shù)，用符號θ表示。該參數(shù)反映的是配送車輛在選擇道路時的懲罰程度，當(dāng)?shù)缆返燃壴礁撸以浇咏诮煌ǜ叻迤跁r，懲罰系數(shù)θ值越大，表明配送車輛越應(yīng)該回避該條道路，反之亦然?，F(xiàn)給出交通懲罰系數(shù)θ在不同道路等級和交通時段的具體數(shù)值，見表1。

表1 交通懲罰系數(shù)θ取值

懲罰系數(shù)θ與道路長度d（單位：km）的乘積θd反映的是配送車輛在相應(yīng)時段選擇該條道路的交通懲罰成本，用符號C表示。顯然，交通懲罰成本C越大，配送車輛越應(yīng)該回避該條道路。

2.2 軟時間窗影響條件

時間窗口期按照時段設(shè)定的嚴(yán)格程度可分為硬時間窗和軟時間窗兩種類型［12］。由于快遞物流面向的客戶大多是訂貨量有限的散戶，對于時間窗的限定并不嚴(yán)格，因此將客戶簽收貨物的窗口期設(shè)定為軟時間窗。本文采用分段表示的時間懲罰函數(shù)來定義軟時間窗約束條件下的時間懲罰成本。時間懲罰函數(shù)表示如下：

該函數(shù)中的時間段單位均以分鐘表示。其中：時段［ET，LT］為最佳配送時段，在該時段內(nèi)沒有時間懲罰成本；時段［E，ET］和［LT，L］為可接受配送時段，在這兩個時段內(nèi)懲罰成本以時間懲罰系數(shù) ρ1和ρ2為斜率逐漸升高，本文將ρ1和ρ2的數(shù)值分別定為0.35和0.45；而時段［-∞,E］和［L,+∞］為不可接受配送時段，在這兩個時段內(nèi)配送貨物，認(rèn)為時間懲罰成本為無窮大，在蟻群算法實現(xiàn)中可設(shè)置為一個足夠大的數(shù)值表示該時間懲罰成本，本文將這一數(shù)值設(shè)為10 000。

此外，在計算過程中，對于無軟時間窗要求的客戶點，可將時段［ET，LT］定義為無窮大，即Q（t）始終為0。

3 VRPTRSTW數(shù)學(xué)模型構(gòu)建

本文研究的VRPTRSTW問題屬于多目標(biāo)優(yōu)化問題，包含固定成本優(yōu)化、距離成本優(yōu)化、交通懲罰成本優(yōu)化和時間懲罰成本優(yōu)化四項優(yōu)化目標(biāo)。本文的固定成本是指安排配送車輛和快遞員所耗費(fèi)的成本，由于規(guī)定每條配送線路只由一輛車承擔(dān)配送任務(wù)，因此固定成本優(yōu)化目標(biāo)可直接轉(zhuǎn)化為配送路線數(shù)量優(yōu)化目標(biāo)。為進(jìn)行綜合優(yōu)化，本文采取加權(quán)求和的方式將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題。

VRPTRSTW問題可描述為：某城市有一個配送中心，負(fù)責(zé)其周邊n個客戶網(wǎng)點的快遞配送任務(wù)，承擔(dān)配送任務(wù)的各輛車型號相同，每個客戶網(wǎng)點i的貨物需求量gi一定，部分客戶對簽收貨物有軟時間窗要求，現(xiàn)要求合理安排配送路線，使配送路線數(shù)量m最少，配送車輛總行駛距離最短，同時盡量降低城市交通壓力，滿足客戶軟時間窗要求，并且必須滿足以下約束條件：①每輛車各負(fù)責(zé)一條配送路線；②每條配送路線上的客戶需求量之和不得超過車輛的最大載重量q；③每條配送路線的長度不得超過車輛的最大行駛里程L；④每個客戶的貨物需求量gi必須得到滿足；⑤每個客戶僅接受一次

配送服務(wù)。

根據(jù)以上問題描述，構(gòu)建VRPTRSTW數(shù)學(xué)模型如下：

在該數(shù)學(xué)模型中，（2）式為目標(biāo)函數(shù)，等式右側(cè)對應(yīng)四項優(yōu)化目標(biāo)，其中ω1、ω2、ω3和ω4為四項優(yōu)化目標(biāo)對應(yīng)的權(quán)重，分別取值0.2、0.2、0.3和0.3；dij為路徑i-j的長度；xijk為判定車輛k是否選擇路徑i-j的判定系數(shù)；Cij為路徑i-j的交通懲罰成本；Qi（t）為客戶i對應(yīng)的時間懲罰成本；si為判定客戶i是否有軟時間窗要求的判定系數(shù)；（3）式限定了每條路線的長度不能超過車輛的最大行駛里程L；（4）式限定了每條路線配送貨物的總量不能超出車輛的最大載重量q；（5）式限定了每個客戶i僅接受一次配送服務(wù)，其中yik為判定車輛k是否服務(wù)于客戶i的判定系數(shù)；（6）-（8）式共同確定了每條配送路線能夠形成一條完整的閉合回路，其中Vk是指由車輛k提供配送服務(wù)的客戶集合；（9）式?jīng)Q定了車輛k在服務(wù)完客戶j后應(yīng)立即離開，前往下一個客戶點l；（10）式?jīng)Q定了各車輛初始時刻均從配送中心出發(fā)，并在完成配送任務(wù)后最終返回配送中心，此處配送中心用數(shù)字編號0表示。

4 基于VRPTRSTW的蟻群算法改進(jìn)

蟻群算法（Ant Colony Optimization，ACO）已經(jīng)被證明是求解VRP問題的一種有效的啟發(fā)式算法［13-14］。然而，VRPTRSTW問題作為VRP問題的一種延伸，應(yīng)用傳統(tǒng)的蟻群算法對其進(jìn)行求解并不能得到令人滿意的優(yōu)化結(jié)果。為此，本文針對VRPTRSTW問題中的交通限制和軟時間窗影響條件，提出一種基于蟻群系統(tǒng)（Ant Colony System,ACS）的改進(jìn)策略。

4.1 螞蟻轉(zhuǎn)移概率調(diào)整

在蟻群系統(tǒng)中，決定各螞蟻（配送車輛）選擇下一客戶點的影響因素是各段路徑的信息素量和路徑長度，但是交通懲罰成本和時間懲罰成本也應(yīng)對螞蟻的路徑選擇產(chǎn)生影響，因此將任一螞蟻k在客戶點i向客戶點j轉(zhuǎn)移的概率表述為：

其中：α、β、γ和σ為四個參數(shù)，反應(yīng)四項決定因素的相對重要性，本文分別取值1、3、2、3；τij（t）和ηij（t）分別表示t時刻路段i-j的信息素量和能見度；μij（t）表示t時刻路段i-j的交通決定因素；λj（t）表示t時刻客戶點j的軟時間窗決定因素，μij（t）和λj（t）的定義見公式（15）和（16）。

同樣道理，在蟻群系統(tǒng)的偽隨機(jī)比例選擇規(guī)則中，也引入 μij（t）和λj（t）兩項決定因素，則螞蟻轉(zhuǎn)移選擇公式可調(diào)整為：

其中：q0為一介于［0,1］之間的參數(shù)，每當(dāng)螞蟻要選擇下一路徑時，都要先隨機(jī)選?。?,1］之間的某一數(shù)值q，并將q與q0做大小比較，以判定螞蟻在各段路徑上的轉(zhuǎn)

從式（15）和（16）可知，交通懲罰成本Cij和時間懲罰成本Qj值越大，則交通決定因素 μij（t）和軟時間窗決定因素λj（t）值越小，導(dǎo)致轉(zhuǎn)移概率Pijk（t）值越小，即t時刻螞蟻k越應(yīng)該回避i-j路段。因此，引入 μij（t）和λj（t）兩項決定因素，有助于螞蟻在搜索路徑時盡量避免選擇交通壓力大的路線，同時盡量滿足客戶的軟時間窗要求。

4.2 信息素更新規(guī)則改進(jìn)

蟻群系統(tǒng)有全局更新和局部更新兩種信息素更新規(guī)則［15］。目前已證明，與局部更新規(guī)則相比，全局更新規(guī)則在最優(yōu)路徑搜索效率方面更具優(yōu)勢［16］。因此本文采用全局更新規(guī)則對各段路徑的信息素進(jìn)行更新，并根據(jù)VRPTRSTW問題描述，對全局更新規(guī)則加以改進(jìn)。

在VRPTRSTW問題中，由于考慮了交通限制和軟時間窗影響條件，為了使這兩項因素在信息素全局更新中得到更充分體現(xiàn)，需要對單位路段信息素增量Δτ做重新定義，現(xiàn)給出Δτ新的定義公式如下：

其中：Δτ（i,j）表示路段i-j的信息素增量；Lgb表示全局最優(yōu)路徑總長度；Cgb和分別表示全局最優(yōu)路徑的交通懲罰成本和時間懲罰成本；a、b、c分別是反應(yīng)相對重要性的參數(shù)，分別取值0.3、0.3、0.4。

同對照組給予飲食指導(dǎo)；同時給予中藥內(nèi)服，藥物組成：柴胡10 g，陳皮9 g，白芍15 g，白術(shù)15 g，郁金15 g，砂仁6 g，枳殼9 g，香附10 g，麥芽15 g，黨參15 g，茯苓15 g，瓦楞子15 g，炙甘草9 g。1劑/d，水煎取汁300 mL，分早晚2次口服；配合中藥艾灸法，取中脘穴、雙側(cè)足三里穴，施以艾灸法，每次艾灸30 min，1次/d。治療14 d為1個療程。

與蟻群系統(tǒng)原有的單位路段信息素增量定義相比，新的定義中在考慮全局最優(yōu)路徑的總長度Lgb對信息素增量影響的同時，也充分體現(xiàn)了全局最優(yōu)路徑的交通懲罰成本Cgb和時間懲罰成本對信息素增量的影響，這有利于進(jìn)一步提高螞蟻搜索最優(yōu)路徑的效率，同時避免蟻群系統(tǒng)陷入局部最優(yōu)解。

在給出Δτ新的定義后，各路段信息素按照蟻群系統(tǒng)既定公式（19）進(jìn)行更新。在公式（19）中，δ為信息素?fù)]發(fā)系數(shù)，其值介于［0,1］之間，反映的是信息素?fù)]發(fā)的速度，本文取值0.2。

5 改進(jìn)的蟻群算法在VRPTRSTW實際案例中的應(yīng)用

5.1 案例背景與基礎(chǔ)數(shù)據(jù)

本文以YT速遞西寧分公司一分部（以下簡稱YT速遞一分部）的快遞配送業(yè)務(wù)為實證對象，應(yīng)用MATLAB7.9軟件平臺對改進(jìn)的蟻群算法加以實現(xiàn)。

YT速遞一分部的快遞配送中心位于西寧市城東區(qū)楊家三巷，地理坐標(biāo)為東經(jīng)101.814 889°，北緯36.614 963°，主要負(fù)責(zé)西寧市城東區(qū)八一路片區(qū)的快遞配送業(yè)務(wù)，業(yè)務(wù)覆蓋范圍包括18個客戶點，配送車輛為統(tǒng)一制式的電動三輪車，最大載貨量為150件，最大行駛里程為250km。18個客戶網(wǎng)點的基礎(chǔ)信息見表2。

表2 客戶網(wǎng)點基礎(chǔ)信息

此外，為便于蟻群算法實現(xiàn)，將配送中心所在位置定義為編號0。

根據(jù)表2中18個客戶點的地理坐標(biāo)，蟻群系統(tǒng)在搜索配送路徑時會計算出各客戶點間的曼哈頓距離；此

YT速遞一分部配送服務(wù)范圍內(nèi)各主要交通路線的道路等級統(tǒng)計見表3。

表3 主要交通路線道路等級

此外，YT速遞一分部每天的快遞配送時間段為10：00-18：00。而在西寧市，每個工作日的11：00-14：00期間是城市居民中午上下班和學(xué)生上下學(xué)的時間段，這段時間城市各主要街道交通量激增，會出現(xiàn)不同程度的交通擁堵，因此將每個工作日的11：00-14：00時間段確定為交通高峰期。

5.2 配送路徑優(yōu)化前后比較分析

本文采用“路徑數(shù)量”、“距離成本”、“交通懲罰成本”、“時間懲罰成本”以及“綜合成本”這五項指標(biāo)對原配送方案和優(yōu)化后配送方案進(jìn)行對比分析。

首先，對原配送方案進(jìn)行調(diào)查與統(tǒng)計，得到原配送方案中的各項指標(biāo)值見表4。

表4 原配送方案各項指標(biāo)值

在得到原配送方案的路徑數(shù)量、距離成本、交通懲罰成本和時間懲罰成本后，按照式（2）計算綜合成本T= 8.56，綜合成本即為VRPTRSTW數(shù)學(xué)模型中的優(yōu)化目標(biāo)。

然后運(yùn)用改進(jìn)的蟻群算法搜索新路徑，經(jīng)運(yùn)算得出新配送方案，新方案中的各項指標(biāo)值見表5。

表5 優(yōu)化后配送方案各項指標(biāo)值

在得到優(yōu)化后配送方案的各項指標(biāo)值后，按照相同方式，應(yīng)用式（2）計算優(yōu)化后綜合成本T*=5.77。

將優(yōu)化前后兩套配送方案的各項指標(biāo)值進(jìn)行對比分析，得出對比分析結(jié)果見表6。

表6 優(yōu)化前后配送方案各項指標(biāo)值對比分析

表6中各項指標(biāo)對應(yīng)的優(yōu)化值是由原方案指標(biāo)值減去優(yōu)化后方案對應(yīng)指標(biāo)值得到；優(yōu)化率是由優(yōu)化值除以原方案相應(yīng)指標(biāo)值得到。

由表6中各項指標(biāo)的優(yōu)化值和優(yōu)化率可知，由于考慮到西寧市城東區(qū)的交通限制和客戶軟時間窗影響條件，配送路線總里程（距離成本）的優(yōu)化效果并不明顯，但是優(yōu)化后配送方案的交通懲罰成本明顯降低，說明該方案可使當(dāng)?shù)氐慕煌▔毫Φ靡杂行Ь徑?，同時該方案的時間懲罰成本降為0，說明該方案能夠保證所有客戶的軟時間窗要求都得到滿足，從而保證綜合成本得以顯著降低。因此，本案例證明改進(jìn)的蟻群算法對于VRPTRSTW問題的優(yōu)化求解具有顯著效果。

6 結(jié)論

本文根據(jù)快遞行業(yè)物流配送業(yè)務(wù)的實際情況，考慮到城市交通限制和客戶軟時間窗要求對快遞配送的影響，提出了交通懲罰成本和時間懲罰成本兩個概念，并給出量化公式；將這兩項成本與傳統(tǒng)的VRP問題相結(jié)合，提出了VRPTRSTW問題；并根據(jù)問題描述構(gòu)建了VRPTRSTW數(shù)學(xué)模型；然后依據(jù)模型的求解要求，對蟻群系統(tǒng)的螞蟻轉(zhuǎn)移概率和信息素更新規(guī)則加以改進(jìn)；最后通過實際案例對改進(jìn)的蟻群算法求解VRPTRSTW問題的效果進(jìn)行驗證，試驗結(jié)果表明，改進(jìn)的蟻群算法對

于求解VRPTRSTW問題的效果比較顯著。

［1］黃飛.基于B2C模式我國快遞行業(yè)發(fā)展影響因素分析［J］.中國集體經(jīng)濟(jì),2016,（22）：16-17.

［2］朱永升,韓伯棠,夏平,等.交通限制條件下城市物流配送路線優(yōu)化選擇［J］.武漢理工大學(xué)學(xué)報（交通科學(xué)與工程版）,2004, 28（3）：391-394.

［3］Br?ysy O,Gendreau M.Vehicle routing problem with time windows,part I：Route construction and local search algorithms［J］. Transportation Science,2005,39：104-118.

［4］Urazghildiiev I,Ragnarsson R,Ridderstrom P,etal.Vehicle classification based on the radar measurement of height profiles［J］.IEEE Transactions on Intelligent Transportation Systems,2007,8（2）：245-253.

［5］段鳳華,符卓.B2C電子商務(wù)環(huán)境下物流配送路徑模型與算法［J］.計算機(jī)應(yīng)用,2009,29（2）：580-582.

［6］Sarildis D,Power S.A heuristic method for the open vehicle routing problem［J］.Journal of the Operational Research Society,2000,51：564-573.

［7］Brandao J.A tabu search algorithm for the open vehicle routing problem［J］.European Journal of Operational Research, 2004,157：552-564.

［8］崔雪麗,馬良,范炳全.車輛路徑問題（VRP）的螞蟻搜索算法［J］.系統(tǒng)工程學(xué)報,2004,（4）：418-422.

［9］Ghoseiri K,Ghannadpour S F.Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm［J］.Applied Soft Computing,2010,（10）：1 096-1 107.

［10］Fu Z,Eglese R,Li L Y O.A unified tabu search algorithm for vehicle routing problems with soft time windows［J］.Journal of the Operational Research Society,2008,59（5）：663-673.

［11］張云龍,李昂.城市道路網(wǎng)等級級配研究［J］.市政技術(shù),2013, 31（1）：19-21.

［12］于芹.基于蟻群算法的物流車輛路徑優(yōu)化問題的研究［D］.上海：上海交通大學(xué),2007.

［13］Bell J E,Mc Mullen P R.Ant colony optimization techniques for the vehicle routing problem［J］.Advanced Engineering Informatics,2004,18（1）：41-48.

［14］Kuo R J,Chiu C Y,Lin Y J.Integration of fuzzy theory and ant algorithm for vehicle routing problem with time window［A］. Proceedings of the IEEE Annual Meeting of the Fuzzy Information［C］.2004.

［15］李士勇,陳永強(qiáng),李研.蟻群算法及其應(yīng)用［M］.哈爾濱：哈爾濱工業(yè)大學(xué)出版社,2004.

［16］陳迎欣.基于改進(jìn)蟻群算法的車輛路徑優(yōu)化問題研究［J］.計算機(jī)應(yīng)用研究,2012,29（6）：2 031-2 034.

Improved Ant Colony Algorithm for VRP with Traffic Restriction and Soft Time Window

Liu Lan1,Wu Jinzhuo2,Hu Hong1
（1. School of Safety Environment Engineering, Hunan Institute of Technology, Hengyang 421002；2. School of Engineering Technology, Northeast University of Forestry, Harbin 150040, China）

In this paper, in light of the impact of urban traffic restriction and customer soft time window on the express deliverybusiness, we proposed the concept of traffic penalty cost and time penalty cost and combined the two with the VRP to become theVRPTRSTW. Next, according to the description of the VRPTRSTW, we built its mathematical model which included four optimizationtargets, namely the fixed cost, distance cost, traffic penalty cost and time penalty cost. Then, based on the conditions for the solution of themodel and through an empirical case, we improved the migration probability equation and pheromone updating rule of the ant colony system.At the end, we verified the effectiveness of the improved ant colony algorithm in solving the VRPTRSTW.

VRP； traffic restriction； soft time window； traffic penalty cost； time penalty cost； VRPTRSTW； ant colony algorithm

U116.2；F224

A

1005-152X（2016）09-0091-06

10.3969/j.issn.1005-152X.2016.09.020

2016-08-08

劉瀾（1988-），男，黑龍江綏化人，碩士，助理實驗師，主要研究方向：物流系統(tǒng)仿真與優(yōu)化。