基于散射搜索的煙草物流配送優(yōu)化方法研究

楊璞光 陳安 呂永貴 羅艷輝

摘 要：本文研究了煙草物流配送時間的優(yōu)化問題。該問題具有組合復(fù)雜性和計算困難性。本文首先根據(jù)卷煙工業(yè)物流實際情況建立相應(yīng)的數(shù)學(xué)模型，采用了基于啟發(fā)式策略和散射搜索算法的優(yōu)化方法來縮短煙草物流配送的時間。該方法通過放寬問題的限制條件，構(gòu)造優(yōu)化配送的位置順序，尋找最優(yōu)配送周期來減少配送時間。最后通過數(shù)值實驗對該算法進行了評價，并與現(xiàn)有強約束下的啟發(fā)式算法進行了比較。結(jié)果表明，該算法具有較好的優(yōu)化效果，能夠有效縮短工煙物流配送的時間。

關(guān)鍵詞：煙草物流配送;優(yōu)化方法;散射搜索算法;啟發(fā)式算法

引言：煙草物流是指煙草及其制品和原輔料從生產(chǎn)、收購、儲存、運輸、加工到銷售服務(wù)整個過程中物質(zhì)實體運動以及流通環(huán)節(jié)的所有附加增值活動，進一步可以狹義地認(rèn)為是指煙草行業(yè)基于社會職能分工的不同，工煙企業(yè)、商煙企業(yè)及相互之間發(fā)生的煙草制品和相關(guān)物資實物的移動活動。煙草行業(yè)是一個壟斷經(jīng)營的高利潤行業(yè)，因此高利潤有時候掩蓋了現(xiàn)代物流對企業(yè)競爭力的價值。物流成本是煙草企業(yè)成本中的重要組成部分，物流成本的降低就是企業(yè)的“第三利潤源”。因此要以強大的物流體系來支撐煙草行業(yè)的持續(xù)發(fā)展，應(yīng)對市場環(huán)境帶來的風(fēng)險。

當(dāng)今，很多行業(yè)相關(guān)的優(yōu)化問題被提出，有一些在相關(guān)文獻中得到了解決，并提出了多種求解算法。例如漳州煙草配送區(qū)域及線路優(yōu)化借助柔性線路截取算法以及GIS線路優(yōu)化輔助系統(tǒng)，依據(jù)零售戶的地理位置、歷史銷量對全區(qū)所有零售客戶進行線路調(diào)整，改變傳統(tǒng)既定計劃、線路、車輛、人員“以線定車”的固定配送模式，建立了“以量定車，以戶定線，戶量均衡，動態(tài)優(yōu)化”的彈性送貨新模式。又例如宜春市煙草公司針對物流配送線路建立VRP模型，通過節(jié)約算法優(yōu)化問題，提高卷煙配送運輸效率，降低配送成本。安陽市煙草公司利用GIS系統(tǒng)，添加適當(dāng)?shù)募s束條件，達到“送貨線路到最優(yōu)，車輛配載經(jīng)濟”的目標(biāo)。

卷煙工業(yè)物流配送中心負(fù)責(zé)給煙草商業(yè)公司點至點的分發(fā)，配送中心發(fā)出配送車輛，完成配送任務(wù)后返回物流配送中心。各地商煙公司比較分散，導(dǎo)致物流末端配送呈現(xiàn)多批次、少批量的特點，對配送中心的物流配送路線優(yōu)化提出了嚴(yán)峻挑戰(zhàn)。本文將著重圍繞物流配送路線優(yōu)化問題展開探討，提出相應(yīng)的優(yōu)化解決方法。

一、問題描述

卷煙工業(yè)物流配送指的是各個送貨車輛從物流配送中心配貨到向各個煙草商業(yè)公司送貨的過程。送貨路徑選擇的合理性對于整個配送過程的成本和效率都有很大的影響。所以如何采用科學(xué)合理的方式規(guī)劃配送過程，是煙草物流管理過程中需要研究的一個重要問題。

