基于物流配送的車(chē)輛路徑優(yōu)化問(wèn)題綜述

王雪鳳，陳 昊

基于物流配送的車(chē)輛路徑優(yōu)化問(wèn)題綜述

王雪鳳，陳 昊

（遼寧工業(yè)大學(xué) 電子與信息工程學(xué)院，遼寧 錦州 121001）

針對(duì)日常運(yùn)營(yíng)中與物流配送相關(guān)的車(chē)輛路徑規(guī)劃問(wèn)題進(jìn)行了匯總，從不同角度歸納了基于物流配送的車(chē)輛路徑優(yōu)化問(wèn)題的研究分類(lèi)，并歸納了幾種常見(jiàn)的求解算法，旨在確定近幾年VRP變體和應(yīng)用算法的發(fā)展趨勢(shì)，最后對(duì)未來(lái)物流配送中車(chē)輛路徑問(wèn)題的發(fā)展方向進(jìn)行了討論。

車(chē)輛路徑優(yōu)化；物流配送；算法

近年來(lái)，受各種因素推力作用，我國(guó)的物流行業(yè)得到了迅猛發(fā)展，物流作為“第三效益源”，顯著影響著經(jīng)濟(jì)發(fā)展水平。隨著更多企業(yè)加入到物流行業(yè)中，物流行業(yè)已經(jīng)成為競(jìng)爭(zhēng)最激烈的行業(yè)之一。物流配送是指根據(jù)客戶(hù)需求，進(jìn)行備貨、裝貨、運(yùn)輸、送達(dá)的過(guò)程。配送調(diào)度和車(chē)輛路徑規(guī)劃對(duì)物流配送至關(guān)重要，在很大程度上決定了配送成本、客戶(hù)滿(mǎn)意度、配送時(shí)間等。由于貨物的配送受到運(yùn)輸公司、客戶(hù)和外部環(huán)境等多種因素的影響，物流配送與車(chē)輛路徑優(yōu)化問(wèn)題(vehicle routing optimization in material distribution)已經(jīng)成為眾多學(xué)者研究的熱門(mén)課題。如何實(shí)現(xiàn)科學(xué)物流配送是每個(gè)物流企業(yè)必須面臨的一個(gè)非常復(fù)雜和關(guān)鍵的問(wèn)題。物流配送過(guò)程中不僅僅要考慮車(chē)輛的路線規(guī)劃，還要考慮車(chē)輛數(shù)量、車(chē)輛容量、配送時(shí)間和突發(fā)情況等，加之物流企業(yè)服務(wù)水平的提高和客戶(hù)需求的隨機(jī)性，使得現(xiàn)代物流配送在實(shí)際運(yùn)營(yíng)中難度更大。車(chē)輛路徑優(yōu)化是物流配送中的關(guān)鍵一環(huán)，直接影響到配送完成時(shí)間和配送成本。

車(chē)輛路徑問(wèn)題(vehicle routing optimization problem，VRP)最早是由Dantzig等[1]提出來(lái)的，是一組高級(jí)而復(fù)雜的路線問(wèn)題，物流的合理化在很大程度上依賴(lài)于運(yùn)輸決策的合理化，通過(guò)運(yùn)輸路線的優(yōu)化，可以提高物流配送車(chē)輛的效率，滿(mǎn)足客戶(hù)的服務(wù)需求。車(chē)輛路徑優(yōu)化問(wèn)題被廣泛應(yīng)用于現(xiàn)實(shí)生活中。貨物的配送受到多種因素的影響，這些因素被轉(zhuǎn)化為問(wèn)題的約束或變量，并最終導(dǎo)致VRP不同變體的產(chǎn)生。比如，帶車(chē)輛容量限制的路徑優(yōu)化問(wèn)題、動(dòng)態(tài)車(chē)輛路徑優(yōu)化問(wèn)題、綠色車(chē)輛路徑優(yōu)化問(wèn)題等。學(xué)者們對(duì)該類(lèi)問(wèn)題的研究已經(jīng)取得豐富的成果，理想又高效的物流配送與車(chē)輛運(yùn)輸調(diào)度計(jì)劃是現(xiàn)今物流業(yè)急切需要的。

在復(fù)雜多變的現(xiàn)實(shí)環(huán)境下，對(duì)物流配送與車(chē)輛路徑優(yōu)化這一問(wèn)題，如何綜合多種目標(biāo)，合理制定車(chē)輛調(diào)度計(jì)劃，一直是國(guó)內(nèi)外學(xué)者關(guān)注的焦點(diǎn)，因此本文主要總結(jié)現(xiàn)實(shí)情況下的VRP變體、問(wèn)題的表述、目標(biāo)函數(shù)以及對(duì)應(yīng)求解算法。

