希爾平斯基曲線在物流路線問題中的應用

[摘要] 物流配送車輛路徑問題(VRP)屬于NP-Hard問題，對這類問題如何求解學術界提出了多種算法，但往往復雜性較高，易用性較差。以基于西爾平斯基曲線的空間填充方法來求解此類問題，具有快速、靈活、運算量少的特點。

[關鍵詞] 空間填充曲線 SFC Sierpinski Curve VRP

一、物流路徑問題概述

車輛路徑問題（Vehicle Routing Problem，VRP）最早是由Dantzig和Ramser于1959年首次提出的。在物流中的解釋是對一系列客戶的需求點設計適當的路線，使車輛有序地通過它們，在滿足一定的約束條件下（如貨物需求量、發送量、交發貨時間、車輛載重量限制、行駛里程限制、時間限制等等），達到一定的優化目標（如里程最短、費用最少、時間最短，車隊規模最少、車輛利用率高）。

VPR是物流運輸過程中的關鍵環節，將直接影響對客戶需求的響應速度、客戶對物流環節的滿意度以及服務商的配送成本。

由于VRP包含了銷售員問題 (Traveling Salesman Problem，TSP)，而 TSP本身就是NP-Hard問題，所以 VRP也是一個NP組合優化難題。VRP問題和TSP問題的區別在于：客戶群體的數量大，有多輛交通工具的訪問順序進行求解。相對于TSP問題，VRP問題更復雜，求解更困難，但也更接近實際情況。國內外許多學者對VRP問題的求解方法進行了大量研究，總體上分精確算法和啟發式算法兩類。精確算法可分為分支定界法、動態規劃、整數規劃、非線性規劃。啟發式算法有：最近鄰點法（Nearest Neighbor）、最近插入法（Nearest Insertion）、節約里程法（Saving Algorithm）、掃描算法（Sweep Algorithm）。

這些解法雖然可以給出較為滿意的答案，但也存在計算過程復雜、參數可獲得性準確請較差、限制條件較多、時間花費偏長、靈活性差等缺點，尤其不利于中小企業解決物流中的實際問題。那么是否存在較為簡便直觀的方法，更快速的求解出優化的訪問順序呢？不妨換一種思路進行解答。

二、毛線團的啟示

對于古典的歐幾里德式的幾何，重視的是圖形的長度、寬度、厚度等實際可測的幾種值。于是我們可以知道：我們生活的空間是三維，平面是二維，直線是一維，一點的維度則為零。

20世紀70年代的數學家畢諾特·曼德布洛特-加龍省(Benoit Mandelbrot)提出一個問題：毛線團的維度是多少？他的答案是：這要看你的觀點而異。

遠距離來看，繩團凝聚成點，維度為零；再近一點，看出來毛線團占據球形的空間，維度擴展成三；再走近一些，看出毛線團是由一根根毛線所構成，他的維度為一，即使它已糾結充斥了三維空間。那么，再看下去呢？當我們看到線繩為圓柱、構成圓柱的一條條纖維……曼德布洛特-加龍省這樣闡釋：“數據結果視觀測者與其對象而改變。”

如此一來，VRP問題可以有一個用圖論語言的描述方式：平面上有n個點，如何用最短的線將全部的點連起來，即“一筆畫”問題（Drawing by one line）。對于“一筆畫”問題可以用“空間填充曲線”(Space Filling Curve，SFC)方法進行求解。一條線只是一維的，彎折扭曲仍是一維的，但是在這個平面上，沒有一點是SFC畫不到的。

三、希爾平斯基曲線在物流路線問題中的應用

1.希爾平斯基曲線與SFC方法簡介

SFC法是由Bartholdi和Platzman兩人提出的，以Peano(1890)、Hilbert(1891)、Sierpinski(1921)等人開發出來的空間填充曲線為基礎，根據配送地點在SFC上出現的順序決定配送次序的方法。Bartholdi和Platzman把分散在2維空間（X，Y）坐標上的配送地 投影到被SFC填充的1維曲線上，再尋找配送地在SFC上所出現的順序，把此順序作為配送的順序，再根據具體路況確定訪問路線。因為只需計算投影和順序排列，所以SFC計算速度非常快。美中不足的是解的質量不算太好，最差的時候巡回距離比最佳解長20％左右。

