劉長石，黃福華

（湖南商學(xué)院 工商管理學(xué)院，長沙 410205）

混合啟發(fā)式算法的多產(chǎn)品正向/逆向物流網(wǎng)絡(luò)設(shè)計(jì)

劉長石，黃福華

（湖南商學(xué)院 工商管理學(xué)院，長沙 410205）

文章探討了一個(gè)多產(chǎn)品的二階段的正向/逆向物流配送網(wǎng)絡(luò)設(shè)計(jì)問題，即在有配送量限制的各個(gè)生產(chǎn)企業(yè)地址已知、客戶地址已知、客戶需求量與回收量不確定的條件下來確定配送/回收中心地址與規(guī)模，使該物流網(wǎng)絡(luò)總費(fèi)用最小。并設(shè)計(jì)了混合啟發(fā)式算法與二階段轉(zhuǎn)載算法來解決該問題。計(jì)算結(jié)果表明該算法的具有很好的效果。

混合啟發(fā)式算法；禁忌搜索算法

0 引言

企業(yè)產(chǎn)品正向/逆向物流網(wǎng)絡(luò)設(shè)計(jì)提供了一個(gè)用來模擬企業(yè)生產(chǎn)與物流活動(dòng)的有效工具。一般來說，為了達(dá)到企業(yè)的長期戰(zhàn)略目標(biāo)，企業(yè)產(chǎn)品正向/逆向物流網(wǎng)絡(luò)設(shè)計(jì)問題包括了生產(chǎn)企業(yè)的規(guī)模和地址選擇、配送/回收中心的規(guī)模與地址確定、產(chǎn)品供應(yīng)量、配送決策和資源最優(yōu)配置等方面。本文探討了一個(gè)多產(chǎn)品的二階段的正向/逆向物流配送網(wǎng)絡(luò)設(shè)計(jì)問題，即在有配送量限制的各個(gè)生產(chǎn)企業(yè)地址已知、客戶地址已知、客戶需求量與回收量不確定的條件下來確定配送/回收中心地址與規(guī)模，同時(shí)考慮用機(jī)會(huì)成本和存儲(chǔ)成本來處理需求量的不確定性，用處理成本來處理回收量的不確定性，使該物流網(wǎng)絡(luò)總費(fèi)用最小，符合實(shí)際需要。該問題包括配送/回收中心選址、各產(chǎn)品從生產(chǎn)企業(yè)配送到配送中心、各產(chǎn)品從配送中心運(yùn)輸?shù)娇蛻襞c各產(chǎn)品從客戶回收到回收中心等方面的決策問題。

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

1 模型

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

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

基于以上的假設(shè),我們構(gòu)建了如下的多產(chǎn)品二階段正向/逆向物流配送網(wǎng)絡(luò)設(shè)計(jì)模型。

模型參數(shù)說明:

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

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

K 生產(chǎn)企業(yè)集,k=1,…，f

L 產(chǎn)品集,l=1,…，g

P 被選擇的地址的數(shù)量

Dil客戶i∈I對(duì)產(chǎn)品l∈L的需求量

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

Bk生產(chǎn)企業(yè)k∈K配送量限制

cijl單位產(chǎn)品l∈L從配送中心j∈J配送到客戶i∈I運(yùn)輸費(fèi)用

tjkl單位產(chǎn)品l∈L從生產(chǎn)企業(yè)k∈K配送到配送中心j∈J運(yùn)輸費(fèi)用

rijl單位產(chǎn)品l∈L從客戶i∈I回收到回收中心j∈J運(yùn)輸費(fèi)用

決策變量說明：

目標(biāo)函數(shù)中的第一部分代表產(chǎn)品從各配送中心配送到各客戶的總費(fèi)用；第二部分代表產(chǎn)品從各生產(chǎn)企業(yè)配送到各配送中心的總費(fèi)用；第三部分代表回收產(chǎn)品從客戶回收到回收中心的總費(fèi)用；第四部分代表當(dāng)企業(yè)配送量多于客戶需求時(shí)配送中心的多余產(chǎn)品的存儲(chǔ)費(fèi)用；第五部分指當(dāng)回收產(chǎn)品量大于回收中心處理能力是多余回收產(chǎn)品的處理費(fèi)用；第六部分指當(dāng)客戶需求被部分滿足時(shí)的機(jī)會(huì)成本。

約束（1）保證每類產(chǎn)品滿足每個(gè)客戶，產(chǎn)品回收量小于回收中心容量；約束（2）和（4）分別代表生產(chǎn)企業(yè)容量限制、配送/回收中心容量限制，而且對(duì)每類產(chǎn)品沒有特殊的體積要求；約束（3）保證每個(gè)配送中心配送量小于或者等于企業(yè)配送到配送中心產(chǎn)品量；約束（5）指要確定配送/回收中心的數(shù)量；約束（6）保證每個(gè)客戶只能由一個(gè)配送中心配送；約束（7）保證企業(yè)總配送量必須小于備選配送中心的總?cè)萘肯拗疲患s束（8）和（9）分別代表各變量的非負(fù)限制。

2 混合遺傳算法

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

步驟1：差異性

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

步驟2：可行性

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

