約束不均衡條件下車輛雙層線路規劃流動穩定性問題研究

收稿日期：2021-12-02；修回日期：2022-01-13

基金項目：四川省地方普通本科高校應用型示范課程《貨物運輸組織》建設項目（川教涵（2019）31號）

作者簡介：馬貴平（1982-），男，四川簡陽人，副教授，博士，主要研究方向為物流優化與信息化、交通運輸、高等教育研究（maguiping2021@126.com）；周玉清（1986-），女，四川自貢人，副教授，碩士，主要研究方向為綜合運輸與物流.

摘 要：雙層線路在高峰期時，車輛規劃計算最優解過程中為每個約束條件都分配一個最優解，會極大地浪費計算資源。車輛物流線路規劃過程中，約束條件不均衡的天然特性，會導致規劃過程車輛的流動穩定性受到影響。針對約束條件不均衡，對車輛雙層線路規劃流動穩定性影響的問題展開研究。構建了車輛物流線路雙層規劃Stackelberg模型，上層部分主要用于約束車輛物流線路的容量以及結構，排除不可用路線；下層部分主要對車輛物流線路實施均衡化配流，防止過多的車輛擁擠在同一路線中。利用模型將調度業務整合到高容量的路線中調度。在模型中加入調度資源緩存技術，保證調度過程的穩定性。實驗結果表明：與使用單一模型求解相比，使用該模型進行調度業務疏導，可以在很大程度上獲得更穩定的性能，解決了車輛物流線路規劃流動穩定性問題。

關鍵詞：車輛物流線路； 雙層問題； 斯塔克爾伯格模型； 約束條件； 優化模型； 流動穩定性

中圖分類號：TP399"" 文獻標志碼：A

文章編號：1001-3695（2022）06-034-1805-04

doi：10.19734/j.issn.1001-3695.2021.12.0633

Study on flow stability of vehicle bilevel route planning under constrained disequilibrium

Ma Guiping， Zhou Yuqing

（School of Rail Transportation， Southwest Jiaotong University Hope College， Chengdu 610400， China）

Abstract：In the peak period of double-layer line， in the process of calculating the optimal solution of vehicle planning， assigning an optimal solution to each constraint will greatly waste computing resources. In the process of vehicle logistics route planning， the natural characteristics of unbalanced constraints will affect the flow stability of vehicles in the planning process. This paper studied the influence of unbalanced constraints on the flow stability of vehicle bilevel route planning. It constructed a two-level programming Stackelberg model for vehicle logistics lines. The upper part was mainly used to restrict the capacity and structure of vehicle logistics lines and eliminate unavailable routes. The lower part mainly implemented balanced distribution of vehicle logistics lines to prevent too many vehicles from crowding in the same route. It used model to integrate scheduling business into high capacity routing. It added the scheduling resource cache technology to the model to ensure the stability of the scheduling process. The experimental results show that， compared with the single model solution， using the model to schedule the business grooming can achieve a more stable performance to a large extent， and solve the flow stability problem of vehicle logistics line planning.

Key words：vehicle logistics line; double layer problem; Stackelberg model; constraints; optimization model; flow stability

0 引言

在城市化發展進程不斷加快的社會背景下，城市道路交通壓力也不斷增加，交通安全、交通擁堵等問題不斷發酵，成為交通安全秩序平穩過程中亟待解決的問題之一［1］。高峰期間，一些大城市復雜路段的車流量急劇增加，針對這種情況，通過車輛線路規劃能夠及時且主動地按需分配路網的時間與空間資源，使復雜路段的車輛通行效率得到提高［2］。然而，由于一些復雜路段的路口路況存在的復雜性與不確定性，大大增加了車輛線路規劃工作的難度［3］。當前的相關車輛線路規劃方法存在一些問題。

