物流包裝租賃系統(tǒng)配送庫存路徑模型與算法

李家斌，何世偉，刁丹丹，靳國偉，郭小樂

1.河南工程學(xué)院 商學(xué)院，鄭州451191

2.北京交通大學(xué) 綜合交通運(yùn)輸大數(shù)據(jù)應(yīng)用技術(shù)交通運(yùn)輸行業(yè)重點(diǎn)實(shí)驗(yàn)室，北京100044

3.鄭州科技學(xué)院 外國語學(xué)院，鄭州450064

在我國，各行各業(yè)普遍在生產(chǎn)和流通過程中使用了大量的一次性紙箱、鐵桶、木箱等物流包裝，這種落后的包裝使用方式不僅成為社會環(huán)境的負(fù)擔(dān)，也造成了巨大的資源和成本的浪費(fèi)。發(fā)展物流包裝租賃共享系統(tǒng)是解決這一問題的有效手段。

目前在我國市場上，已有多個(gè)物流包裝租賃系統(tǒng)，如中包精力、邦臣、招商路凱、無錫美捷、箱箱共用等，但由于我國的物流包裝租賃系統(tǒng)剛起步，還存在著服務(wù)站點(diǎn)和網(wǎng)絡(luò)不完善，標(biāo)準(zhǔn)化不足，空容器派送、回收調(diào)度復(fù)雜以及容器維修程序繁瑣，有關(guān)政策缺失等問題[1]。物流包裝租賃系統(tǒng)建立以后，對空包裝的合理分布以及對空包裝的配送與回收的集成優(yōu)化問題——庫存路徑問題（Inventory Routing Problem，IRP）的解決就成了日常運(yùn)營層面頻繁和迫切需要解決的問題。

國外對庫存路徑問題的研究是在20世紀(jì)80年代出現(xiàn)，它是車輛路徑問題（Vehicle Routing Problem，VRP）的擴(kuò)展，對車輛路徑問題、配送計(jì)劃和庫存決策進(jìn)行了綜合考慮[2]，在車輛路徑問題的空間維度上增加了時(shí)間維度，進(jìn)一步增加了路徑問題的復(fù)雜性。它是在滿足一定的約束條件下（如客戶需求的數(shù)量、時(shí)間、庫存量等約束），在計(jì)劃期內(nèi)針對多個(gè)需求客戶，確定給各客戶進(jìn)行庫存補(bǔ)充的數(shù)量和時(shí)間，并優(yōu)化車輛的運(yùn)輸路徑，使系統(tǒng)總成本最小或總效益最大的問題。VRP 模型只能解決某一天的車輛、路徑?jīng)Q策優(yōu)化問題，而IRP 可以解決更長時(shí)間的包含車輛路徑及庫存綜合優(yōu)化問題。

Coelho 等人[3]在2013 年對IRP 進(jìn)行了文獻(xiàn)綜述，總結(jié)了其主要擴(kuò)展形式、模型和算法，該作者關(guān)注的是問題的方法論，而Andersson 等人[4-5]進(jìn)行的綜述調(diào)查則是強(qiáng)調(diào)企業(yè)的實(shí)踐應(yīng)用。

IRP模型涉及的情況非常復(fù)雜，可以按照服務(wù)中心和客戶不同數(shù)目組成的拓?fù)浣Y(jié)構(gòu)（1-1，1-多-1，多-多）、貨物品種數(shù)（單品種，多品種）、客戶需求類型（確定，不確定）、庫存補(bǔ)貨方式（最大補(bǔ)貨，隨機(jī)補(bǔ)貨）、車輛型號（同型，異型）、成本（庫存成本，運(yùn)輸成本）、求解方法（精確算法，啟發(fā)式算法）等特征角度進(jìn)行具體分類，見文獻(xiàn)[6]。具體闡述如下：

