模糊需求車輛路徑問題及其優化算法研究

李子豪

摘要：在實際物流配送問題中，客戶需求量可能在制定物流配送路徑計劃問題時無法被準確獲取，隨著配送工作的進行，才能逐步獲取客戶的實際需求量，在需求未明的預優化階段建立初始路徑規劃模型，在獲知實際需求的實時調整階段，制定調整策略進行調整。通過對當前模糊需求車輛路徑問題相關文獻的研究，文章不僅對常見的模糊需求車輛路徑問題模型進行了系統的歸納，還對現有的尋優算法進行總結歸納，指出不足，拓展今后可能的研究方向。

Abstract： In the actual logistics distribution problem， the customer demand may not be accurately obtained when formulating the logistics distribution path planning problem. With the progress of the distribution work， the actual customer demand can be gradually acquired. The initial path planning model is established in the pre-optimization stage with unknown demand， in the real-time adjustment stage when the actual demand is known， an adjustment strategy is formulated for adjustment. Based on the current literature on fuzzy demand vehicle routing problems， this article not only systematically summarizes common fuzzy demand vehicle routing problems， but also summarizes existing optimization algorithms， points out deficiencies， and expands possible future research direction.

關鍵詞：車輛路徑;模糊需求;模糊可信性;啟發式算法

Key words： vehicle path;fuzzy demand;fuzzy credibility;heuristic algorithm

中圖分類號：U116.2 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼：A ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文章編號：1006-4311（2020）06-0138-03

0 ?引言

作為物流配送的重要組成部分，車輛路徑問題是物流運輸決策的核心，能否實現物流現化關鍵因素也取決于車輛的路徑問題。在滿足約束條件的情況下，合理的運輸路徑能夠幫助企業取得更高的經濟效益，對于實現資源、環境和價值觀的內在統一也有所幫助，對整個物流行業的飛速發展以及經濟的可持續發展也起一定的推動作用。模糊需求車輛路徑問題（VRPFD）考慮實際配送過程中客戶需求存在模糊性這一情況，使研究更貼近實際。

通常采用兩階段法求解VRPFD，當客戶發出需求指令時，由于需求未明，首先應根據當前信息制定預優化路徑，在此基礎上隨著配送活動的進行，確定客戶的需求量后進行實時調整使得其配送活動順利進行。已有文獻研究從兩方面進行：一是預優化階段模型的構建，Teodorovic[1]等運用模糊推理求解;Luci和Teodorovic [2]提出運用模糊集合進行求解;Liu[3]運用模糊可信性理論進行求解。二是實時調整策略的選擇，多數文獻均采用文獻[1]中的調整策略，即一種基于服務失敗點返回配送中心的策略，當一輛車計劃服務第p個客戶后，其剩余車載量為DP，當DP<0時，標記p點為配送失敗的點，車輛服務完第p個客戶之后返回原配送中心補貨，再回到p點繼續服務緊接著再服務原路徑剩余的客戶點;由三角形三邊定理可知，在失敗點的前一個客戶點返回配送中心會比在失敗點返回路徑更短，Yang[4]在此基礎上做了改進，當DP<下一客戶需求期望值時，車輛則返回配送中心進行補貨，但此策略在降低配送失敗概率的同時，卻使得出現不恰當返回次數的可能性大大增加，產生不必要的成本;然而以上種種調整策略均要求車輛返回配送中心，裝貨（或者卸貨），然后返回該客戶點。這通常只適用于不考慮配送時效的車輛路徑問題，然而實際配送活動中往往不能忽略客戶的配送時間要求，針對單條配送線路服務客戶點較多或客戶點偏遠的情況，若在該時間點重回車庫再駛回客戶點，必將沖破時間窗的約束，從而導致客戶滿意度及服務質量下降。因此帶時間窗的模糊需求車輛路徑問題不僅需要考慮車輛的行駛距離，同時也要兼顧車輛配送滿足對客戶服務時間的要求。

1 ?模糊需求車輛路徑問題描述與一般模型

2 ?VRPFD的求解算法分析

VRPFD問題屬于復雜的NP難問題，計算難度較高，通常使用優化算法進行求解。然而由于精確算法本身的局限性使其對求解數量規模較大的問題計算難度呈指數型提升，目前專家學者主要研究如何構造優質的啟發式算法來提升求解效率和準確性。求解VRPFD問題的主要啟發式算法如下：

①掃描算法（Sweep Algorithm）。掃描算法本質上是通過建立極坐標系，根據客戶點與配送中心的位置關系，將鄰近的客戶點歸并到一個子路徑中去。首先在極坐標系下對客戶點位置進行轉換，以角度最小的兩個客戶首先建組，之后沿同一方向轉動，將客戶點逐步進行添組，當滿足車輛載重量約束時，則該路線完成。重復此操作直至所有客戶都被分到某個組為止。各個組中的客戶點可看作獨立的TSP問題，進行求解，最后進行線路優化。Teodorovic和Pavkovic[1]最早研究了考慮模糊需求這類車輛路徑問題，以決策者風險偏好為基礎建立模糊評判規則，用Sweep算法對路徑進行優化。