本文假設(shè)問題里的送貨車輛在一個運送周期里可運送多種貨物到多個地點，每個配送點坐標(biāo)都各不相同，送貨車輛載重量一定。送貨車輛先到配貨倉庫一次性裝配多種貨物，然后分別移動到對應(yīng)的煙草商業(yè)公司卸下所需貨物，這個過程中送貨車輛不會再返回物流中心裝配貨物，除非它已經(jīng)放置完之前取的所有貨物。理論上是一次裝配后，依次去多個煙草商業(yè)公司卸貨，在規(guī)劃的路徑終點剛好完全卸完貨物。之后再次返回物流中心配貨，循環(huán)往復(fù)的過程。

二、問題分析和建模

卷煙工業(yè)物流配送的總時間可以分為以下幾個部分：（1）送貨車輛在送貨路途行駛的時間;（2）送貨車輛在倉庫裝配貨物的時間;（3）送貨車輛在各個煙草商業(yè)公司卸貨的時間。

假設(shè)配送完所有貨物需要K個配送周期（以下簡稱周期），用Ti表示一個周期所需要的時間（1

Tipick：在第i個周期中送貨車輛從配送中心的倉庫裝配貨物的時間。包括了在配送中心中行駛的時間和貨物裝配所需的時間。

Tidownload：在第i個周期中送貨車輛從貨物裝配完成后到第一個煙草商業(yè)公司的時間。

Tiplace：在第i個周期中送貨車輛卸貨的時間。包括在不同煙草商業(yè)公司間移動的時間和卸貨所需要的時間。

Tiupload：在第i個周期中送貨車輛從最后一個煙草商業(yè)公司卸完貨后離開到新的配送中心的時間。

因此，卷煙工業(yè)物流配送的總時間可以由以下數(shù)學(xué)公式表示：

■（1）

假設(shè)第i周期送貨車輛裝配的貨物份數(shù)為■（1

■（2）

其中，■表示一次裝貨的時間。

同時，第i周期送貨車輛需要到達的煙草商業(yè)公司卸貨次數(shù)為■（1

■（3）

其中，■表示在煙草商業(yè)公司卸貨所需要的時間，■表示在不同煙草商業(yè)公司間移動的時間，（j，j+1）表示從第j個煙草商業(yè)公司到第j+1個煙草商業(yè)公司?？山普J(rèn)為是個常數(shù)，因此，由公式（2）可知，主要影響送貨時間的是在煙草商業(yè)公司之間移動的時間。

通過以上分析，影響卷煙工業(yè)物流配送時間的主要因素為送貨車輛去各個煙草商業(yè)公司送貨的順序。這個因素在整體優(yōu)化問題中高度耦合，使得問題變得復(fù)雜。因此，本文嘗試用一種分解相關(guān)問題的方法，然后設(shè)計相應(yīng)的方法來求解問題。

通過合并等式（1），（2），（3），能得到：

■（4）

在等式（4）中，第三項和第四項主要取決于循環(huán)次數(shù)K和送貨車輛最大裝載量;其余項主要取決于行駛的時間和循環(huán)次數(shù)K。因此，為了縮短配送時間，應(yīng)當(dāng)縮短配送周期內(nèi)行駛的時間和減少總的周期數(shù)。

三、優(yōu)化方法

1.可行解的編碼和評價函數(shù)

優(yōu)化方法中的可行解不僅要包含問題中的決策信息，而且要適合所使用的算法。因此，為可行解設(shè)計一個合適的編碼表示形式是必要的。

假設(shè)每個送貨目的地都用一個連續(xù)的整數(shù)進行連續(xù)編號。使用不同目的地的編號構(gòu)造編碼序列來表示不同的可行解。編碼序列可以通過以下方法進行解碼：首先，從序列開始通過分組G區(qū)分送貨組，也對應(yīng)于送貨周期。每組G表示一輛車一個周期所要到達的目的地集合。然后，對于每個送貨組G，根據(jù)整數(shù)編號在序列中出現(xiàn)的順序，依次將H1到HN（N是送貨組中整數(shù)編號數(shù)量）分配給編號的目的地。