在建立的模型類型方面，主要有類經(jīng)濟(jì)訂貨批量（EOQ-liked）模型、混合整數(shù)規(guī)劃模型和隨機(jī)動態(tài)規(guī)劃模型這三大類IRP 模型[7]。在模型的拓?fù)浣Y(jié)構(gòu)方面，大多數(shù)考慮兩層級1-多系統(tǒng)（1 個(gè)服務(wù)中心，多個(gè)客戶）為對象，三層級問題的研究也有所增加[8-12]。在模型的目標(biāo)方面，主要考慮的是費(fèi)用目標(biāo)，考慮低碳和多個(gè)目標(biāo)的研究也出現(xiàn)不少，如唐金環(huán)等人[13]的研究。關(guān)于貨物種類方面，多以單產(chǎn)品為主要研究對象，多產(chǎn)品研究成果較少[14]。在需求的特性方面，多以確定性需求問題為研究對象，隨機(jī)性需求研究也有不少[15-18]。在需求的周期性方面，單周期研究較多，多周期研究也有所增加[19-21]。大部分IRP研究仍然只是考慮客戶處庫存單一環(huán)節(jié)與運(yùn)輸?shù)恼蟽?yōu)化，考慮多環(huán)節(jié)庫存成本的研究也已出現(xiàn)[17]。

在模型的求解算法方面，可采用的算法有精確算法和啟發(fā)式算法，目前仍以啟發(fā)式算法為主要研究方向。采用的方法如禁忌搜索算法和改進(jìn)的Clarke-Wright 算法（C-W算法）[10]、整合貪婪算法、遺傳算法以及禁忌算法思想的混合啟發(fā)式算法[22]、遺傳算法[23-24]、免疫算法[25]、模擬退火算法[26]等。

在結(jié)合的行業(yè)方面，有電廠燃煤運(yùn)輸-庫存問題[27]、分銷行業(yè)[28]、備件物流[29]、原油[30]、沿河子公司運(yùn)煤問題[31]、制造行業(yè)[32]、易腐品[33-[34]、汽車零部件[35]、救援物資[36]、軍事領(lǐng)域[37]等研究。

但在針對物流包裝租賃系統(tǒng)的配送庫存路徑問題研究方面，現(xiàn)有研究比較缺乏。國內(nèi)研究方面，筆者在中國知網(wǎng)數(shù)據(jù)庫以“物流包裝的配送與庫存”“托盤回收”“托盤配送”為關(guān)鍵字搜索共找到相關(guān)文章12 篇。其中3 篇是從運(yùn)輸問題模型的角度進(jìn)行空托盤調(diào)度模型的研究[38-41]，但沒有考慮車輛路徑的問題；有3篇文章考慮了路徑問題[42-44]，但都沒有考慮相關(guān)的庫存費(fèi)用。有些文章結(jié)合庫存、路徑進(jìn)行了研究[45]，但只考慮了服務(wù)中心的庫存控制問題，沒有考慮客戶點(diǎn)的庫存能力和費(fèi)用問題。在國外方面，筆者以“returnable transport items”+“routing”+“inventory”為關(guān)鍵字在ScienceDirect、Springer、Taylor &Francis 三大數(shù)據(jù)庫中搜索，共找到與本文研究主題物流包裝庫存與路徑集成優(yōu)化問題相關(guān)的有3篇文獻(xiàn)[46-48]，其他稍相關(guān)的是物流包裝的庫存控制或其他方面的研究[49-51]。但這些研究都是站在生產(chǎn)企業(yè)自我進(jìn)行采購包裝使用和回收的角度，未考慮容器租賃模式下的企業(yè)運(yùn)營與管理目標(biāo)和約束。

基于以上考慮，借鑒供應(yīng)商管理庫存（Vendor Managed Inventory，VMI）模式下庫存路徑模型[53]，本文建立了物流包裝租賃共享系統(tǒng)的庫存路徑問題優(yōu)化模型并設(shè)計(jì)了求解算法，結(jié)合算例分析對比了精確算法和設(shè)計(jì)算法的主要性能差異，以為物流包裝租賃共享系統(tǒng)日常運(yùn)營層面的庫存路徑問題的決策需求提供決策方法和依據(jù)。

1 問題描述及模型建立

1.1 物流包裝租賃共享系統(tǒng)

物流包裝租賃共享是指采用租賃的方式完成物流包裝社會化的共享，從而達(dá)到優(yōu)化社會資源配置，提高資源利用效率的一種共享經(jīng)濟(jì)形式。物流包裝租賃共享系統(tǒng)是向生產(chǎn)企業(yè)等提供物流包裝租賃、配送與回收、檢查、清洗維護(hù)到最后報(bào)廢等運(yùn)營與管理服務(wù)的服務(wù)運(yùn)作系統(tǒng)。該系統(tǒng)主要由物流包裝租賃企業(yè)及其信息平臺、租賃企業(yè)自有或加盟服務(wù)中心、有空包裝租賃需求或回收需求的客戶等組成。主要流程如圖1所示。

圖1 物流包裝租賃共享系統(tǒng)運(yùn)作流程Fig.1 Business flow of logistics package rental sharing system

1.2 物流包裝租賃共享系統(tǒng)的配送庫存路徑問題

物流包裝租賃共享系統(tǒng)一般由多個(gè)物流包裝租賃服務(wù)中心和有空物流包裝回收和配送需求的客戶點(diǎn)組成。但考慮到現(xiàn)階段我國物流包裝種類較多，物流作業(yè)條件較差，回收的物流包裝一般不能直接供客戶使用，而是需要先回到服務(wù)中心進(jìn)行檢查和清洗，合格的才可以配送給需求客戶，這就要求將整個(gè)物流包裝回收和配送的過程分開進(jìn)行考慮。這里只考慮從1 個(gè)租賃服務(wù)中心出發(fā)，給多個(gè)有空包裝配送需求的客戶點(diǎn)進(jìn)行空包裝的配送而產(chǎn)生的配送庫存路徑問題。

該問題具體描述如下：某個(gè)租賃企業(yè)下屬的1個(gè)服務(wù)中心為多個(gè)有空包裝租賃需求的客戶點(diǎn)（如多個(gè)生產(chǎn)企業(yè)）提供空包裝租賃及配送服務(wù)。各客戶點(diǎn)都具有一定的空包裝庫存和一定的空包裝庫存能力。各客戶點(diǎn)對空包裝的需求有周期化的特征。為滿足各個(gè)客戶點(diǎn)的空包裝租賃需求和使總配送運(yùn)輸和庫存成本最低，該租賃服務(wù)中心以若干個(gè)客戶需求周期為計(jì)劃期，需要確定計(jì)劃期里的各個(gè)周期每次配送服務(wù)的客戶對象、配送數(shù)量，并針對每輛車的服務(wù)區(qū)域?qū)ふ易顑?yōu)的配送路徑。具體如圖2所示。

