孫壯志，鄢烈虎，要學瑋

北京煙草物流中心，北京市通州區(qū)九棵樹西路198號 101101

基于線路優(yōu)化算法的卷煙配送調(diào)度系統(tǒng)

孫壯志，鄢烈虎，要學瑋

北京煙草物流中心，北京市通州區(qū)九棵樹西路198號 101101

為研究線路優(yōu)化算法在卷煙配送中的應用，以北京卷煙配送市場為背景，結(jié)合配送條件的限制，采用中心聚類、禁忌搜索、局部搜索等多種專業(yè)算法，提出了一套適應性強、運算速度快、可實施性高的解決方案。同時，通過選擇性地取用原有固定線路的數(shù)據(jù)作為最終路順的參考，結(jié)合配送車型和配送員的工作負荷，強化了動態(tài)調(diào)度結(jié)果的可實施性。方案實施測試效果良好，月平均裝載率達90%以上。

線路優(yōu)化；中心聚類；禁忌搜索；局部搜索

隨著物流相關技術(shù)的蓬勃發(fā)展，物流行業(yè)正在經(jīng)歷一場深刻的變革。以先進的算法輔助實現(xiàn)物流配送線路優(yōu)化是新技術(shù)應用的一項重要措施。

優(yōu)化技術(shù)是一種以數(shù)學為基礎的，用于求解各種工程問題優(yōu)化解的應用技術(shù)。所謂優(yōu)化算法，就是一種搜索過程或規(guī)則，它是基于某種思想和機制，通過一定的途徑或規(guī)則來得到滿足用戶要求的問題的解[1]。聚類算法是一種數(shù)據(jù)簡化技術(shù)，把基于相似數(shù)據(jù)特征的變量和個案組合在一起[2]。禁忌搜索是彌補局部搜索先天弱點的一種改進算法，局部搜索算法的先天弱點在于會陷入局部最優(yōu)，所以設計好的跳離局部最優(yōu)的啟發(fā)策略是設計局部搜索算法的關鍵[3]。禁忌搜索算法基本思想相當簡單，它采用一種“記憶”裝置驅(qū)使算法去探索搜索空間的新的區(qū)域[4]。我們可以記住最近被檢查過的解，它們將成為下一個解的禁忌（被禁止）。貪婪法是一種對某些求最優(yōu)解問題的更簡單、更迅速的設計技術(shù)，其特點是一步一步地按策略進行，常以以前情況為基礎根據(jù)某個優(yōu)化測度作最優(yōu)選擇，而不是考慮各種可能的整體情況[5]。

論文以設計和開發(fā)一個以線路優(yōu)化算法為基礎的卷煙配送線路調(diào)度系統(tǒng)為目標，根據(jù)需求分析，進行線路優(yōu)化算法的選擇，最終期望完成一個線路調(diào)度系統(tǒng)，并對結(jié)果進行理論驗證。

1 系統(tǒng)需求分析

1.1 實際業(yè)務需求情況

每天從訪銷中心接收訪銷數(shù)據(jù)，包括訂單日期、零售戶信息、訂貨量。根據(jù)配送實際情況，需設計一套算法，根據(jù)北京市地理情況、配送車輛最大裝載量限制、考慮配送員熟悉度，在盡量短的時間內(nèi)對當日訂單進行配送線路優(yōu)化，為每位配送人員提供相對合理、科學的配送線路。同時要求計算結(jié)果線路可人工調(diào)整，并使月平均裝載率達到90%以上。

1.2 基礎數(shù)據(jù)需求

根據(jù)實際業(yè)務需求，調(diào)度系統(tǒng)需要以下6方面的基礎數(shù)據(jù)支撐：

1)城市道路基礎信息：北京市道路網(wǎng)絡圖，即GIS地圖；

2)零售戶信息：零售戶地理坐標點，并將其投影在北京市道路網(wǎng)絡圖上；訂貨量；送貨車型限制；

3)車輛基礎信息：車型、最大裝載量；

4)人員信息：司機以及配送員的基礎信息；他們在前一段時間的歷史工作負荷；

5)送貨區(qū)域信息：所屬區(qū)域組；是否進行融合；區(qū)域內(nèi)線路最大送貨時間；區(qū)域內(nèi)可用配送資源（指司機、配送員及車輛合成一個組合關系）；

6)原送貨線路信息：客戶原屬線路信息。

1.3 返回結(jié)果需求

根據(jù)業(yè)務需求，在計算結(jié)果時需要返回的信息有以下8類：每條線路的司機、配送員、送貨車輛、包含的客戶以及其送貨順序、預計里程、預計送貨時間、送貨量、裝載率。

