車輛路徑問題研究進(jìn)展

2022-04-18 14:44:00蔣華偉

電子學(xué)報(bào) 2022年2期

蔣華偉，郭陶，楊震

（1. 糧食信息處理與控制教育部重點(diǎn)實(shí)驗(yàn)室(河南工業(yè)大學(xué))，河南鄭州 450001；2. 河南工業(yè)大學(xué)信息科學(xué)與工程學(xué)院，河南鄭州 450001）

1 引言

近年來，由于國(guó)內(nèi)外突發(fā)性公共事件和自然災(zāi)害時(shí)有發(fā)生，應(yīng)急管理工作的順利進(jìn)行顯得尤為重要，而車輛路徑問題作為其核心問題，直接影響應(yīng)急管理工作能否快速、高效地開展. 此外，隨著物流運(yùn)輸業(yè)的迅猛發(fā)展，道路車輛和物流量急劇增長(zhǎng). 因此，為了高效開展應(yīng)急管理工作，提高車輛配送效率，研究人員對(duì)車輛路徑問題（Vehicle Routing Problem，VRP）進(jìn)行了大量研究，并取得了顯著的成果.

筆者分別在中國(guó)知網(wǎng)和Web of Science核心合集中以“車輛路徑問題”和“Vehicle routing problem”為關(guān)鍵詞，檢索了近十年的期刊論文，并對(duì)每一年的論文數(shù)目進(jìn)行統(tǒng)計(jì)，其結(jié)果如圖1 所示. 從2010 年至2019 年，中國(guó)知網(wǎng)上有關(guān)車輛路徑問題的期刊論文共3 634 篇，其中2013 發(fā)表在《系統(tǒng)工程理論與實(shí)踐》上的一篇文章被引用152 次；Web of Science 核心合集上的發(fā)文量為4 799篇，其中高被引論文70篇，2013年發(fā)表在TOP期刊European Journal of Operational Research上的一篇文章被引用421次. 從近十年的發(fā)文量上來看，基本呈遞增趨勢(shì)，由此可以看出VRP仍然是目前學(xué)者研究的熱點(diǎn)領(lǐng)域.

圖1 VRP求解算法研究趨勢(shì)

VRP 自1959 年由Dantzig 和Ramser［1］首次提出之后，便受到許多專家學(xué)者的高度關(guān)注. 該問題指對(duì)具有不同物資需要的需求點(diǎn)，由配送中心對(duì)其進(jìn)行物資配送，通過規(guī)劃合理的行車路線，使得成本（如路程最短、耗費(fèi)時(shí)間最少等）最小化，其示意圖如圖2 所示. 作為一種經(jīng)典的組合優(yōu)化問題，VRP 已被證明是NP-hard 問題［2］，即當(dāng)問題規(guī)模很大時(shí)求解最優(yōu)路徑非常困難. 近年來，隨著社會(huì)經(jīng)濟(jì)的發(fā)展，越來越多的VRP 變體問題被得以提出，逐漸成為研究的熱點(diǎn)，如帶時(shí)間窗的車輛路徑問題（Vehicle Routing Problem With Time Windows）［3］、多配送中心車輛路徑問題（Multi Distribution Center Vehicle Routing Problem）［4］、多目標(biāo)優(yōu)化的車輛路徑問題（Vehicle Routing Problem Based on Multi Objec-tive Optimization）［5］、動(dòng)態(tài)車輛路徑問題（Dynamic Vehicle Routing Problem）［6，7］及大規(guī)模車輛路徑問題（Large Scale Vehicle Routing Problem）等［8，9］.

圖2 VRP場(chǎng)景示意圖