圖2 物流包裝租賃共享系統(tǒng)庫存路徑問題示意圖Fig.2 Schematic diagram of IRP of logistics package rental sharing system

1.3 模型建立

1.3.1 模型假設(shè)及變量、參數(shù)定義

在借鑒文獻(xiàn)[3，47]部分模型基礎(chǔ)上，考慮一對多的二層級物流包裝租賃共享服務(wù)系統(tǒng)，其包含1個(gè)物流包裝租賃服務(wù)中心和多個(gè)有空包裝租賃需求的客戶點(diǎn)。初始周期車輛從租賃服務(wù)中心出發(fā)，為各個(gè)客戶點(diǎn)配送空物流包裝，當(dāng)配送任務(wù)結(jié)束后返回租賃服務(wù)中心。依據(jù)物流包裝租賃企業(yè)業(yè)務(wù)實(shí)際，做如下假設(shè)：

（1）租賃服務(wù)中心僅提供一種規(guī)格的物流包裝。租賃數(shù)目為整數(shù)個(gè)（如以10 個(gè)為單位），這主要是考慮到物流包裝的標(biāo)準(zhǔn)化趨勢、低價(jià)值特性以及充分利用車輛的裝載能力，也考慮到物流包裝租賃共享企業(yè)的服務(wù)便利性。租賃服務(wù)中心初始庫存有限，庫存能力無限。這是因?yàn)闉榭蛻籼峁┌b租賃服務(wù)的一般是物流包裝租賃企業(yè)的各個(gè)區(qū)域或地區(qū)服務(wù)中心，所以其必然具有不同的包裝初始庫存。