1 物流供應(yīng)與車(chē)輛路徑優(yōu)化問(wèn)題的問(wèn)題描述和研究分類(lèi)

1.1 問(wèn)題描述

物流供應(yīng)與車(chē)輛路徑優(yōu)化問(wèn)題旨在滿(mǎn)足項(xiàng)目活動(dòng)優(yōu)先級(jí)和各種約束的情況下，合理安排不同裝載容量的車(chē)輛，并根據(jù)實(shí)際路線情況選擇適合的路線，以達(dá)到總成本最小、用時(shí)最短等目標(biāo)。VRP問(wèn)題可以描述如下。

(1)物流配送問(wèn)題評(píng)價(jià)指標(biāo)

最大效益、最小總成本、最高滿(mǎn)意度、最低能源消耗等，VRP問(wèn)題中配送總成本一般由車(chē)輛固定成本、等待成本、服務(wù)成本、懲罰成本、能源消耗費(fèi)用等多種成本組成。

(2)物流配送路線優(yōu)化數(shù)學(xué)模型

一個(gè)物流配送網(wǎng)絡(luò)包含個(gè)客戶(hù)站點(diǎn)，這些客戶(hù)站點(diǎn)有不同的位置和貨物需求；物流配送中心共有輛配送車(chē)，每輛車(chē)已知最大承載能力P(=1, 2, …,)，從配送中心出發(fā)并返回配送中心。

(3)約束條件

每輛車(chē)在執(zhí)行物流配送任務(wù)時(shí)，且物流裝載量不能大于車(chē)輛承載能力；車(chē)輛從配送中心出發(fā)，執(zhí)行完任務(wù)必須回到配送中心，且每個(gè)客戶(hù)只訪問(wèn)1次。

(4)VRP問(wèn)題的決策變量

1.2 目標(biāo)函數(shù)

VRP問(wèn)題的目標(biāo)函數(shù)一般情況下可以分為以下幾類(lèi)：總成本最小化(minimum total cost)、時(shí)間最短化(shortesttime)、客戶(hù)滿(mǎn)意度最高化(highest customer satisfaction)、碳排放量最少化(least carbon emissions)。

(1)總成本最小

(2)時(shí)間最短

(3)客戶(hù)滿(mǎn)意度最高

(4)碳排放量最少

(5)路程最短

總成本最小化的目標(biāo)函數(shù)公式見(jiàn)式(1)，其中是車(chē)輛使用的固定費(fèi)用，為車(chē)輛行駛單位時(shí)間內(nèi)動(dòng)態(tài)費(fèi)用(如行駛過(guò)程中單位時(shí)間內(nèi)的燃油費(fèi)用和碳排放納稅額)。t表示車(chē)輛從節(jié)點(diǎn)行駛到節(jié)點(diǎn)的行駛時(shí)間，δ是提前到達(dá)目的地的等待時(shí)間，g是服務(wù)客戶(hù)的時(shí)間。是項(xiàng)目中所有節(jié)點(diǎn)的集合，是客戶(hù)集合。

客戶(hù)滿(mǎn)意度最高的目標(biāo)函數(shù)公式見(jiàn)式(3)，在VRP問(wèn)題中，客戶(hù)期望物流能夠及時(shí)配送且對(duì)配送的及時(shí)性有一定容忍度，一般而言，越接近客戶(hù)的期望值，客戶(hù)滿(mǎn)意度就越高。F是關(guān)于客戶(hù)滿(mǎn)意度函數(shù)。

碳排放量的目標(biāo)函數(shù)公式見(jiàn)式(4)，燃油消耗是衡量碳排放量的重要指標(biāo)，通常用燃油消耗的函數(shù)進(jìn)行碳排放量的計(jì)算。配送過(guò)程中使用車(chē)輛數(shù)量為，G表示車(chē)輛從節(jié)點(diǎn)到節(jié)點(diǎn)完成配送的碳排放量。

路程最短的目標(biāo)函數(shù)公式見(jiàn)式(5)，其中d表示車(chē)輛從節(jié)點(diǎn)行駛到節(jié)點(diǎn)距離。配送總路程等于所有車(chē)輛所經(jīng)過(guò)節(jié)點(diǎn)的累加和。

2 VRP變體分類(lèi)

車(chē)輛路線問(wèn)題(VRP)是當(dāng)今物流業(yè)面臨的關(guān)鍵性挑戰(zhàn)之一，自提出以來(lái)產(chǎn)生了大量的變體，現(xiàn)實(shí)的路徑問(wèn)題中包含的約束和參數(shù)與不同的VRP變體有關(guān)，它們決定了路線、長(zhǎng)度和持續(xù)時(shí)間。

