物流車輛路徑優(yōu)化問題研究綜述

摘" 要：物流系統(tǒng)優(yōu)化中的關(guān)鍵內(nèi)容之一是車輛路徑問題（Vehicle Routing Problem，VRP），它也是現(xiàn)代物流管理研究中的重要內(nèi)容。首先，總結(jié)了常見的VRP問題的分類和基本的數(shù)學(xué)模型及其算法；其次，闡述了求解VRP問題常用的啟發(fā)式算法及相應(yīng)的研究現(xiàn)狀；最后分析了當前物流車輛路徑優(yōu)化研究中所面臨的一些問題，并對未來的研究方向進行了展望。

" 關(guān)鍵詞：車輛路徑問題；開放式車輛路徑；啟發(fā)式算法；路徑優(yōu)化

中圖分類號：U116.2" " 文獻標志碼：A" " DOI：10.13714/j.cnki.1002-3100.2024.21.021

Abstract： One of the key contents of logistics system optimization is Vehicle Routing Problem（VRP）， which is also an important part of modern logistics management research. Firstly， the classification of common VRP problems and their basic mathematical models and algorithms are summarized. Secondly， the heuristic algorithms commonly used to solve VRP problems and the corresponding research status is described. Finally， some problems in the current research of logistics vehicle routing optimization are analyzed， and the future research direction is prospected.

Key words： vehicle routing problem; open vehicle path; heuristic algorithm; path optimization

0" 引" 言

" 車輛路徑優(yōu)化就是在滿足某種約束條件（如時間、交通、車輛能力等）下，對一系列的發(fā)送、接收和配送節(jié)點以及客戶的出行路線進行合理規(guī)劃，在滿足顧客需要的情況下，實現(xiàn)最少的配送車輛，最短的配送時間，最低的配送費用，最短的配送距離。車輛路徑優(yōu)化問題是物流管理與運輸組織優(yōu)化中重要的研究問題之一。由于僅考慮運輸成本最小容易導(dǎo)致物流資源浪費等一系列問題，考慮車輛利用率的物流配送路徑優(yōu)化研究逐漸獲得學(xué)者們的關(guān)注。本文通過對車輛路徑優(yōu)化的研究從多車型、多車場、帶時間窗口、開放式VRP四個方面，對已有的研究成果進行總結(jié)，列舉了與之相關(guān)的部分算法，并總結(jié)了未來的發(fā)展方向，以便為研究者提供參考，把握研究重點。

1" 車輛路徑優(yōu)化問題

" 車輛路徑優(yōu)化是交通領(lǐng)域中的一個重要問題，1959年Dantzig et al.[1]（“Management Science”）發(fā)表了“The Truck Dispatching Problem”（Truck Dispatching Problem），首次研究了美國亞特蘭大煉油廠的成品油分銷路線優(yōu)化問題。在之后的幾十年里，車輛路徑優(yōu)化問題得到了進一步的拓展和發(fā)展。經(jīng)典的VRP問題如圖1所示，由一個配送中心完成對多個用戶的配送，通過合理的規(guī)劃配送路徑，使運輸成本最低。

自車輛路徑優(yōu)化問題被提出后，Linus，Bodin，Golden，Assad，Desrochers等許多學(xué)者分別從不同的角度和標準對該問題進行了歸類[2]。根據(jù)載體的載荷狀況，將載體分為非滿載與滿載兩種類型；根據(jù)操作特征，可分為“僅裝”、“僅卸”和“混卸”三種；根據(jù)目標數(shù)的多少，可將該問題分為兩種類型：一種是單目標規(guī)劃問題，另一種是多目標規(guī)劃；按照交通工具的同構(gòu)關(guān)系，將其分為同種車型和異質(zhì)車型兩類；根據(jù)客戶接收或發(fā)貨時間的窗口約束，將問題分為沒有時間窗口和有時間窗口的問題；根據(jù)客戶需求的可分性，將其分為兩類：一類是可拆型，另一類是不可分型；在此基礎(chǔ)上，將客戶的需求分為有優(yōu)先限制的車輛路線問題和沒有優(yōu)先限制的車輛路線問題；根據(jù)配送完成后，車輛需不需要返回起始點的情況，將其分為開放型和封閉型兩類。此外，將上述兩個或幾個限制條件結(jié)合起來，構(gòu)成更復(fù)雜的車輛路徑問題。

