帶時(shí)間窗口的超市物流配送不確定規(guī)劃模型

吳攀峰， 劉慧清， 彭 錦

(1.湖北大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院，湖北 武漢 430062； 2.黃岡師范學(xué)院，不確定系統(tǒng)研究所，湖北 黃岡 438000)

?

帶時(shí)間窗口的超市物流配送不確定規(guī)劃模型

吳攀峰， 劉慧清， 彭 錦

(1.湖北大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院，湖北 武漢 430062； 2.黃岡師范學(xué)院，不確定系統(tǒng)研究所，湖北 黃岡 438000)

主要研究了不確定環(huán)境下帶時(shí)間窗口的超市物流配送問(wèn)題。假設(shè)超市的日需求量是不確定變量,在配送過(guò)程中車輛的行駛時(shí)間也為不確定變量。為了最小化配送過(guò)程中車輛行駛時(shí)間,建立了不確定機(jī)會(huì)約束模型。然后應(yīng)用不確定變量的運(yùn)算法則對(duì)模型進(jìn)行等價(jià)轉(zhuǎn)化,并為求解模型設(shè)計(jì)了算法。最后給出了一個(gè)數(shù)值算例來(lái)說(shuō)明模型的實(shí)際應(yīng)用。

物流配送;時(shí)間窗口;不確定變量;機(jī)會(huì)約束

0 引言

物流是現(xiàn)代社會(huì)企業(yè)價(jià)值創(chuàng)造和價(jià)值實(shí)現(xiàn)的關(guān)鍵環(huán)節(jié),是企業(yè)生產(chǎn)經(jīng)營(yíng)的生命線之一。物流配送是實(shí)現(xiàn)物流的基礎(chǔ)體現(xiàn)。隨著物流的快速發(fā)展,物流配送在整個(gè)物流系統(tǒng)中的作用越來(lái)越顯著。在物流配送過(guò)程中,配送中心一般要向多個(gè)客戶配送,在各客戶對(duì)配送中心服務(wù)滿意的情況下,讓配送成本最小是配送中心所關(guān)注的問(wèn)題。這里的配送成本主要考慮的是配送車輛在行駛過(guò)程中的能源消耗,在一定程度上,車輛的行駛時(shí)間與能源消耗正相關(guān)。因此縮短配送時(shí)間已成為當(dāng)今一個(gè)重要的研究課題。

在物流配送過(guò)程中,存在很多不確定信息。需求商品特征的不確定性、需求客戶時(shí)間的不確定性、道路的不確定性和配送車輛的不確定性等都會(huì)影響配送效率。而配送時(shí)間是影響配送效率的首要因素之一。在近些年里,從配送時(shí)間對(duì)物流配送的影響方面,一些學(xué)者對(duì)物流配送進(jìn)行了研究,并建立了物流配送模型。賀國(guó)先和劉凱[1]充分考慮所運(yùn)載貨物交付時(shí)間的緊迫性,構(gòu)造了滿載約束的數(shù)學(xué)期望模型。李延暉等[2]在基于時(shí)間競(jìng)爭(zhēng)的環(huán)境下,建立了多源配送系統(tǒng)隨機(jī)模型。王紹仁和馬祖軍[3]針對(duì)震后緊急響應(yīng)階段路網(wǎng)中斷和救援物資需求不確定性,建立了航空物流中的隨機(jī)定位路線安排問(wèn)題模型。張樂(lè)誠(chéng)和楊信豐[4]考慮城市物流配送中道路交叉口時(shí)間延誤的影響,構(gòu)造了有車輛載重、多車型和時(shí)間窗約束的隨機(jī)機(jī)會(huì)約束規(guī)劃模型。

