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

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

一、物流路徑問題概述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

四、SFC方法的適用性

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

綜合上文分析以及其他研究可以發(fā)現(xiàn)，每一種算法單獨(dú)工作都會(huì)存在一些比較大的缺陷，而且隨著社會(huì)的發(fā)展、問題規(guī)模不斷擴(kuò)大化、結(jié)構(gòu)不斷復(fù)雜化，單一的算法很難解決現(xiàn)實(shí)中復(fù)雜的問題，需要將幾類算法融合貫通，揚(yáng)長避短，構(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)容請(qǐng)以PDF格式閱讀原文。