2.1 考慮環(huán)境影響的研究

考慮環(huán)境影響的車(chē)輛路徑問(wèn)題是VRP重要的變體之一，被稱(chēng)之為GreenVRP(GVRP)。隨著全球平均氣溫的上升和全球能源緊張局勢(shì)，氣候變化問(wèn)題已成為全球關(guān)注的焦點(diǎn)。節(jié)能減排已成為國(guó)際社會(huì)的共同責(zé)任。碳排放是溫室氣體的主要來(lái)源，而交通運(yùn)輸是溫室氣體產(chǎn)生的主要途徑之一，經(jīng)濟(jì)日益發(fā)展，交通運(yùn)輸與日增長(zhǎng)，如何節(jié)能減排和提高資源效率是一項(xiàng)重要的科學(xué)研究課題。眾多學(xué)者致力于減少碳排放的綠色車(chē)輛路徑優(yōu)化問(wèn)題研究。

車(chē)輛中的碳排放取決于許多因素，如車(chē)輛負(fù)荷、重量、燃料的類(lèi)型、燃料效率、行駛速度以及起點(diǎn)和目的地之間的距離等。距離并不是唯一的決定性因素，其他因素也有不同的涉及，傳統(tǒng)測(cè)量燃油消耗的方法是行程長(zhǎng)度的線性函數(shù)，但這不夠精確。因此Liu等[2]提出了一種基于速度的碳排放量算法，發(fā)現(xiàn)以速度作為決策變量的路徑優(yōu)化策略比固定速度決策更有效地減少能源消耗和碳排放，且證明了在以最短路徑為目標(biāo)時(shí)，最短路徑不一定能源消耗最小。邱金紅等[3]研究了基于配送收益的多目標(biāo)綠色車(chē)輛路徑優(yōu)化問(wèn)題。Ganji等[4]針對(duì)具有多異質(zhì)車(chē)輛進(jìn)行配送的集成供應(yīng)調(diào)度問(wèn)題，綜合考慮了車(chē)輛負(fù)載、速度和實(shí)際行駛距離3個(gè)因素對(duì)碳排放水平的影響，并采用3種多目標(biāo)元啟發(fā)式算法：多目標(biāo)粒子群算法、NSGAII-非支配排序遺傳算法和多目標(biāo)蟻群算法求解。

2.2 考慮實(shí)時(shí)性和隨機(jī)需求的研究

在現(xiàn)實(shí)的物流配送中，會(huì)面臨很多諸如天氣變化、事故等復(fù)雜的、不確定的情況，造成客戶(hù)需求的變化。若大型車(chē)輛進(jìn)行物流配送，客戶(hù)減少需求量，會(huì)造成額外的車(chē)輛成本增加；若客戶(hù)需求量突然增加，會(huì)造成部分客戶(hù)的需求無(wú)法滿(mǎn)足。訂單和不可預(yù)見(jiàn)的事件可能會(huì)在執(zhí)行過(guò)程中動(dòng)態(tài)出現(xiàn)。

在運(yùn)輸因素不穩(wěn)定的情況下，Dror等[5]首次提出允許分割交付的物流配送模型，以節(jié)省總距離和車(chē)輛費(fèi)用。魯玉等[6]研究了具有隨機(jī)需求的鐵路冷鏈物流運(yùn)輸問(wèn)題，研究發(fā)現(xiàn)，客戶(hù)需求量在一定的時(shí)期內(nèi)服從正態(tài)分布，利用機(jī)會(huì)約束規(guī)劃理論，將該問(wèn)題轉(zhuǎn)化為滿(mǎn)足一定置信水平的約束條件的確定性問(wèn)題。并設(shè)計(jì)了自適應(yīng)遺傳-模擬退火算法進(jìn)行求解。陳治亞等[7]通過(guò)分析基于隨機(jī)需求下的物流運(yùn)輸?shù)目煽啃裕谲?chē)輛限載量滿(mǎn)足一定的約束下，構(gòu)造多目標(biāo)車(chē)輛路徑優(yōu)化模型，改進(jìn)蟻群算法并引入貪心策略進(jìn)行求解。張得志等[8]提出了一種考慮隨機(jī)需求和各線路均衡的訂單拆分、車(chē)輛隨機(jī)配對(duì)的服務(wù)策略，發(fā)現(xiàn)當(dāng)客戶(hù)需求大于車(chē)輛最大容量，那么訂單將進(jìn)行拆分，使用2個(gè)或2個(gè)以上的車(chē)輛進(jìn)行物流運(yùn)輸。

考慮隨機(jī)需求的車(chē)輛路徑優(yōu)化模型更具有現(xiàn)實(shí)意義，很大程度上提高了訂單完成數(shù)量，節(jié)約配送成本。

