混合啟發式算法的多產品正向/逆向物流網絡設計

劉長石，黃福華

（湖南商學院 工商管理學院，長沙 410205）

混合啟發式算法的多產品正向/逆向物流網絡設計

劉長石，黃福華

（湖南商學院 工商管理學院，長沙 410205）

文章探討了一個多產品的二階段的正向/逆向物流配送網絡設計問題，即在有配送量限制的各個生產企業地址已知、客戶地址已知、客戶需求量與回收量不確定的條件下來確定配送/回收中心地址與規模，使該物流網絡總費用最小。并設計了混合啟發式算法與二階段轉載算法來解決該問題。計算結果表明該算法的具有很好的效果。

混合啟發式算法；禁忌搜索算法

0 引言

企業產品正向/逆向物流網絡設計提供了一個用來模擬企業生產與物流活動的有效工具。一般來說，為了達到企業的長期戰略目標，企業產品正向/逆向物流網絡設計問題包括了生產企業的規模和地址選擇、配送/回收中心的規模與地址確定、產品供應量、配送決策和資源最優配置等方面。本文探討了一個多產品的二階段的正向/逆向物流配送網絡設計問題，即在有配送量限制的各個生產企業地址已知、客戶地址已知、客戶需求量與回收量不確定的條件下來確定配送/回收中心地址與規模，同時考慮用機會成本和存儲成本來處理需求量的不確定性，用處理成本來處理回收量的不確定性，使該物流網絡總費用最小，符合實際需要。該問題包括配送/回收中心選址、各產品從生產企業配送到配送中心、各產品從配送中心運輸到客戶與各產品從客戶回收到回收中心等方面的決策問題。

相對于已有的文獻來說，本文不同之處有：首先考慮了一個兩階段多產品的正向/逆向物流配送與回收問題，而且采取了機會成本與存儲成本來處理客戶需求量的不確定性，用處理成本來處理回收量的不確定性。其次提出了用混合啟發式算法來解決這個問題，包括分散搜索算法與帶有記憶特性的禁忌搜索算法，在合理的運行時間內取得了很好的解決效果。最后，模型中正向物流與逆向物流共享運輸網絡，配送中心和回收中心可以建立在共同的備選地址上，模型體現了最大可能性地節約配送與回收成本，而且符合了不同規模的實際企業的需要。

1 模型

本文探討了一個多產品的二階段的正向/逆向物流配送網絡設計問題，即在有容量限制的各生產企業地址已知、客戶地址已知、客戶需求已知與回收量不確定情況下的條件下來確定配送/回收中心地址與規模。第一階段是產品根據配送中心的需求從生產企業配送產品到配送中心；第二階段是產品在配送中心根據客戶需求進行分揀與組合，再配送到具體客戶，同時一些回收產品從客戶處回收到有容量限制的回收中心。正向物流與逆向物流共享運輸網絡，配送中心和回收中心可以建立在共同的備選地址上。

本文假設各種產品種類和體積、各個生產企業地址與客戶地址都是已知的，而且存在一系列的有容量限制的配送/回收中心備選地址。同時假設存在多產品流，客戶需求是持續的，每一個客戶和每類產品都是不同的，需求量和回收量是獨立變量。如果需求只是被部分滿足就要考慮機會成本；如果生產企業配送量超過了配送中心的存儲容量限制必須考慮存儲成本；如果產品回收量超過了回收中心的存儲容量就要考慮處理成本。該模型以最小的代價來確定各產品量從各生產企業配送到各配送中心，然后再從配送中心配送到客戶；同時確定各產品回收量從客戶回收到回收中心。

基于以上的假設,我們構建了如下的多產品二階段正向/逆向物流配送網絡設計模型。

模型參數說明:

I 客戶集,i=1,…，m

J 備選地址集,j=1,…，n

K 生產企業集,k=1,…，f

L 產品集,l=1,…，g

P 被選擇的地址的數量

Dil客戶i∈I對產品l∈L的需求量

Wj配送中心j∈J容量限制

Bk生產企業k∈K配送量限制

cijl單位產品l∈L從配送中心j∈J配送到客戶i∈I運輸費用

tjkl單位產品l∈L從生產企業k∈K配送到配送中心j∈J運輸費用

rijl單位產品l∈L從客戶i∈I回收到回收中心j∈J運輸費用

決策變量說明：