孫滬增等人［4］提出了一種帶時間窗車輛路徑規劃方法，該方法首先根據狀態轉移規則設計了多個局部搜索算子，用于優化不同子回路之間的路徑，在引入動態更新信息素的基礎上，設計車輛轉移規則，用于指導車輛線路動態參數的選擇。但該方法僅僅以時間約束為條件，應用到復雜路段的情況下效率較低。李麟等人［5］提出了基于穩定性和宏觀交通流模型的車輛路徑規劃方法，其首先通過預測交通流來判斷未來一段時間內的交通環境，然后使用穩定性判斷模型評估未來一段時間內交通環境的安全性，再結合車流密度變化趨勢規劃出最快且最安全的車輛路線，在復雜路段該模型的穩定性會受到較大影響。陳群等人［6］對區域交通微循環支線網絡交叉口無沖突交通流組織優化方法展開研究，該方法在分析交叉口車流沖突的基礎上，將最小車流時間作為規劃目標，構建無沖突交通流組織規劃模型，并利用遺傳算法對模型進行求解；但是在復雜路段，模型求解會陷入不收斂的境地，造成流動穩定性被破壞。吳奇倫［7］優化了車輛路徑規劃算法，提出了基于權值累加的多車輛動態路徑規劃算法，根據過去時段的車流量累計情況，研判當前時刻車輛行駛最優方案。Li等人［8］采用反學習模型優化灰狼算法，提高路徑規劃的收斂速度，結合車流量情況，合理分配路段資源。Kaffash等人［9］應用大數據算法，提升交通領域應用的智能化程度，通過智能交通系統中的信號識別、目標檢測等數據信息對交通流量進行預測，合理規劃出行時間和出行路線規劃。以上三種方法在復雜路段應用過程中均存在穩定性被破壞的問題。在實際應用中發現，以上傳統方法在一定程度上可以起到緩解交通壓力的作用，但是由于均未對可用車輛線路進行均衡化配流處理，導致大部分車輛均擁堵在最優線路中，從而增加了車輛行駛或等待的時間，降低了車輛行駛效率，違背了最優線路規劃的目的，導致規劃方法存在線路規劃收斂性低以及路線分擔率不均衡的問題，弱化了線路規劃效果，破壞了流動穩定性。

為了解決上述方法中存在的問題，本文針對復雜路況中的雙層路況，提出了一種路口車輛線路雙層規劃方法，在構建雙層規劃斯塔克爾伯格（Stackelberg）模型的基礎上，對車輛線路進行均衡化配流，防止大部分車輛擁擠在同一路線中，以此緩解高峰期交叉路口的交通壓力。

1 雙層線路規劃流動穩定性問題的提出

當車輛規劃線路處在雙層的復雜情況下，以單一模型計算最優解的方式，很難保證路線規劃的穩定性。因為相關算法需要依靠過多的約束條件進行求解，雖然具備了模型的全局優化性能，但在局部會出現穩定性問題。目前，復雜區域的車輛線路規劃模型，實質就是在多種約束條件下完成區域車輛線路的最優規劃問題。本文以最常見的蟻群算法為例：螞蟻在運動的過程中會留下信息素，蟻群會根據信息素的含量不斷選取最優線路進行爬行［10］。蟻群算法的實質就是根據蟻群的智能行為選取出信息素最多的路徑，同時拋棄不符合目前模型約束條件的線路，進而確保可在全局路徑中搜索出最有效的路徑，進而得到最完整、最優的區域車輛線路［11，12］。將這種常見的調度模型應用到雙層路況車輛調度中。

在求解模型前需要設置出雙層網絡的路徑選擇規則，路徑選擇的規則如式（1）所示。

px（i，j）=τα（i，j）·ηβ（i，j）τα（i，h）·ηβ（i，h）（1）

其中：px（i，j）代表螞蟻x從路徑節點i運動到路徑節點j可能發生的概率，i和j均代表路徑節點;h代表循環次數;τ（i，j）代表路徑內（i，j）的信息濃度;α和β代表路徑選取過程中各種因子之間的相對關系;η（i，j）代表路徑（i，j）中的整體啟發因子，其表達式為

η（i，j）=LkG－1ω/wk（2）

其中：Lk代表約束參數集合;wk代表具有可乘性的約束參數。

蟻群算法的另一規則是蟻群信息素的更新規則，當螞蟻抵達路徑目標節點時，已完成信息素的更新。為保證不出現殘留信息含量掩蓋啟發信息的問題，需要提前對殘留信息進行消除，則路徑（i，j）中信息素的消除規則表達式為

