針對車輛路徑問題的專利分析

趙文華 吳雪

摘要 車輛路徑問題是調度管理和運輸組織優化中的核心問題，也屬于運籌學中的一種組合優化問題，旨在構造合適的車輛行駛路線從而實現運輸成本的最優化。文章介紹了路徑規劃問題的常見種類以及多種算法，總結了上述算法的研究現狀，以及研究中還存在的問題，并利用專利分析系統對各個算法下的相關專利進行統計分析，便于對各個方法的研究熱度進行討論，以期對今后車輛路徑問題方面的專利申請給予參考和指引。

關鍵詞 車輛路徑問題；算法；專利；物流；運輸；配送

中圖分類號 U116.2文獻標識碼 A文章編號 2096-8949（2023）09-0183-03

0 引言

車輛路徑問題（Vehicle Routing Program，VRP）最早來源于Dantzig和Ramser于1959年發表在《Management Science》上的文章《The Truck Dispatching Problem》。該問題起源于交通運輸，涉及查找一組路線，這些路線共同覆蓋一組客戶，每個客戶都有給定的需求，目標是最大限度地減少總行駛距離或使用的車輛數量，或這些的組合[1]。路徑規劃問題是現實生活中普遍存在的，且根據實際約束條件的不同，可以抽象出VRP問題的不同種類，例如，帶容量限制的車輛路徑問題（CVRP）（Kallehauge et al. 2006）。近年來，有時間約束限制的派送服務急劇增長，這種服務中訪問的客戶可能要求在某個時間點前完成派送等，即一種帶時間窗的車輛路徑問題（VRPTW）。早期有關解決帶時間窗口路徑問題的研究可參考（Desrochers et al. 1988）和（Solomon and Desrosiers，1988）。日常生活中有隨機需求的收送服務，需要根據不同時段中隨機出現的需求服務的客戶點進行路徑規劃。上述VRP的種類中，又各自分為路徑在一個或多個配送中心（depot）兩種情況，也涉及同類車型或不同車型的問題。

1 VRP的常用算法

車輛路徑問題的一般求解方式是根據優化目標結合一個或多個約束條件進行建模，然后基于構建的數學模型選擇合適的算法，從而獲得該問題的最優解或次優解。在解決上述路徑問題時，通常會用到精確算法和啟發式算法。在算法方面，國內外的很多學者都進行了深入研究，20世紀60年代集中在各種形式的節約算法，到70—80年代又提出了多種基于數學規劃的算法，80年后期至今又涌現出各種智能算法[2]。

1.1 精確算法

VRP問題中常用的精確算法有：動態規劃，列生成，分支定界，分支切割，拉格朗日松弛算法等。Desrochers et al.（1992）用列生成算法解決了Solomon的100個訪問節點的問題；Pecin等提出了分支定價割平面算法（Branch Price and Cut）來求解帶時間窗的VRP，減少了計算復雜度，從而加快了算法求解速度[3]。ZHAO[4]通過列生成算法和動態規劃算法實現了對循環式帶訪問頻率的多車輛路徑問題的解決。胡劍鵬等針對柔性時間窗的電動車車輛路徑問題建立了以配送成本最小為目標的混合整數規劃模型，利用列生成算法進行求解，將模型轉換化為有資源約束的最短路徑子問題。這類算法適用于規模較小、結構簡單的情況，能夠獲得問題的最優解，但是隨著客戶點的增加，算法復雜度呈指數級增加，普遍耗時較長[5]。

1.2 啟發式算法