目標函數中的第一部分代表產品從各配送中心配送到各客戶的總費用；第二部分代表產品從各生產企業配送到各配送中心的總費用；第三部分代表回收產品從客戶回收到回收中心的總費用；第四部分代表當企業配送量多于客戶需求時配送中心的多余產品的存儲費用；第五部分指當回收產品量大于回收中心處理能力是多余回收產品的處理費用；第六部分指當客戶需求被部分滿足時的機會成本。

約束（1）保證每類產品滿足每個客戶，產品回收量小于回收中心容量；約束（2）和（4）分別代表生產企業容量限制、配送/回收中心容量限制，而且對每類產品沒有特殊的體積要求；約束（3）保證每個配送中心配送量小于或者等于企業配送到配送中心產品量；約束（5）指要確定配送/回收中心的數量；約束（6）保證每個客戶只能由一個配送中心配送；約束（7）保證企業總配送量必須小于備選配送中心的總容量限制；約束（8）和（9）分別代表各變量的非負限制。

2 混合遺傳算法

混合遺傳算法是對規模為n的二進制向量Z進行運算，向量Z代表備選的配送/回收中心地址。對每一個向量Z的實例，我們解決了相應的有容量限制的轉載優化問題，算法程序用C++實現。對一個特定的解向量Z，我們使用增加有容量限制的轉載問題最優目標值的方法來得到它的目標函數值。分散搜索算法的參數有群體大小2*hmax、hmax表示差異性參數，b1表示質量，b2表示差異性數目。參數的選擇對分散搜索算法性能有很重要的作用。我們隨機選擇我們算法的初始解，一個二進制向量Z，作為分散搜索開始的一個輸入數據，從而我們可以得到差異性解的群體。

步驟1：差異性

這一步產生重要的而且又不同的試探解。在這個過程中，我們用解空間的樣品系統地識別各種高質量的試探解。Glover提供了兩種不同的生成二元解向量作為試探解的方法。我們綜合使用了他的兩種方法，令zj為二元解向量z的一個元素，z作為種子解，發生器產生2*hmax個新試探解。根據Burcu B.Keskin and Halit Uster,第一個hmax個試探解Z1,…，Zhmax是用增量參數k和下列公式產生的k=0,1,…，[n,/h].增量參數k的最大值與h值交換。第二個hmax個試探解用關系式1-Zh,h=1,…，hmax，取得。

步驟2：可行性

一般來時，群體中的試探解是不可行的，因為它們違反了約束2和約束5。首先這些初始解可能不滿足約束5，因為選擇的配送/回收地址的數目要小于或者大于指定的P值。如果是小于指定的P值我們就從還沒有選擇的地址中隨機的選擇，否則就要從已經選定的地址中隨機的刪除一些，一直到等于指定的P值為止。其次我們要考慮試探解的總配送量。如果配送/回收地址總配送量小于總客戶需求量，我們從未選定的地址中隨機選擇一個，從已經選擇的地址中隨機關閉一個，一直進行地址交換直到配送/回收地址總配送量滿足總客戶需求量為止，這樣也沒有違反約束5。我們一直這樣修正群體中的試探解的可行性，直到它們都可行為止。

步驟3：構造參考集

參考集中包括了一組高質量的最有差異性的解。用b1代表的高質量的解的標準是基于目標函數值，即選擇比較低的總費用的解作為高質量的解。為了選擇b2代表的差異性的解，我們使用兩個解之間的距離作為差異性的標準。首先我們把高質量的解加入參考集中，然后我們從群體中選擇當前沒有在參考集中的解距離是最大或者最小的解作為最具有差異性的解加入參考集中，直到我們選擇了所有的差異性的解。

步驟4：子集產生器

在這一步中產生參考集的子集，它們將被結合成新的解。我們使用三個子集產生器去取得規模不同的子集，即類型II,類型III和類型IV。類型 II的子集對應于從參考集中取出的每一對解。類型 III的子集由最高質量的解和一對參考集中的解組成。類型 IV的子集從參考集中選擇兩個最高質量的解，并把它們與剩下的每一對解結合在一起。

步驟5：解組合

使用線性組合方法把每一個子集中的試探解組合成新解。我們使用解的目標值的倒數作為試探解的系數，所以具有較低目標值的那些解擁有了較高的權重。無疑地組合解中的每一部分都具有部分值。為了取得合理的解，我們把最終解的每一部分四舍五入成最接近的二進制值。

步驟6：參考集更新