2 系統(tǒng)設計

2.1 整體設計

動態(tài)線路調(diào)度包含客戶區(qū)域分配、區(qū)域識別、線路生成與區(qū)域間調(diào)整三個步驟。其中線路生成以及區(qū)域間調(diào)整被分成2條獨立的路徑，一條采用以中心聚類為核心的算法進行計算，另一條是采用線路串接的方式進行計算，如圖1所示。

圖1 整體設計思路Fig.1 Integrated design map

2.2 詳細設計

2.2.1 客戶區(qū)域分配

獲取營銷訂單后，根據(jù)系統(tǒng)內(nèi)劃定的區(qū)域，將訂單分拆到各個區(qū)域內(nèi)進行運算。

2.2.2 區(qū)域識別

線路優(yōu)化針對不同的客戶分布情況，采用不同的算法加以應對。

如果區(qū)塊內(nèi)的客戶基本上是按照訪銷周期訂貨的，都是捆綁得比較好的一整條的線路，那么采用配送人員比較認可、熟悉度較高的線路進行串接，將多條線路頭尾相接串聯(lián)到一起,切割拆分生成多個車次。

如果區(qū)塊內(nèi)的客戶是隨機訪問的，七零八落地分布在各個線路中，那么采用中心聚類的算法加以聚類分割，生成多條線路。

分類判定算法是分析整線路的客戶所占的比例。根據(jù)區(qū)塊內(nèi)已有的原線路，將客戶分配到各條原線路上去，生成多個客戶序列。如果序列內(nèi)客戶數(shù)最多的8個客戶序列的總客戶數(shù)占全部客戶數(shù)的80%以上，就說明該區(qū)域中被綁定在原有固定線路中的客戶占所有客戶的大多數(shù)。

2.2.3 線路生成與區(qū)域間調(diào)整

2.2.3.1 客戶群生成

在每個區(qū)塊中，再次根據(jù)區(qū)塊內(nèi)已有的原線路，將客戶分配到各條原線路上去（根據(jù)訂單情況不同，有可能出現(xiàn)大部分客戶都集中于某幾條線路，也有可能出現(xiàn)客戶分散于區(qū)塊內(nèi)的所有原線路）。分析各條原線路，倘若發(fā)現(xiàn)其客戶序列中，前后兩戶不是相對接近的，就進行分拆，最終形成若干個連續(xù)并互相靠近的客戶群。（有可能因為客戶分散的關系，大多數(shù)客戶組都只包含了單個客戶）。

2.2.3.2 線路裝填

根據(jù)前面區(qū)域分析的結(jié)果，用不同的算法（聚類分析或者線路串接），對生成的客戶群進行合并以及拆分，將彼此靠近的客戶群根據(jù)車輛的容量，以及最大送貨時間，合并為一條線路。歸并的同時，允許對那些“整個加進去太多，不加又太少”的客戶群進行分拆，以最大程度提高裝載率。根據(jù)當前客戶的情況選擇合適的車型進行配送，避免無法配送到戶的情況。同時在選擇出車車輛時，對司機的工作負荷進行一定的均衡（因為車輛和司機是綁定的），確保各人的勞動時間不會差異太大。

（1）聚類分析算法

其基本策略是先對每個簇任意選擇一個代表對象，剩余的對象根據(jù)其與代表對象的距離分配給最近的一個簇。然后反復利用非代表對象來代替代表對象，以改進聚類的質(zhì)量。聚類結(jié)果的質(zhì)量用一個代價函數(shù)估算，該函數(shù)度量對象與參照對象之間的平均相異度。為了判定一個非代表對象是否是當前一個代表對象的好的代表，對于每一個非中心對象p，需要分為四種情況考慮：① p當前隸屬于中心點對象。如果被所代替，且p離一個最近，，那么p被中心分配給。② p當前隸屬于中心點對象。如果被所代替，且p離最近，那么p被中心分配給。③ p當前隸屬于中心點對象，。如果被代替作為一個中心點，且p仍離最近，那么對象的隸屬不發(fā)生變化。④ p當前隸屬于中心點對象，。如果被代替作為一個中心點，且p離最近，那么p被重新分配給。

計算時，輸入：簇的數(shù)目k和包涵n個對象的數(shù)據(jù)庫。其中，簇就是線路，而對象就是客戶群。輸出：k個簇，使得所有對象與其最近中心點的相異度總和最小。