啟發式算法具有全局搜索能力強、求解效率高的特點，通常研究人員更多地采用啟發式算法。這類算法適用于規模較大的VRP，面對CVRP和VRPTW等約束條件較多的VRP問題時，此類算法仍能較快地獲得最終解，缺點是問題規模增大時收斂速度慢，無法得到最優解。常用的啟發式算法包括：遺傳算法（GA）、模擬退火（SA）、蟻群算法（ACA）、粒子群算法（PSO）、禁忌搜索（TS）、變鄰域搜索（VNS）、迭代局部搜索（ILS）、大鄰域搜索（LNS）和貪婪隨機自適應搜索程序（GRASP）。ZHAO[4]針對隨機環境中訪問節點對應給定的訪問概率，以及訪問節點同時有訪問概率又帶軟時間窗的路徑規劃問題，使用了鄰域搜索算法VNS進行求解，其運算速度明顯提升。蔣波針對帶懲罰函數的VRPTW模型設計了遺傳算法，滿足配送總成本最小的目標函數[6]。趙辰基于遺傳算法求解了從生產中心到倉庫之間的路徑優化問題，實現了配送路徑優化的目的[7]。Mirabi等提出了一種基于模擬退火思想的三步啟發式算法求解最小配送時間的多配送中心VRP問題。馬炫等提出了一種基于粒子變換原理的整數粒子更新方法求解帶時間窗口的車輛路徑問題[8]。Angel等基于非確定性的模擬框架，提出了基于貪婪原則的初始解搜索方法，從最近若干節點中選擇某一節點，生成多條可行路徑，之后結合單一路徑中充電節點位置優化、2-Opt和路徑間客戶點交換三種鄰域搜索算法求解[9]。Jun等利用2階段禁忌搜索算法求解VRPTW問題[10]。Schneider等為了避免單一算法的局限性，利用VNS和TS算法相結合的方法進行求解，在算法早期允許劣解加入候選路徑，加快了算法的收斂速度。

1.3 人工智能算法

傳統求解方法通常針對具體的問題進行建模求解，并不具備自主學習和決策的能力。隨著機器學習技術的推進，目前也出現了通過深度學習等人工智能方法解決上述路徑問題的研究成果。徐郁等針對電力物資配送路徑問題，建立了以電力物資配送路徑長度最小、成本最低、物資需求點滿意度最高為目標的多目標優化模型，設計了一種基于深度強化學習（Deep Reinforcement Learning，DRL）的電力物資配送路徑優化算法。黃琰等提出了一種基于上置信區間算法改進動作選擇的深度Q網絡（Deep Q-learning Networks，DQN）方法，相比傳統的DQN方法計算效率得到了提升。王萬良等針對多配送中心車輛路徑問題（Multi-Depot Vehicle Routing Problem，MDVRP）提出了一種基于多智能體深度強化學習的求解模型，實現了快速獲得高質量解的目的。后來Wang等人提出了一種新的DQN模型：Dueling DQN（DDQN），不同于DQN算法，而是把卷積層得到的特征分為狀態值和動作優勢函數兩部分。根據前述相關研究成果的分析，獲得VRP的相關算法技術分支表如表1所示：

2 專利分析

首先針對VRP的中國專利申請進行統計分析，在智能檢索系統的CNBAS庫中，輸入“車輛路徑問題”“Vehicle Routing Problem”進行檢索，獲得116篇中國專利申請，基于各個算法的具體數量，統計出餅狀圖見圖1，可以直觀地看出占比較大的是局部搜索算法、遺傳算法以及變鄰域搜索算法，其他啟發式算法占比都比較?。恢袊鳹RP相關專利申請中啟發式算法占據很大的比重。

且經過檢索統計，中國專利申請人的類別中，大專院校和科研單位的占比達73%左右，企業占比為26%，其余為個人申請，可見該技術主題的專利研究主體主要集中在高校和研究院所，也說明該技術問題處在理論研究階段，商業轉化率比較低。

接下來，針對全球VRP領域的專利申請情況進行統計分析，利用Incopat專利檢索系統，在Incopat的高級檢索框中輸入“車輛路徑問題”“Vehicle Routing Problem”，為了避免重復，選擇相同申請號合并，獲得166件全球專利申請，其中涉及精確算法的專利數量為15條，啟發式算法的專利數量為166條。全球專利申請的相關算法中，排名靠前的是迭代局部搜索、蟻群算法、粒子群算法、遺傳算法和變領域搜索，與中國專利申請統計結果一致，足以說明上述幾種啟發式算法在求解車輛路徑問題中的相對有效性。

由圖2可以看出，雖然VRP問題提出是在1959年，但是相關的專利申請是從20世紀90年代才開始。由圖2曲線可以看出，相應領域的專利申請量先經過緩慢波動增長，在2012年之后呈快速增加的趨勢，并在2018年左右專利年申請量達到了高點。

