基于和聲搜索算法的多層級物流中心選址問題

湯杼彬

（北京交通大學(xué)海濱學(xué)院，河北 黃驊 061199）

1 引言

物流中心作為物流運(yùn)輸體系的重要基礎(chǔ)設(shè)施，對于整個(gè)物流網(wǎng)絡(luò)體系運(yùn)營效率的發(fā)揮具有重要意義。物流中心作為承接物流園區(qū)及末端配送節(jié)點(diǎn)的關(guān)鍵設(shè)施，其選址對于運(yùn)輸成本及運(yùn)輸效率具有至關(guān)重要的影響。特別是隨著我國電商產(chǎn)業(yè)的飛速推進(jìn)，如何快速滿足城市配送的要求，提升用戶的購物體驗(yàn)，有效滿足用戶的時(shí)效性需求，也是各個(gè)電商平臺及物流運(yùn)輸企業(yè)主要的戰(zhàn)略方向，經(jīng)濟(jì)合理地滿足用戶的服務(wù)水平要求也是物流運(yùn)輸發(fā)展的重點(diǎn)。而物流中心的位置不但能夠影響物流運(yùn)輸?shù)目偝杀荆瑫r(shí)也能對物流的整體服務(wù)水平產(chǎn)生重要影響。在此背景下，考慮服務(wù)水平的因素，研究物流中心選址問題具有重要的理論和現(xiàn)實(shí)意義。

目前在物流中心選址方面，國內(nèi)外很多學(xué)者已經(jīng)有了大量的研究成果：O'Kelly最先提出了樞紐選址的數(shù)學(xué)模型[1-2]；Campbell提出p-中位問題、p-hub中心問題、樞紐覆蓋問題等四種類型的樞紐選址問題[3]；尹莉考慮多式聯(lián)運(yùn)型物流網(wǎng)絡(luò)中不同運(yùn)輸方式的銜接成本與時(shí)間、樞紐點(diǎn)間貨物運(yùn)輸產(chǎn)生的規(guī)模經(jīng)濟(jì)效益和服務(wù)時(shí)間的約束，建立了多式聯(lián)運(yùn)型物流網(wǎng)絡(luò)的貨運(yùn)樞紐選址模型[4]；李振宇在介紹GIS網(wǎng)絡(luò)分析技術(shù)的基礎(chǔ)上，重點(diǎn)分析了影響城市物流配送中心選址的若干因素。結(jié)合鮑姆爾-沃爾夫法的選址思想，提出了基于GIS的城市配送中心選址模型，并對模型進(jìn)行了實(shí)證分析[5]。通過對以上研究成果的分析可知，物流中心的選址研究中首先未考慮服務(wù)的差異，不同的物流服務(wù)對物流中心選址所產(chǎn)生的影響亦有較大的不同，同時(shí)現(xiàn)有的研究中也沒有從用戶需求的角度出發(fā)，而是從建設(shè)成本及運(yùn)輸成本最小化的角度著手選擇物流中心節(jié)點(diǎn)，這容易導(dǎo)致在當(dāng)前的配送體系中，難以滿足用戶時(shí)效性的需求，從而在未來的市場競爭中逐漸失去競爭力。因此，本文考慮運(yùn)輸服務(wù)和用戶需求對物流中心選址的影響，以時(shí)效性作為服務(wù)水平的重要評判要素，構(gòu)建了基于服務(wù)水平的物流中心選址模型，并采用和聲搜索算法進(jìn)行求解，從而為運(yùn)輸需求導(dǎo)向下的物流中心選址提供一定的決策依據(jù)。

2 物流中心選址模型

2.1 符號定義