上述學(xué)者都采用的是概率論的方法對(duì)配送時(shí)間進(jìn)行研究,然而利用概率理論的基本前提是得到的概率分布與實(shí)際頻率非常接近。由于配送過(guò)程中的各種因素的不確定性,在實(shí)際情況下我們往往很難得到樣本數(shù)據(jù)。當(dāng)我們不能得到充足樣本數(shù)據(jù)時(shí),一般會(huì)向這方面的專家請(qǐng)教,請(qǐng)他們給出事件發(fā)生的信度。通常情況下,這個(gè)信度與概率測(cè)度在運(yùn)算上有較大的差別。Liu[5]2007年提出了基于規(guī)范性、對(duì)偶性、次可加性和乘積測(cè)度公理下的不確定理論可以用來(lái)處理這種信度。作為不確定理論在實(shí)際生活中的重要應(yīng)用,Liu[5]在不確定理論的公理化體系下提出了不確定規(guī)劃[6],用于解決機(jī)器排序、車輛路徑和工程進(jìn)度等實(shí)際問(wèn)題。近年來(lái), 不確定規(guī)劃作為一種數(shù)學(xué)工具被很多學(xué)者所應(yīng)用。Zhang和Peng[7]研究了中國(guó)郵路問(wèn)題,從不同的角度給出了三個(gè)不確定規(guī)劃模型。Gao[8]根據(jù)不同的滿意度建立了兩個(gè)不確定規(guī)劃模型來(lái)解決網(wǎng)絡(luò)單設(shè)施選址問(wèn)題。Ding[9]以糧食的質(zhì)量、工廠建立費(fèi)用作為不確定變量建立不確定規(guī)劃來(lái)解決糧食供應(yīng)鏈問(wèn)題。Jiang[10]建立了不確定機(jī)會(huì)約束規(guī)劃模型解決集裝箱空箱調(diào)運(yùn)問(wèn)題。Rong[11]將儲(chǔ)存成本、缺貨成本、訂購(gòu)單位成本看作不確定變量構(gòu)造了兩個(gè)經(jīng)濟(jì)訂貨批量不確定規(guī)劃模型。Zhang和Peng[12]提出α-最優(yōu)指派的概念后建立了α-最優(yōu)不確定規(guī)劃模型來(lái)解決最優(yōu)指派問(wèn)題等。

本文在不確定環(huán)境下, 以超市的日需求量和配送過(guò)程中車輛的行駛時(shí)間為不確定變量,建立了以配送時(shí)間最短為目標(biāo)的不確定規(guī)劃模型, 并設(shè)計(jì)了一種算法對(duì)模型進(jìn)行求解, 最后為了模型的實(shí)際應(yīng)用給出了一個(gè)數(shù)值算例。

本文的結(jié)構(gòu)框架如下：第一節(jié)簡(jiǎn)要介紹不確定理論的基礎(chǔ)知識(shí), 第二節(jié)描述了以超市的日需求量和車輛的行駛時(shí)間為不確定變量的物流配送問(wèn)題, 且為解決此問(wèn)題建立了不確定規(guī)劃模型, 第三節(jié)利用不確定理論的基礎(chǔ)知識(shí)將不確定規(guī)劃模型轉(zhuǎn)化為一般的數(shù)學(xué)模型, 并給出了模型的算法, 第四節(jié)給出了一個(gè)數(shù)值算例。最后對(duì)本文做了小結(jié)。

1 不確定理論基礎(chǔ)知識(shí)

定義1 (Liu[5]) 設(shè)Γ是一個(gè)非空集合,L是Γ上的一個(gè)σ-代數(shù),L中的每一個(gè)元素Λ稱為一個(gè)事件。若L上的集函數(shù)M滿足以下公理：

公理1(規(guī)范性) 對(duì)全集Γ,有M{Γ}=1;

公理2(對(duì)偶性) 對(duì)任意的事件Λ∈L,有M{Λ}+M{ΛC}=1;

定義1 (Liu[5]) 不確定變量ξ的分布函數(shù)Φ定義為Φ(x)=M{γ|ξ(γ)≤x},x∈R,它的反函數(shù)Φ-1稱為不確定變量ξ的逆分布。