τ（i，j）=Δτ（i，j）+Δτx（i，j）·（1-ρ）（3）

其中：ρ代表路徑中信息素的揮發系數;1－ρ代表路徑中信息素的殘留因子;Δτ（i，j）代表信息素在每次更新過程中增加的量;Δτx（i，j）代表螞蟻x在更新信息素過程中其貢獻的信息素含量。

由以上推理過程可以看出，由于雙層路況的車輛負載被定義為交通網絡的臨時行為，這種行為可以直接表達出車輛調度的真實情況，因此這個行為的性能和道路擁塞相關。一旦式（2）中，雙層路線約束集合中的約束條件過多，會導致式（2）的結果對式（3）造成影響，因為式（3）中在進行路線消除中，為了保證模型收斂，需要保證結果的唯一性，導致在眾多最優解中，必須刪除一些次優解，但次優解可能大幅影響模型穩定性，一旦刪除，規劃穩定性會受到大幅影響。由此可得，路況中的約束條件不均衡性是普遍的，如果能有效地利用約束條件不均衡特性，路況的利用率和阻塞性能都將得到改善。

2 車輛線路雙層規劃Stackelberg模型

為保證在高峰期交叉路口車輛線路的效率以及準確性，提出車輛線路雙層規劃Stackelberg模型。該模型共分為兩層，上層是針對車輛線路的容量以及結構的定義問題，下層是針對目前道路調度需求對道路進行車輛均衡配流。其中，上層模型的表達式為

min F1［U，v］=U∑a∈Acava=U∑a∈Aθpa

min F2［U，v］=U∑a∈Ava（4）

其中：min F1［U，v］代表車輛行駛時間成本總和最小化的模型；min F2［U，v］代表路徑結構模型；U代表模型中帶有區間數的弧容量；v代表弧流量;ca代表模型中弧a線路上產生的車輛行駛間隙時間系數;va代表弧a中的車流量;A（a∈A）代表高峰期路口處所有可通行的路徑的集合;θpa代表整個路徑網的關系。

上述模型屬于雙重目標的規劃問題。兩個目標分別是將車輛行駛時間成本最小化以及構建出通行率最高的車輛線路，盡可能地滿足高峰期交叉路口的通車需要。此問題通常情況下可轉換為對模型的約束問題［13］，而上層模型中弧a的車流量是根據下層配流模型進行設定的。Stackelberg模型的下層主要是在目前可行駛的線路中，將車輛均勻地分配到各條道路中，從而保證高峰期交叉路口處的暢通以及控制車輛的成本，即生成車輛均衡化配流模型。由于目前汽車保有量持續攀升，導致城市道路常處于相對擁擠的狀態，出現時間不斷加長，以及車輛行駛時間成本增加的問題［14］。因此，本文研究在彈性需求的基礎上構建車輛線路網絡下層模型［15］，即構建高峰期交叉路口處車輛均衡化配流模型，其表達式為

min Z=∑ω∈W∫gω0ξ×Rwumaxadxy×G-1ω（5）

其中：min Z代表車輛行駛時間成本最低的車輛路線配流;ω代表車輛行駛路徑;W（ω∈W）代表全部車輛起點的集合;Rw代表起點集合針對w中線路的集合;ξ代表車輛線路節點;umaxa代表弧a中可允許通行的最大容量;gω代表起點集合針對w而言的通行量;dxy代表點x和y之間的距離;G－1ω代表配流模型中時間與成本之間的單調增函數，其表達式為

G－1ω=f（ω）/A×ca（6）

其中：f（ω）代表時間函數。

式（5）中最主要的約束條件為符合弧上容量的約束，其余的約束條件均是車輛線路網絡中允許進行且符合流量守恒條件限制的流量。

3 緩存區的引入

在考慮模型的整體穩定性性能時，針對約束條件不均衡的問題，在模型中設計一個緩存容量的約束值，該值會隨著路況上車輛擁堵程度的變化而變化。該值在模型中隨著車輛負載的變化調整，方法如下：

a）將雙層路況中到達可規劃的車輛業務記為高優先級業務。

b）在得到車輛路況上交通負載強度下，從0開始調整模型中設置的緩存區大小，調整單位以調度業務梳理比例為基礎。