（1）參數(shù)。I為物流園區(qū)集合，i∈I；J為末端配送節(jié)點(diǎn)的集合，j∈J；K為物流中心備選節(jié)點(diǎn)的集合，k∈K；cik為節(jié)點(diǎn)i與k之間的單位運(yùn)輸費(fèi)用；dik為節(jié)點(diǎn)i與節(jié)點(diǎn)k之間的運(yùn)輸距離；N為物流中心的總數(shù)量；W為區(qū)域內(nèi)重要OD對的集合，w∈W；Ow、Dw分別為OD對w的起點(diǎn)及終點(diǎn)；pw為OD對w的最短路徑為0-1參數(shù)，當(dāng)OD對w的最短路徑經(jīng)過節(jié)點(diǎn)i、k所構(gòu)成的弧段時(shí)為1，否則為0；tik為節(jié)點(diǎn)i與節(jié)點(diǎn)k之間的運(yùn)輸時(shí)間。

（2）決策變量。xk為0-1決策變量，表示物流中心備選節(jié)點(diǎn)k是否為物流中心，如果節(jié)點(diǎn)k為物流中心，則xk=1，否則xk=0；yik為0-1決策變量，表示物流園區(qū)i是否與備選物流中心k相連，如果兩者相連，則yik=1，否則yik=0；ykj為0-1決策變量，表示備選物流中心k是否與末端配送節(jié)點(diǎn)j相連，如果兩者相連，則ykj=1，否則ykj=0。

2.2 物流中心選址模型

不同物流服務(wù)間最大的差異突出表現(xiàn)為運(yùn)輸時(shí)間和運(yùn)輸費(fèi)用的差異，在此也以運(yùn)輸時(shí)間及運(yùn)輸費(fèi)用表征各物流服務(wù)。此外為了縮小問題的求解規(guī)模，在此考慮物流中心選址影響因素，將可能的物流中心節(jié)點(diǎn)放入物流中心備選集合中，即最終的物流中心只能是物流中心備選集合中的部分節(jié)點(diǎn)，從而有效縮小了解空間。在此基礎(chǔ)上，以滿足用戶的時(shí)效性需求為前提，并考慮物流中心與物流園區(qū)及配送節(jié)點(diǎn)之間的對應(yīng)關(guān)系，構(gòu)建物流中心選址模型，具體模型如下：

上述模型中，式（1）為模型的目標(biāo)函數(shù)，表示運(yùn)輸費(fèi)用最小化；式（2）-式（9）為模型約束，約束（2）為物流中心選址數(shù)量約束；約束（3）和約束（4）為聯(lián)鎖關(guān)系約束，即物流園區(qū)i與備選物流中心k相連，則節(jié)點(diǎn)k必為物流中心節(jié)點(diǎn)；約束（5）表示對于每一個(gè)物流園區(qū)，至少有一個(gè)物流中心節(jié)點(diǎn)與其相連接；約束（6）表示對于每一個(gè)末端配送節(jié)點(diǎn)，至少有一個(gè)物流中心與其相連接；約束（7）表示對于重點(diǎn)OD需求，應(yīng)該滿足其運(yùn)輸時(shí)限性要求；約束（8）及約束（9）為決策變量的邏輯約束。

3 求解算法

考慮服務(wù)水平的物流中心選址模型為0-1線性規(guī)劃模型，在此采用和聲搜索算法進(jìn)行求解。和聲搜索算法是根據(jù)音樂師創(chuàng)制音樂的過程而形成的一種啟發(fā)式算法[6]，該算法對于求解0-1規(guī)劃問題具有較好的求解效果，此外該算法也具有原理簡單、實(shí)現(xiàn)容易的特點(diǎn)。

3.1 和聲編碼

由于模型的決策變量主要有三個(gè)，分別為xk、yik及ykj，但是xk與yik及ykj分別存在連鎖關(guān)系約束（3）和（4），即通過決策變量yik及ykj的值也可獲取xk的值，因此初始解主要由yik及ykj的決策值構(gòu)成，yik的決策值為一矩陣，其元素個(gè)數(shù)與物流園區(qū)的個(gè)數(shù)及備選物流中心點(diǎn)的個(gè)數(shù)有關(guān)，同理ykj的元素個(gè)數(shù)與末端配送節(jié)點(diǎn)的個(gè)數(shù)及備選物流中心點(diǎn)的個(gè)數(shù)相關(guān)，初始解結(jié)構(gòu)如圖1所示。

