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

趙文華 吳雪

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

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

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

0 引言

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

1 VRP的常用算法

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

1.1 精確算法

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

1.2 啟發(fā)式算法

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

1.3 人工智能算法

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

2 專利分析

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

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

接下來，針對全球VRP領(lǐng)域的專利申請情況進行統(tǒng)計分析，利用Incopat專利檢索系統(tǒng)，在Incopat的高級檢索框中輸入“車輛路徑問題”“Vehicle Routing Problem”，為了避免重復(fù)，選擇相同申請?zhí)柡喜?，獲得166件全球?qū)＠暾?，其中涉及精確算法的專利數(shù)量為15條，啟發(fā)式算法的專利數(shù)量為166條。全球?qū)＠暾埖南嚓P(guān)算法中，排名靠前的是迭代局部搜索、蟻群算法、粒子群算法、遺傳算法和變領(lǐng)域搜索，與中國專利申請統(tǒng)計結(jié)果一致，足以說明上述幾種啟發(fā)式算法在求解車輛路徑問題中的相對有效性。

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

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

3 相關(guān)重點專利

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

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

4 結(jié)論

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

參考文獻

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

[2]畢國通. 車輛路徑問題及其優(yōu)化算法研究綜述[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]. 計算機集成制造系統(tǒng)： 1-21[2023-04-20]. http： //kns. cnki. net/kcms/detail/11. 5946. TP. 20220520. 1805. 010. html

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

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

[8]馬炫， 彭芃， 劉慶. 求解帶時間窗車輛路徑問題的改進粒子群算法[J]. 計算機工程與應(yīng)用， 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]. 系統(tǒng)工程學報， 2005（5）： 41-47.

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