2.用希爾平斯基曲線填充VRP平面

希爾平斯基曲線（Sierpinski Curve）是空間填充曲線的一種，它通過自我復制和連接可以無限的擴展。很明顯希爾平斯基曲線是一個閉合的線路，而且有著優異的對稱性。

可以在上面任意取一點作為起點，當然這一點也就是終點。以沿曲線繞行一周的距離作為1，則在這個線路上的其他任何一點都對應一個0至1之間的數值，這個數值就是確定先后次序的依據，即數值小的點先訪問，而數值大的點排在后面訪問。

3.分割希爾平斯基曲線確定順序數值

用希爾平斯基曲線填充VRP所要經過的點以后，該如何確定各個點的訪問順序呢？例如求出圖中A、B點的順序。最簡單的方法就是分割法。

不妨假設左下角為起始點0%（也是終點100%），由于曲線的閉合性和對稱性，則對角點為50%，而且左上方半個區域的點總是優先于右下方的點，兩個頂點分別為25%和75%。

第一次從左下角向右上角分割后，可以知道A、B點的順序數值都在50%和100%之間；繼續將50%～100%區域分割為兩個相等的三角形，可進一步知道A、B點的順序數值在75%和100%之間；繼續分割剩下的區域，A、B點的順序數值在75%和87.5%之間；第四次分割后，A點的順序數值在75%和81.25%之間，B點的順序數值則在81.25%和87.5%之間；所以A點先于B點。

實際上由于所有的點會相互連接成一條封閉的線路，無論以何處作為起點，訪問線路都不會有什么變化，問題的關鍵在于求出點的次序。需要注意的是，要把倉庫（圖4中的Ｄ點）包括進去才能得到正確的路線。

4.訪問任務分配

簡單的TSP問題只假定了一臺交通工具，而VRP問題則考慮了一個公司協調多臺交通工具進行運輸作業的情況。在SFC方法中，安排n個交通工具的路線也很簡單，只要把訪問路線平分為1/n即可，訪問順序不變。假設一個物流公司有3輛運輸車，要完成60個客戶，則1號司機就負責送貨到線路圖上第１到20號客戶，2號司機負責送貨到第21到40號客戶，以此類推。當然，實際操作中也不必要如此精確。

SFC方法還具有很強的靈活性。如果增加新的訪問點，只需要在圖上確定它的順序數值，把它插入到已有的點的序列里面去，不再有業務的訪問點直接從序列里刪去即可；如果出動的車輛數目有變化，只需要簡單得重新劃分路線；由于只規定了訪問序列，具體的道路選擇可以由司機靈活掌握，如根據交管部門的臨時限制、車流高峰等情況變換道路。

值得注意的是，雖然每輛車分配到的客戶數目都差不多，但實際位置的遠近很可能不一樣，每輛車的路線長短可能差別較大，這就需要不均勻的分配送貨量。但如果客戶接近于均勻分布，采用希爾平斯基曲線來確定客戶點的次序，在此基礎上再在各車之間平均分配送貨量，每輛車行駛距離的差異就會比較小。

四、SFC方法的適用性

基于空間填充曲線的方法和各種精確算法、啟發算法相比具有快速、靈活、運算量少的特點，可以很好的解決確定訪問順序，規劃最短路線問題。但對于含有滿載約束、分批裝貨、回程裝載、時間窗約束的VRP的復雜情況無法給出解答。

綜合上文分析以及其他研究可以發現，每一種算法單獨工作都會存在一些比較大的缺陷，而且隨著社會的發展、問題規模不斷擴大化、結構不斷復雜化，單一的算法很難解決現實中復雜的問題，需要將幾類算法融合貫通，揚長避短，構造混合算法求解體系。

參考文獻:

[1]孫麗君胡祥培王征:車輛路徑規劃問題及其求解方法研究進展[J].當代中國出版社，2006

[2]蘇麗杰聶義勇:旅行商問題典型算法的綜合性能[J]．企業研究，2004，（11）

[3]John J.Bartholdi．A routing system based on space filling curves

[4]沈翔馮大為等:供應鏈的力量[M].電子工業出版社，2005

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。