計算方法：任意選擇k個對象為初始的簇中心。指派每個剩余對象給離它最近的中心點所代表的簇。隨機地選擇一個非中心點的對象，計算用代替的總代價S，如果S＜0，那么代替，形成新的k個中心點的集合。直到不發(fā)生變化。本算法以裝載率盡量接近滿載為代價函數(shù)f(x)，即f(x)=|Loading Rate-1|其中Loading Rate為裝載率。如果沒裝滿送貨時間就超標了，則代價函數(shù)f(x)改為時間上接近最大送貨時間，即f(x)=|Time-Max Time|其中Time為送貨時間，Max Time為最大送貨時間。

分割完畢后，選擇包含有計算起點的線路作為原始線路（此線路內(nèi)包含有多個客戶群），進入客戶群拆分階段。由于中心聚類不可能獲得非常精密的結(jié)果，上面的原始線路很有可能會出現(xiàn)超出最大裝載量（超出最大工作時間）的情況。此時就需要對原始線路內(nèi)的客戶群進行排序，按照順序逐個將客戶進行裝車，直到裝不下為止。剩余的原始線路內(nèi)客戶重新組成客戶群，返還到待計算客戶中，與其他線路中的客戶群一起回爐，等待下一次計算，這樣就得到了一條線路的結(jié)果。

接下來，對剩余待計算的客戶群重新開始這一輪步驟：首先預估所需的車輛，再次取離區(qū)域中心最遠的客戶群作為計算起點，繼續(xù)中心聚類計算，獲取原始線路后，再做客戶群拆分。如此迭代，直到只剩下2條線路為止。

（2）線路串接算法

線路串接并非簡單的把區(qū)域的客戶群從頭到尾串到一起，然后根據(jù)車容量和工作時間來切分車輛，它是直達目標的。也就是說，它并不是通過事先優(yōu)化客戶群的連接順序來間接的優(yōu)化最終的線路，而是使用禁忌搜索嘗試各種客戶群排序的組合方式，對此排序下的客戶序列進行裝車切割，以實際得出的線路結(jié)果作為最終的評估對象。通過評估不同客戶群排序組合下實際的切分裝車結(jié)果，來找出較優(yōu)的客戶群排序方式。

① 禁忌搜索：為了得到更優(yōu)的計算結(jié)果，擴大計算范圍，減少計算量，本算法引入了禁忌搜索。首先，對置換問題定義一種鄰域搜索結(jié)構(gòu)，如互換操作（SWAP），即隨機交換兩個點的位置，則每個狀態(tài)的鄰域解有Cn2=n（n-1）/2個其中n為點數(shù)。稱從一個狀態(tài)轉(zhuǎn)移到其鄰域中的另一個狀態(tài)為一次移動（move），顯然每次移動將導致適配值（反比于目標函數(shù)值）的變化。其次，采用一個存儲結(jié)構(gòu)來區(qū)分移動 的屬性，即是否為禁忌“對象”。需要指出的是，由于當前的禁忌對象對應狀態(tài)的適配值可能很好，因此在算法中設置判斷，若禁忌對象對應的適配值優(yōu)于“best so far”狀態(tài)，則無視其禁忌屬性而仍采納其為當前選擇，也就是通常所說的藐視準則（或稱特赦準則）。

② 評估參數(shù)：評估的基本參數(shù)是所有線路的總工作時間。如果需要和其它區(qū)域連接，那么還需要加上尾車的最后一戶到下一個區(qū)域的連結(jié)點客戶的時間，總時間越短越好。此外，如果有區(qū)域融合的要求，還會附加上盡量能使尾車和與其它區(qū)域相連這個條件。

③對于特定客戶群序的裝車切割流程：裝車時，默認方法為安排好的客戶順序裝車，假如碰到自己車子無法配送的客戶，將這一戶剔出來，繼續(xù)裝后面的，這幾戶被剔除的客戶留待后面的車子來嘗試配送。倘若裝車中碰到一個訂貨大戶，如果加上去，車子裝不下，如果不加，車子裝載率又太低，這時候?qū)⑻^此戶，繼續(xù)裝后面訂貨量沒這么大的，保證裝載率不會太低。

④ 車型匹配：將起始客戶初始化為第一個客戶，進行車型適配度的評估。其做法是，嘗試使用各種車型進行裝車，把生成的各個線路結(jié)果作為評估對象。生成線路的時候，由于車型關系剔除的客戶越多，說明此車型的適配度越低。取適配度較好的幾個車型作為待選車型，從中選出一輛駕駛員歷史累計送貨時間較低的作為最終選擇結(jié)果。另外，如果可能的話，區(qū)域內(nèi)的每個駕駛員都需要至少出車一次。所以選擇時，優(yōu)先從今天沒有出過車的駕駛員里選擇。