1.1" 多車型車輛路徑問題。多車型車輛路徑問題可以看作是車輛路徑問題的推廣，車輛路徑問題按其類型不同可劃分為單一車型問題（Vehicle Routing Problem， VRP）與多車型問題（Heterogeneous Vehicle Routing Problem， HVRP）。單車型優(yōu)化問題假設(shè)各個變量，如最大載重率、最大行程、固定費用及可變費用等均相同；然而，多車型問題則需要面對各種不同車型的最大載重率、最大行程、固定費用和可變費用等不同特性。

" 多車型車輛路徑問題是在1984年由Golden等人首先提出，隨后國內(nèi)外學(xué)者對其進行了大量的研究。例如：Gendreau et al.[3]采用禁忌搜索方法，對車輛數(shù)為無窮時的車輛路徑優(yōu)化問題進行了研究。為了解決多車型車輛路線問題，Taillard et al.[4]提出了一種啟發(fā)式算法。葉志堅等[5]對國外五類多車型優(yōu)化問題進行了歸納，并將禁忌搜索與大旅程法有機地結(jié)合起來，形成了一種新型的多車型優(yōu)化方法。

1.2" 多車場車輛路徑問題。多車場車輛路徑問題（Multi-depot Vehicle Routing Problem， MDVRP）涉及多個停車場為多個用戶提供服務(wù)，需要合理安排各個停車場的車輛及行車路線，以最小化總體運輸費用，同時滿足不同用戶的需要。多車場的車輛路徑問題，實質(zhì)上不只是一條路徑問題，而是對每一個場站的選址與用戶指派問題。

" 目前，針對多個停車場的車輛路徑問題，多數(shù)研究集中在優(yōu)化算法上，從經(jīng)典的啟發(fā)式算法向現(xiàn)代啟發(fā)式算法拓展，并將多個停車場的實際運營情況進行拓展。Klots et al.[6]將線性規(guī)劃和啟發(fā)式算法有機地結(jié)合起來，對MDVRP問題進行了研究；Polacek et al.[7]提出了一種基于變鄰域的MDVRPTW方法，并對其進行了改進。鄒彤等[8]利用遺傳算法對MDVRP進行了優(yōu)化。此外，陳美軍等[9]將時間窗、道路狀況、客戶優(yōu)先權(quán)等因素引入到MDVRP模型中，從而提升了優(yōu)化問題的求解效率。

1.3" 帶時間窗的車輛路徑問題。帶時間窗口的車輛路徑問題（Vehicle Routing Problems with Time Windows， VRPTW）對基本車輛路徑問題進行擴展的一種形式，它引入了服務(wù)時間窗口約束，時間窗口是由客戶要求的最早可服務(wù)時間和最晚可服務(wù)時間來定義的。這里的時間窗口指的是客戶的角度，即客戶需求時間窗口。所以，研究帶時間約束的車輛路徑優(yōu)化問題，既要對車輛的空間路徑進行規(guī)劃，又要對時間進行合理的調(diào)度。

" 對于VRPTW難題，求解算法主要分為精確算法和啟發(fā)式算法。其中，精確算法隨著應(yīng)用范圍的擴大已無法滿足實時動態(tài)調(diào)度和大規(guī)模問題的需要，因此尋找近似算法已成為人們密切關(guān)注的熱點問題。如禁忌搜索算法、模擬退火算法、遺傳算法、混合啟發(fā)式算法、捕食搜索算法等。但由于現(xiàn)實生活中的許多問題都可歸結(jié)為VRPTW，如普通物流、特快物流、加急特快物流問題等，因此加快客戶需求的反應(yīng)速度，提高配送效率，降低運營成本是物流優(yōu)化與控制的核心問題。

1.4" 開放式車輛路徑問題。開放式車輛路徑問題（Open Multi-depot Vehicle Routing Problem， OVRP）其最大的不同之處在于，在完成了收貨作業(yè)后，不需要再回到原來的起點，若需要返回原出發(fā)點，則只需沿原路線返回即可。這樣車輛路徑便由封閉式轉(zhuǎn)向開放型，如圖2所示。

OVRP通常被定義為：存在一個停車場，一組具有確定需求的顧客送貨點或取貨點，以及一組確定了貨物容量和運行費用的車輛，并且已知停車場與顧客之間、顧客與顧客之間的車輛行駛費用，從而確定一套使以下目標均為最小的車輛路徑：（1）滿足全部顧客需求的車輛數(shù)量；（2）車輛行駛總成本。