定理2 (Liu[5]) 設(shè)ξ和η是具有有限的期望值的兩個(gè)獨(dú)立的不確定變量。對(duì)于任意實(shí)數(shù)a和b, 我們有E[aξ+bη]=aE[ξ]+bE[η]。

定理3 (Liu[13]) 一個(gè)實(shí)值函數(shù)f(x1,x2,…,xn)被稱為嚴(yán)格增的,若當(dāng)xi≤yi,i=1,2,…,n時(shí),有f(x1,x2,…,xn)≤f(y1,y2,…,yn)，當(dāng)xi

2 問(wèn)題描述與模型的建立

2.1 問(wèn)題描述

某配送中心與該市的多個(gè)超市合作進(jìn)行物流配送服務(wù)。據(jù)實(shí)際情況,各個(gè)超市點(diǎn)的日需求量是不確定的。配送中心每天根據(jù)各超市點(diǎn)的需求向其執(zhí)行配送任務(wù),因?yàn)槌菂^(qū)不同時(shí)段不同的路況,以及天氣情況的影響,配送過(guò)程中車輛的行駛時(shí)間也是不確定的。在各超市點(diǎn)對(duì)配送中心服務(wù)滿意的前提下,考慮以上不確定因素的影響,車輛如何配送貨物使行駛時(shí)間最短,是本文要解決的問(wèn)題。

在配送過(guò)程中,為了不影響正常經(jīng)營(yíng),所有超市點(diǎn)設(shè)定了接受配送的時(shí)間窗口,即規(guī)定了配送車輛的到達(dá)時(shí)間范圍。已知配送中心配送的是可混裝的物資,并且運(yùn)載的貨物量都能滿足客戶需求。這里,配送中心有足夠的運(yùn)力可供調(diào)配車輛, 每輛車的一次載重量不能超過(guò)其額定載重量,而且每個(gè)超市點(diǎn)只能由一輛車服務(wù),每輛車最多使用一次,車輛行駛的每條路線的起點(diǎn)和終點(diǎn)都在配送中心。

在本文中,車輛的行駛時(shí)間和各超市點(diǎn)的日需求量是不確定的變量,并且假設(shè)它們都是獨(dú)立的。在建模之前,先介紹參數(shù)：

i=0為配送中心；i=1,2,…,n為超市點(diǎn)；k=1,2,…,m為車輛；ξi為超市點(diǎn)的日需求量,i=1,2,…,n；γi為ξi的不確定分布,i=1,2,…,n；ηij為車輛從超市點(diǎn)i到超市點(diǎn)j的行駛時(shí)間,i,j=0,1,2,…,n；Φij為ηij的不確定分布,i,j=0,1,2,…,n；Ck為車輛的載重量,與車型相關(guān),k=1,2,…,m；[ai,bi]為超市i接受配送的時(shí)間窗口,i=1,2,…,n。

本文描述的是帶時(shí)間窗口的超市物流配送問(wèn)題, 這里的配送過(guò)程用決策向量x,y,t來(lái)表示：x=(x1,x2,…,xn),整數(shù)向量,代表n個(gè)超市點(diǎn),其中1≤xi≤n,且當(dāng)i≠j時(shí),xi≠xj,這里i,j=1,2,…,n。

y=(y1,y2,…,ym-1),整數(shù)向量,代表車輛的使用情況,且y0≡0≤y1≤y2≤…≤ym-1≤n≡ym。對(duì)于每個(gè)k(1≤k≤m),若yk=yk-1,則車輛k不使用,若yk>yk-1,則車輛k使用。

t=(t1,t2,…,tk,…,tm),tk代表車輛k從配送中心出發(fā)的時(shí)間。

若車輛k被使用,在時(shí)刻tk從配送中心出發(fā),其配送路線為：0→xyk-1+1→xyk-1+2→…→xyk→0。

