希爾平斯基曲線在物流路線問題中的應(yīng)用

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

[關(guān)鍵詞] 空間填充曲線 SFC Sierpinski Curve VRP

一、物流路徑問題概述

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

VPR是物流運輸過程中的關(guān)鍵環(huán)節(jié)，將直接影響對客戶需求的響應(yīng)速度、客戶對物流環(huán)節(jié)的滿意度以及服務(wù)商的配送成本。

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

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

二、毛線團(tuán)的啟示

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

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

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

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

三、希爾平斯基曲線在物流路線問題中的應(yīng)用

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

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

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

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

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

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

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

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

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

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

4.訪問任務(wù)分配

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

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

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

四、SFC方法的適用性

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

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

參考文獻(xiàn):

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

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

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

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

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