c）當模型中的緩存區以單位速度調整時，注意雙層路況交通網絡中的穩定性波動情況，直到波動不足1%時，記錄該數值。然后繼續調整緩存區大小，并反復進行步驟c）的操作，直到記錄的阻塞率出現極小值時結束。

d）在計算出阻塞率極小值后，以該數值確定的業務負載強度下緩存區大小的限定額度值。

e）設定想要的交通線路堵塞負載長度的大小反復進行步驟b）～d）的流程，直到模型中的交通網絡阻塞率數值，達到要求數值的上限。但是一般會留出一定的富余，一般為最優條件的20%。這樣就找到了緩存區大小最優數值，隨業務負載強度變化的情況。

為了讓模型中的緩存區起到更好的作用，規定在線路規劃過程中，只有高優先級的車輛調度業務和滿足一定條件的低優先級的車輛規劃業務，例如一些突發狀況，才能開啟緩存區。正常的車輛調度過程中，低優先級的線路規劃業務，必須同時需要滿足以下條件才能開啟。

4 實驗結果與分析

為了驗證約束不均衡條件下車輛雙層線路規劃流動穩定性問題研究方法的有效性，利用MATLAB建立車輛線路雙層規劃Stackelberg模型，并對模型進行求解，并設計如下對比實驗。選取某高峰期交叉路的a、b、c三條線路，分別采用本文方法（方法1）、帶時間窗車輛路徑規劃方法（方法2）和基于穩定性和宏觀交通流模型的車輛路徑規劃方法（方法3）展開測試。

4.1 收斂性檢驗

首先將車輛雙層線路規劃結果的收斂性作為測試指標。收斂性越高表明該方法的車輛雙層線路規劃效果越好。收斂性反映的是每種車輛線路規劃方法生成最優解時所需的實驗次數，實驗次數的多少即可反映方法規劃的快慢程度，且其生成最優解的效率直接影響收斂性的效果。間隙時間系數能夠反映每種車輛線路規劃方法生成的等待時間差總和的最優解。當間隙系數達到同一標準時，所需的實驗次數越少，表明方法的收斂性越好。因此，選取規劃車輛線路時生成最優路徑的間隙時間系數作為收斂指標，指定三種方法的間隙系數達到同一標準，比較三種方法所需的實驗次數，進而得出三種方法的收斂性。測試結果如圖1所示。根據圖1結果顯示，經過多次實驗后三種方法均到達指定的間隙函數，三種方法所需的實驗次數從多到少依次排序為方法3、方法2以及方法1，從而可知收斂性最好的是方法1，其次是方法2，方法3的收斂性能最差。

4.2 路線分擔能力檢驗

目前車輛路線規劃的另一大問題是配流不均衡，導致部分可用路線無車輛通過，部分路線內的車輛十分擁擠，大大降低了高峰期交叉口車輛通過效率。因此，將可行駛路線分擔率作為路線分擔能力的評價指標。可行駛路線分擔率是指在可行駛路線中，車輛的出行量占總出行量的比率，其計算公式為

FD=CCZC×100%（7）

其中：CC代表車輛的出行量；ZC代表總出行量。其可行駛路線分擔率越平衡，表明方法的路線分擔能力越好。根據式（7）計算三種方法在a、b、c三條線路下的分擔率，得出三個車輛路線規劃方法的優劣，結果如表1所示。

根據表1可看出，三條路線的分擔率最平衡的是方法1，其余兩種方法的分擔率大部分都在線路a中，尤其是方法3的線路a，其分擔率過高，容易造成道路擁堵，降低車輛效率和高峰期交叉口車輛通過效率。

方法1分擔率均衡的原因是在構建車輛線路規劃模型時，加入了車輛均衡配流模型，可有效控制每條最優路徑中的車流量，避免出現因車輛過多而導致的道路擁堵等情況。

4.3 流動穩定性檢驗

為了進一步驗證方法的流動穩定性，將緩存區的道路資源利用率作為評價指標。緩存區的道路資源利用率是指緩存區的道路中線路被使用的情況與包含的道路數量之間的比率。當緩存區的道路資源利用率小于其設定的閾值時，表明線路未被使用;反之，該線路被使用。緩存區的道路資源利用率計算公式為