2.3 考慮時(shí)間窗的研究

帶有時(shí)間窗口的VRP(VRPTW)也是最常見(jiàn)的變體之一。在車(chē)輛運(yùn)輸?shù)穆窂絻?yōu)化問(wèn)題中，一般情況會(huì)加入時(shí)間窗限制，用來(lái)更好地定義客戶(hù)滿(mǎn)意度和計(jì)算運(yùn)輸過(guò)程中提前成本和延遲費(fèi)用，其中每個(gè)客戶(hù)確定了必須交付訂單的時(shí)間窗，時(shí)間窗分為軟時(shí)間窗、硬時(shí)間窗、模糊時(shí)間窗。軟時(shí)間窗VRP要求車(chē)輛在時(shí)間窗內(nèi)[ET, LT]到達(dá)，在[EET, ET]或[LT, LLT]到達(dá)會(huì)給予一定的懲罰；硬時(shí)間窗VRP要求必須在時(shí)間窗內(nèi)到達(dá)，否則拒絕服務(wù)；模糊時(shí)間窗VRP是構(gòu)造車(chē)輛到達(dá)時(shí)間的隸屬模糊度函數(shù)，來(lái)定義客戶(hù)滿(mǎn)意度或懲罰費(fèi)用。

吳倩云等[9]針對(duì)集成物流調(diào)度下的車(chē)輛路徑優(yōu)化問(wèn)題，結(jié)合軟時(shí)間窗和裝載約束，建立了基于遺傳算法的車(chē)輛路徑優(yōu)化模型；Pérez-Rodríguez等[10]研究了一種帶有硬時(shí)間窗VRP問(wèn)題，考慮服務(wù)每個(gè)客戶(hù)的時(shí)間窗間隔、車(chē)輛數(shù)量和客戶(hù)數(shù)量的關(guān)系，提出了一種分布估計(jì)算法來(lái)解決該問(wèn)題；但經(jīng)典的時(shí)間窗的概念并不能很好地表現(xiàn)出車(chē)輛未在合理時(shí)間內(nèi)到達(dá)所造成的損失，也不能很好地模擬客戶(hù)的偏好，因此戶(hù)佐安等[11]對(duì)時(shí)間窗采用模糊化處理，用隸屬度函數(shù)表示客戶(hù)的偏好，在一定程度上提高了物流配送車(chē)輛路徑問(wèn)題的有效性和實(shí)用性。

2.4 考慮協(xié)同配送的研究

協(xié)同配送是包含多個(gè)配送中心的物流配送問(wèn)題，旨在提高物流配送效率。Renaud等[12]描述一種新的啟發(fā)式算法的多倉(cāng)庫(kù)車(chē)輛路線問(wèn)題(MDVRP)在有多個(gè)配送中心的情況下，客戶(hù)通常被分配到最近的倉(cāng)庫(kù)，該倉(cāng)庫(kù)包含每個(gè)客戶(hù)訂購(gòu)的貨物。MDVRP在許多情況下都會(huì)遇到，并且具有相當(dāng)大的經(jīng)濟(jì)重要性，比如快遞送餐、石油運(yùn)輸、包裝食品等。Wang等[13]提出了一種基于多倉(cāng)庫(kù)的協(xié)同配送車(chē)輛路徑優(yōu)化問(wèn)題(CMCVRP)，通過(guò)協(xié)作機(jī)制，使客戶(hù)需求合理分配到相鄰的倉(cāng)庫(kù)，以實(shí)現(xiàn)運(yùn)營(yíng)成本和分銷(xiāo)成本最小化的目標(biāo)，有效地提高車(chē)輛裝載率，減少交叉運(yùn)輸現(xiàn)象，提高物流網(wǎng)絡(luò)運(yùn)營(yíng)效率。

在運(yùn)輸公司中不太常見(jiàn)的2種VRP變體，分割交付VRP(SDVRP)和定期VRP(PVRP)。Dror等[14]研究VRP的松弛版本，在通常情況下，每個(gè)客戶(hù)必須由1輛車(chē)訪問(wèn)1次的約束被放寬，并且客戶(hù)需求的交付可以分給任意數(shù)量的車(chē)輛。在某些配送環(huán)境中，特殊放松可能是有利的，例如當(dāng)平均客戶(hù)需求略超過(guò)車(chē)輛容量時(shí)，增加車(chē)輛負(fù)荷系數(shù)和減少交付路線數(shù)量，會(huì)節(jié)約成本。而PVRP，最早是Coene等[15]提出來(lái)的，是針對(duì)一個(gè)時(shí)期的優(yōu)化，與傳統(tǒng)的VRP一樣，給出了每個(gè)具有特定需求功能的客戶(hù)位置，以及一組有能力的車(chē)輛。此外，路線的計(jì)劃發(fā)生在天的時(shí)間內(nèi)，客戶(hù)以不同的頻率訪問(wèn)。其目標(biāo)是使規(guī)劃范圍內(nèi)所有路線的成本總和最小化。Francis等[16]在PVPP問(wèn)題中引入服務(wù)頻率進(jìn)行建模，在一段時(shí)間內(nèi)為每輛車(chē)每天尋找一組行程，以減少總旅行成本減去服務(wù)效益的目標(biāo)，同時(shí)滿(mǎn)足操作限制(車(chē)輛容量和訪問(wèn)頻率最小值)。

