基于散射搜索的煙草物流配送優化方法研究

楊璞光 陳安 呂永貴 羅艷輝

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

關鍵詞：煙草物流配送;優化方法;散射搜索算法;啟發式算法

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

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

卷煙工業物流配送中心負責給煙草商業公司點至點的分發，配送中心發出配送車輛，完成配送任務后返回物流配送中心。各地商煙公司比較分散，導致物流末端配送呈現多批次、少批量的特點，對配送中心的物流配送路線優化提出了嚴峻挑戰。本文將著重圍繞物流配送路線優化問題展開探討，提出相應的優化解決方法。

一、問題描述

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

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

二、問題分析和建模

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

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

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

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

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

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

因此，卷煙工業物流配送的總時間可以由以下數學公式表示：

■（1）

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

■（2）

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

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

■（3）

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

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

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

■（4）

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

三、優化方法

1.可行解的編碼和評價函數

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

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

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

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

從一個可行解的編碼中可以得出兩個決策信息：運送貨物的周期數和一個周期內向目的地送貨的順序。可行解的編碼實現了包含必要的決策信息，并使得可行解能夠適用于算法。所以把問題的可行解經過編碼后輸入算法，把算法得到的結果解碼便能得到所期望的決策信息。

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

2.基于散射搜索的優化算法

由第2章的問題建?？芍@個問題很難通過局部搜索方法找到最優解或次最優解。所以本文采用了一種基于散射搜索（SS）的優化算法，該算法是由Glover提出的一種全局搜索方法，其很少依賴搜索過程的隨機性，而是采用其框架中一系列系統性方法來實現對優化問題的求解。基于SS方法的算法流程圖如圖5所示。

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

（1）生成初始解集

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

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

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

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

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

（2）初始解的改進

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

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

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

（3）構造初始參考解集

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

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

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

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

（4）組合解集

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

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

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

（5）參考解集更新

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

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

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

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

四、實際應用

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

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

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

實際應用的比較結果如下表：

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

五、結論

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

參考文獻：

[1]李朵.地級市煙草現代物流配送系統優化[D].西安建筑科技大學，2016.

[2]章惠民.煙草商業系統物流線路優化研究與應用[J].中國煙草學報，2018，24（03）：100-105.

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

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

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

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

[7]李陽，范厚明，張曉楠，楊翔.隨機需求車輛路徑問題及混合變鄰域分散搜索算法求解[J].控制理論與應用，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]陳萍.啟發式算法及其在車輛路徑問題中的應用[D].北京交通大學，2009.

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