舉例說明，一輛送貨車輛要到達4個目的地，用H1表示一個周期內(nèi)計劃送的第1個目的地。而一共有14個目的地需要它送貨，那么送貨順序問題的可行解可以用下圖所示的編碼序列表示。

圖中，編碼序列{3，14，1，12，5，13，8，6，9，4，11，10，2，7}可被解碼為下面兩個內(nèi)容：（1）目的地被分成了四組{3，14，1，12}，{5，13，8，6}，{9，4，11，10}和{2，7}，對應(yīng)了四個送貨周期：G1、G2、G3、G4。（2）每貨物組中的目的地編號按其在組中的出現(xiàn)順序?qū)?yīng)了依次送貨到煙草商業(yè)公司的順序：如G1中先送編號3的目的地，到14號目的地，再到1號目的地，最后到12號目的地。

從一個可行解的編碼中可以得出兩個決策信息：運送貨物的周期數(shù)和一個周期內(nèi)向目的地送貨的順序?？尚薪獾木幋a實現(xiàn)了包含必要的決策信息，并使得可行解能夠適用于算法。所以把問題的可行解經(jīng)過編碼后輸入算法，把算法得到的結(jié)果解碼便能得到所期望的決策信息。

在煙草物流配送的過程中，裝貨和卸貨過程的時間可以近似為常數(shù)，主要的時間為在不同的煙草商業(yè)公司間移動所用的時間。因此，煙草物流配送的時間基本可以由送貨車輛行駛的時間來衡量，而已知不同煙草商業(yè)公司的距離，可以通過計算距離的方式得到近似的行駛所需時間。本文通過建立數(shù)學(xué)函數(shù)的方式來計算各個物流配送方案所耗費的時間，來評估下文提出算法的不同可行解。

2.基于散射搜索的優(yōu)化算法

由第2章的問題建模可知這個問題很難通過局部搜索方法找到最優(yōu)解或次最優(yōu)解。所以本文采用了一種基于散射搜索（SS）的優(yōu)化算法，該算法是由Glover提出的一種全局搜索方法，其很少依賴搜索過程的隨機性，而是采用其框架中一系列系統(tǒng)性方法來實現(xiàn)對優(yōu)化問題的求解。基于SS方法的算法流程圖如圖5所示。

算法的具體操作步驟如下：

（1）生成初始解集

對于散射搜索法，要求初始集的解盡可能分散在整個解空間中。為了滿足這一需求，按照以下步驟生成初始解集：

第一步：利用貨物的編碼集M，隨機地生成初始可行解L0={m1，m2...mi...mM}，mi表示第i份貨物的編碼，|M|是貨物的總數(shù)量。L（i）=mi。

第二步：定義一個序列P（h：s）=（L0（s），L0（s+h），L0（s+2h），...，L0（s+rh）），其中1

第三步：通過改變[1，|M|]中的h，能從初始解中得到|M|個不同的可行解。從而構(gòu)造出初始解集S。

為了保證初始解集的多樣性，本文對第三步做一點小的改動。對于可行解L（h），引入它的翻轉(zhuǎn)序列，表示為L*（h），那么它同樣也是可行解。例如，對于可行解L（4）=（4，9，6，3，7，2，5，1，8），它的翻轉(zhuǎn)序列為L*（4）=4）=（8，1，5，2，7，3，6，4，9）。如果改變[1，|M|/2]中的h，生成|M|/2組初始解，還可以得到|M|/2組翻轉(zhuǎn)解，進而能通過這些可行解構(gòu)造初始解集。如果需要產(chǎn)生更多的解來擴展初始解集，能夠使用這種方法隨機地生成另一組可行集。

（2）初始解的改進