2.5 考慮車(chē)輛能力的研究

道路物流運(yùn)輸會(huì)用到不同類(lèi)型和容量的車(chē)輛，任何情況下都不能違背車(chē)輛的運(yùn)輸能力限制。車(chē)輛的容量是車(chē)輛路徑問(wèn)題的一個(gè)關(guān)鍵因素，因?yàn)樗乾F(xiàn)實(shí)分布情況中研究最多的2個(gè)變體VRP：(1)同構(gòu)VRP(CVRP)，所有車(chē)輛具有相同的容量；(2)異構(gòu)VRP(HFVRP)，車(chē)輛具有不同的容量。

Ganji等[4]根據(jù)訂單貨物容量分配訂單給不同的異構(gòu)車(chē)輛，在一定程度上減少了燃料成本和碳排放量。陳希瓊等[17]在研究帶車(chē)輛容量限制的同構(gòu)VRP問(wèn)題時(shí)，用有向圖表示網(wǎng)狀物流運(yùn)輸路線，并設(shè)置最大車(chē)輛運(yùn)輸距離和每條邊上流量不能超過(guò)最大車(chē)輛容量的約束條件，以達(dá)到成本和各車(chē)輛工作負(fù)荷之差最小的雙目標(biāo)模型。

殷亞等[18]在對(duì)同構(gòu)VRP問(wèn)題的研究中引入車(chē)輛路線限制和裝載能力約束。無(wú)論車(chē)輛異構(gòu)的還是同構(gòu)的，考慮裝載約束時(shí)，又有2個(gè)變體產(chǎn)生：二維(2D-VRP)裝載約束和三維(3D-VRP)裝載約束。

尚正陽(yáng)等[19]在考慮車(chē)輛容量和裝載約束的情況下，設(shè)計(jì)了最少剩余開(kāi)放空間的貨物裝載方法，更大限度提高車(chē)輛利用率。王勇等[20]研究了三維裝載約束的車(chē)輛路徑優(yōu)化問(wèn)題，裝車(chē)時(shí)對(duì)貨物的行數(shù)、列數(shù)、層數(shù)進(jìn)行規(guī)劃，并結(jié)合車(chē)輛裝載貨物的數(shù)量、體積、重量，采用NSGA-Ⅱ算法生成配送路徑和三維裝載方案。

2.6 帶有回程和同時(shí)拾取交付的研究

物流操作并不會(huì)在貨物交付階段結(jié)束，因?yàn)榭蛻?hù)退貨的現(xiàn)象在實(shí)踐中是常見(jiàn)的。最早的取貨和送貨VRP的研究為帶有回程的VRP(VRPB)，VRPB中車(chē)輛送貨后取貨，避免了回程的空車(chē)行駛，節(jié)省了運(yùn)輸成本。然而在傳統(tǒng)的VRPB中，需服務(wù)完送貨點(diǎn)后再服務(wù)取貨點(diǎn)，這樣勢(shì)必造成車(chē)輛路徑的迂回，對(duì)于既有送貨需求又有取貨需求的客戶(hù)，產(chǎn)生了同時(shí)拾取和交付的VRP(VRPSPD)。這2種變體幾乎都以最小化車(chē)輛數(shù)或總行駛距離為研究目標(biāo)。

Montané等[21]首次提出VRPSPD問(wèn)題，在VRPSPD的情況下，貨物從中央倉(cāng)庫(kù)開(kāi)始交付給客戶(hù)，同時(shí)取貨裝載到車(chē)輛上，然后返回倉(cāng)庫(kù)。在每個(gè)階段，都必須考慮交付和拾取負(fù)荷，因?yàn)椴荒艹^(guò)車(chē)輛的總?cè)萘?。另一方面，Goetschalckx等[22]研究的VRPB也涉及拾取和交付，并且所有拾取都是在每條路線交貨后收集的。所以這2種變體被認(rèn)為是同一變體，在文獻(xiàn)的分類(lèi)中被命名為VRPPD，因?yàn)樗鼈兌忌婕暗绞叭『徒桓丁?/p>

