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

劉 瀾，吳金卓，胡 鴻

（1.湖南工學院 安全與環境工程學院，湖南 衡陽 421002；2.東北林業大學 工程技術學院，黑龍江 哈爾濱 150040）

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

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

（1.湖南工學院 安全與環境工程學院，湖南 衡陽 421002；2.東北林業大學 工程技術學院，黑龍江 哈爾濱 150040）

根據城市交通限制和客戶軟時間窗要求對快遞配送業務的影響，提出交通懲罰成本和時間懲罰成本兩個概念，將這兩項成本與VRP問題相結合，提出VRPTRSTW問題。根據VRPTRSTW問題描述構建VRPTRSTW數學模型，該模型包含固定成本、距離成本、交通懲罰成本和時間懲罰成本四項優化目標。依據VRPTRSTW模型求解要求，改進蟻群系統的螞蟻轉移概率公式和信息素更新規則。通過實際案例對改進的蟻群算法求解VRPTRSTW問題的有效性加以驗證。

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

1 引言

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

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

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

2 VRPTRSTW影響條件分析

2.1 交通限制影響條件

與長途交通相比，城市交通相對密集，且不同道路等級和運輸時段的道路交通量存在顯著差異，其中快速路和主干路的交通量明顯高于次干路和支路，高峰期道路交通量明顯高于其他時段交通量［2,11］。基于城市交通的這一特點，本文提出在交通高峰期，快遞配送優先選擇低等級道路，以減緩城市交通壓力的思想。為將該思想融入到車輛路徑優化問題中，引出交通懲罰系數這一參數，用符號θ表示。該參數反映的是配送車輛在選擇道路時的懲罰程度，當道路等級越高，且越接近于交通高峰期時，懲罰系數θ值越大，表明配送車輛越應該回避該條道路，反之亦然。現給出交通懲罰系數θ在不同道路等級和交通時段的具體數值，見表1。

表1 交通懲罰系數θ取值

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

2.2 軟時間窗影響條件

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

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

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

3 VRPTRSTW數學模型構建

本文研究的VRPTRSTW問題屬于多目標優化問題，包含固定成本優化、距離成本優化、交通懲罰成本優化和時間懲罰成本優化四項優化目標。本文的固定成本是指安排配送車輛和快遞員所耗費的成本，由于規定每條配送線路只由一輛車承擔配送任務，因此固定成本優化目標可直接轉化為配送路線數量優化目標。為進行綜合優化，本文采取加權求和的方式將多目標優化問題轉化為單目標優化問題。

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

配送服務。

根據以上問題描述，構建VRPTRSTW數學模型如下：

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

4 基于VRPTRSTW的蟻群算法改進

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

4.1 螞蟻轉移概率調整

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

其中：α、β、γ和σ為四個參數，反應四項決定因素的相對重要性，本文分別取值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）。

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

其中：q0為一介于［0,1］之間的參數，每當螞蟻要選擇下一路徑時，都要先隨機選取［0,1］之間的某一數值q，并將q與q0做大小比較，以判定螞蟻在各段路徑上的轉

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

4.2 信息素更新規則改進

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

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

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

同對照組給予飲食指導；同時給予中藥內服，藥物組成：柴胡10 g，陳皮9 g，白芍15 g，白術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次口服；配合中藥艾灸法，取中脘穴、雙側足三里穴，施以艾灸法，每次艾灸30 min，1次/d。治療14 d為1個療程。

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

在給出Δτ新的定義后，各路段信息素按照蟻群系統既定公式（19）進行更新。在公式（19）中，δ為信息素揮發系數，其值介于［0,1］之間，反映的是信息素揮發的速度，本文取值0.2。

5 改進的蟻群算法在VRPTRSTW實際案例中的應用

5.1 案例背景與基礎數據

本文以YT速遞西寧分公司一分部（以下簡稱YT速遞一分部）的快遞配送業務為實證對象，應用MATLAB7.9軟件平臺對改進的蟻群算法加以實現。

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

表2 客戶網點基礎信息

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

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

YT速遞一分部配送服務范圍內各主要交通路線的道路等級統計見表3。

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

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

5.2 配送路徑優化前后比較分析

本文采用“路徑數量”、“距離成本”、“交通懲罰成本”、“時間懲罰成本”以及“綜合成本”這五項指標對原配送方案和優化后配送方案進行對比分析。

首先，對原配送方案進行調查與統計，得到原配送方案中的各項指標值見表4。

表4 原配送方案各項指標值

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

然后運用改進的蟻群算法搜索新路徑，經運算得出新配送方案，新方案中的各項指標值見表5。

表5 優化后配送方案各項指標值

在得到優化后配送方案的各項指標值后，按照相同方式，應用式（2）計算優化后綜合成本T*=5.77。

將優化前后兩套配送方案的各項指標值進行對比分析，得出對比分析結果見表6。

表6 優化前后配送方案各項指標值對比分析

表6中各項指標對應的優化值是由原方案指標值減去優化后方案對應指標值得到；優化率是由優化值除以原方案相應指標值得到。

由表6中各項指標的優化值和優化率可知，由于考慮到西寧市城東區的交通限制和客戶軟時間窗影響條件，配送路線總里程（距離成本）的優化效果并不明顯，但是優化后配送方案的交通懲罰成本明顯降低，說明該方案可使當地的交通壓力得以有效緩解，同時該方案的時間懲罰成本降為0，說明該方案能夠保證所有客戶的軟時間窗要求都得到滿足，從而保證綜合成本得以顯著降低。因此，本案例證明改進的蟻群算法對于VRPTRSTW問題的優化求解具有顯著效果。

6 結論

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

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

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

［2］朱永升,韓伯棠,夏平,等.交通限制條件下城市物流配送路線優化選擇［J］.武漢理工大學學報（交通科學與工程版）,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電子商務環境下物流配送路徑模型與算法［J］.計算機應用,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］.系統工程學報,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］張云龍,李昂.城市道路網等級級配研究［J］.市政技術,2013, 31（1）：19-21.

［12］于芹.基于蟻群算法的物流車輛路徑優化問題的研究［D］.上海：上海交通大學,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］李士勇,陳永強,李研.蟻群算法及其應用［M］.哈爾濱：哈爾濱工業大學出版社,2004.

［16］陳迎欣.基于改進蟻群算法的車輛路徑優化問題研究［J］.計算機應用研究,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-），男，黑龍江綏化人，碩士，助理實驗師，主要研究方向：物流系統仿真與優化。