改進初始解的操作的目的是將初始集合中的每個原始解轉(zhuǎn)換為一個或多個更好的解?？梢杂煤唵位驈?fù)雜的方法來改進解?？紤]算法的時間復(fù)雜度，本文采用兩元素優(yōu)化局部搜索方法對初始解集S的解進行改進。

解改進的基本操作描述如下。利用兩元素優(yōu)化方法對S中的一個解進行改進時，將解序列中的兩個分量按其位置進行交換，從而產(chǎn)生一個新的解。如果找到一個更好的解，用它來替代S中的原始解;否則，保留原始解。應(yīng)該注意的是，改進解的操作應(yīng)該應(yīng)用于S中的每個初始解。解的改進操作可以根據(jù)實際需要靈活設(shè)置終止條件。例如，可以為解引入持續(xù)改進或持續(xù)不改進的時間計數(shù)器，以確定何時可以終止改進。

通過改進初始解集，可以得到Simp（改進解集）。

（3）構(gòu)造初始參考解集

設(shè)初始參考解集RefSet，是配送時間少的較好解和配送時間多的較差解的集合。設(shè)RefSet1為較優(yōu)解子集，RefSet2為較差解子集。它們的大小都是b/2（b是一個整數(shù)，依賴于問題的規(guī)模，但不大于初始解集的大?。?。RefSet是RefSet1和RefSet2的并集。初始RefSet的構(gòu)造包括以下步驟：

第一步：從改進解集Simp中選擇配送時間更短的b/2最佳解來構(gòu)造子集RefSet1，將它們添加到參考解集RefSet并從Simp中刪除它們。

第二步：對于Simp中其余的每個解，計算它與RefSet中每個解之間的最小“距離”。在這些最小距離上取最大值的解被添加到RefSet中，然后從Simp中移除。這個解也稱為多樣解，保留它是為了保持解的多樣性。同樣的過程重復(fù)b/2次，得到b/2不同的解，構(gòu)造RefSet2。將這些解添加到RefSet。這樣便得到了完整的參考解集RefSet。

上述兩個解之間的“距離”的概念定義為兩個解序列中相同位置的分量彼此所相差的次數(shù)。例如，有兩個解序列s1=（1，5，2，4，3）和s2=（2，5，3，4，1），那它們的距離是3，因為有兩對位置相同的分量是相同的。兩個解之間的距離表示兩個解之間的差異程度。

（4）組合解集

通過解的組合，生成新的解，擴大解空間的搜索范圍。這個操作有兩個步驟。第一步是生成解子集，第二步是每個子集的解的組合。

為了使子集覆蓋盡可能分散的不同區(qū)域，子集應(yīng)該同時包含優(yōu)解和劣解。由于參考解集包含較好的解和較差的解，因此可以用它來生成子集。在這里，對參考解集RefSet應(yīng)用成對組合方法，生成一種稱為雙解的子集。每個雙解子集由兩個解組成，這兩個解分別從兩個母解中選擇。例如，如果得到一對集合為S1=（x1，x2，x3）和S2=（y1，y2），它最多有6個雙解子集，（x1，y1），（x1， y2），（x2，y1），（x2，y2），（x3，y1）和（x3，y2）。所以，參考解集RefSet中任何兩個解都能用來產(chǎn)生了兩個一個雙解子集。然而，由于兩個不同的解可以構(gòu)造一個有效的雙解子集。因為RefSet中有b個解，結(jié)果最多可以得到b（b-1）/2個子集。

在生成雙解子集之后，可以使用簡單方法或復(fù)雜方法將兩個解合并到子集中生成新的解。這里采用部分匹配交叉的方法。它起源于遺傳算法。一個子集中兩個解的每個組合都可以通過部分匹配交叉方法生成兩個“新”解。通過這種方法，得到了一個具有b（b-1）/2“新”解的集合，記作TemSet。然后，再次使用兩元素優(yōu)化方法對TemSet中的所有解進行改進。

（5）參考解集更新