3 求解算法

車(chē)輛路徑規(guī)劃問(wèn)題是經(jīng)典的組合優(yōu)化問(wèn)題之一，屬于NP-hard問(wèn)題。在這個(gè)問(wèn)題被提出的幾十年歷史中，算法研究逐漸繁榮起來(lái)，總體上可以分為精確算法、啟發(fā)式算法和元啟發(fā)式算法等。精確算法可以求得小規(guī)模物流配送路徑優(yōu)化問(wèn)題的最優(yōu)解，但對(duì)現(xiàn)代大型物流配送路徑優(yōu)化問(wèn)題來(lái)說(shuō)，計(jì)算復(fù)雜性大，求解效率低。啟發(fā)式算法與精確方法相比，提高了求解效率，但很難得到物流配送路線的最優(yōu)解決方案。元啟發(fā)式算法具有搜索速度快，能夠獲得高質(zhì)量解等優(yōu)點(diǎn)，因此成為解決物流配送問(wèn)題的主要方法。

不同的算法具有不同的優(yōu)缺點(diǎn)，在車(chē)輛路徑優(yōu)化的研究中，學(xué)者不斷改進(jìn)或融合各算法的優(yōu)勢(shì)，提出具有更高效率或最優(yōu)解的算法。Bhagade等[23]首次應(yīng)用人工蜂群算法求解物流配送中的車(chē)輛路徑優(yōu)化問(wèn)題。人工蜂群算法具有很高的靈活性，通過(guò)考慮很少的控制參數(shù)，可以有效地尋找最短路徑。Zhao等[24]提出了一種基于成本、碳排放和客戶(hù)滿(mǎn)意度的多目標(biāo)優(yōu)化模型，并設(shè)計(jì)了一種具有多目標(biāo)啟發(fā)式函數(shù)的蟻群算法(ACOMO)來(lái)求解，ACOMO算法優(yōu)于經(jīng)典的蟻群算法。

Liu等[25]提出了一種基于對(duì)立學(xué)習(xí)的物流配送路徑優(yōu)化(OBLPSO)算法，建立物流配送路徑優(yōu)化數(shù)學(xué)模型，通過(guò)粒子間的協(xié)作和信息交換求解，引入基于對(duì)立的學(xué)習(xí)機(jī)制來(lái)提高粒子群優(yōu)化能力和收斂速度，與其他物流配送路線優(yōu)化算法相比，OBLPSO算法可以獲得短時(shí)間、合理路線的物流配送解決方案。Ganji等[4]采用3種多目標(biāo)元啟發(fā)式算法：多目標(biāo)粒子群算法(MOPSO)、非支配排序遺傳算法(NSGA-Ⅱ)和多目標(biāo)蟻群算法(MOACO)求解車(chē)輛路徑優(yōu)化問(wèn)題，實(shí)驗(yàn)表明，NSGA-Ⅱ在求得最優(yōu)解和處理時(shí)間上，優(yōu)于其他2種算法。Xiong[26]針對(duì)物流配送路徑優(yōu)化問(wèn)題，提出了一種新的混合更新信息素策略的蟻群算法(ICAO)，在以最短距離和最短時(shí)間為目標(biāo)時(shí)，IACO算法明顯優(yōu)于經(jīng)典ACO算法，有效縮短了配送任務(wù)時(shí)間和運(yùn)輸路徑距離，最大限度地提高物流整體和配送的效率。Jabir等[27]提出了一種將蟻群優(yōu)化算法與變量鄰域搜索相結(jié)合的混合求解算法(ACO-VNS)，混合ACO-VNS啟發(fā)式算法將提供一組通向Pareto最優(yōu)解邊界的非支配解。Liu等[2]提出了一種基于云模型的多目標(biāo)混合量子免疫算法(CHQIA)。郭森等[28]提出了一種基于動(dòng)態(tài)學(xué)習(xí)和突變因子的粒子群算法(DSPSO)，采用動(dòng)態(tài)學(xué)習(xí)策略來(lái)自適應(yīng)更新PSO認(rèn)知成分和社會(huì)成分的權(quán)重，突變因子使PSO算法具有跳出局部收斂的能力。羅梓瑄等[29]設(shè)計(jì)帶有精英策略的非支配排序遺傳算法(NSGA-Ⅱ)對(duì)物流配送路徑優(yōu)化模型進(jìn)行求解。Fran?ois等[30]開(kāi)發(fā)并測(cè)試了2種自適應(yīng)大鄰域搜索(ALNS)算法，該算法不考慮持續(xù)時(shí)間的約束。Nalepa等[31]針對(duì)帶有時(shí)間窗車(chē)輛路徑問(wèn)題，提出了一種自適應(yīng)模因算法，算法的參數(shù)，如選擇方案、種群大小和生成的子解的數(shù)量，在搜索過(guò)程中被動(dòng)態(tài)調(diào)整。主要優(yōu)化目標(biāo)及其算法如表1所示。