U=k∑|E|j=1∑kj=1eij|E|×100%（8）

其中：eij代表緩存區中第i線路在第j次被使用的情況;|E|代表緩存區包含的道路數量;k代表取樣次數。設定緩存區的道路資源利用率閾值為1%，當緩存區的道路資源利用率小于設定的閾值時，表明緩存區線路未被使用，其道路資源利用率較低，車輛雙層線路規劃流動穩定性較好。選取緩存區的d、e、f三條線路，根據式（8）計算得到三種方法的緩存區道路資源利用率，如表2所示。

根據表2可看出，針對d、e、f三條緩存區路線，當取樣次數為5次時，方法1的平均緩存區道路資源利用率分別為0.22%、0.25%、0.19%，而方法2和3的平均緩存區道路資源利用率分別為1.32%、1.37%、1.42%和1.43%、1.75%、1.85%。由此可知，針對三條緩存區路線，方法2和3的緩存區道路資源利用率均大于設定的閾值，表明上述兩種方法的緩存區線路被使用，其道路資源利用率較高，不能確保車輛雙層線路規劃流動穩定性。而方法1的緩存區道路資源利用率均小于設定的閾值，表明緩存區線路未被使用，其道路資源利用率較低，車輛雙層線路規劃流動穩定性較好。

4.4 道路擁塞檢驗

由于雙層線路規劃的車輛負載強度被定義為交通網絡的臨時行為，該行為能夠直接表達出車輛調度的真實情況，可以有效反映道路的擁塞情況。為此，將路況上的車輛負載強度作為道路擁塞的評價指標。路況上的車輛負載強度是指路況中瞬時車流量與可通行的道路數量的比值。當路況上的車輛負載強度大于設定的閾值時，會發生道路的擁塞。路況中車輛瞬時業務負載強度計算公式為

I=InsTrafNumN（9）

其中：InsTrafNum表示路況中的瞬時車流量;N表示路況中可通行的道路數量。設定車輛負載強度閾值為1 000 pcu/d，當車輛負載強度大于設定的閾值時，表明該方法的車輛雙層線路規劃道路發生了擁塞。根據式（9）計算得到三種方法的車輛負載強度如圖2所示。

根據圖2可知，針對a、b、c三條可通行路線，方法1的車輛負載強度分別為849 pcu/d、926 pcu/d、784 pcu/d，而方法2和3的車輛負載強度分別為1 075 pcu/d、1 046 pcu/d、1 089 pcu/d和1 192 pcu/d、1 012 pcu/d、1 157 pcu/d。由此可知，針對三條可通行路線，方法2和3的車輛負載強度均大于設定的閾值，表明上述兩種方法的車輛雙層線路規劃道路發生了擁塞。而方法1的車輛負載強度均小于設定的閾值，表明該方法的車輛雙層線路規劃道路未發生擁塞，能夠有效控制每條最優路徑中的車流量，避免道路擁堵的情況。

5 結束語

車輛路線的規劃是交通調控工作的核心。目前車輛線路規劃方法，在約束條件不均衡這一先天條件下，在復雜線路中，存在線路規劃收斂性低以及路線分擔率不均衡的問題，導致線路規劃效果較差。為此，本文設計了交叉路口車輛線路雙層規劃方法。該方法首先構建車輛線路雙層規劃Stackelberg模型，其次利用緩沖區對模型進行優化，最后生成最優規劃的車輛路線，實現車輛線路的規劃，從而加大了高峰期交叉路口車輛的通行效率。

參考文獻：

[1]趙志學，李夏苗，周鮮成.考慮擁堵區域的多車型綠色車輛路徑問題優化［J］.計算機應用，2020，40（3）：883-890.（Zhao Zhixue， Li Xiamiao， Zhou Xiancheng. Green vehicle routing problem optimization for multi-type vehicles considering traffic congestion areas［J］.Journal of Computer Applications，2020，40（3）：883-890.）

［2]Yan Xueming， Huang Han， Hao Zhifeng， et al. A graph-based fuzzy evolutionary algorithm for solving two-echelon vehicle routing problems［J］.IEEE Trans on Evolutionary Computation，2020，24（1）：129-141.