由于VRP問題屬于NP問題，問題復雜度較高，而精確算法僅適合規模較小的情況，啟發式算法和人工智能算法由于具有較高的計算效率，所以備受研究人員青睞，為了適應日益復雜的應用場景，追求效率提高和成本降低依舊是該研究領域首當其沖要改進的方面。計算機較強的并行計算能力、多種啟發式算法相結合、深度學習等人工智能算法以及大數據等的運用，會為該技術問題的研究提供新的發展空間。

3 相關重點專利

在啟發式算法結合方面，廣東工業大學在2015年（公開號為CN104951850A）針對多配送中心物流運輸車輛路徑問題，提出了通過粒子群算法對蟻群算法啟發因子進行優化，求解最優配送路徑的方法，具有較好的全局和局部尋優能力。同年，還提出了一種求解帶軟時間窗口物流運輸車輛路徑問題的方法（公開號為CN104992242A），采用時間窗懲罰機制，建立數學模型，使用自適應混沌蟻群算法求解該模型，具有更好的優化搜索能力，能夠避免搜索過程陷入局部最優，提高解的多樣性。

在新興技術應用方面，深圳市德邦物流有限公司于2021年提出了一本基于大數據的智慧物流取件分析系統及方法的專利申請（公開號分別為CN113592440A），該申請已于2022年7月獲得專利權，該專利中通過改進型算法的物流配送優化模型，為配送管理員提供科學的路線決策依據，解決了實際出單過程中的問題，保證滿足客戶需求，提高系統的實用性。

4 結論

隨著實際生活中客戶需求的多樣化，車輛路徑問題涌現出了多個變種，多重約束條件的疊加使得問題更加復雜，求解難度也增大，需要不斷提出新的模型來滿足實際應用場景。同時，隨著信息技術與互聯網技術的發展，特別是電子商務的快速發展，如何整合社會資源，合理調度多個配送企業的車輛資源從而建立一個車輛調度聯盟，也將是車輛路徑問題的一個研究方向。因此，未來如果能夠針對實際應用場景提出更快速有效的算法，在滿足客戶需求的基礎上降低成本，以靈活應用于多種場景下的路徑規劃問題，將會在交通運輸、貨物配送以及物流管理等多個領域產生深刻的影響。

參考文獻

[1]Dantzig G， Ramser J. The Truck Dispatching Problem[J]. Management Science， 1959（6）： 80-91.

[2]畢國通. 車輛路徑問題及其優化算法研究綜述[J]. 物流科技， 2016（6）： 95-97.

[3]Pecin D， Contardo C， Desaulniers G， et al. New Enhancements for the Exact Solution of the Vehicle Routing Problem with Time Windows[J]. Informs Journal on Computing， 2017（3）： 489-502.

[4]ZHAO W H. Study of Routing Problems in Wireless Sensor Networks and Logistics[C]. Doctor Thesis， 2012.

[5]胡劍鵬， 羅霞， 甘易玄. 基于列生成算法的魯棒電動車路徑問題[J/OL]. 計算機集成制造系統： 1-21[2023-04-20]. http： //kns. cnki. net/kcms/detail/11. 5946. TP. 20220520. 1805. 010. html

[6]蔣波. 基于遺傳算法的帶時間窗車輛路徑優化問題研究[D]. 北京：北京交通大學， 2010.

[7]趙辰. 基于遺傳算法的車輛路徑優化問題研究[D]. 天津：天津大學， 2012.

[8]馬炫， 彭芃， 劉慶. 求解帶時間窗車輛路徑問題的改進粒子群算法[J]. 計算機工程與應用， 2009（27）： 200-202+218.

[9]Angel F M et al. A Heuristic Approach for the Green Vehicle Routing Problem with Multiple Technologies and Partial Recharges[J]. Transportation Research Part E： Logistic and Transportation Review. 2014， 71： 111-128.

[10]Jun Jiang， et al. Vehicle Routing Problem with a Heterogeneous Fleet and Time Windows[J]. Expert Systems with Applications， 2014（8）： 3748-3760.

[11]Yang Xin-She. A New Metaheuristic Bat-inspired Algorithm， Nature-Inspired Coopreative Strategies for Optimization[EB/OL].? Research Gate， 2010.

[12]郎茂祥. 裝卸混合車輛路徑問題的模擬退火算法研究[J]. 系統工程學報， 2005（5）： 41-47.

[13]辛穎. 基于蟻群算法的車輛路徑規劃問題求解研究[D]. 長春：吉林大學， 2015.