" 并滿足三個主要的約束條件：（1）每一條線路都以停車場為起點，以某個顧客點結(jié)束，或者相反；（2）每個客戶點只能由一輛車輛訪問，并且僅能被服務(wù)一次，滿足其需求量；（3）每條線路上所有客戶點的需求總和都不能超過該線路的總有效載重量。

" OVRP是在1981年由Schrage[10]將車輛路徑問題歸類時所提出來，近年來學(xué)術(shù)界對其進行了更深入的理論研究。Sariklis et al.[11]在2020年5月首次就這一問題展開了深入的理論研究，并在此基礎(chǔ)上，利用經(jīng)典的啟發(fā)式思想，設(shè)計了相應(yīng)的求解算法。Brandao[12]隨后也開展了OVRP的研究，并嘗試將禁忌搜索（Tucu Search）作為一種新的啟發(fā)式算法來構(gòu)建問題的求解方案，并獲得了良好的結(jié)果。在此方面，國內(nèi)尚無文獻報道。

2" 車輛路徑優(yōu)化模型及算法

" 車輛調(diào)度問題實質(zhì)上就是車輛路徑問題，它是指對運輸車輛的種類、數(shù)量和路線進行適當?shù)倪x擇，在滿足顧客的送貨時間、具體需求等條件下，對里程、工作時間、運輸費用等進行全面的分析計算，以使總的運輸費用最小化。車輛調(diào)度問題是一種復(fù)雜的組合優(yōu)化問題，其數(shù)學(xué)模型具有多個方面的特點。通常情況下，車輛調(diào)度問題可以通過整數(shù)規(guī)劃、圖論等方法進行建模，這些方法之間存在內(nèi)在的聯(lián)系。然而，從建模的角度來看，大多數(shù)模型都是多個模型的變形和合并。

" 自從車輛路徑問題被提出以來，已經(jīng)有很多研究人員提出了各種不同的數(shù)學(xué)模型和求解算法。根據(jù)這些方法，車輛路徑問題的求解方法基本可以分為精確算法、啟發(fā)式算法和亞啟發(fā)式算法三類。具體的分類情況如表1所示。

2.1" 遺傳算法（Genetic Algorithm，GA）。遺傳算法（GA）是一種模擬生物演化過程的優(yōu)化算法，它通過選擇、交叉、變異等方式生成代表新解集合的群體，并在此基礎(chǔ)上進行反復(fù)迭代，最終達到最優(yōu)解的目的。但它也存在著一些不足，如搜索速度較慢，容易早熟，以及整體可行解的品質(zhì)較差等。

" 利用遺傳算法對車輛路徑問題進行研究，主要有以下幾個方面：蔣波[14]提出了一種基于遺傳算法的車輛路徑優(yōu)化方法，該方法的目標函數(shù)是最小化分銷費用，并在此基礎(chǔ)上建立了帶懲罰函數(shù)的帶時間約束的車輛路徑優(yōu)化模型；趙辰[15]利用遺傳算法對物流中心與物流中心間的路線進行了優(yōu)化，并對物流路線進行了優(yōu)化；張群等[16]建立了一個多車型的物流中心-多車型車輛調(diào)度模型，并利用該模型提出了一種基于模糊遺傳算法的多個配送中心-多車型車輛路徑優(yōu)化問題。

2.2" 模擬退火算法（Simulated Annealing，SA）。相似于禁忌搜索，SA也是一種局部尋優(yōu)算法，但是模擬了金屬材料的熱處理過程，把溫度函數(shù)轉(zhuǎn)換成極值點，采用基于概率的方法進行求解。郎茂祥[17]研究了裝卸貨物的混合車輛路徑路線問題，建立了模擬退火算法，并對其進行了求解；穆東等[18]提出了一種并行的模擬退火方法，并將該方法應(yīng)用于其他車輛路線問題和組合最優(yōu)問題；魏江寧等[19]運用模擬退火法，研究了由單一分銷中心向多個客戶之間的分銷問題；Mirabi et al.[20]將仿真退火的思路引入到多配送中心物流路線優(yōu)化中，并將其應(yīng)用于多配送中心的調(diào)度問題。