［3]Normasari N， Yu V F， Bachtiyar C， et al. A simulated annealing heuristic for the capacitated green vehicle routing problem［J］.Mathe-matical Problems in Engineering，2019，15（1）：1-18.

［4]孫滬增，李章維，秦子豪，等.帶時間窗車輛路徑規劃算法研究與實現［J］.小型微型計算機系統，2020，41（5）：972-978.（Sun Huzeng， Li Zhangwei， Qin Zihao， et al. Research and implementation on time-window vehicle routing problem［J］.Journal of Chinese Computer Systems，2020，41（5）：972-978.）

［5]李麟，裴玉龍，尹亮，等.基于穩定性和宏觀交通流模型的車輛路徑規劃［J］.中國公路學報，2020，33（8）：71-80.（Li Lin， Pei Yulong， Yin Liang， et al. Vehicle path planning based on stability and macroscopic traffic flow model［J］.China Journal of Highway and Transport，2020，33（8）：71-80.）

［6]陳群，劉嘉暉.區域交通微循環支線網絡交叉口無沖突交通流組織優化［J］.公路與汽運，2020（6）：19-23.（Chen Qun， Liu Jiahui. Regional traffic microcirculation branch network intersections have excellent conflict-free traffic flow organization［J］.Highways amp; Automotive Applications，2020（6）：19-23.）

［7]吳奇倫.一種基于權值累加的多車輛動態路徑規劃算法［J］.工業控制計算機，2019，32（8）：147-148，151.（Wu Qilun. A multi-vehicle dynamic path planning algorithm based on weight accumulation［J］.Industrial Control Computer，2019，32（8）：147-148，151.）

［8]Li Shijin，Wang Fucai.Research on optimization of improved gray wolf optimization-extreme learning machine algorithm in vehicle route planning［J］.Discrete Dynamics in Nature and Society，2020，2020：article ID 8647820.

［9]Kaffash S， Nguyen A T， Zhu J. Big data algorithms and applications in intelligent transportation system： a review and bibliometric analysis［J］.International Journal of Production Economics，2021，231：107868.

［10]周鮮成，劉長石，周開軍，等.時間依賴型綠色車輛路徑模型及改進蟻群算法［J］.管理科學學報，2019，22（5）：57-68.（Zhou Xiancheng， Liu Changshi， Zhou Kaijun， et al. Improved ant colony algorithm and modelling of time-dependent green vehicle routing problem［J］.Journal of Management Sciences in China，2019，22（5）：57-68.）

［11]廖偉志，夏小云，賈小軍.基于蟻群算法的多路徑覆蓋測試數據生成［J］.電子學報，2020，48（7）：1330-1342.（Liao Weizhi， Xia Xiao-yun， Jia Xiaojun. Test data generation for multiple paths coverage based on ant colony algorithm［J］.Acta Electronica Sinica，2020，48（7）：1330-1342.）

［12]馬寧.基于聚類蟻群算法的物流最優路徑［J］.科學技術與工程，2020，20（31）：12911-12915.（Ma Ning. Logistics optimal path based on cluster ant colony algorithm［J］.Science Technology and Engineering，2020，20（31）：12911-12915.）

［13]崔根群，胡可潤，唐風敏.融合遺傳貝塞爾曲線的智能汽車路徑規劃［J］.現代電子技術，2021，44（1）：144-148.（Cui Genqun， Hu Kerun， Tang Fengmin. Intelligent vehicle path planning based on genetic algorithm and Bézier curve［J］.Modern Electronics Technique，2021，44（1）：144-148.）

［14]Medina A M， Creemers F， Lefeber E， et al. Optimal access management for cooperative intersection control［J］.IEEE Trans on Intelligent Transportation Systems，2019，16（5）：1-14.

［15]薛運強，郭俊，安靜，等.公交線路配車問題的不確定雙層規劃模型［J］.交通運輸系統工程與信息，2020，20（2）：145-150.（Xue Yunqiang， Guo Jun， An Jing， et al. Uncertain bi-level programming model for vehicle allocation problem of bus lines［J］.Journal of Transportation Systems Engineering and Information Techno-logy，2020，20（2）：145-150.）