⑤ 標記：一條線路生成后，將線路中的客戶作上已計算標記，繼續(xù)按照上面的算法，選擇車型，選擇車輛，計算剩下的客戶序列中的客戶，直到所有的客戶都被計算完成。

2.2.3.3 路順優(yōu)化

線路生成后，分別以全體打亂重排的方式和保留客戶群內(nèi)客戶順序進行路順計算。默認為保留客戶群內(nèi)的順序，但如果默認結(jié)果與打亂重算的結(jié)果差很多，那么以打亂重排后的順序為最終的線路路順。打亂重排涉及局部搜索和禁忌搜索算法。

基本思想是在搜索過程中沿著某一方向搜索，該方向是從當前點到該點的所有鄰居中離目標點最近的那一點的方向。

① 隨機選擇一個初始的可能解

② 如果不滿足結(jié)束條件，則開始循環(huán)。

③ Begin

⑦ End

⑧ 輸出計算結(jié)果。

而禁忌搜索是對局部搜索的擴展，是一種局部搜索能力很強的全局迭代尋優(yōu)算法，其詳細計算機制如前所述。與局部搜索相比具有以下特點：一是在搜索過程中可以接受劣解。二是新解不是在當前鄰域中隨機產(chǎn)生，而是優(yōu)于“best so far”的解，或是非禁忌的最優(yōu)解，因此選取優(yōu)良解的概率遠大于其它解。

2.2.3.4 尾車劃撥

假如該區(qū)域（區(qū)塊）開啟了區(qū)域融合，那么首先要通過設置獲取信息，判斷該區(qū)域（區(qū)塊）能和哪些其他區(qū)域（區(qū)塊）交換客戶。

接下來，查看本區(qū)域是否需要往外劃撥的尾車，如果需要，那么查找距離這個尾車最近的可交換區(qū)域，將尾車的所有客戶劃撥給到那個區(qū)域去(或者抓取足夠的客戶填充)。假如需要將尾車交給其他區(qū)域，程序運算時會將尾車客戶盡量放置在本區(qū)域的邊緣地區(qū)，跟將要劃撥到的鄰居區(qū)域盡量接近。

如果找不到其他可劃撥的區(qū)域了，尾車將獨自成為一條線路。這種情形通常出現(xiàn)在幾種情況下：這個區(qū)域與其他的任何區(qū)域都很遠，距離太遠的話是不會劃撥過去的；這個區(qū)域是所有可交換區(qū)域中，最后一個待計算的區(qū)域了；尾車的客戶附近的其他車輛都無法配送。

2.3 曾使用的其它算法及遇到的問題

2.3.1 第一版算法

粗略預估一個月平均裝載率大致能達到90%左右的車輛數(shù)，根據(jù)車輛列表獲取所用的車輛。采用中心聚類，以裝載率越平均越好為目標，對整個區(qū)域進行一次性的分割計算得到初步結(jié)果，然后使用滲透模擬的方式，在線路之間調(diào)整客戶。

這種方式比單純的中心聚類分割線路，穩(wěn)定性要好不少。但由于僅僅考慮客戶點的地理信息來安排路順，不參考其原線路，所以路順都是重新計算的。在基礎信息不準確的情況下，路順的計算結(jié)果往往不如人意。

另外，由于中心聚類天生的穩(wěn)定性的缺陷，以及滲透模擬無法進行大范圍調(diào)節(jié)的劣勢，偶爾會可能出現(xiàn)一些穿插的很遠的較劣結(jié)果。

2.3.2 第二版算法

參照原線路，把區(qū)域內(nèi)的客戶劃分成一個個客戶群，然后對客戶群進行排序，生成一個很大的客戶序列，之后，使用區(qū)域內(nèi)車輛列表，對這個客戶序列進行逐次裝車，以車輛的最大裝載量和最大送貨時間為限制條件，分割成一條條線路。

分割完畢后，檢查每個區(qū)域的尾車是否能和其他區(qū)域尾車進行合并，通過最大連接距離來限制尾車的合并范圍，避免與過遠的尾車連接。倘若無法簡單合并，將嘗試將尾車拆成多份，分配到附近區(qū)域的其他尾車上面去，以減少尾車數(shù)目，提高裝載率。

這個做法在客戶群較少的情況下效果較好，但如果客戶群數(shù)量較多，通過簡單的串接排序生成的線路，其聚團性較差，線路之間穿插較嚴重。另外，由于每個區(qū)域之間的尾車一般相距較遠，尾車所能交互的對象并不多，所以其合并相對的有限。在開啟全區(qū)合并的情況下，只能減少一半不到的尾車。

3 系統(tǒng)測試與結(jié)果分析