以上決策變量x,y,t可確保：

(1)每輛車最多使用一次。

(2)所有路線的起點(diǎn)與終點(diǎn)都是配送中心。

(3)每個(gè)超市點(diǎn)有且僅有一輛車服務(wù)。

(4)配送路線經(jīng)過(guò)每個(gè)超市點(diǎn), 且不重復(fù)。

用fi(x,y,t,η)表示車輛到達(dá)超市點(diǎn)i時(shí)的到達(dá)時(shí)間函數(shù),其中i=1,2,…,n。在這里不妨假設(shè)當(dāng)fi(x,y,t,η)在時(shí)間窗口的開始時(shí)刻ai之后時(shí),車輛可立即卸貨; 當(dāng)fi(x,y,t,η)在時(shí)間窗口的開始時(shí)刻ai之前時(shí),車輛要等到時(shí)刻ai才能卸貨。本文中車輛在超市點(diǎn)的卸貨時(shí)間忽略不計(jì)。

對(duì)車輛k,1≤k≤m,當(dāng)車輛k被使用,即yk>yk-1時(shí),有

fxyk-1+1(x,y,t,η)=tk+η0xyk-1+1

(1)

此時(shí)到達(dá)超市點(diǎn)xyk-1+1的時(shí)間fxyk-1+1(x,y,t,η)是不確定變量,其逆分布為

(2)

且

fxyk-1+j(x,y,t,η)=fxyk-1+j-1(x,y,t,η)∨axyk-1+j-1+ηxyk-1+j-1xyk-1+j

(3)

(4)

其中2≤j≤yk-yk-1。這個(gè)遞推過(guò)程能夠推出車輛k到達(dá)所有超市點(diǎn)時(shí)間的逆分布。

2.2 模型的建立

我們希望每個(gè)超市點(diǎn)i(1≤i≤n)都在接受配送的時(shí)間窗口[ai,bi]內(nèi)被服務(wù)(即車輛在時(shí)刻bi前到達(dá)超市點(diǎn)i處)的置信水平為α, 于是有以下機(jī)會(huì)約束：

M{fi(x,y,t,η)≤bi}≥α

(5)

由于居民在城區(qū)的分布密度不同, 各超市點(diǎn)每天貨物的需求量是不確定的。這里各種車輛的載重量為Ck,k=1,2,…,m, 則車輛所到達(dá)超市點(diǎn)的貨物需求量之和要小于車輛載重量。給定一個(gè)置信水平β, 有下面的機(jī)會(huì)約束：

(6)

令Tk(x,y,η)為車輛k在配送過(guò)程中的總行駛時(shí)間, 則

(7)

現(xiàn)建立超市物流配送的不確定規(guī)劃模型如下

(8)

其中α和β是給定的置信水平。

3 模型的轉(zhuǎn)化與算法

3.1 模型的轉(zhuǎn)化

上節(jié)給出了帶時(shí)間窗口的超市物流配送不確定規(guī)劃模型,其中含有很多不確定變量。如何求解此類不確定規(guī)劃模型? 一般情況下,我們希望將不確定規(guī)劃模型轉(zhuǎn)化為確定形式,從而對(duì)模型進(jìn)行簡(jiǎn)化。接下來(lái),我們主要討論模型的轉(zhuǎn)化問(wèn)題。

定理5 假設(shè)ξi和ηij是獨(dú)立的不確定變量, 且它們的不確定分布分別為Υi和Φij, 則模型(8)可以轉(zhuǎn)化為

(9)

(10)

證明 根據(jù)定理2,不確定變量期望值算子的線性性質(zhì)(10)顯然成立。

利用定義1,不確定變量的逆分布, 約束條件(5)等價(jià)于

(11)

且約束條件(6)等價(jià)于

(12)

定理得證。

3.2 算法