（2）在所考慮的計(jì)劃期開始時(shí)已確定各個(gè)客戶點(diǎn)的空物流包裝配送需求情況，這是基于較長時(shí)間的預(yù)測做的合理假設(shè)。

（3）每個(gè)客戶點(diǎn)空物流包裝庫存能力有限制，這主要考慮到客戶點(diǎn)的倉儲場地等資源限制。每個(gè)周期配送給各個(gè)客戶點(diǎn)的空物流包裝數(shù)量不能大于其庫存能力限制。

（4）已知租賃服務(wù)中心和客戶點(diǎn)處的初始庫存量。整個(gè)決策計(jì)劃期間，為避免缺貨，設(shè)定租賃服務(wù)中心和客戶點(diǎn)處的庫存量均不能為負(fù)值。

（5）各租賃服務(wù)中心具有的配送車輛車型、裝載能力相同且數(shù)目有限制。在每個(gè)服務(wù)周期里派出的每輛配送車輛最多可實(shí)施一次空包裝配送工作。

（6）每個(gè)服務(wù)周期內(nèi)，每一個(gè)客戶點(diǎn)最多可以送貨1次?？紤]到物流包裝的低價(jià)值性和充分利用車容，假設(shè)每次配送時(shí)補(bǔ)充物流包裝的數(shù)量必須達(dá)到庫存能力的最大值（即補(bǔ)充數(shù)量等于庫存能力－現(xiàn)有庫存）。

（7）為方便分析考慮，將運(yùn)輸固定費(fèi)用和倉儲固定費(fèi)用分?jǐn)偟竭\(yùn)輸費(fèi)率和庫存持有費(fèi)率中。因此本文考慮決策目標(biāo)時(shí)只考慮變動運(yùn)輸成本和庫存持有成本兩個(gè)成本，這對于追求企業(yè)經(jīng)濟(jì)利益的物流包裝租賃企業(yè)來說，該目標(biāo)是合適的?？紤]決策的變量包括每個(gè)服務(wù)周期內(nèi)每輛車訪問哪些客戶點(diǎn)、給各個(gè)客戶點(diǎn)配送的物流包裝數(shù)量及車輛配送時(shí)的配送路線。

涉及的參數(shù)定義及決策變量如表1所示。

表1 主要參數(shù)和變量Table 1 Main parameters and variables

1.3.2 數(shù)學(xué)模型

在該模型中，式（1）是目標(biāo)函數(shù)，表示最小化物流包裝共享系統(tǒng)的空包裝過程中整個(gè)計(jì)劃期內(nèi)所有成本，其中第1部分表示運(yùn)輸成本，第2部分表示庫存成本。式（2）表示租賃服務(wù)中心的初始庫存非負(fù)約束。約束（3）和（4）分別表示租賃服務(wù)中心、各個(gè)客戶點(diǎn)的庫存流量平衡約束，其中（3）表示服務(wù)中心第t期的庫存等于其第t-1 期的庫存減去第t期所有車輛給所有客戶的送出包裝量，約束（4）的含義類似，不同的是針對的是客戶點(diǎn)。約束（5）表示各客戶點(diǎn)的庫存水平非負(fù)。式（6）表示每個(gè)周期結(jié)束時(shí)各個(gè)客戶點(diǎn)的庫存量不能大于其庫存容量限制。約束條件（7）和（8）確保在時(shí)間段t交付給客戶i的數(shù)量在客戶服務(wù)時(shí)不會超過該客戶的可用庫存容量，否則將為0。約束（9）意味著空包裝配送量不能超過車輛容量。約束（10）表示每個(gè)周期配送給客戶點(diǎn)的空包裝總量不能超過該客戶最大庫存能力。約束（11）前半邊等式表示各頂點(diǎn)處進(jìn)入車輛數(shù)目和離開車輛數(shù)目相等，后半邊等式則表示車輛如果進(jìn)入或離開某客戶，則該客戶必進(jìn)行了配送服務(wù)。約束（12）表示每個(gè)周期每輛車從租賃服務(wù)中心出發(fā)配送至多一次。約束（13）表示每個(gè)周期每個(gè)客戶至多接受配送服務(wù)一次。約束（14）表示每個(gè)車輛沿其行走路線進(jìn)行送貨的一致性約束并且消除子回路，即若車輛k在t周期時(shí)服務(wù)完客戶i后緊接著服務(wù)客戶j，則服務(wù)完i后已配送的包裝總數(shù)量等于服務(wù)完客戶j后已配送的包裝總數(shù)量減去對客戶j的送貨量，否則服務(wù)完i后已配送的包裝總數(shù)量必小于服務(wù)完客戶j后已配送的包裝總數(shù)量加上車輛容量。約束（15）表示周期t車輛k訪問客戶點(diǎn)i后的送貨量取值約束。約束（16）和（17）是非負(fù)性和整數(shù)約束。