根據(jù)VRP 求解方式的不同，目前VRP 的優(yōu)化求解算法可分為精確算法、啟發(fā)式算法和機(jī)器學(xué)習(xí)相關(guān)的算法三大類，圖3給出了具體的VRP 求解算法分類. 其中，精確算法一定可以求出問題的最優(yōu)解；啟發(fā)式算法能在可接受的計(jì)算成本（計(jì)算時(shí)間、占用空間等）內(nèi)，給出一個(gè)近似最優(yōu)解；機(jī)器學(xué)習(xí)相關(guān)算法利用自動(dòng)學(xué)習(xí)特征這一優(yōu)點(diǎn)，可求得問題的近似最優(yōu)解. 本文對(duì)這些算法的發(fā)展現(xiàn)狀及存在的問題進(jìn)行了總結(jié)分析，并對(duì)未來的研究趨勢(shì)進(jìn)行了討論.

圖3 VRP求解算法分類

2 精確算法

精確算法是針對(duì)某一具體問題建立相應(yīng)的數(shù)學(xué)模型，然后利用數(shù)學(xué)方法進(jìn)行求解，通常用于求解問題的最優(yōu)解，常用的精確算法有分支定界法、列生成法和動(dòng)態(tài)規(guī)劃法等.

2.1 分支定界法

分支定界法（Branch And Bound，BAB）［10］由“分支”策略和“限界”策略兩部分組成，采用廣度優(yōu)先或最小耗費(fèi)優(yōu)先的方法，在問題的解空間樹上搜索可行解，并在找不到比當(dāng)前解更好的解時(shí)修剪子樹，是一種廣義搜索窮舉算法，其原理如圖4所示.

圖4 分支定界法求解原理

由圖4 可知，采用分支定界法對(duì)VRP 進(jìn)行求解時(shí)，把全部可行的解空間不斷分割成越來越小的子集，通過設(shè)置子集的上界或下界判斷子集是否需要進(jìn)行下一步的劃分，縮小解的搜索范圍，減少計(jì)算量. 求解VRP 時(shí)，其目標(biāo)一般為最小化成本，對(duì)于問題F（x），其松弛問題RF（x）的最優(yōu)解即可作為問題F（x）的一個(gè)下界，將F（x）分解為兩個(gè)新的子問題，其劃分如式（1）所示.

由式（1）可知，分支定界算法執(zhí)行的效率取決于問題解空間的上下界，尋找的上下界越緊湊，算法的執(zhí)行效率越高. 由于需要對(duì)問題的所有可行解空間進(jìn)行搜索，對(duì)于規(guī)模稍大的VRP 來說，其所有可行解空間無(wú)疑是龐大的，因此使用分支定界法對(duì)VRP 進(jìn)行求解需要耗費(fèi)很長(zhǎng)的時(shí)間. 為此，Pecin 等［11］提出了分支價(jià)格和消減（Branch Price and Cut，BPC）法來求解帶時(shí)間窗的VRP，當(dāng)使用標(biāo)記算法計(jì)算難以求解實(shí)例的列生成定價(jià)子問題時(shí)，使用弧子集代替節(jié)點(diǎn)子集，減少了計(jì)算復(fù)雜度，從而加快了算法求解VRP 最優(yōu)解的速度. 另外，Ceselli 等［12］為求解廢物管理系統(tǒng)中的VRP，通過在分支定界框架下動(dòng)態(tài)生成行和列，對(duì)定價(jià)問題提出特定的精確算法，減少了尋找最優(yōu)解的時(shí)間. 此外，針對(duì)分支定界法中搜索樹存在的對(duì)稱性問題，Santos 等［13］在求解兩級(jí)容量受限VRP 時(shí)，設(shè)計(jì)了一個(gè)新的集合分區(qū)重構(gòu)方式，使其不涉及按車輛索引的變量，消除了搜索樹中存在的對(duì)稱性問題.

2.2 列生成法

列生成法［14］是求解VRP 的一種高效算法，目前先進(jìn)的求解VRP 的精確算法大多是基于列生成法形成的. 采用列生成法求解時(shí)，根據(jù)文獻(xiàn)［14］將問題分解為限制主問題和定價(jià)子問題. 一般主問題為一個(gè)帶有二元變量的劃分問題，子問題為一個(gè)約束最短路徑問題.將其應(yīng)用于VRP 中，分解后的子問題和限制主問題分別如式（2）、式（3）所示［15］.

