車(chē)輛路徑規(guī)劃算法及其應(yīng)用綜述

□ 顧 蕾

(廣東理工學(xué)院 經(jīng)濟(jì)管理學(xué)院，廣東 肇慶 526100)

伴隨著貿(mào)易和經(jīng)濟(jì)全球化的發(fā)展，市場(chǎng)競(jìng)爭(zhēng)愈演愈烈，人們對(duì)于效率的要求也越來(lái)越高。車(chē)輛路徑規(guī)劃問(wèn)題逐漸引起人們的關(guān)注，并且成為人工智能和經(jīng)濟(jì)發(fā)展過(guò)程當(dāng)中亟待要解決的問(wèn)題。

截至北京時(shí)間2018年10月9日，全球最權(quán)威的車(chē)輛路徑規(guī)劃(VRP)問(wèn)題評(píng)測(cè)系統(tǒng)中有二十六項(xiàng)世界記錄是由菜鳥(niǎo)保持的。作為中國(guó)第一個(gè)問(wèn)鼎該評(píng)測(cè)系統(tǒng)的研究機(jī)構(gòu)，菜鳥(niǎo)將VRP算法優(yōu)化應(yīng)用到他們的各項(xiàng)實(shí)際操作的業(yè)務(wù)當(dāng)中。VRP算法在配送中，大幅度減少車(chē)輛行駛的距離和車(chē)輛分配的數(shù)量；在倉(cāng)庫(kù)內(nèi)部揀選作業(yè)中，VRP算法大幅度減少倉(cāng)庫(kù)操作人員行走的距離。除此之外，菜鳥(niǎo)還將VRP算法應(yīng)用到外賣(mài)的配送路徑規(guī)劃當(dāng)中，縮短外賣(mài)配送時(shí)間，增加有限時(shí)間內(nèi)外賣(mài)的配送數(shù)量，極大地提高了外賣(mài)員的工作效率，提升了顧客滿意度的同時(shí)又增加了外賣(mài)員的收入。

1 車(chē)輛路徑規(guī)劃問(wèn)題

VRP可以概述為：從實(shí)際的角度出發(fā)，在各種限制條件下，車(chē)輛從一個(gè)或者多個(gè)配送中心出發(fā)，按照一定的順序注意經(jīng)過(guò)隨機(jī)分布的若干個(gè)配送點(diǎn)，且每一個(gè)配送點(diǎn)保證有且僅有一輛車(chē)經(jīng)過(guò)提供服務(wù)。對(duì)于此類(lèi)VRP問(wèn)題的設(shè)計(jì)就是要求規(guī)劃出一條效率最高，配送所付出的代價(jià)最低的路徑車(chē)輛路徑問(wèn)題的求解，目的在于設(shè)計(jì)一條最合理的路徑，使得配送代價(jià)最低。當(dāng)約束條件不同時(shí)，納悶選擇求解的算法當(dāng)然也不相同。

標(biāo)準(zhǔn)車(chē)輛路徑問(wèn)題就是有能力約束的車(chē)輛路徑問(wèn)題(Capacitated Vehicle Routing Problem，CVRP)。在此系統(tǒng)內(nèi)，每輛車(chē)都有限制最大載重量。這只是VRP系統(tǒng)中的一種模型，只給出了一個(gè)約束條件，根據(jù)現(xiàn)實(shí)當(dāng)中約束條件的不同，還有其他各種模型。CVRP只是其中最基本的模型[1]。

CVRP模型是有一個(gè)配送中心、若干個(gè)地理上隨機(jī)分散的配送點(diǎn)，車(chē)輛從配送中心出發(fā)為這些配送點(diǎn)提供服務(wù)，要從眾多配送方案中找出車(chē)輛行駛的最佳路線，使得整個(gè)系統(tǒng)配送時(shí)間最短，成本最低，同時(shí)需要滿足三個(gè)條件：

①每輛車(chē)的最大載重量要大于或等于每條配送線路上的最大需求量；

②每輛車(chē)的能夠行駛的最大距離不小于每次交付路徑所需距離的最大值；

③配送中心只有一輛配送汽車(chē)[1]。

2 VRP算法應(yīng)用綜述

Dantzig和Ramser[2]在1959年第一次提出車(chē)輛路徑規(guī)劃的問(wèn)題。VRP屬于 NP難題，隨著節(jié)點(diǎn)數(shù)目的越來(lái)越多，想要求解此類(lèi)問(wèn)題的困難越來(lái)越大，VRP對(duì)于運(yùn)行時(shí)間和存儲(chǔ)空間的要求非常高，它對(duì)于更方面知識(shí)的要求都也非常高，因此VRP出現(xiàn)之后很快引起了各學(xué)科的專(zhuān)家、運(yùn)輸計(jì)劃制訂者和管理者的極大重視。隨著電子商務(wù)的發(fā)展，帶動(dòng)了物流供應(yīng)鏈系統(tǒng)的發(fā)展，VRP也逐漸成為人們研究的熱點(diǎn)。