99算法是Liu[13]提出來(lái)的, 用來(lái)計(jì)算不確定變量中單調(diào)函數(shù)的不確定分布。

我們用表1來(lái)表示不確定變量ζi。

表1 不確定變量ζi的分布

步驟1 設(shè)E=0,j=1。

步驟3 若j<99, 令j←j+1，回到步驟2。

步驟4 得到E即為E[ζi]估計(jì)值。

由于模型(9)比較復(fù)雜, 用傳統(tǒng)的方法不能解決。下面給出求模型近似最優(yōu)解的一個(gè)算法。

算法

步驟1 輸入初始參數(shù)值n,m,Ck及目標(biāo)函數(shù)值S(此處S是一個(gè)足夠大的正數(shù)),令超市物流配送計(jì)劃x=0,y=0且t=0。

…

…

否則, 返回1;

步驟4 若S′

步驟5 重復(fù)第二步到第四步操作, 如此重復(fù)循環(huán)檢驗(yàn)直到滿足終止條件。

步驟6 輸出的最終結(jié)果(x;y;t)即為最優(yōu)解, 且S是最優(yōu)目標(biāo)函數(shù)值。

4 數(shù)值算例

作為模型的實(shí)際應(yīng)用,我們給出一個(gè)數(shù)值算例。黃岡市某配送中心向7個(gè)超市點(diǎn)提供配送服務(wù),用于配送的3輛車的載重量分別為C1=10,C2=14,C3=16,單位是噸。據(jù)實(shí)際情況,7個(gè)超市點(diǎn)的日需求量是不確定的,車輛在配送路途中,受車流量和紅綠燈等影響,行駛時(shí)間也是不確定的。假設(shè)超市的日需求量服從表2所示的之字形不確定分布ξi～Zi(a,b,c),i=1,2,…,7 。

表2 超市的日需求量ξi的之字形不確定分布Zi(a,b,c)

車輛的行駛時(shí)間服從正態(tài)不確定分布(單位：小時(shí))

Tij～N(|i-j|,1),i,j=0,1,2,…,7

其中當(dāng)i=j=0時(shí),Tij=0。

又已知7個(gè)超市點(diǎn)接受配送的時(shí)間窗口如表3所示

表3 各超市點(diǎn)接受配送的時(shí)間窗口

而且車輛在超市點(diǎn)接受配送的時(shí)間窗口內(nèi)到達(dá)的置信水平為0.9, 車輛所到達(dá)超市點(diǎn)的貨物需求量之和小于車輛載重量的置信水平為0.95。

根據(jù)以上給出的數(shù)值, 模型(9)即為

(13)

(14)

車輛1 配送中心→2→3→配送中心,出發(fā)時(shí)間6∶22;

車輛2 配送中心→1→配送中心, 出發(fā)時(shí)間5∶17;

車輛3 配送中心→4→5→6→7→配送中心, 出發(fā)時(shí)間7∶27,此時(shí)車輛最短行駛時(shí)間T=22。

5 結(jié)束語(yǔ)

本文基于不確定理論, 研究了不確定環(huán)境下帶時(shí)間窗口的超市物流配送問(wèn)題。在配送過(guò)程中, 超市點(diǎn)的日需求量和配送車輛的行駛時(shí)間是不確定變量, 為了最小化配送車輛的行駛時(shí)間, 建立了不確定規(guī)劃模型。又用不確定理論的基礎(chǔ)知識(shí)對(duì)該模型進(jìn)行轉(zhuǎn)化, 再給出了算法來(lái)解所建立的數(shù)學(xué)模型。最后用一個(gè)數(shù)值算例說(shuō)明了模型的實(shí)際應(yīng)用。文章只是研究了單個(gè)配送中心向各超市點(diǎn)運(yùn)送貨物的例子, 對(duì)于多個(gè)配送中心向超市點(diǎn)運(yùn)送貨物的問(wèn)題建模是今后值得深入思考的問(wèn)題。