2 算法設(shè)計(jì)及算法性能對比

所建模型為混合整數(shù)規(guī)劃模型，如果模型的數(shù)據(jù)規(guī)模較小，可直接采用一些已有的數(shù)學(xué)優(yōu)化軟件如GUROBI、CPLEX等進(jìn)行求解。但稍大規(guī)模的問題則需要設(shè)計(jì)啟發(fā)式算法求解。關(guān)于利用遺傳算法（Genetic Algorithm，GA）求解庫存路徑問題（IRP），已有一些相關(guān)研究[53-54]。借鑒文獻(xiàn)[53-54]的部分思路利用，本文設(shè)計(jì)利用帶精英保留的改進(jìn)遺傳算法求解。算法的總體框架如圖3所示。

圖3 IRP模型遺傳算法求解流程Fig.3 Genetic algorithm solution process of IRP model

圖中，種群規(guī)模用Popsize表示；種群進(jìn)化的最大代數(shù)用G表示；交叉概率用Pc表示；變異概率用Pm表示。

2.1 染色體的編碼及空物流包裝配送數(shù)量的計(jì)算

本文利用一個(gè)N（客戶數(shù)）行T（周期數(shù)）列的0-1矩陣排列來組成一個(gè)染色體，染色體中的每個(gè)基因用來表示，該基因可取0或1，表示每個(gè)空物流包裝配送客戶i是否在周期t訪問，若表示l染色體表示的租賃客戶i在周期t進(jìn)行了空包裝的配送；同理，若，表示租賃客戶i在周期t不進(jìn)行空包裝的配送。

若在周期t給租賃客戶i處進(jìn)行空物流包裝的配送，則其配送的數(shù)量要看在其后的周期是否還對其進(jìn)行配送。假設(shè)在之后的周期t′(t′＞t)再一次進(jìn)行配送，那么周期t時(shí)給客戶i處配送的物流包裝數(shù)量至少是該客戶i在周期[t,t′-1]之間對空物流包裝的需求之和。

表2給出了包括7個(gè)包裝租賃客戶（客戶1～客戶7），4 個(gè)周期（T1～T4）的染色體編碼矩陣、物流包裝配送量矩陣及對應(yīng)的庫存量計(jì)算矩陣算例。

表2 染色體編碼方式及配送量計(jì)算舉例Table 2 Example of chromosome coding method and delivery quantity calculation

通過表2 可以看出，在第1 個(gè)周期時(shí)所有的客戶都沒有進(jìn)行空包裝的配送。對客戶2來說，其分別在第2、3 周期進(jìn)行了訪問，配送包裝量分別為8 件、16 件，最后客戶2各周期末的庫存量分別是0件、0件、8件、0件。

2.2 初始種群的產(chǎn)生

初始種群需要產(chǎn)生設(shè)置的種群數(shù)(Popsize)個(gè)染色體，每個(gè)染色體都由N×T個(gè)0或1的基因組成，其中N為客戶點(diǎn)數(shù)，T為周期數(shù)。初始種群的產(chǎn)生具體步驟如下（以某個(gè)染色體l為例）。