其中，K為車輛總數(shù)；Ck表示第k輛車的最大載重；N為節(jié)點(diǎn)總數(shù)；A表示節(jié)點(diǎn)之間弧的集合；S表示節(jié)點(diǎn)集合；Ωk表示車輛k的有效路徑集合；d（i，j）表示節(jié)點(diǎn)i與j之間的距離；qi表示節(jié)點(diǎn)i的需求量；表示車輛k的行駛路線p的成本；表示在路徑p下節(jié)點(diǎn)i被車輛k訪問的次數(shù)；表示車輛k在路徑p的極值點(diǎn)；ai和bi為節(jié)點(diǎn)i的時(shí)間要求.

由式（2）、式（3）可知，列生成法并不是同時(shí)處理所有的可行解，而是基于當(dāng)前生成列的子集，通過限制主問題進(jìn)行優(yōu)化求解，當(dāng)其余的可行解可以改善當(dāng)前限制主問題的最優(yōu)解時(shí)，才會(huì)進(jìn)入該子集. 但由于列生成法只能求解線性松弛問題，在使用列生成法求解VRP時(shí)，一般將其與其他精確算法相結(jié)合. 為此，Hernandez等［16］在求解帶時(shí)間窗的VRP 時(shí)，使用兩組覆蓋公式和分支定價(jià)法對(duì)問題進(jìn)行求解，為減少計(jì)算量，使用列生成法計(jì)算其下界，在列生成過程中，對(duì)受限主問題和定價(jià)問題進(jìn)行迭代求解，當(dāng)定價(jià)問題無(wú)法為受限主問題找到新的潛在改進(jìn)列時(shí)停止，有效降低了VRP 的求解時(shí)間. 此外，Pecin等［17］為求解容量受限的VRP，在分支削減和價(jià)格算法（Branch Cut and Price，BCP）中使用列生成法，將列與ng-路由關(guān)聯(lián)，采用標(biāo)簽算法求解相應(yīng)的定價(jià)子問題，同時(shí)當(dāng)列生成法出現(xiàn)嚴(yán)重的收斂問題時(shí)，BCP 算法會(huì)自動(dòng)執(zhí)行雙重穩(wěn)定，防止算法在求解VRP 時(shí)過早收斂.Fukasawa 等［18］采用分支定價(jià)算法與列生成相結(jié)合的方式求解容量受限的VRP，首先使用分支定價(jià)算法求解根節(jié)點(diǎn)，并記錄得到的下界和運(yùn)行時(shí)間，再次求解時(shí)采用列生成法尋找其下界，以平衡下界的優(yōu)劣與尋找更優(yōu)下界所耗費(fèi)時(shí)間之間的關(guān)系，提高算法的整體運(yùn)算效率.

2.3 動(dòng)態(tài)規(guī)劃法

動(dòng)態(tài)規(guī)劃算法［19］求解時(shí)將復(fù)雜的原問題分解為相對(duì)簡(jiǎn)單的子問題，然后把子問題的解合并得出原問題的解. 采用動(dòng)態(tài)規(guī)劃法求解VRP，根據(jù)VRP 的優(yōu)化目標(biāo)，即總成本最小（總行駛距離最短、總運(yùn)輸成本最小或總服務(wù)時(shí)間最短），將其看作一個(gè)多階段決策問題，分解成一系列的單階段問題. 當(dāng)每一個(gè)單階段問題的成本最小時(shí)，該問題的總成本一定是最小的. 訪問所有節(jié)點(diǎn)需要的成本可由式（4）表示［20］.

其中，β用于記錄車輛運(yùn)輸期間的時(shí)間，初始值為相應(yīng)操作的開始時(shí)間，當(dāng)訪問到車場(chǎng)時(shí)則重置為初始值；V=｛0，1，…，n｝表示節(jié)點(diǎn)集；Φ表示訪問節(jié)點(diǎn)的集合，Φ∈V