物流車輛路徑優化問題研究綜述

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

" 關鍵詞：車輛路徑問題；開放式車輛路徑；啟發式算法；路徑優化

中圖分類號：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" 引" 言

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

1" 車輛路徑優化問題

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

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

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

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

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

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

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

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

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

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

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

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

2" 車輛路徑優化模型及算法

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

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

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

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

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

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

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

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

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

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

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

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

5" 總" 結

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

參考文獻：

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

[2] 李軍，郭耀煌. 物流配送車輛優化調度理論與方法[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]. 計算機工程與應用，2004（21）：82-83.

[9] 陳美軍，張志勝，史金飛. MDVRPMC問題的智能多態蟻群算法研究[D]. 南京：東南大學，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] 唐連生，梁劍. 突發事件下的車輛路徑問題研究綜述[J]. 鐵道運輸與經濟，2008（12）：56-60.

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

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

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

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

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

[19] 魏江寧，夏唐斌. 基于混合模擬退火算法的多階段庫存路徑問題研究[J]. 工業工程與管理，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]. 系統工程理論與實踐，2011，31（8）：1508-1516.

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

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

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

收稿日期：2023-11-29

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

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