模型的使用中，人們將VRP分解成各種子問(wèn)題可。根據(jù)不同的約束條件分解成各種不同類(lèi)型的VRP。例如：當(dāng)車(chē)輛裝載狀況取值為：最大載重量；配送中心數(shù)目取值為：多配送中心；車(chē)型數(shù)目取值為：同車(chē)型；時(shí)間限制取值為：軟時(shí)間窗；需求信息取值為：需求不確定；那么該問(wèn)題就是一個(gè)載重量限制下的多配送中心、同車(chē)型、軟時(shí)間窗的隨機(jī)需求的VRP問(wèn)題。

在實(shí)際的求解過(guò)程中約束條件越多，那么求解的過(guò)程將越復(fù)雜，需要花費(fèi)的時(shí)間越長(zhǎng)。就目前求解的現(xiàn)實(shí)狀況來(lái)看，一般人們研究的最復(fù)雜的VRP問(wèn)題也就是三到四個(gè)屬性。為了簡(jiǎn)化模型，更多的研究小合著只選擇一到兩個(gè)屬性來(lái)作為約束條件，這種情況下求解貨稍微簡(jiǎn)單一些，模型也更加凸顯某方面的問(wèn)題。例：Dror等[3]主要研究的滿載問(wèn)題；李軍等[4]主要研究的非滿載問(wèn)題；Cordeau等[5]研究的帶有時(shí)間窗的問(wèn)題；Gendreau等[6]研究的多車(chē)型的問(wèn)題等等，諸如此類(lèi)都是的研究選取一到兩個(gè)屬性。

近年來(lái)，隨著VRP應(yīng)用的越來(lái)越廣，幾種車(chē)輛路徑規(guī)劃的求解算法：

2.1 遺傳算法

龔藝[7]等采用改進(jìn)遺傳算法對(duì)外賣(mài)配送系統(tǒng)建立了路徑最短的帶時(shí)間窗約束的模型。易欣[8]等針對(duì)機(jī)器人運(yùn)動(dòng)規(guī)劃中可能出現(xiàn)的局部陷阱和過(guò)早收斂問(wèn)題，提出了一種自適應(yīng)遺傳算法，用自適應(yīng)算子代替常規(guī)選擇算子，令自適應(yīng)算子在整個(gè)算法運(yùn)行中恰當(dāng)?shù)倪x擇壓力。梁凱[9]等主要針對(duì)配送中障礙物的位置與機(jī)器人行駛路徑之間的關(guān)系，通過(guò)采用可視圖法建立環(huán)境模型并進(jìn)行全局路徑規(guī)劃，移除影響路徑規(guī)劃障礙。將粗糙集理論和遺傳算法融合，在路徑規(guī)劃中減少可供選擇項(xiàng)，從而提高機(jī)器人路徑規(guī)劃的效率，減少搜索時(shí)間，提升機(jī)器人路徑規(guī)劃的整體性能。余文曌[10]等針對(duì)標(biāo)準(zhǔn)遺傳算法進(jìn)行路徑規(guī)劃時(shí)搜索空間大、出現(xiàn)過(guò)多搜索冗余和收斂效率低等問(wèn)題,給出在網(wǎng)格的遺傳算法上加入彈性網(wǎng)格概念。在低密度的網(wǎng)格地圖下求解最優(yōu)路徑，增加轉(zhuǎn)向點(diǎn)從而增加網(wǎng)格的密度，繼續(xù)搜索，反復(fù)此步驟，以減小算法搜索空間,提高路徑規(guī)劃效率；給出自適應(yīng)變異概率，使其根據(jù)各代路徑離散程度自適應(yīng)調(diào)整大小，以提高各代路徑多樣化。

2.2 RRT算法