更新參考解集需要從RefSet和TemSet兩個解集中選擇b個“最佳”解，并在RefSet中替換原始解。更新方法與初始參考解集的構(gòu)造相同，唯一的區(qū)別是源解集是這里的RefSet和TemSet的結(jié)合。然而，TemSet中的一些解決可能存在于RefSet中。為了判斷TemSet中是否生成了真正的新解，算法計算差分集TemSet-RefSet，并將其設(shè)置為新的解集NewSet。然后，該算法決定是否結(jié)束當(dāng)前的搜索循環(huán)判斷如果NewSet是空集，如果NewSet不是一個空集，這意味解搜索過程中至少有一個新的解生成。當(dāng)前循環(huán)的散射搜索將繼續(xù)進行解的組合、改進和更新操作，如前面給出的算法框架所示。否則，當(dāng)前搜索周期（不是整個算法）將終止。

3.算法運行效果與收斂性分析

為了檢驗算法的運行效果，通過MATLAB實現(xiàn)上述算法并進行檢驗。第一種檢驗方法為一次輸入31個城市坐標(biāo)數(shù)據(jù)，通過算法找出經(jīng)過所有城市的最短路徑以及相應(yīng)的配送順序。運行效果如圖6所示。從圖中可以看出，在復(fù)雜的情況下，人工已經(jīng)難以計算出最短的連續(xù)路徑的順序，此時算法仍能夠很好地計算出最短路徑的順序結(jié)果。第二種檢驗方法是同時輸入15個城市數(shù)據(jù)，模擬3輛送貨車輛的情況，運行效果如圖7所示。從圖中可以看出，在多路徑多種分配的情況下，算法仍能夠合理的分配送貨車輛得到最短的配送路徑順序。

收斂性方面，由算法本身的原理特性，算法在迭代的過程中會保留原始的解集中一半的較優(yōu)解集，在另一半較差解集的基礎(chǔ)上進行改進，構(gòu)造新的解集，利用匹配交叉變異等方法探索更多的解空間。上述的原理保證了算法的收斂性，在迭代的過程中能夠不斷的保存優(yōu)質(zhì)解，丟棄較差解，從而向期望的解空間收斂。第一種檢驗方法在迭代過程中算法的收斂性分析如圖8所示，可以看出，隨著算法的迭代，其求得的最短距離也在不斷減小，最終達到了較穩(wěn)定的水平。

四、實際應(yīng)用

為了驗證該算法的可行性和有效性，利用紅塔集團的在廣東省近年卷煙工業(yè)物流配送中某個月的實際數(shù)據(jù)進行實際應(yīng)用。其中一輛送貨車輛的裝載量為150箱，即750件。實物包裝一箱煙草，煙草行業(yè)一般稱之為“件”，是50條。而在煙草報表中的統(tǒng)計概念，是以實物五件為一箱，是250條。

紅塔集團廣東省煙草某個月需求情況如下表所示。

以廣東省煙草實際需求數(shù)據(jù)作為仿真實驗的對象，為了下一步運用到物流配送系統(tǒng)內(nèi)，在Microsoft Visual Basic 6.0中實現(xiàn)了該算法。根據(jù)實際，一輛送貨車輛能裝150箱煙，送貨車輛的數(shù)量能夠靈活調(diào)整，保證車輛滿載。各地市之間的相對位置和距離按照實際地理位置設(shè)定，均為確定和已知的不變量。為了評估本文所運用的算法的性能，將其與文獻中提出的強約束下的啟發(fā)式算法進行了比較，該算法將整體問題分解為子問題的層次結(jié)構(gòu)，并基于動態(tài)規(guī)劃和最近鄰旅行商問題的求解。另外，由于有些地市煙草需求量大，一部分煙草需要選擇整車裝載其所需煙草然后直達的運送方式。在煙草物流配送優(yōu)化過程中無需對這部分直達運送方式進行優(yōu)化，故在結(jié)果顯示中將這部分運用直達運送方式的結(jié)果剔除。只討論地市需求量不足整車裝載量的情況下，如何分配送貨車輛的配送路徑以達到最短路程。

