王雪鳳，陳 昊

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

王雪鳳，陳 昊

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

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

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

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

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

在復(fù)雜多變的現(xiàn)實(shí)環(huán)境下，對(duì)物流配送與車輛路徑優(yōu)化這一問(wèn)題，如何綜合多種目標(biāo)，合理制定車輛調(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)與車輛路徑優(yōu)化問(wèn)題的問(wèn)題描述和研究分類

1.1 問(wèn)題描述

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

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

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

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

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

(3)約束條件

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

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

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

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

(1)總成本最小

(2)時(shí)間最短

(3)客戶滿意度最高

(4)碳排放量最少

(5)路程最短

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

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

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

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

2 VRP變體分類

車輛路線問(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)境影響的車輛路徑問(wèn)題是VRP重要的變體之一，被稱之為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é)者致力于減少碳排放的綠色車輛路徑優(yōu)化問(wèn)題研究。

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

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

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

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

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

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

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

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

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

協(xié)同配送是包含多個(gè)配送中心的物流配送問(wèn)題，旨在提高物流配送效率。Renaud等[12]描述一種新的啟發(fā)式算法的多倉(cāng)庫(kù)車輛路線問(wèn)題(MDVRP)在有多個(gè)配送中心的情況下，客戶通常被分配到最近的倉(cāng)庫(kù)，該倉(cāng)庫(kù)包含每個(gè)客戶訂購(gòu)的貨物。MDVRP在許多情況下都會(huì)遇到，并且具有相當(dāng)大的經(jīng)濟(jì)重要性，比如快遞送餐、石油運(yùn)輸、包裝食品等。Wang等[13]提出了一種基于多倉(cāng)庫(kù)的協(xié)同配送車輛路徑優(yōu)化問(wèn)題(CMCVRP)，通過(guò)協(xié)作機(jī)制，使客戶需求合理分配到相鄰的倉(cāng)庫(kù)，以實(shí)現(xiàn)運(yùn)營(yíng)成本和分銷成本最小化的目標(biāo)，有效地提高車輛裝載率，減少交叉運(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è)客戶必須由1輛車訪問(wèn)1次的約束被放寬，并且客戶需求的交付可以分給任意數(shù)量的車輛。在某些配送環(huán)境中，特殊放松可能是有利的，例如當(dāng)平均客戶需求略超過(guò)車輛容量時(shí)，增加車輛負(fù)荷系數(shù)和減少交付路線數(shù)量，會(huì)節(jié)約成本。而PVRP，最早是Coene等[15]提出來(lái)的，是針對(duì)一個(gè)時(shí)期的優(yōu)化，與傳統(tǒng)的VRP一樣，給出了每個(gè)具有特定需求功能的客戶位置，以及一組有能力的車輛。此外，路線的計(jì)劃發(fā)生在天的時(shí)間內(nèi)，客戶以不同的頻率訪問(wèn)。其目標(biāo)是使規(guī)劃范圍內(nèi)所有路線的成本總和最小化。Francis等[16]在PVPP問(wèn)題中引入服務(wù)頻率進(jìn)行建模，在一段時(shí)間內(nèi)為每輛車每天尋找一組行程，以減少總旅行成本減去服務(wù)效益的目標(biāo)，同時(shí)滿足操作限制(車輛容量和訪問(wèn)頻率最小值)。

2.5 考慮車輛能力的研究

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

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

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

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

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

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

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

3 求解算法

車輛路徑規(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)，在車輛路徑優(yōu)化的研究中，學(xué)者不斷改進(jìn)或融合各算法的優(yōu)勢(shì)，提出具有更高效率或最優(yōu)解的算法。Bhagade等[23]首次應(yīng)用人工蜂群算法求解物流配送中的車輛路徑優(yōu)化問(wèn)題。人工蜂群算法具有很高的靈活性，通過(guò)考慮很少的控制參數(shù)，可以有效地尋找最短路徑。Zhao等[24]提出了一種基于成本、碳排放和客戶滿意度的多目標(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)求解車輛路徑優(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]開發(fā)并測(cè)試了2種自適應(yīng)大鄰域搜索(ALNS)算法，該算法不考慮持續(xù)時(shí)間的約束。Nalepa等[31]針對(duì)帶有時(shí)間窗車輛路徑問(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)研究展望

物流配送與車輛路徑優(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)汽車的普及，帶充電站的電動(dòng)汽車物流配送可作為未來(lái)研究的新熱點(diǎn)。

(2)在實(shí)際的物流配送車輛路徑優(yōu)化所構(gòu)建的模型中，大部分研究忽略了天氣、道路交通、客戶需求不穩(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)的車輛調(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] 邱金紅, 孫靖, 仲兆滿. 基于配送收益均衡的多目標(biāo)綠色車輛路徑優(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)車輛路徑優(yōu)化方法[J]. 鐵道科學(xué)與工程學(xué)報(bào), 2021, 18(12): 3110-3120.

[8] 張得志, 何亦揚(yáng), 龔浩翔. 隨機(jī)需求訂單可拆分的多目標(biāo)車輛路徑問(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] 戶佐安, 賈葉子, 李博威, 等. 考慮客戶滿意度的車輛路徑優(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í)取送貨車輛路徑問(wèn)題的改進(jìn)蟻群算法[J]. 控制理論與應(yīng)用, 2018, 35(9): 1347-1356.

[18] 殷亞, 張惠珍. 求解帶硬時(shí)間窗的多目標(biāo)車輛路徑問(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à)的逆向物流車輛路徑優(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)車輛路徑問(wèn)題的粒子群優(yōu)化算法研究[J]. 西安交通大學(xué)學(xué)報(bào), 2016, 50(9): 97-104.

[29] 羅梓瑄, 楊杰慶, 劉學(xué)文. 基于NSGA-Ⅱ的考慮客戶滿意度的多目標(biāo)車輛路徑問(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-)，女，河南開封人，碩士生。

責(zé)任編輯：孫 林