取得一個新的解之后，我們要確定該解是否該加入參考集。如果新解的目標值比參考集中的任意解要低，刪除參考集中目標值最差的解，同時把新解加入參考集；否則我們檢查新解的差異性，計算新解與參考集中的每一個解的距離，如果如果新解的距離比參考集中的任意解要長，刪除參考集中距離最短的解，同時把新解加入參考集。如果新解沒有滿足這兩個條件，新解不能加入參考集，我們轉移到下一個子集來產生另外的新解。如果參考集被更新，算法返回到步驟4去產生新的子集。當參考集不能進一步更新時，算法結束同時取得了最優解。下面我們使用禁忌搜索算法來改良分散搜索算法取得的結果。

步驟7：禁忌搜索算法

禁忌搜索算法一般是用來解決組合優化問題，例如固定費用的運輸問題,車輛問題。它廣義化了基本的局部搜索過程，當最終解達到最佳狀態時搜索過程停止。在禁忌搜索算法的基本應用中，禁忌搜索算法列表具有短期記憶功能，能避免訪問相同的解。基于記憶的策略可以設立重要的性能改良前提。在這種框架下，禁忌搜索算法提供了一個避開局部最優的機會來訪問解空間中的更大的子集。

前面我們為討論的問題提供了一個二進制向量解z=(z1,…，zn)，zj∈{0,1},j∈J。由于禁忌搜索算法使用臨域β和φ偶對交換方法，β代表已經選用的地址集合，φ代表不被選用的地址集合，臨域的偶對移動交換對應于同時改變zj，j∈β的值為0，改變zj，j∈φ的值為1。禁忌搜索移動限制被用來預防循環訪問和重復訪問先前已經訪問過的解。在我們的實現方法中，我們把用偶對交換取得的一個解分類作為一個列表，如果它相當于關閉一個先前已經被選的配送/回收中心。這說明了列表狀態對于一個已經選用的配送/回收中心來說不是永久的。我們用列表使用期限來標記已經選用的配送/回收中心在列表中的迭代次數。本文選擇固定的列表使用期限，即新選定的配送/回收中心必須在列表中有一定的迭代次數。

禁忌搜索算法使用表T=(T1,…，Tn)，Tj代表配送/回收中心 j,j∈J 的列表使用期限。 如果 Tj＞0，j∈J，那么配送/回收中心j∈J就被加入列表；否則不會被加入列表。在每一次迭代中，當一個候選解產生了一個新的被選解j∈J，Tj被賦予列表使用期限，列表中其余的解的使用期限就要減去1。這就是一種短時記憶，列表反映了解在最近的時間內是如何被訪問的。本文中即使沒有記憶的中間體，我們也取得了高質量的解集。期望標準用來控制禁忌搜索限制，能避免遺漏沒有訪問的解。即使是在涉及偶對移動的一次迭代中新取得的解，如果它符合期望標準，也能被接收為一個合法的解。在我們的研究中，期望標準規定，如果一個涉及偶對移動的解擁有比已知的解更好的目標值，這時可以忽略列表狀態。否則，如果期望標準沒有被滿足，繼續用未被選的集進行下一次迭代。

我們注意到混合啟發式算法需要比較長的計算時間，尤其是在大規模的算例。在配送/回收中心已經被上述混合算法確定后，我們設計了啟發式二階段轉載算法（圖1）來改進該算法。該啟發式算法最少減少了一半的計算時間。令j^∈J為被選配送/回收中心地址集，故|j^|=P。該算法中我們先解決配送/回收中心與客戶之間的配送問題，然后用這客戶需求作為配送中心的需求，再解決了生產企業與配送中心之間的配送問題。

3 計算結果

為了解決我們提出的問題，本文使用C++語言和傳統的位串編碼方法開發混合啟發式程序，運行環境是PIV 3.2G和1 GB內存。每個決策變量按照計劃排列，每段位串編碼占11位 （表1）。第一位代表生產企業的數目范圍。第二位表示備選配送/回收中心的數目范圍。第三位代表生產企業配送到配送中心的配送量的數目范圍。第四位指配送中心配送到客戶的配送量的數目范圍。第五位指每個配送中心的容量限制范圍。第六位指每個回收中心從客戶回收產品到回收中心的量的范圍。第七位指每個回收中心的容量限制范圍。第八位指需求沒有被滿足的數目范圍。第九位指超過需求的量的范圍。第十位代表超過回收中心的回收量的范圍。第十一位P代表需要被選的配送/回收中心的數目。

圖1 啟發式二階段轉載算法偽碼

表1 測試數據集最優解運行時間

表2 混合遺傳算法計算結果比較