3.1 系統(tǒng)的測試環(huán)境

編程語言為C#，編譯環(huán)境為Visual Studio 2012，基于.NET Framework4.5 ，操作系統(tǒng)為Win7 32bit。

部署軟件環(huán)境，操作系統(tǒng)為Windows Server 2008 R2 64bit，安裝.NET Framework4.5框架。

部署硬件環(huán)境為IBM X3650 M4服務器 （至強CPU，內(nèi)存32G）。

3.2 測試結(jié)果

以2014年2月訂貨量為實驗數(shù)據(jù)，計算原有送貨模式和線路優(yōu)化新模式下兩種配送結(jié)果，以裝載率和出車趟次作為比較指標進行分析。選取10天的訂單量進行測試，數(shù)據(jù)結(jié)果如表1所示。

由表1數(shù)據(jù)繪制圖2、3的曲線圖，其中橫坐標為序號值，圖2為裝載率對比曲線圖，圖3為出車趟次對比曲線圖。

表1 2014年2月測試數(shù)據(jù)結(jié)果Tab.1 Test results of February 2014

圖2 裝載率對比曲線圖Fig.2 Comparison graph of loading rates

圖3 出車趟次對比曲線圖Fig.3 Comparison graph of department quantity

3.3 結(jié)果分析

（1）如圖2所示，在訂單量一定的情況下，優(yōu)化后裝載率全部高于原有線路裝載率，平均增加20.1%。優(yōu)化后，平均裝載率達到了90%以上的指標要求。

（2）如圖3所示，在訂單量一定的情況下，優(yōu)化后出車趟次全部少于原有線路出車趟次，平均減少超過20%。

（3）在線路裝填時，本算法通過評估不同客戶群排序組合下，實際的切分裝車結(jié)果，來找出較優(yōu)的客戶群排序方式。一般來說，很少有人會用這種系統(tǒng)資源巨大的方式來實現(xiàn)這個要求，但由于已經(jīng)作了區(qū)域識別分析，能夠確保區(qū)域內(nèi)的客戶基本上都是整線的，客戶群的數(shù)目不會太多，計算負荷不至于無法接受。

（4）本算法中心聚類算法與普通中心聚類不同，最大的區(qū)別是在于計算的次數(shù)。普通中心聚類，是一次性計算出所有的線路；而這個算法，每次只取包含有計算起點的線路作為結(jié)果，剩余的線路統(tǒng)統(tǒng)回爐重算，需要逐次計算N-1次，才能獲取N條線路。保證尾車的線路與其他區(qū)域很接近，方便進行區(qū)域間的客戶調(diào)配。

4 結(jié)論

本算法滿足了業(yè)務指標要求，突破了原有行政區(qū)縣劃分的界限限制，優(yōu)化了配送調(diào)度結(jié)果，在大計算量的情況下仍能滿足計算要求。對卷煙配送裝載率和出車趟次具有良好的改善效果。同時，本算法具有普適性，在適應北京復雜路線的情況下仍能適應業(yè)務需求，具有較好的推廣價值。

[1]張曉輝.禁忌搜索算法研究及其在電磁場優(yōu)化問題中的應用 [D].碩士學位論文，河北工業(yè)大學，2003.

[2]劉志成，文全剛.K-中心點聚類算法分析及其實現(xiàn)[J]電腦知識與技術(shù)，2005（2）：20-24.

[3]朱建中.求解可滿足性問題的局部搜索算法[D].碩士學位論文，南京大學，2004.

[4]郭娜.基于節(jié)約算法和移動方向的禁忌搜索算法[D].碩士學位論文，大連理工大學，2009.

[5]李少芳.連續(xù)背包問題貪婪算法最優(yōu)解的實現(xiàn) [J].福建電腦，2003（11）：12-13.

Cigarette distribution scheduling system based on route optimization algorithm

SUN Zhuangzhi,YAN Liehu,YAO Xuewei
Beijing Tobacco Logistics Center,Beijing 101101，China

An adaptable,quick-responsive and feasible real-time solution was introduced by applying algorithms such as central clustering,tabu search and local search on the basis of cigarette distribution market in Beijing.Dynamic scheduling was fully achievable by taking original delivery map as reference and work load of delivery vehicles and working staff into full consideration.The solution was proved to be effective with monthly average loading rate exceeding 90%.

route optimization; central clustering; tabu search; local search

10.3969/j.issn.1004-5708.2014.05.021

TP315 文獻標志碼：A 文章編號：1004-5708（2014）05-0128-06

孫壯志（1971—），高級工程師 ，主要從事卷煙物流等方面的研究，Email:349890782@qq.com

2014-03-12