實際應(yīng)用的比較結(jié)果如下表：

優(yōu)化結(jié)果表明，該算法的性能優(yōu)于HA算法，提高了近10%。不僅在總送貨周期的基礎(chǔ)上減少了一個送貨周期，而且總路程上也有所縮短，相當(dāng)于節(jié)省了一輛車的運載量和路程中的成本費用。究其原因主要有兩個方面：一是SS算法放松了一些強約束，使得解空間擴大，這意味著獲得更好解的可能性更高;二是具有全局搜索機制的SS算法比HA算法有更多的機會找到更好的解，HA算法對貨物的配送排序采用局部搜索的方法。將該套方法運用到實際工作后，實現(xiàn)了配送貨物數(shù)量相同的情況下，送貨車輛和配送人員減少、裝載量及送貨戶數(shù)增加的效果，達到了提高卷煙配送效率、降低配送成本的目的。

五、結(jié)論

本文研究了卷煙工業(yè)物流配送時間最小化的優(yōu)化問題。對該問題進行了分析，指出了現(xiàn)有優(yōu)化算法存在的一些強約束，導(dǎo)致了實際應(yīng)用性能不理想的情況。由于問題具有組合性和計算難解性，本文提出了一種基于啟發(fā)式策略和分散搜索方法的優(yōu)化算法，優(yōu)化卷煙工業(yè)物流配送的時間。通過紅塔集團在廣東省煙草物流配送數(shù)據(jù)實際應(yīng)用結(jié)果表明，該算法能取得較好的效果，明顯縮短了煙草物流配送過程中的時間，證明該套優(yōu)化方法能夠在實際卷煙工業(yè)物流配送中起到指導(dǎo)作用，達到提升配送效率、降低配送成本的目的。需要指出的是，本文的方法將整個問題分解為單獨的子問題，并獨立研究求解，得到最優(yōu)解。在今后的工作中，將深入建立整體優(yōu)化問題的集成模型，設(shè)計協(xié)同優(yōu)化算法，同時解決相關(guān)子問題，進一步提高算法性能。

參考文獻：

[1]李朵.地級市煙草現(xiàn)代物流配送系統(tǒng)優(yōu)化[D].西安建筑科技大學(xué)，2016.

[2]章惠民.煙草商業(yè)系統(tǒng)物流線路優(yōu)化研究與應(yīng)用[J].中國煙草學(xué)報，2018，24（03）：100-105.

[3]陳小麗，曲媛，肖鴻.宜春市煙草公司物流配送線路優(yōu)化[J].佳木斯大學(xué)學(xué)報（自然科學(xué)版），2012，30（01）：49-52.

[4]潘國鵬.安陽煙草公司物流配送路線優(yōu)化問題研究[D].鄭州大學(xué)，2017.

[5]陳影，孫虎.基于Flexsim的煙草物流配送中心規(guī)劃仿真[J].物流技術(shù)，2018，37（07）：105-110.

[6]陳成.基于改進遺傳算法的物流車輛路徑問題優(yōu)化[J].信息技術(shù)與信息化，2018（09）：41-43.

[7]李陽，范厚明，張曉楠，楊翔.隨機需求車輛路徑問題及混合變鄰域分散搜索算法求解[J].控制理論與應(yīng)用，2017，34（12）：1594-1604.

[8]張曉楠，范厚明.混合分散搜索算法求解帶容量約束車輛路徑問題[J].控制與決策，2015，30（11）：1937-1944.

[9]F.Glover， Heuristics for Integer programming using Surrogate constraints，Decision Sciences，8（7）：156-166，1977.

[10]陳萍.啟發(fā)式算法及其在車輛路徑問題中的應(yīng)用[D].北京交通大學(xué)，2009.

作者簡介：楊璞光（1994- ），男，華南理工大學(xué)在讀碩士生，研究方向：自動駕駛