構(gòu)造完初始種群后，接著可計(jì)算每個(gè)染色體對應(yīng)的物流包裝配送數(shù)量矩陣。因?yàn)樵跇?gòu)造初始染色體時(shí)有一些基因值是隨機(jī)產(chǎn)生的，所以若全部根據(jù)上述的步驟計(jì)算物流包裝配送數(shù)量矩陣，則有可能會產(chǎn)生不可行的解或者給某一個(gè)客戶處配送的空包裝容器超過車輛載重要求。故而這里對空包裝配送量的計(jì)算方法進(jìn)行如下調(diào)整：

2.3 適應(yīng)度函數(shù)值和種群評價(jià)

適應(yīng)度函數(shù)值是判斷種群中染色體個(gè)體優(yōu)良的指標(biāo)，遺傳算法通過適應(yīng)度函數(shù)值的變化選擇來找到最優(yōu)解。本文采用經(jīng)典的輪盤賭選擇法，由于輪盤賭選擇法需要適應(yīng)度函數(shù)值非負(fù)，且適應(yīng)度函數(shù)值的大小說明了染色體個(gè)體的優(yōu)劣。

由于本文計(jì)算的目標(biāo)函數(shù)是總成本，并不能將其直接作為適應(yīng)度函數(shù)值，但是可以用一個(gè)足夠大的數(shù)M（取M＝1 000）除去目標(biāo)函數(shù)然后將其作為適應(yīng)度函數(shù)，即并且為了方便對每個(gè)目標(biāo)函數(shù)值的適應(yīng)度值進(jìn)行區(qū)分，加大選擇的壓力，本文還將對每個(gè)適應(yīng)度函數(shù)進(jìn)行15次乘方處理，即將F(x)＝f(x)15作為計(jì)算的適應(yīng)度，從而擴(kuò)大適應(yīng)度的差異。

此外，本文利用精英保存策略將適應(yīng)度最好的個(gè)體直接遺傳給子代。即若某代種群中獲得的最優(yōu)染色體的適應(yīng)度比上代染色體中的最優(yōu)染色體適應(yīng)度差，則將上代染色體中的最優(yōu)染色體直接遺傳給下一代種群中最優(yōu)染色體。

關(guān)于各個(gè)周期每個(gè)車輛的路徑成本，本文采用C-W節(jié)約算法[55]產(chǎn)生每個(gè)周期的路徑并進(jìn)行路徑費(fèi)用的計(jì)算。具體操作方法如下：

首先，找到每個(gè)染色體編碼中各個(gè)周期t中需訪問的客戶點(diǎn)i，將所有需訪問的客戶點(diǎn)（設(shè)為m個(gè)）加上初始服務(wù)中心后形成一個(gè)由m＋1 頂點(diǎn)組成的集合。然后，添加已知的各個(gè)客戶點(diǎn)的需求（服務(wù)中心需求設(shè)為0）及其相互間的距離矩陣，結(jié)合車輛容量Qk，利用C-W節(jié)約算法解決一個(gè)多車輛路徑問題。最后，獲得各個(gè)車輛訪問的客戶點(diǎn)順序集并計(jì)算其總的運(yùn)輸距離及費(fèi)用。

2.4 改進(jìn)交叉算子

交叉表示將所選擇的兩個(gè)父代染色體的一部分基因進(jìn)行互換，然后得到子代染色體的方法。交叉算子對遺傳算法全局搜索能力有關(guān)鍵影響。本文的交叉算子采用如下交叉方式：針對某一代利用輪盤賭方法選中的兩個(gè)父代染色體P1和P2，隨機(jī)生成一個(gè)大小為N×1的由0和1組成的行向量如[1 0 0 1 0 0 1]，該行向量中的第i個(gè)值決定了其子代1 的每個(gè)客戶i＝1,2,…,N相應(yīng)周期的基因值的獲得繼承關(guān)系，即假如i位置取值為0，則子染色體C1中相應(yīng)第i個(gè)客戶相應(yīng)行的基因值完全從父代1獲得。假如i的位置取值為1，則子染色體C1中相應(yīng)第i個(gè)客戶相應(yīng)行的基因值完全從父代2獲得。反之，可以用相似的原理創(chuàng)建子代C2，即假如i位置取值為0，則子染色體C2中相應(yīng)第i個(gè)客戶相應(yīng)行的基因值完全從父代2獲得，假如i的位置取值為1，則子染色體C2中相應(yīng)第i個(gè)客戶相應(yīng)行的基因值完全從父代1獲得。