2.3" 蟻群算法（Ant Colony Optimization，ACO）。人類通過對螞蟻的覓食方法研究，從而提出了蟻群算法。蟻群算法的基本思想是：螞蟻的記憶，信息素的相互作用，以及螞蟻的分群行為。個體螞蟻沒有智慧，但是群體整體卻顯示出高效的智慧。在此基礎(chǔ)上，提出了一種基于群集智能的尋優(yōu)策略，使得蟻群算法能夠更好地逼近最優(yōu)解。

" 馬建華等[21]提出了一種新的基于遺傳算法的車輛路徑優(yōu)化算法，并對其進行了改進。辛穎[22]將MMAS螞蟻算法轉(zhuǎn)化為三個策略，實驗結(jié)果顯示，改進后的算法不僅效率高，而且穩(wěn)定性好；針對蟻群算法的缺點，陳迎欣[23]對其進行了改進，引入了“熱點”概念，對其進行改進，提高了算法的效率；段征宇等[24]提出一種新的螞蟻算法，即用最小代價最接近方法產(chǎn)生螞蟻算法，并結(jié)合局部搜索運算，對TDVRP問題進行了改進。

" 總之，對于上述三種算法，遺傳算法能夠在大規(guī)模搜索空間中尋找全局最優(yōu)解，但一般其計算復(fù)雜度較高，收斂速度慢；模擬退火算法能夠在大規(guī)模搜索空間中快速收斂，但其對參數(shù)要求苛刻，處理問題時需要合適的參數(shù)選擇；蟻群算法對于組合優(yōu)化和離散優(yōu)化問題的解決具有明顯優(yōu)勢。三者之間各有優(yōu)劣，實際應(yīng)用中需要根據(jù)具體問題選擇恰當?shù)乃惴ㄟM行處理。

3" 車輛路徑問題目前存在的問題

" 車輛路徑問題是一類典型的組合規(guī)劃問題，雖然目前已經(jīng)有許多針對車輛路徑問題的算法與研究，但仍然存在一些問題：（1）研究對象過于理想化。現(xiàn)有的VRP研究主要集中于費用極小、路徑最短等方面，且大多為單目標優(yōu)化，然而，在現(xiàn)實生活中，由于各種因素導(dǎo)致的出行延遲、客戶需求差異等，導(dǎo)致客戶滿意度與企業(yè)成本最小化目標的矛盾；（2）目前，單約束VRP問題的研究已相對成熟，但是它的適用范圍也有很大的局限性，使用時受到了很多限制；（3）啟發(fā)式算法存在具有局部尋優(yōu)能力差，收斂時間長，容易陷入局部最優(yōu)等缺點。

4" 車輛路徑問題未來研究趨勢

" 車輛路徑優(yōu)化是一類復(fù)雜的路徑規(guī)劃問題，涉及到能力約束、時間窗、取貨、不同車型、以及信息動態(tài)性等多個因素。由于受到約束、附加條件以及實際情況等因素的影響，產(chǎn)生了新的交通需求，針對這些新的交通需求，建議未來的研究與發(fā)展可放在以下三個方面：（1）針對研究對象過于理想的問題，未來研究可將成本、里程、司機休息時間、客戶滿意度等多目標有機結(jié)合，采用線性權(quán)重法對其進行集成優(yōu)化；（2）單獨的群體智能算法在解決車輛路徑問題時仍然存在諸多缺陷，因此，將兩種或兩種以上的群體智能算法相結(jié)合，可以實現(xiàn)優(yōu)勢互補，是未來需要進一步研究的問題。在此基礎(chǔ)上，進一步研究如何利用智能優(yōu)化算法解決車輛路徑問題；（3）開放式車輛路徑問題，作為一種特殊的車輛路徑問題，屬于交通運籌學(xué)中的新興研究方向，目前尚處于起步階段。但是，不管是在理論上，還是在實踐上，都需要進一步的研究。

5" 總" 結(jié)

" 隨著我國經(jīng)濟和社會的迅速發(fā)展，人們對于服務(wù)品質(zhì)的需求也在不斷提高。車輛路徑問題是物流系統(tǒng)的重要一環(huán)。本文介紹了車輛路徑問題的基礎(chǔ)理論，對常見的車輛路徑問題進行了分類，建立了相應(yīng)的數(shù)學(xué)模型，并對其算法進行了詳細的介紹?，F(xiàn)有的求解方法雖有多種，但大都是針對特定需求而提出，適用面有限，能否在保證精度的前提下，設(shè)計一種既能減少初值又能快速收斂的新方法，可能是今后研究的一個重要方向。

參考文獻：