表1 主要優(yōu)化目標(biāo)及其求解算法

4 未來(lái)研究展望

物流配送與車(chē)輛路徑優(yōu)化問(wèn)題隨著時(shí)代發(fā)展不斷發(fā)展，該問(wèn)題已經(jīng)產(chǎn)生了大量變體，并且由此而產(chǎn)生的解決方案已經(jīng)應(yīng)用于現(xiàn)實(shí)生活中，未來(lái)的研究方向主要包括以下方面。

(1)隨著清潔能源的電動(dòng)汽車(chē)的普及，帶充電站的電動(dòng)汽車(chē)物流配送可作為未來(lái)研究的新熱點(diǎn)。

(2)在實(shí)際的物流配送車(chē)輛路徑優(yōu)化所構(gòu)建的模型中，大部分研究忽略了天氣、道路交通、客戶(hù)需求不穩(wěn)定等不確定性因素。不確定環(huán)境下的動(dòng)態(tài)物流配送問(wèn)題，將是未來(lái)的研究方向，也更加貼近生活需要。

(3)未來(lái)的信息價(jià)值將呈現(xiàn)出重要價(jià)值。如何對(duì)現(xiàn)在的信息進(jìn)行整合，對(duì)未來(lái)的車(chē)輛調(diào)度或者路徑規(guī)劃進(jìn)行合理的指導(dǎo)，獲得一個(gè)最優(yōu)方案將是物流配送中亟待解決的問(wèn)題。

[1] Dantzig G B, Ramser J H. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80-91.

[2] Liu X H, Shan M Y, Zhang R L, et al. Green Vehicle Routing Optimization Based on Carbon Emission and Multi-objective Hybrid Quantum Immune Algorithm[J]. Mathematical Problems in Engineering, 2018, 2018(4): 1-9.

[3] 邱金紅, 孫靖, 仲兆滿(mǎn). 基于配送收益均衡的多目標(biāo)綠色車(chē)輛路徑優(yōu)化算法[J]. 控制與決策, 2021, 12(3): 1-7.

[4] Ganji M, Kazemipoor H, Molana S. A green multi-objective integrated scheduling of production and distribution with heterogeneous fleet vehicle routing and time windows[J]. Journal of Cleaner Production, 2020, 259: 120824.

[5] Dror M, Trudeau P. Savings by Split Delivery Routing[J]. Transportation Science, 1989, 23(2): 141-145.

[6] 魯玉, 徐行方, 尹傳忠, 等. 鐵路冷鏈物流運(yùn)輸多目標(biāo)機(jī)會(huì)約束規(guī)劃[J]. 同濟(jì)大學(xué)學(xué)報(bào): 自然科學(xué)版, 2021, 49(10): 1407-1416.

[7] 陳治亞, 高輝, 徐光明, 等. 考慮隨機(jī)需求和硬時(shí)間窗的多目標(biāo)車(chē)輛路徑優(yōu)化方法[J]. 鐵道科學(xué)與工程學(xué)報(bào), 2021, 18(12): 3110-3120.

[8] 張得志, 何亦揚(yáng), 龔浩翔. 隨機(jī)需求訂單可拆分的多目標(biāo)車(chē)輛路徑問(wèn)題[J]. 鐵道科學(xué)與工程學(xué)報(bào), 2018, 15(5): 1-10.