2.5 變異算子

為防止算法過早收斂，GA 一般通過變異算子來實(shí)現(xiàn)種群多樣性。它一般是通過挑選某些染色體部分基因進(jìn)行變異來具體實(shí)現(xiàn)，變異的方式有多種。本文采取基本位變異的形式，即隨機(jī)選擇某個(gè)染色體的某一位基因，將它的基因值由0變成1或者由1變成0。

原種群中的染色體在交叉和變異操作完后需要檢查該染色體的可行性以免出現(xiàn)如不符合車輛裝載容量限制和庫存不足導(dǎo)致缺貨的情況。采用如下方式調(diào)整：如果，則置；t＞1 且客戶i在周期t以前都未進(jìn)行過訪問，則置；此外，在交叉和變異操作結(jié)束后再利用2.2節(jié)中的方法計(jì)算物流包裝配送數(shù)量矩陣。當(dāng)?shù)螖?shù)達(dá)到G代時(shí)，算法結(jié)束。G的取值依據(jù)不同情況可進(jìn)行調(diào)整，此處取值為100。

3 數(shù)值實(shí)驗(yàn)結(jié)果及與算法結(jié)果討論

為比較精確算法和啟發(fā)式算法的性能，本文采用文獻(xiàn)[45]中稍小規(guī)模（7個(gè)客戶）和稍大規(guī)模（20個(gè)客戶）的兩個(gè)算例進(jìn)行數(shù)值實(shí)驗(yàn)分析。設(shè)某物流包裝租賃企業(yè)在某區(qū)域內(nèi)有1個(gè)服務(wù)中心服務(wù)7（20）個(gè)客戶，考慮4個(gè)周期為1個(gè)計(jì)劃期，每個(gè)決策周期內(nèi)對各個(gè)客戶點(diǎn)進(jìn)行物流包裝配送服務(wù)。其中0表示租賃服務(wù)中心，1～7（1～20）表示有空包裝容器需求的客戶點(diǎn)。服務(wù)中心有配送車3（4）輛，每一輛車最多裝載25件空包裝，單件空包裝在租賃服務(wù)中心和客戶點(diǎn)的單位周期保管費(fèi)用分別為0.1 和0.3 歐元。單件物流包裝單位距離的變動運(yùn)輸費(fèi)用為0.04 歐元。需通過優(yōu)化獲得各客戶點(diǎn)最優(yōu)的服務(wù)策略及最合理的車輛運(yùn)輸線路以實(shí)現(xiàn)總費(fèi)用最小。

將以上模型和數(shù)據(jù)編制程序，利用優(yōu)化軟件CPLEX 12.4在Intel Core i5-2450M CPU＠2.50 GHz，內(nèi)存3 GB，Windows7操作系統(tǒng)環(huán)境下，采用CPLEX默認(rèn)求解配置，稍小規(guī)模模型求解運(yùn)行時(shí)間為208 s，總費(fèi)用為75.88歐元，庫存費(fèi)45 歐元，運(yùn)輸費(fèi)30.88 歐元。具體配送方案和庫存變化情況如表3所示。

表3 小規(guī)模算例模型CPLEX求解結(jié)果Table 3 CPLEX solution of small-scale data model

采用本文設(shè)計(jì)的一般遺傳算法編碼進(jìn)行求解，其中種群數(shù)為100，代數(shù)為50，交叉率Pc＝0.9,變異率Pm＝0.2，利用Matlab7.10編制程序，在Intel Core i5-2450M CPU＠2.50 GHz，內(nèi)存3 GB，Windows7 操作系統(tǒng)環(huán)境下，模型的小規(guī)模算例的一般遺傳算法（GA）求解結(jié)果如表4所示。

表4 小規(guī)模算例模型IGA求解結(jié)果Table 4 IGA solution of small-scale data model