[1] 賀國(guó)先,劉凱.優(yōu)化物流中心配送方案的遺傳算法[J].系統(tǒng)工程理論與實(shí)踐,2003,(4):76- 81.

[2] 李延暉,劉向,馬士華.基于時(shí)間約束的多源多品種隨機(jī)配送系統(tǒng)模型[J].科技管理創(chuàng)新,2006,(6):69-71.

[3] 王紹仁,馬祖軍.航空緊急配送中的隨機(jī)LRP模型及算法[J].計(jì)算機(jī)應(yīng)用,2010,30(12):3207-3210.

[4] 張樂(lè)誠(chéng),楊信豐.隨機(jī)時(shí)間約束的城市物流配送車輛路徑問(wèn)題研究[J].物流技術(shù),2005,(9):68-70.

[5] Liu B. Uncertainty theory[M]. 2nd ed. Berlin: Springer-Verlag, 2007.

[6] Liu B. Theory and practice of uncertain programming[M]. 2nd ed. Berlin: Springer-Verlag, 2009.

[7] Zhang B, Peng J. Uncertain programming model for Chinese postman problem with uncertain weights[J]. Industrial Engineering and Management Systems, 2012, 11(1): 18-25.

[8] Gao Y. Uncertain models for single facility location problems on networks[J]. Applied Mathematical Modeling, 2012, 36(6): 2592-2599.

[9] Ding S. A new uncertain programming model for grain supply chain design[J]. Information: An International Interdisciplinary Journal, 2013, 16(2): 1069-1076.

[10] Jiang G. An uncertain programming model of chance constrains for empty container allocation[J]. Information: An International Interdisciplinary Journal, 2013, 16(2): 1119-1124.

[11] Rong L. Two new uncertainty programming models of inventory with uncertain costs[J]. Journal of Information and Computational Science, 2011, 8(2): 280-288.

[12] Zhang B, Peng J. Uncertain programming model for uncertain optimal assignment problem[J]. Applied Mathematical Modeling, 2013, 37(9): 6458- 6468.

[13] Liu B. Uncertainty theory: A branch of mathematics for modeling human uncertainty[M]. 2nd ed. Berlin: Springer-Verlag, 2010.

Uncertain Programming Model for Supermarket Logistics Distribution with Time Windows

WU Pan-feng, LIU Hui-qing, PENG Jin

(1.SchoolofMathematicsandStatistics,HubeiUniversity,Wuhan430062,China; 2.InstituteofUncertainSystems,HuanggangNormalUniversity,Huanggang438000,China)

This paper deals with the supermarket logistics distribution problem with time windows in an uncertain environment. The daily demands of supermarkets and travel times of vehicles are treated as uncertain variables. In order to minimize the total travel time of all the vehicles, an uncertain chance constrained programming model is constructed. Then the proposed model is converted into a crisp equivalent model by operational law of uncertain variable. Moreover, an algorithm for solving the model is designed. Finally, a numerical example is presented to illustrate the modeling idea.

logistics distribution; time windows; uncertain variables; chance constrained

2014- 02-26

教育部人文社會(huì)科學(xué)基金項(xiàng)目(13YJA630065)；湖北省自然科學(xué)基金重點(diǎn)項(xiàng)目(2012FFA0 65)；湖北省教育廳科技創(chuàng)新團(tuán)隊(duì)項(xiàng)目(T201110)

吳攀峰(1988-)，女，湖北襄陽(yáng)人，碩士研究生，研究方向?yàn)椴淮_定理論及其應(yīng)用；劉慧清(1968-)，女，湖北大悟人，博士，教授，研究方向?yàn)閳D論與組合優(yōu)化；彭錦(1961-)，男，湖北麻城人，博士，教授，研究方向?yàn)椴淮_定理論及其應(yīng)用。

O221.2

A

1007-3221(2015)06- 0058- 07

10.12005/orms.2015.0196