步驟3：構(gòu)造參考集

參考集中包括了一組高質(zhì)量的最有差異性的解。用b1代表的高質(zhì)量的解的標(biāo)準(zhǔn)是基于目標(biāo)函數(shù)值，即選擇比較低的總費(fèi)用的解作為高質(zhì)量的解。為了選擇b2代表的差異性的解，我們使用兩個(gè)解之間的距離作為差異性的標(biāo)準(zhǔn)。首先我們把高質(zhì)量的解加入?yún)⒖技?，然后我們從群體中選擇當(dāng)前沒有在參考集中的解距離是最大或者最小的解作為最具有差異性的解加入?yún)⒖技校钡轿覀冞x擇了所有的差異性的解。

步驟4：子集產(chǎn)生器

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

步驟5：解組合

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

步驟6：參考集更新

取得一個(gè)新的解之后，我們要確定該解是否該加入?yún)⒖技?。如果新解的目?biāo)值比參考集中的任意解要低，刪除參考集中目標(biāo)值最差的解，同時(shí)把新解加入?yún)⒖技?；否則我們檢查新解的差異性，計(jì)算新解與參考集中的每一個(gè)解的距離，如果如果新解的距離比參考集中的任意解要長，刪除參考集中距離最短的解，同時(shí)把新解加入?yún)⒖技?。如果新解沒有滿足這兩個(gè)條件，新解不能加入?yún)⒖技?，我們轉(zhuǎn)移到下一個(gè)子集來產(chǎn)生另外的新解。如果參考集被更新，算法返回到步驟4去產(chǎn)生新的子集。當(dāng)參考集不能進(jìn)一步更新時(shí)，算法結(jié)束同時(shí)取得了最優(yōu)解。下面我們使用禁忌搜索算法來改良分散搜索算法取得的結(jié)果。

步驟7：禁忌搜索算法

禁忌搜索算法一般是用來解決組合優(yōu)化問題，例如固定費(fèi)用的運(yùn)輸問題,車輛問題。它廣義化了基本的局部搜索過程，當(dāng)最終解達(dá)到最佳狀態(tài)時(shí)搜索過程停止。在禁忌搜索算法的基本應(yīng)用中，禁忌搜索算法列表具有短期記憶功能，能避免訪問相同的解?；谟洃浀牟呗钥梢栽O(shè)立重要的性能改良前提。在這種框架下，禁忌搜索算法提供了一個(gè)避開局部最優(yōu)的機(jī)會(huì)來訪問解空間中的更大的子集。

前面我們?yōu)橛懻摰膯栴}提供了一個(gè)二進(jìn)制向量解z=(z1,…，zn)，zj∈{0,1},j∈J。由于禁忌搜索算法使用臨域β和φ偶對(duì)交換方法，β代表已經(jīng)選用的地址集合，φ代表不被選用的地址集合，臨域的偶對(duì)移動(dòng)交換對(duì)應(yīng)于同時(shí)改變zj，j∈β的值為0，改變zj，j∈φ的值為1。禁忌搜索移動(dòng)限制被用來預(yù)防循環(huán)訪問和重復(fù)訪問先前已經(jīng)訪問過的解。在我們的實(shí)現(xiàn)方法中，我們把用偶對(duì)交換取得的一個(gè)解分類作為一個(gè)列表，如果它相當(dāng)于關(guān)閉一個(gè)先前已經(jīng)被選的配送/回收中心。這說明了列表狀態(tài)對(duì)于一個(gè)已經(jīng)選用的配送/回收中心來說不是永久的。我們用列表使用期限來標(biāo)記已經(jīng)選用的配送/回收中心在列表中的迭代次數(shù)。本文選擇固定的列表使用期限，即新選定的配送/回收中心必須在列表中有一定的迭代次數(shù)。

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

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

3 計(jì)算結(jié)果

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

圖1 啟發(fā)式二階段轉(zhuǎn)載算法偽碼

表1 測試數(shù)據(jù)集最優(yōu)解運(yùn)行時(shí)間

表2 混合遺傳算法計(jì)算結(jié)果比較

為了測試混合啟發(fā)式算法的性能和效率，我們隨機(jī)產(chǎn)生了一系列的測試數(shù)據(jù)（表1），數(shù)據(jù)范圍從小規(guī)模到中等規(guī)模以及大規(guī)模。在表1中我們還報(bào)告了每個(gè)集合中的10個(gè)問題的最優(yōu)解的平均時(shí)間與最大時(shí)間。這樣我們可以比較解的質(zhì)量和運(yùn)行時(shí)間。共考慮了5個(gè)數(shù)據(jù)集，每個(gè)數(shù)據(jù)集有10個(gè)實(shí)例。

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

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

4 結(jié)論和展望

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

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

本文中的方法如果經(jīng)過改進(jìn)，也可以用來解決確定生產(chǎn)企業(yè)和配送/回收中心地址的問題。

[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).

（責(zé)任編輯/浩 天）

TP301

A

1002－6487（2010）18－0168-04

國家科技支撐計(jì)劃項(xiàng)目（2006BAJ07B03）；高等學(xué)校博士點(diǎn)基金資助項(xiàng)目（20050532029）

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