[9] 吳倩云, 謝乃明, 邵雨婷. 考慮時(shí)間窗和裝載約束的裝配線集成物流調(diào)度[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2020, 26(3): 806-814.

[10] Pérez-Rodríguez R, Hernández-Aguirre A. A hybrid estimation of distribution algorithm for the vehicle routing problem with time windows[J]. Computers & Industrial Engineering, 2019, 130: 75-96.

[11] 戶(hù)佐安, 賈葉子, 李博威, 等. 考慮客戶(hù)滿(mǎn)意度的車(chē)輛路徑優(yōu)化研究[J]. 工業(yè)工程, 2019, 22(1): 100-107.

[12] Renaud J, Laporte G, Boctor F F. A tabu search heuristic for the multi-depot vehicle routing problem[J]. Computers & Operations Research, 1996, 23(3): 229-235.

[13] Wang Y, Ma X, Li Z, et al. Profit distribution in collaborative multiple centers vehicle routing problem[J]. Journal of Cleaner Production, 2017, 144: 203-219.

[14] Dror M, Trudeau P. Savings by split delivery routing[J]. Transportation Science, 1989, 23(2): 141-145.

[15] Coene S, Arnout A, Spieksma F C R. On a periodic vehicle routing problem[J]. Journal of the Operational Research Society, 2010, 61(12): 1719-1728.

[16] Francis P, Smilowitz K, Tzur M. The Period Vehicle Routing Problem with Service Choice[J]. Transportation Science, 2006, 40(4):439-454.

[17] 陳希瓊, 胡大偉, 楊倩倩, 等. 多目標(biāo)同時(shí)取送貨車(chē)輛路徑問(wèn)題的改進(jìn)蟻群算法[J]. 控制理論與應(yīng)用, 2018, 35(9): 1347-1356.

[18] 殷亞, 張惠珍. 求解帶硬時(shí)間窗的多目標(biāo)車(chē)輛路徑問(wèn)題的多種混合蝙蝠算法[J]. 計(jì)算機(jī)應(yīng)用研究, 2017, 34(12): 3632-3636.

[19] 尚正陽(yáng), 顧寄南, 潘家保. 考慮LIFO約束的2L-CVRP優(yōu)化[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2021, 27(7): 2134-2143.

[20] 王勇, 左佳昕, 蔣瓊, 等. 基于產(chǎn)品回收定價(jià)的逆向物流車(chē)輛路徑優(yōu)化問(wèn)題[J].系統(tǒng)管理學(xué)報(bào), 2022, 31(2): 199-216.

[21] Montané F A T, Galvao R D. A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service[J]. Computers & Operations Research, 2006, 33(3): 595-619.

[22] Goetschalckx M, Jacobs-Blecha C. The vehicle routing problem with backhauls[J]. European Journal of Operational Research, 1989, 42(1): 39-51.

[23] Bhagade A S, Puranik P V. Artificial bee colony algorithm for vehicle routing optimization problem[J]. International Journal of Soft Computing and Engineering, 2012, 2(2): 329-333.

[24] Zhao B, Gui H, Li H, et al. Cold chain logistics path optimization via improved multi-objectiveant colony algorithm[J]. Ieee Access, 2020, 8(1): 142977-142995.

[25] Liu X J, Zhang B. Study on Optimization of Logistics Distribution Routes Based on Opposition- based Learning Particle Swarm Optimization Algorithm[J]. Logistics Technology, 2014, 7(1): 1318-1322.

[26] Xiong H. Research on cold chain logistics distribution route based on ant colony optimization algorithm[J]. Discrete Dynamics in Nature and Society, 2021, 2021(1): 134-139.

[27] Jabir E, Panicker V V, Sridharan R. Multi-objective Optimization Model for a Green Vehicle Routing Problem[J]. Procedia-Social and Behavioral Sciences, 2015, 189: 33-39.

[28] 郭森, 秦貴和, 張晉東, 等. 多目標(biāo)車(chē)輛路徑問(wèn)題的粒子群優(yōu)化算法研究[J]. 西安交通大學(xué)學(xué)報(bào), 2016, 50(9): 97-104.

[29] 羅梓瑄, 楊杰慶, 劉學(xué)文. 基于NSGA-Ⅱ的考慮客戶(hù)滿(mǎn)意度的多目標(biāo)車(chē)輛路徑問(wèn)題研究[J]. 重慶師范大學(xué)學(xué)報(bào): 自然科學(xué)版, 2020, 37(6): 1-5.

[30] Fran?ois V, Arda Y, Crama Y, et al. Large neighborhood search for multi-trip vehicle routing[J]. European Journal of Operational Research, 2016, 255(2): 422-441.

[31] Nalepa J, Blocho M. Adaptive memetic algorithm for minimizing distance in the vehicle routing problem with time windows[J]. Soft Computing, 2016, 20(6): 2309-2327.

Review of Vehicle Routing Optimization Based on Logistics Distribution

WANG Xue-feng, CHEN Hao

（School of Electronics & Information Engineering, Liaoning University of Technology, Jinzhou 121001, China）

This paper summarizes the vehicle routing plan problems related to logistics distribution in daily operations, the research classifications of vehicle routing optimization problems based on logistics distribution from different perspectives, and several common algorithms to determine the development trend of VRP variants and application algorithms in recent years, and finally discusses the development direction of vehicle routing problems in logistics distribution in the future.

vehicle routing optimization; logistics distribution; algorithm

10.15916/j.issn1674-3261.2022.06.008

TP311

A

1674-3261(2022)06-0386-07

2022-04-12

王雪鳳(1996-)，女，河南開(kāi)封人，碩士生。

責(zé)任編輯：孫 林