帶時間窗口的超市物流配送不確定規劃模型

吳攀峰， 劉慧清， 彭 錦

(1.湖北大學 數學與統計學學院，湖北 武漢 430062； 2.黃岡師范學院，不確定系統研究所，湖北 黃岡 438000)

?

帶時間窗口的超市物流配送不確定規劃模型

吳攀峰， 劉慧清， 彭 錦

(1.湖北大學 數學與統計學學院，湖北 武漢 430062； 2.黃岡師范學院，不確定系統研究所，湖北 黃岡 438000)

主要研究了不確定環境下帶時間窗口的超市物流配送問題。假設超市的日需求量是不確定變量,在配送過程中車輛的行駛時間也為不確定變量。為了最小化配送過程中車輛行駛時間,建立了不確定機會約束模型。然后應用不確定變量的運算法則對模型進行等價轉化,并為求解模型設計了算法。最后給出了一個數值算例來說明模型的實際應用。

物流配送;時間窗口;不確定變量;機會約束

0 引言

物流是現代社會企業價值創造和價值實現的關鍵環節,是企業生產經營的生命線之一。物流配送是實現物流的基礎體現。隨著物流的快速發展,物流配送在整個物流系統中的作用越來越顯著。在物流配送過程中,配送中心一般要向多個客戶配送,在各客戶對配送中心服務滿意的情況下,讓配送成本最小是配送中心所關注的問題。這里的配送成本主要考慮的是配送車輛在行駛過程中的能源消耗,在一定程度上,車輛的行駛時間與能源消耗正相關。因此縮短配送時間已成為當今一個重要的研究課題。

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

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

本文在不確定環境下, 以超市的日需求量和配送過程中車輛的行駛時間為不確定變量,建立了以配送時間最短為目標的不確定規劃模型, 并設計了一種算法對模型進行求解, 最后為了模型的實際應用給出了一個數值算例。

本文的結構框架如下：第一節簡要介紹不確定理論的基礎知識, 第二節描述了以超市的日需求量和車輛的行駛時間為不確定變量的物流配送問題, 且為解決此問題建立了不確定規劃模型, 第三節利用不確定理論的基礎知識將不確定規劃模型轉化為一般的數學模型, 并給出了模型的算法, 第四節給出了一個數值算例。最后對本文做了小結。

1 不確定理論基礎知識

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

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

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

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

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

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

2 問題描述與模型的建立

2.1 問題描述

某配送中心與該市的多個超市合作進行物流配送服務。據實際情況,各個超市點的日需求量是不確定的。配送中心每天根據各超市點的需求向其執行配送任務,因為城區不同時段不同的路況,以及天氣情況的影響,配送過程中車輛的行駛時間也是不確定的。在各超市點對配送中心服務滿意的前提下,考慮以上不確定因素的影響,車輛如何配送貨物使行駛時間最短,是本文要解決的問題。

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

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

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

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

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

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

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

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

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

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

(3)每個超市點有且僅有一輛車服務。

(4)配送路線經過每個超市點, 且不重復。

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

對車輛k,1≤k≤m,當車輛k被使用,即yk>yk-1時,有

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

(1)

此時到達超市點xyk-1+1的時間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。這個遞推過程能夠推出車輛k到達所有超市點時間的逆分布。

2.2 模型的建立

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

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

(5)

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

(6)

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

(7)

現建立超市物流配送的不確定規劃模型如下

(8)

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

3 模型的轉化與算法

3.1 模型的轉化

上節給出了帶時間窗口的超市物流配送不確定規劃模型,其中含有很多不確定變量。如何求解此類不確定規劃模型? 一般情況下,我們希望將不確定規劃模型轉化為確定形式,從而對模型進行簡化。接下來,我們主要討論模型的轉化問題。

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

(9)

(10)

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

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

(11)

且約束條件(6)等價于

(12)

定理得證。

3.2 算法

99算法是Liu[13]提出來的, 用來計算不確定變量中單調函數的不確定分布。

我們用表1來表示不確定變量ζi。

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

步驟1 設E=0,j=1。

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

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

由于模型(9)比較復雜, 用傳統的方法不能解決。下面給出求模型近似最優解的一個算法。

算法

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

…

…

否則, 返回1;

步驟4 若S′

步驟5 重復第二步到第四步操作, 如此重復循環檢驗直到滿足終止條件。

步驟6 輸出的最終結果(x;y;t)即為最優解, 且S是最優目標函數值。

4 數值算例

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

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

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

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

其中當i=j=0時,Tij=0。

又已知7個超市點接受配送的時間窗口如表3所示

表3 各超市點接受配送的時間窗口

而且車輛在超市點接受配送的時間窗口內到達的置信水平為0.9, 車輛所到達超市點的貨物需求量之和小于車輛載重量的置信水平為0.95。

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

(13)

(14)

車輛1 配送中心→2→3→配送中心,出發時間6∶22;

車輛2 配送中心→1→配送中心, 出發時間5∶17;

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

5 結束語

本文基于不確定理論, 研究了不確定環境下帶時間窗口的超市物流配送問題。在配送過程中, 超市點的日需求量和配送車輛的行駛時間是不確定變量, 為了最小化配送車輛的行駛時間, 建立了不確定規劃模型。又用不確定理論的基礎知識對該模型進行轉化, 再給出了算法來解所建立的數學模型。最后用一個數值算例說明了模型的實際應用。文章只是研究了單個配送中心向各超市點運送貨物的例子, 對于多個配送中心向超市點運送貨物的問題建模是今后值得深入思考的問題。

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

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

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

[4] 張樂誠,楊信豐.隨機時間約束的城市物流配送車輛路徑問題研究[J].物流技術,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

教育部人文社會科學基金項目(13YJA630065)；湖北省自然科學基金重點項目(2012FFA0 65)；湖北省教育廳科技創新團隊項目(T201110)

吳攀峰(1988-)，女，湖北襄陽人，碩士研究生，研究方向為不確定理論及其應用；劉慧清(1968-)，女，湖北大悟人，博士，教授，研究方向為圖論與組合優化；彭錦(1961-)，男，湖北麻城人，博士，教授，研究方向為不確定理論及其應用。

O221.2

A

1007-3221(2015)06- 0058- 07

10.12005/orms.2015.0196