基于改進分支定價法的車輛路徑優化研究

呂欣昊

（山東科技大學 計算機科學與工程學院，山東 青島 266590）

0 引言

全球物流產業相關數據顯示，快遞平均單價持續走低，配送成本增加，導致企業利潤空間進一步被壓縮。雖然末端配送距離不足整個運輸距離的5%，花費的時長卻占據了整個快遞業務時長的45%，這不僅影響著物流配送的最終成本還直接決定了客戶的購物體驗。末端配送的目的是在保證滿足客戶需求的前提下，最小化配送的總成本。為了追求更低的配送成本，就要進一步提高解的質量。

為了追求更低的配送成本，就要進一步提高解的質量。學術界不滿足于啟發式算法帶來的近似解，開始從多個角度運用精確算法對末端配送優化問題進行了研究并取得了相應的成果。Desrochers[1]等在1988年采用標簽算法研究了SPPTW（The Shortest Path Problem With Time Windows）問題，成功處理了2500個節點和250000條弧的車輛路徑問題。1992年 Desrochers[2]又依托標簽算法結合列生成研究了VRPTW（The Vehicle Routing Problem With Time Windows）問題，即分支定價算法的雛形。Augerat[3]在 1998年從分支切割的角度研究了 CVRP（The Capacitated Vehicle Routing Problem）問題，構建出可以識別違反有效不等式的算法。精確算法開始由初始應用階段轉變到提高效率階段。2006年Irnich[4]采用K循環消除成功解決了帶資源約束的最短路徑問題，得出 2K≤ 時提升算法效率最高的結論。2006年Chabrier[5]等對更大規模的CVRP問題進行研究，提出了新的優勢規則，結果表明新優勢規則的提出，可大幅度減少了動態規劃算法中標簽的數量。此后研究者又開始根據問題本身的屬性特點，通過調整精確算法的結構來提高效率。2011年Toth[6]等結合CVRP問題的特點，設計了離散的方案。Desaulniers[7]在 2016年采用分支定價算法解決了 SDVRPTW（The Split-delivery Vehicle Routing Problem With Time Windows）問題，成功處理了504個DSVRPT基本算例中的176個。2016年揭婉晨[8]運用分支定價算法處理多車型電動汽車車輛問題。2017年Spliet[9]結合TWAVRP問題的特點，設計了相應的分支定價模型來處理不同概率下的客戶需求。隨著處理效率的提升，精確算法已經可以處理更大規模，更加復雜情況下的車輛路徑優化問題。2018年Qie He[10]從具有凸節點成本的角度指出不便成本對配送成本影響的重要性，采用分支切割定價算法驗證了不便成本會對車輛路徑規劃的影響。2018年Pessozai[11]為異構車輛路徑提出了一種新的 BCP（Branch-Cut-and- Price）算法，解決了200個客戶節點的VRP變體問題。2018年Bulh?es[12]從最小延遲問題(MLP)的角度提出了一個新的MLP分支定價算法。目前以分支定價算法為精確算法的代表，其改進工作也主要集中在優化標簽規則方面，較少的考慮分支階段對算法性能的影響。在分支階段，以往的基于{0,1}的分支策略會造成分支定界樹的嚴重不平衡，這使得算法在運行的時候，分支定界樹中會出現某條分支過長而另一條分支會很短，進而影響二叉樹的尋優效率。基于這個問題本文提出了一種新的分支策略來改進分支定價方案，通過維持分支定界樹平衡性從而提升效率。本文使用改進后分支定價算法處理考慮（1）客戶的時間窗，（2）車輛的里程，（3）車輛的載重，（4）等待成本，（5）運輸成本五種約束條件下的車輛路徑問題。通過與原有分支策略進行對比，驗證改進算法在求解效率上的優越性。

1 多約束條件下車輛路徑問題模型的建立

1.1 問題描述

某物流公司在某地有一個物流倉庫負責給本地區的一定數量的客戶提供配送服務，倉庫配送車輛數量充足且車型相同。車輛一開始都從配送中心出發，最終都需要返回配送中心。配送中心和客戶都有一個時間窗。每輛車必須在客戶給定時間窗截止時間前到達并在時間窗最早時間后進行服務，這里強制在時間窗內進行服務即強時間窗約束。如果車輛早于時間窗口到達需要等待并計算成本，在倉庫等待不計算等待成本。假設車輛具有里程約束，從配送中心出發的車輛為滿電狀態，在配送區域設有一定數量的充電站可以供車輛充電。假設車輛具有載重約束，一輛車服務總的客戶需求不能超過其車輛的載重約束。每個客戶都要被服務且只能被服務一次，每個客戶具有相同的服務時間。

1.2 模型建立

建立一個有向圖G(A,N)，圖中的詳細變量說明如下。

表1 符號說明Tab.1 Symbol description

通過 Danizig-Wolfe分解獲得松弛后的受限的主問題模型如下。關于Danizig-Wolfe分解更詳細的分解過程請參考Vanderbeck和Savelsbergh (2006)[13]的論文。

公式（1）是目標函數。公式（2）要求每個客戶至少需要被訪問一次。公式（3）表示變量rx為非負數。這里RR′?，R′是R的子集并且初始化狀態是每個客戶單獨分配一輛車。

2 算法設計