蔡文濤[11]等針對(duì)快速探索隨機(jī)樹(shù)(RRT)路徑規(guī)劃算法缺乏導(dǎo)向性和規(guī)劃空間增大時(shí)算法時(shí)間復(fù)雜度高的問(wèn)題，提出一種目標(biāo)概率偏置與步長(zhǎng)控制的改進(jìn)RRT算法(I-RRT)。I-RRT結(jié)合目標(biāo)概率偏置，以一定概率使采樣點(diǎn)偏置為目標(biāo)點(diǎn)，提高路徑規(guī)劃的導(dǎo)向性，并引入步長(zhǎng)控制優(yōu)化算法，提高運(yùn)算效率，優(yōu)化路徑。王坤[12]等針對(duì)雙向快速擴(kuò)展隨機(jī)樹(shù)(RRT-Connect)算法的路徑規(guī)劃效率較低且采樣具有隨機(jī)性，對(duì)RRT-Connect算法進(jìn)行改進(jìn)，并提出了改進(jìn)后的算法DRRT-Connect。改進(jìn)后的算法在起始點(diǎn)與目標(biāo)點(diǎn)中間隨機(jī)抽取一個(gè)節(jié)點(diǎn)，做為第三節(jié)點(diǎn)也就稱之為擴(kuò)展點(diǎn)，抽取新的節(jié)點(diǎn)后算法可以同時(shí)從起始點(diǎn)、第三節(jié)點(diǎn)、目標(biāo)節(jié)點(diǎn)生成四棵隨機(jī)樹(shù)；同時(shí)在改進(jìn)算法中引入自適應(yīng)步長(zhǎng)調(diào)節(jié)函數(shù)，當(dāng)搜索不到障礙時(shí)，步長(zhǎng)調(diào)節(jié)函數(shù)自動(dòng)增大調(diào)節(jié)步長(zhǎng)，提高四棵隨機(jī)樹(shù)的搜索效率；在標(biāo)準(zhǔn)RRT-Connect算法的上引入目標(biāo)偏置策略，當(dāng)改進(jìn)后算法在探索無(wú)障礙空間時(shí)可以通過(guò)調(diào)節(jié)步長(zhǎng)朝目標(biāo)點(diǎn)快速擴(kuò)展，在探索障礙物空間時(shí)則調(diào)用隨機(jī)采樣函數(shù)，可以使算法效率提高，但又不會(huì)陷入局部最優(yōu)。

2.3 A～*算法

王銘楓[13]等提出一種基于轉(zhuǎn)向約束和能耗最優(yōu)的A～*路徑規(guī)劃算法。在采用載波相位差分(real-time kinematic,簡(jiǎn)稱RTK)全球?qū)Ш叫l(wèi)星系統(tǒng)(global navigation satellite system,簡(jiǎn)稱GNSS)精確采集及存儲(chǔ)田間道路路徑信息的基礎(chǔ)上，針對(duì)道路坡度起伏大的問(wèn)題,建立起伏道路的能耗計(jì)算函數(shù)，對(duì)A～*算法估價(jià)函數(shù)進(jìn)行重新設(shè)計(jì)；同時(shí)，針對(duì)部分路口轉(zhuǎn)向困難的問(wèn)題，引入路口轉(zhuǎn)向曲率進(jìn)行約束判斷。陸皖麟[14]等針對(duì)A～*算法的缺陷進(jìn)行改進(jìn)，A～*算法有搜索過(guò)程慢、路徑不光滑、折點(diǎn)過(guò)多浪費(fèi)時(shí)間等問(wèn)題。通過(guò)openlist添加閾值N，如果搜索次數(shù)大于N且最先插入的節(jié)點(diǎn)未擴(kuò)展，就將該節(jié)點(diǎn)設(shè)為最高級(jí)優(yōu)先擴(kuò)展，減少了搜索時(shí)間，將Floyd算法和A～*算法融合，兩種算法優(yōu)勢(shì)互補(bǔ)，解決A～*算法的缺陷，解決路徑不光滑等問(wèn)題。

3 總結(jié)

物流供應(yīng)鏈系統(tǒng)不斷的發(fā)展，VRP作為物流系統(tǒng)中至關(guān)重要的環(huán)節(jié)，已經(jīng)受到越來(lái)越多的重視。目前人們對(duì)于VRP的研究主要集中在對(duì)于各種算法的優(yōu)化與改進(jìn)上，研究學(xué)者們致力于提出更優(yōu)的算法，使得路徑規(guī)劃變得更快速更優(yōu)。各種算法在單獨(dú)使用時(shí)都會(huì)存在一些比較大的缺陷，而且隨著社會(huì)的發(fā)展，人們所要解決的問(wèn)題規(guī)模越來(lái)越大，結(jié)構(gòu)越來(lái)越復(fù)雜，僅僅只依靠一種算法很難解決現(xiàn)實(shí)中復(fù)雜的問(wèn)題。于是人們開(kāi)始致力于算法融合和改進(jìn)，各種算法互相彌補(bǔ)，克服了單一算法的很多缺點(diǎn)，構(gòu)造出改進(jìn)后更優(yōu)的算法。近十幾年，人們對(duì)于算法的研究更加側(cè)重于多種算法的融合，不斷構(gòu)造新的混合算法。