為了測試混合啟發式算法的性能和效率，我們隨機產生了一系列的測試數據（表1），數據范圍從小規模到中等規模以及大規模。在表1中我們還報告了每個集合中的10個問題的最優解的平均時間與最大時間。這樣我們可以比較解的質量和運行時間。共考慮了5個數據集，每個數據集有10個實例。

我們總結了混合啟發式算法的比較結果（表2），即比較帶禁忌搜索改進算法的分散搜索算法和沒有改進算法的分散搜索算法。在本實驗中，分散搜索算法的參數是hmax=10，b1=1,b2=2重新開始的數目是6，即每個實例求解5次，每次使用不同的種子解，報告最優解與計算的總時間。為了顯示該啟發式算法的效率，我們還報告了平均最優解差距、最大最優解差距與最優解的數目。為了比較混合遺傳算法的速度，在每個數據集中我們提供了平均運行時間和最大運行時間，運行時間以秒計算。

對于很小規模與中等規模的問題，如數據集1、2和5，具有改進算法的混合遺傳算法與沒有改進算法的平均差距不到1%。對于大規模的問題，如數據集3和4，平均差距可以高達4.5%，最高可以到6.5%。而且在更大規模的問題上，可以取得更好的效果。

4 結論和展望

本文研究了一個多產品的二階段正向/逆向物流配送與回收網絡設計問題。雖然已經有很多相關文獻，據作者所知，很少有關于混合啟發式算法且綜合正向/逆向物流網絡的文獻，更不用說用機會成本和存儲成本來處理客戶需求量的不確定性，用處理成本來處理回收量的不確定性。本文力圖設計有效的高性能的混合啟發式算法 （分散搜索算法和禁忌搜索算法）來解決該問題。經過實驗發現，該算法運行良好，即使是在大規模的問題上也取得了很好的效果。同時我們發現，分散搜索算法經過禁忌搜索算法改進以后，性能得到了很大的提高。

為了改善混合啟發式算法的運行時間，我們還設計了啟發式二階段轉載算法，該算法至少減少了一半左右的運行時間，同時如果改變參數Pk為Pkl，該算法可以適用生產企業有產品容量限定的情況。

本文中的方法如果經過改進，也可以用來解決確定生產企業和配送/回收中心地址的問題。

[1]B.B.Keskin,H.Uster.A Scatter Search-based Heuristic to Locate Capacitated Transshipment Points[J].Computers and Operations Research,in press.

[2]M.Laguna,R.Marti.Scatter Search:Methodology and Implementations in C[M].Kluwer Academic Publishers,Boston,MA,2003.

[3]F.Glover,Tabu Search Part I[J].ORSA Journal of Computing,1989,(1).

[4]F.Glover,Tabu search Part II[J].ORSA Journal of Computing,1990,(2).

[5]F.Glover,Tabu Search for Nonlinear and Parametric Optimization[J].Discrete Applied Mathematics,1994,(49).

[6]Burcu B.Keskin,Halit Uster.Meta-heuristic Approaches with Memory and Evolution for a Multi-product Production/distribution System Design Problem[J].European Journal of Operational Research,2007,(182).

[7]M.Gendreau,A.Hertz,G.Laporte,A Tabu Search Heuristic for the Vehicle Routing Problem[J].Management Science,1994,(40).

[8]F.Glover,M.Laguna,Tabu Search[M].Kluwer Academic Publishers,Norwell,MA.1997.

[9]E.Rolland,D.A.Schilling,J.R.Current.An Efficient Tabu Search Procedure for the P-median Problem[J].European Journal of Operational Research,1996,(96).

[10]M.Sun.A Tabu Search HeuristicProcedureforSolvingthe Transportation Problem with ExclusionarySide Constraints[J].Journal of Heuristics,1998,(4).

[11]F.Glover.A Template for Scatter Search and Path Relinking,Artificial Evolution,Lecture Notes in Computer Science,1997.

[12]S.S.Erenguc,N.Simpson,A.J.Vakharia.Integrated production/distribution Planning in Supply Chains:An Invited Review[J].European Journal of Operational Research,1999.

[13]A.M.Geoffrion,R.F.Powers.20 Years of Strategic Distributionsystem Design–an Evolutionary Perspective[J].Interfaces,1995,(5).

（責任編輯/浩 天）

TP301

A

1002－6487（2010）18－0168-04

國家科技支撐計劃項目（2006BAJ07B03）；高等學校博士點基金資助項目（20050532029）

劉長石（1975-），男，湖南邵陽人，博士，研究方向：國際貿易，物流與供應鏈。