本節根據第1節中建立的RMP模型使用改進的分支定價和動態規劃算法實現對問題的求解。第一步將通過定價策略對R′擴展，第二步提出新的分支策略，第三步運用動態規劃算法安排充電站位置以完成對最終車輛路徑問題的求解。

2.1 基于標簽規則的定價策略

對RMP求解后，獲得了每個客戶節點關于約束（2）的對偶變量。根據這個值來安排合適的列插入RMP中，組成新的RMP。尋找合適的列稱為定價問題，是列生成算法中的核心問題之一。為了挑選合適的列進入RMP，需要計算可行路徑集合中路徑的邊際成本，邊際成本的值決定該列是否可以插入到 RMP，邊際成本的值和 RMP求解后生成的對偶變量有關。具體的邊際成本公式如下所示：

根據列生成算法的定義，將具有負的邊際成本路線添加到RMP中。在執行定價之前需要組建可行路徑集合R，采用的方式為2006年Chabrier提出的標簽算法。優勢規則的運用將顯著減少了節點中標簽的數量。以50客戶節點為例，正常循環會產生502個標簽，通過使用上述優勢規則后，實際產生到配送中心標簽數量卻只有 3598個（取決于具體的算例）。當R中沒有發現負檢驗數的路線時，對RMP進行分支操作。

2.2 雙重禁用的分支策略

分支策略是依靠分支定界樹執行的操作，目的是獲得最優的整數解。分支策略好壞決定了獲取上界的速度。傳統的分支策略是對所有的弧計算其弧流量ijf，選擇一條弧流量大于0且小于1的弧ije。一個分支禁止使用該弧的路線，另一個分支必須使用包含該弧的路線，但這種效率被證明效率非常低，很容易造成分支定界樹的不平衡，其中 xr=1分支下的節點數量遠遠大于 xr= 0 的數量。針對這個問題，本文提出了新的分支策略平衡分支定界樹的兩側的分支。描述如下：

圖1 分支規則Fig.1 Branching rule

2.3 基于優勢充電站的動態規劃策略

充電站的安排是找到滿足里程約束并且不影響客戶配送時間的最小數量。規則如下：

（1）找到一條路徑中各條弧（i, j）之間距離最近的充電站作為優勢充電站。

（2）將每條弧擁有的優勢充電站組合為一個集合。

（3）通過動態規劃算法搜索該集合，要求使用充電站的次數最少，同時需要滿足車輛的里程約束且不違反該路線的時間窗約束。

3 算例分析

3.1 實例數據

實驗數據采用某大件物流配送中心 50個客戶訂單及其相關數據，所采用的數據集中提供了車輛的數量、載重、里程、充電時間、行駛成本、行駛速度等車輛信息。還有客戶的位置（經緯度）、服務時間、貨物重量、時間窗等信息。此外還包含轄區內100個充電站的位置信息，這里使用距離為歐式距離。

3.2 程序的運行環境

表2 運行環境Tab.2 Operating environment

3.3 運行結果及分析

下表展示了在使用改進的分支策略和基于{0,1}分支策略處理4組數據所獲得計算時間。

表3 50個節點計算時間表Tab.3 50 node calculation schedule

通過上表中數據可以看到對于兩個分支都獲得同樣的結果，證明了改進分支策略的正確性。4組數據改進后的分支策略的運行時間都低于基于{0,1}的分支策略，說明改進的分支策略確實取得了一定的效果，平均的效率提升在12%左右。實際在程序的運行過程中，基于{0,1}的分支策略需要判斷ije禁用和使用兩種情況，而改進的分支策略只需判斷ije禁用這一種情況，所以在這段對弧判斷的時間上，改進的分支策略執行時間只有基于{0,1}分支策略的一半。改進的分支策略所生成的分支定界樹的深度也明顯小于基于{0,1}分支策略，可以更快的獲得問題的解。改進后的分支策略更加相比之前的策略在計算4組數據時間上更加穩定。基于{0,1}分支策略對同樣規模的4組數據計算時間相差較大，也是因為基于{0,1}分支策略會依據數據的特點生成不同的不平衡二叉樹從使得計算效率的不穩定，而改進的分支策略能更好的避免這種情況。

下圖是最終的路線規劃圖，其中0和51表示倉庫，1～50表示客戶，大于51表示充電站。

圖2 最終50客戶節點路線圖Fig.2 Final 50 customer node roadmap

4 結論

本文充分考慮了強時間窗約束、載重約束、里程約束下的車輛配送路徑研究，并提出了改進的分支定價算法。改進的分支定價算法針對分支階段基于{0,1}分支策略不能維持二叉樹平衡而導致的效率低下問題，提出了可維持二叉樹平衡新的分支策略，保持了分支定界樹的平衡性同時也加快求解速度。實驗所采用的數據相對于以往研究的數據更難以處理，以此測試改進的分支策略和基于{0,1}分支策略在尋優能力和算法穩定性方面的表現。

運用對照實驗的方法，在保證處理數據和定價策略相同的條件下，對兩種不同的分支策略分別進行實驗。對照實驗結果驗證了改進的分支定價方案對于客戶需求種類多、時間窗緊、位置分布均勻的復雜情況有更好的處理效果。同時本文也考慮了車輛的里程約束，可以更好的指導車輛在實際生產過程中的路徑規劃。改進的分支定價算法在求解車輛路徑問題的效率和穩定性方面的良好性能，為今后的分支定價算法研究[14-18]做參考。