[1] DANTZIG G， RAMSER J. The truck dispatching problem[J]. Management Science， 1959（6）：80-91.

[2] 李軍，郭耀煌. 物流配送車輛優(yōu)化調(diào)度理論與方法[M]. 北京：中國物資出版社，2001.

[3]" GENDREAU M， LAPORTE G， MUSARAGANYI C， et al. A tabu search heuristic for the heterogenous fleet vehicle routing problem[J]. Computers amp; Operations Research， 1999，26（12）：1153-1173.

[4]" TAILLARD E D. A heuristic column generation method for the heterogeneous fleet VRP[R]. Montreal， Quebec， Canada， University of Montreal， 1999.

[5] 葉志堅，葉懷珍，周道平，等. 多車型車輛路徑問題的算法[J]. 公路交通科技，2005（5）：147-151.

[6]" KLOTS B， GAL S， HARPAZ A. Multi-depot and multi-product delivery optimization problem with time and service constraints[R]. Haifa， Israel， IBM Haifa Research Lab， 1992.

[7]" POLACEK M， HARTL R F， DOERNER K. A variable neighborhood search for the multi depot vehicle routing problem with time windows[J]. Journal of Heuristics， 2004，10（6）：613-627.

[8] 鄒彤，李寧，孫德寶，等. 多車場車輛路徑問題的遺傳算法[J]. 計算機工程與應(yīng)用，2004（21）：82-83.

[9] 陳美軍，張志勝，史金飛. MDVRPMC問題的智能多態(tài)蟻群算法研究[D]. 南京：東南大學(xué)，2007.

[10]" SCHRAGE L. Formulation and structure of more complex/realistic routing and scheduling problems[J]. Networks， 1981，11（2）：229-232.

[11]" SARIKLIS， S POWELL. A heuristic method for the open vehicle routin gproblem[J]. Journal of the Operational Research Society， 2000，51：564-573.

[12]" BRANDAO. A tabu search algorithm for the open routing problem[J]. European Journal of Operational Research， 2020，284（2）：559-571.

[13] 唐連生，梁劍. 突發(fā)事件下的車輛路徑問題研究綜述[J]. 鐵道運輸與經(jīng)濟，2008（12）：56-60.

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

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

[16] 張群，顏瑞. 基于改進遺傳算法的混合車輛路徑問題[J]. 中國管理科學(xué)，2012，20（2）：121-128.

[17] 郎茂祥. 裝卸混合車輛路徑問題的模擬退火算法研究[J]. 系統(tǒng)工程學(xué)報，2005，20（5）：485-491.

[18] 穆東，王超，王勝春，等. 基于并行模擬退火算法求解時間依懶型車輛路徑問題[J]. 計算機集成制造系統(tǒng)，2015，21（6）：1626.

[19] 魏江寧，夏唐斌. 基于混合模擬退火算法的多階段庫存路徑問題研究[J]. 工業(yè)工程與管理，2015，20（3）：1-8.

[20]" M MIRABI， SMTF GHOMI， F JOLAI. Efficent stochastic hybrid heuristics for the multi-depot vehicle routing problem[J].Roboticsand Computer-Integrated Manufacturing， 2010，26（6）：564-569.

[21] 馬建華，房勇，袁杰. 多車場多車型最快完成車輛路徑問題的變異蟻群算法[J]. 系統(tǒng)工程理論與實踐，2011，31（8）：1508-1516.

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

[23] 陳迎欣. 基于改進蟻群算法的車輛路徑優(yōu)化問題研究[J]. 計算機應(yīng)用研究，2012，29（6）：2031-2034.

[24] 段征宇，楊東援，王上. 時間依賴型車輛路徑問題的一種改進蟻群算法[J]. 控制理論與應(yīng)用，2010，27（11）：1557-1563.

收稿日期：2023-11-29

作者簡介：張真卓（1999—），男，山東菏澤人，臨沂大學(xué)自動化與電氣工程學(xué)院碩士研究生，研究方向：供應(yīng)鏈管理；李曉東（1974—），本文通信作者，男，山東臨沂人，臨沂大學(xué)自動化與電氣工程學(xué)院，教授，博士，研究方向：物流系統(tǒng)規(guī)劃設(shè)計與優(yōu)化、物流信息化、供應(yīng)鏈管理。

引文格式：張真卓，孫浩瑜，盧加興，等. 物流車輛路徑優(yōu)化問題研究綜述[J]. 物流科技，2024，47（21）：89-92.