圖1 初始解結(jié)構(gòu)示意圖

3.2 新和聲生成

新和聲的生成質(zhì)量將直接關(guān)系到該算法的求解質(zhì)量，在新和聲的生成中共采用兩種策略：第一種策略為采用和聲記憶庫中的決策值，第二種為隨機(jī)變異策略。假設(shè)生成的新和聲為新和聲生成的步驟為：設(shè)置和聲記憶庫選擇概率為Pr，以為例，則該音調(diào)以Pr的概率從和聲記憶庫中隨機(jī)選擇相同位置的音調(diào)，否則以1-Pr的概率隨機(jī)生成；具體的操作如以下公式所示。

定義了該算法的關(guān)鍵步驟后，和聲搜索算法的詳細(xì)步驟見文獻(xiàn)[7]，在此不做詳述。

4 算例分析

為了驗(yàn)證模型及算法的有效性，在此采用如圖2所示的網(wǎng)絡(luò)對模型及算法進(jìn)行驗(yàn)證。其中該網(wǎng)絡(luò)中共有4 個(gè)物流園區(qū)節(jié)點(diǎn)，6 個(gè)物流中心備選節(jié)點(diǎn)，10個(gè)末端配送節(jié)點(diǎn)，算例中需要的相關(guān)參數(shù)見表1。

圖2 物流運(yùn)輸網(wǎng)絡(luò)示意圖

表1 各節(jié)點(diǎn)之間的距離、時(shí)間及費(fèi)用參數(shù)

在此基礎(chǔ)上，通過計(jì)算上述重點(diǎn)OD對前5條K短路，驗(yàn)證其是否滿足運(yùn)到期限的約束，從而得到重點(diǎn)OD對的起點(diǎn)及終點(diǎn)所途經(jīng)的備選物流中心節(jié)點(diǎn)集合，即在滿足運(yùn)到期限的前提下，重點(diǎn)OD起終點(diǎn)只能途經(jīng)備選集合中的節(jié)點(diǎn)才能滿足運(yùn)到期限的約束，這將有效的縮小問題的求解規(guī)模。得到的重點(diǎn)OD對起終點(diǎn)所對應(yīng)的備選物流中心集合見表2。

表2 重點(diǎn)OD對的備選物流中心集合信息

通過對重點(diǎn)OD對的預(yù)處理操作，能夠有效的縮小解空間，在此基礎(chǔ)上將重點(diǎn)OD對的備選集合信息寫入初始解結(jié)構(gòu)中，并設(shè)置和聲記憶庫規(guī)模l=10；最大創(chuàng)作次數(shù)Tmax=200，和聲記憶庫選擇概率Pr=0.7，設(shè)置物流中心數(shù)量N=4，采用和聲搜索算法計(jì)算得到目標(biāo)函數(shù)值為1050，物流中心節(jié)點(diǎn)分別為K2、K4、K5、K6。物流中心與物流園區(qū)及末端配送節(jié)點(diǎn)的連接關(guān)系如圖3所示。

圖3 物流中心位置與分配關(guān)系示意圖

5 結(jié)論

物流中心選址問題是物流體系規(guī)劃中的關(guān)鍵環(huán)節(jié)，其對于降低物流運(yùn)輸成本、提升配送時(shí)效性具有重要作用。本文考慮物流園區(qū)及末端配送節(jié)點(diǎn)對物流中心選址的影響，構(gòu)建了基于服務(wù)水平的多層次物流中心選址模型，并根據(jù)模型的特點(diǎn)采用和聲搜索算法進(jìn)行求解，最后采用一算例驗(yàn)證了模型及算法的適用性，為物流中心的選址提供一定的決策依據(jù)，但是模型中對多交通方式之間服務(wù)的差異還缺少考慮，這也是下一步研究的方向。