從表4中可以看出，模型的小規(guī)模算例的一般遺傳算法求解運(yùn)行時(shí)間為36.13 s，總費(fèi)用為77.44歐元，庫存費(fèi)49.6 歐元，運(yùn)輸費(fèi)27.84 歐元，優(yōu)化的送貨路徑為6條，共需派出6 個(gè)車次，最多在周期2 同時(shí)派出3 輛車，算法在第11代獲得最優(yōu)解。迭代過程如圖4所示。

圖4 小規(guī)模算例模型GA求解迭代過程Fig.4 Iterative process of GA to solve small-scale data model

模型的稍大規(guī)模算例的一般遺傳算法求解結(jié)果和迭代圖如圖5和表5所示。

圖5 稍大規(guī)模算例GA求解迭代過程Fig.5 Iterative process of GA to solve large-scale data model

從表5中可以看出，模型的稍大規(guī)模算例的一般遺傳算法求解運(yùn)行時(shí)間為183.19 s，總費(fèi)用為101.38歐元，庫存費(fèi)63.2歐元，運(yùn)輸費(fèi)38.18歐元，優(yōu)化的送貨路徑為8條，共需派出8個(gè)車次，最多在周期2同時(shí)派出4輛車，算法在第35代獲得最優(yōu)解。

表5 稍大規(guī)模算例模型IGA求解結(jié)果Table 5 IGA solution of large-scale data model

針對較?。?個(gè)客戶）和稍大規(guī)模（20個(gè)客戶）算例，將一般遺傳算法與CPLEX 精確算法進(jìn)行比較，見表6所示，其中g(shù)ap=（CPLEX求解上界－CPLEX求解下界）/CPLEX 求解上界，Gap=（啟發(fā)式算法次優(yōu)總費(fèi)用－CPLEX最優(yōu)解或上界）/CPLEX最優(yōu)解或上界。

從表6 中可以看出，稍大規(guī)模下，CPLEX 在默認(rèn)配置情況下，求解1 800 s，未獲得最優(yōu)解，只獲得可行解，和本文設(shè)計(jì)的一般遺傳算法比較，雖然設(shè)計(jì)算法求解的結(jié)果較CPLEX求解的結(jié)果稍差，但運(yùn)行時(shí)間大大縮短，說明了本文設(shè)計(jì)的啟發(fā)式算法的有效性。

表6 模型IGA與CPLEX求解比較Table 6 IGA solution comparison with CPLEX

另外，將本文設(shè)計(jì)的改進(jìn)遺傳算法（IGA）與文獻(xiàn)[53]設(shè)計(jì)的遺傳算法（GA）利用以上算例和參數(shù)，分別求解10次比較其平均值，見表7所示。

表7 模型IGA與GA求解結(jié)果比較Table 7 GA solution comparison with IGA

從表7中可以看出，論文設(shè)計(jì)的遺傳算法和改進(jìn)遺傳算法小規(guī)模算例求解運(yùn)行時(shí)間平均分別為50.32 s 和42.35 s，平均總費(fèi)用分別為77.51 歐元和77.43 歐元，平均Gap 分別為2.1%和2.0%；稍大規(guī)模算例求解運(yùn)行時(shí)間平均分別為153.2 s和107.0 s，平均總費(fèi)用分別為102.7歐元和101.6歐元，平均Gap分別為8.1%和7.0%。總體來看，改進(jìn)遺傳算法求解迭代收斂更快，時(shí)間減少43%，優(yōu)化效果更好。

4 結(jié)論與展望

本文結(jié)合物流包裝租賃共享系統(tǒng)的空包裝配送流程，建立了總成本費(fèi)用最小的物流包裝租賃共享系統(tǒng)庫存路徑問題優(yōu)化模型。采用稍小和稍大規(guī)模的兩個(gè)算例，利用CPLEX 軟件和設(shè)計(jì)帶精英保留的遺傳算法進(jìn)行了對比求解分析，驗(yàn)證了設(shè)計(jì)的啟發(fā)式算法和模型的有效性。本文對模型和庫存控制的研究只考慮了空包裝的配送過程，沒有考慮空包裝的回收過程，后期將考慮對空包裝的回收過程進(jìn)行集成建模，并設(shè)計(jì)算法求解。