②遺傳算法（Genetic Algorithm，GA）。遺傳算法的基本原理是模擬生物學中的遺傳機制，針對問題具體情況對隨機產生的種群中個體進行編碼，設計合適的適應度函數，經過復制、交叉、變異等操作對種群進行不斷優化，最后通過反復的迭代計算適應度值直至滿足終止條件得到最優結果。王君等[5]提出了基于模糊需求車輛問題的動態管理策略，并通過在非支配排序混合遺傳算法中運用模糊模擬的方法來進行模型的求解。針對帶模糊需求與模糊時間窗的車輛路徑問題，范厚明等[6]構建基于可信性測度理論的多目標模糊機會約束模型。為提高種群的多樣性，改進了交叉算子，在引入局部優化算法及擂臺法則的基礎上，設計了適合求解多目標車輛路徑問題的混合遺傳算法。

③蟻群算法（Ant Colony Optimization ?ACO）。蟻群算法是通過模仿自然界中蟻群覓食行為發展而來，是一種通過正反饋與分布式協作來尋找最優路徑的隨機優化仿生算法。劉金亮[7]在模糊可信性理論的基礎上為解決單配送中心、單一車輛情況下的模糊需求車輛路徑問題建立了模糊機會約束規劃模型，并提出了一種混合蟻群算法求解此類問題。

④禁忌搜索算法（Tabu Search TS）。禁忌搜索是在搜索過程中構造一個短期記憶表，即為禁忌表，表中存放剛剛搜索過的結果。在一定次數范圍r內，禁忌表中所存放的結果不能重復，r次之后，禁忌解除。禁忌表始終保持r個移動。當滿足停止規則或迭代內所搜索到最好結果無法改進也無法離開時，搜索活動停止。李陽等[8]針對客戶需求量模糊特點，提出分為兩階段法處理該問題，并設計了兩階段變鄰域禁忌搜索算法（VNTS），第一階段基于可信性理論構建模糊機會約束模型設計預處理方案，第二階段通過重調度策略針對客戶點實際需求調整預優化方案。

⑤粒子群算法（Particle Swarm Optimization PSO）。粒子群算法的提出源于研究者發現鳥群在飛行過程中其整體總保持著動態一致性，通過模擬生物群體這一特性，粒子群算法應運而生，屬于經典的群智能算法，不同于遺傳算法，粒子群算法沒有交叉、變異算子，以及復雜多樣的編碼方式，他是通過個體位置和速度信息的不斷更新，通過個體之間的相互聯系和影響在解空間中不斷進行搜索，最終求得全局最優解。Peng和Qian[9]結合模糊模擬運用PSO算法模糊需求車輛問題進行求解。

3 ?總結與展望

模糊需求車量路徑優化問題由于各研究學者所設目標函數及約束條件不同使得問題模型與相應求解算法千差萬別，各有優勢與不足。本文總結了近年來相關學者對模糊需求路徑優化的研究和求解算法，總結出當前研究有待于改進的問題和今后可能的研究方向：①現有的研究多是考慮路徑最短或成本最小，研究目標太過理想化，而在實際應用中駕駛員可能因為諸多原因耽誤行程，駕駛員工作時間，路上交通狀況都應當考慮在內，更貼合實際。②目前模糊需求車輛路徑優化問題多為單配送中心配送，配送模式較為單一，局限性較大，今后的研究可以考慮在多配送中心聯合配送模式下進行，更好的解決企業的配送優化，使得成本進一步降低。③現有的智能優化算法雖然運行較為方便，搜索能力強，但很多算法求解存在不穩定的問題，容易陷入局部最優，或收斂時間較長等問題。應考慮對算法進行不斷改進和創新，提高算法的穩定性和求解效率。

參考文獻：

[1]TEODOROVIC D，PAVKOVICG.The Fuzzy Set Theory Approach to the Vehicle Routing Problem when Demand at Nodes Is Uncertain [J].Fuzzy Sets and Systems，1996，82 （3） ：307-317.

[2]LUCI P， TEODOROVIC D. Vehicle routing problem with uncertain demand at nodes： The bee system and fuzzy logic approach[C]. Fuzzy Sets in Optimization，2003：67-82.

[3]LIU B.Uncertain theory：an introduce to its axiomatic foundations[M].Berlin：Springer， 2004.

[4]YANG W，MATHUR K，BALLOU R H.Stochastic vehicle routing problem with restocking[J].Transportation Science，2000，34（1）：99-112.

[5]王君，李波.基于多目標優化的模糊需求VRPTW動態管理[J].管理學報，2013，10（02）：238-243，279.

[6]范厚明，吳嘉鑫，耿靜，李陽.模糊需求與時間窗的車輛路徑問題及混合遺傳算法求解[J/OL].系統管理學報，2020（01）：107-118.

[7]劉金亮.求解模糊需求條件下車輛路徑問題的混合螞蟻算法[A].中國運籌學會智能計算分會.第三屆中國智能計算大會論文集[C].中國運籌學會智能計算分會：清華大學數學科學系，2009：4.

[8]李陽，范厚明，張曉楠，楊翔.求解模糊需求車輛路徑問題的兩階段變鄰域禁忌搜索算法[J].系統工程理論與實踐，2018，38（02）：522-531.

[9]PENG Y，QIAN Y-M. A particle swarm optimization to vehicle routing problem with fuzzy demands [J]. Journal of Convergence Information Technology，2010，5（Compendex）： 11.