帶時(shí)間窗的三維裝載物流配送優(yōu)化方法研究

王 勇, 魏遠(yuǎn)晗, 蔣 瓊, 許茂增

(重慶交通大學(xué) 經(jīng)濟(jì)與管理學(xué)院,重慶 400074)

0 引言

城市物流配送中合理的貨物裝載方式和科學(xué)的車輛路徑規(guī)劃對(duì)物流配送活動(dòng)具有重要作用。城市物流配送中的三維裝載問(wèn)題主要是研究考慮不同體積和不同重量的貨物在封閉立體式車廂內(nèi)進(jìn)行拼裝、疊放和運(yùn)送的一類問(wèn)題[1]?，F(xiàn)階段，由于不同客戶對(duì)商品類型的需求不同，且服務(wù)時(shí)間窗不一，增加了物流配送中心運(yùn)輸調(diào)度的復(fù)雜性，進(jìn)而導(dǎo)致城市三維裝載物流配送過(guò)程中常出現(xiàn)車輛裝載率低和配送車輛路徑規(guī)劃不合理等問(wèn)題。車廂貨物裝載方式是否合理，配送車輛路徑規(guī)劃是否科學(xué)，直接影響到配送中心的配送效率、成本和效益。根據(jù)配送商品類型，對(duì)配送車廂進(jìn)行合理分區(qū)，進(jìn)而優(yōu)化貨物在車廂中的裝載方式，可以有效提高配送車輛的空間利用率，減少車輛使用數(shù)量；同時(shí)結(jié)合客戶不同的服務(wù)時(shí)間窗制定科學(xué)合理的車輛配送路徑方案可以提高配送效率，降低企業(yè)的物流運(yùn)營(yíng)成本。因此，本文結(jié)合城市物流配送車輛車廂貨物裝載方式和配送車輛路徑規(guī)劃兩個(gè)方面，研究帶時(shí)間窗的三維裝載物流配送優(yōu)化問(wèn)題，有助于物流資源的有效整合與優(yōu)化配置，進(jìn)而有利于完善城市物流配送系統(tǒng)。國(guó)內(nèi)外學(xué)者在帶時(shí)間窗的車輛路徑優(yōu)化方面，帶三維裝載約束的車輛路徑優(yōu)化方面以及兩個(gè)問(wèn)題的結(jié)合方面進(jìn)行了一系列研究工作。

在帶時(shí)間窗的車輛路徑問(wèn)題(Vehicle Routing Problem with Time Windows, VRPTW)方面，符卓等[2]針對(duì)需求可拆分的帶時(shí)間窗的車輛路徑問(wèn)題，建立了以最小化車輛使用數(shù)和最小化車輛行駛成本為優(yōu)化目標(biāo)的數(shù)學(xué)模型，并設(shè)計(jì)了禁忌搜索算法來(lái)求解模型。Hassan等[3]研究了帶時(shí)間窗的多目標(biāo)車輛路徑問(wèn)題，提出一種基于蟻群和禁忌搜索的混合算法進(jìn)行問(wèn)題求解。Shi等[4]研究了帶時(shí)間窗的同時(shí)取、送貨的車輛路徑問(wèn)題，構(gòu)建了使配送成本和車輛使用數(shù)最小化的雙目標(biāo)數(shù)學(xué)模型，提出一種基于禁忌搜索的有效算法進(jìn)行模型求解。Niu等[5]建立了帶時(shí)間窗的開(kāi)放式車輛路徑問(wèn)題的數(shù)學(xué)模型，設(shè)計(jì)了一種禁忌混合搜索算法進(jìn)行模型求解。根據(jù)上述研究可以發(fā)現(xiàn)，混合智能算法常被用于研究帶時(shí)間窗的車輛路徑問(wèn)題，而帶時(shí)間窗的車輛路徑問(wèn)題研究為三維裝載物流配送優(yōu)化問(wèn)題研究提供了方法切入。

三維裝載問(wèn)題和三維裝載約束下的車輛路徑問(wèn)題也引起了部分學(xué)者的關(guān)注。那日薩等[6]應(yīng)用空間切割法對(duì)車廂進(jìn)行空間區(qū)域劃分，在水平方向和豎直方向搜索放入貨物的最佳位置，使箱體空間利用率最大化。Mahvash等[7]研究了考慮貨物不同擺放方位的三維裝載問(wèn)題，并設(shè)計(jì)了貨物在立體式車廂內(nèi)的順序放置方式。Gendreau等[8]在2006年首次提出帶有三維裝箱約束的車輛路徑問(wèn)題優(yōu)化模型，并設(shè)計(jì)了禁忌搜索算法進(jìn)行模型求解研究。Zhang等[9]設(shè)計(jì)了一種進(jìn)化局部搜索方法求解三維裝載約束下的最小化油耗車輛路徑問(wèn)題。Bortfeldt和Yi[10]在分批配送車輛路徑問(wèn)題的基礎(chǔ)上加入了三維裝載約束，建立了具有三維裝載約束條件的分批配送車輛路徑優(yōu)化模型，并提出了一種由局部搜索算法和遺傳算法組成的混合算法求解模型。顏瑞等[11]研究了帶三維裝箱約束的車輛路徑問(wèn)題提出分別應(yīng)用模糊遺傳算法和引導(dǎo)式局部搜索算法求解車輛路徑問(wèn)題和三維裝箱問(wèn)題。由上述相關(guān)研究可知，當(dāng)前關(guān)于三維裝載物流配送優(yōu)化問(wèn)題的研究集中在問(wèn)題求解和算法設(shè)計(jì)方面，而考慮客戶不同規(guī)格的貨物需求和車輛分區(qū)空間等方面的研究還有待進(jìn)一步深入。

本文考慮了客戶服務(wù)時(shí)間窗和貨物的三維裝載空間約束，研究了帶時(shí)間窗的三維裝載物流配送車輛路徑優(yōu)化問(wèn)題，并結(jié)合客戶不同規(guī)格的貨物需求和服務(wù)時(shí)間窗特征，進(jìn)行了合理的車廂空間區(qū)域劃分研究。首先，構(gòu)建了物流運(yùn)營(yíng)成本最小化和配送車輛空間利用率最大化的雙目標(biāo)優(yōu)化模型；然后，設(shè)計(jì)了一種結(jié)合遺傳和禁忌搜索的GA-TS混合算法求解模型；最后，通過(guò)實(shí)例研究了帶時(shí)間窗的三維裝載物流配送優(yōu)化前后以及不同空間分區(qū)模式下的平均裝載率、車輛使用數(shù)和物流運(yùn)營(yíng)成本的變化，進(jìn)而為帶時(shí)間窗的三維裝載物流配送問(wèn)題提供新的研究思路。

1 問(wèn)題描述

帶時(shí)間窗的三維裝載物流配送優(yōu)化問(wèn)題涉及車輛的貨物裝載方式和配送過(guò)程中考慮客戶服務(wù)時(shí)間窗的車輛路徑優(yōu)化兩個(gè)方面。為了有效整合物流資源和減少不合理的貨物裝載方式，需要綜合考慮不同規(guī)格貨物的裝載方式和三維裝載車輛的物流配送成本進(jìn)行合理的配送調(diào)度。圖1出示了帶時(shí)間窗的三維裝載物流配送優(yōu)化前后對(duì)比圖。

圖1 帶時(shí)間窗的三維裝載物流配送優(yōu)化前后對(duì)比圖

圖1(a)表示帶時(shí)間窗的三維裝載物流配送優(yōu)化前，由于客戶需求存在不同規(guī)格的貨物類型和服務(wù)時(shí)間窗要求，導(dǎo)致現(xiàn)有配送方式往往存在車輛裝載率不高和配送線路調(diào)度不合理的情況，進(jìn)而造成違反客戶服務(wù)時(shí)間窗較多和物流運(yùn)營(yíng)成本較高的現(xiàn)象。圖1(b)表示帶時(shí)間窗的三維裝載物流配送優(yōu)化后，基于客戶不同規(guī)格的貨物需求和客戶服務(wù)需求時(shí)間窗，結(jié)合車輛裝載和客戶服務(wù)時(shí)間窗限制進(jìn)行合理的車廂貨物裝載順序設(shè)計(jì)和客戶訪問(wèn)序列優(yōu)化，進(jìn)而提高了車輛裝載率，降低了物流配送成本。假設(shè)單位時(shí)間的配送成本為30元，違反時(shí)間窗的單位時(shí)間懲罰成本是10元，車輛的租賃成本為100元/輛·次。表1出示了三維裝載物流配送優(yōu)化前后物流運(yùn)營(yíng)成本與車輛數(shù)量的比較，結(jié)果表明帶時(shí)間窗的三維裝載物流配送優(yōu)化后有效提高了車輛裝載率，減少了配送車輛使用數(shù)和降低了物流運(yùn)營(yíng)成本。

表1 三維裝載車輛路徑優(yōu)化前后結(jié)果對(duì)比

2 模型建立

在三維裝載物流配送優(yōu)化問(wèn)題研究中[1,9,11]，當(dāng)不同裝載空間可運(yùn)送不同類型的貨物，且貨物類型數(shù)趨向等于裝載空間劃分?jǐn)?shù)時(shí)，裝載率最大。當(dāng)某一空間可裝載兩種或多種貨物類型且可堆疊裝載時(shí)，空間裝載率趨向等于與貨物類型數(shù)相同的區(qū)域劃分?jǐn)?shù)的裝載率，但當(dāng)空間劃分?jǐn)?shù)小于貨物類型數(shù)時(shí)，貨物裝載順序復(fù)雜度遠(yuǎn)大于貨物類型數(shù)與空間區(qū)域劃分?jǐn)?shù)相同的貨物裝載順序復(fù)雜度。

2.1 模型假設(shè)

本模型假設(shè)條件如下：

(1)每位客戶需求的貨物類型、貨物數(shù)量、服務(wù)時(shí)間窗及貨物的長(zhǎng)，寬，高均已知；每位客戶僅由一輛配送車輛訪問(wèn)；

(2)配送車輛車廂被劃分成多個(gè)空間區(qū)域，每個(gè)區(qū)域內(nèi)裝載的貨物規(guī)格大小相同，且貨物需要平行于車廂放置；

(3)訪問(wèn)客戶的服務(wù)時(shí)間忽略不計(jì)。

2.2 符號(hào)定義

本研究涉及的變量和符號(hào)如表2所示。

表2 變量定義

2.3 模型構(gòu)建

本文以配送中心的物流運(yùn)營(yíng)成本Z1最小化和配送車輛裝載率Z2最大化為優(yōu)化目標(biāo)。建立的數(shù)學(xué)模型如下:

minZ1=G+TC+MC+FC+PC

(1)

(2)

G：配送中心的固定成本

(3)

TC：配送車輛將貨物送達(dá)客戶的配送成本

(4)

MC：配送車輛的維修成本，主要是指配送中心出發(fā)的配送車輛在一個(gè)工作周期內(nèi)的平均維修成本。

(5)

FC：配送車輛的租賃成本，主要是指配送中心在一個(gè)工作周期內(nèi)租賃配送車輛的費(fèi)用。

(6)

PC：配送車輛違反客戶服務(wù)時(shí)間窗早到和晚到的懲罰成本。

(7)

約束條件：

(1)車輛路徑約束：

(16)

式(8)表示每個(gè)客戶點(diǎn)只能由一輛車訪問(wèn)，式(9)表示流量約束，即車輛將貨物送達(dá)客戶后必須離開(kāi)；式(10)表示車輛從配送中心出發(fā)，完成任務(wù)后必須返回配送中心；式(11)表示消除子回路約束；式(12)表示車輛上每一區(qū)域內(nèi)貨物數(shù)量的約束；式(13)表示車輛裝載貨物的重量不超過(guò)車輛的最大裝載量；式(14)～(15)表示車輛離開(kāi)和到達(dá)配送中心的時(shí)間需要在其服務(wù)的時(shí)間窗內(nèi)，式(16)表示車輛配送過(guò)程中的時(shí)間連續(xù)性。

(2)三維裝箱約束：

xckdiu≥0

(17)

yckdiu≥0

(18)

zckdiu≥0

(19)

pd·hdc≤hd,?c∈C,d∈D

(20)

rd·ldc≤ld,?c∈C,d∈D

(21)

cd·wdc≤wd,?c∈C,d∈D

(22)

(23)

(24)

xik={0,1},?i∈I,?k∈K

(25)

yijk={0,1},?i,j∈I0且i≠j,?k∈K

(26)

(27)

式(17)～(19)表示貨物必須擺放在車廂內(nèi)；式(20)～(22)表示配送車輛任一區(qū)域內(nèi)裝載的貨物不能超出區(qū)域范圍；式(23)～(24)表示先進(jìn)后出約束，依次表示為后服務(wù)客戶的貨物不能壓在先服務(wù)客戶貨物的上面，后服務(wù)客戶的貨物不能擋在先服務(wù)客戶貨物的前面；式(25)～(27)表示變量約束。

3 GA-TS混合算法

3.1 算法過(guò)程描述

本文提出了一種基于遺傳算法(GA)和禁忌搜索算法(TS)的GA-TS混合優(yōu)化算法求解模型，將GA的全局優(yōu)化與TS的局部搜索的特性相結(jié)合。GA-TS混合算法的流程圖如圖2所示。

圖2 GA-TS混合算法操作流程

3.2 算法設(shè)計(jì)

本研究設(shè)計(jì)了GA-TS混合算法用于求解帶時(shí)間窗的三維裝載物流配送優(yōu)化模型。TS算法對(duì)初始值依賴性較強(qiáng)，引入GA算法為其找到較好的初始點(diǎn)，可加快收斂速度，提高解的質(zhì)量[12]。此外，GA具有較好的全局搜索能力，而TS局部搜索能力較強(qiáng)[2]。因此，GA-TS混合算法有效地結(jié)合了GA和TS算法的優(yōu)點(diǎn)，提高了算法的全局收斂性能。

3.2.1 混合算法適應(yīng)度

本文以配送中心的物流運(yùn)營(yíng)成本最小化和配送車輛裝載率最大化為優(yōu)化目標(biāo)，設(shè)計(jì)的遺傳算法的適應(yīng)度函數(shù)如式(28)所示。

(28)

式(28)中Z1表示配送中心的物流運(yùn)營(yíng)成本，Z2表示配送車輛的裝載率。

3.2.2 禁忌表和禁忌長(zhǎng)度

3.3 算法檢驗(yàn)

為了進(jìn)一步檢驗(yàn)GA-TS混合算法的有效性，將GA-TS混合算法與混合遺傳算法(HGA)[13]、遺傳粒子群混合算法(GA-PSO)[14]進(jìn)行比較，三種算法均為混合算法且遺傳算法是三種混合算法的重要組成部分，相比于本文提出的GA-TS算法，混合遺傳算法設(shè)計(jì)了雙層目標(biāo)優(yōu)化過(guò)程，并以物流運(yùn)營(yíng)成本最小化為主優(yōu)化目標(biāo)，以配送車輛裝載率最大化為次優(yōu)化目標(biāo)進(jìn)行三維裝載車輛路徑優(yōu)化研究；而遺傳-粒子群混合算法過(guò)程針對(duì)三維裝載車輛路徑優(yōu)化目標(biāo)設(shè)計(jì)了遺傳算法和粒子群算法間的循環(huán)迭代機(jī)制，并構(gòu)建了物流運(yùn)營(yíng)成本和車輛轉(zhuǎn)載率的集成適應(yīng)度函數(shù)進(jìn)行問(wèn)題研究。本文的測(cè)試數(shù)據(jù)是在Solomon測(cè)試數(shù)據(jù)集的基礎(chǔ)上增加了客戶不同需求商品類型的貨物來(lái)構(gòu)建的。20個(gè)不同數(shù)據(jù)集的實(shí)驗(yàn)數(shù)據(jù)如表3所示。

結(jié)合表3的實(shí)驗(yàn)數(shù)據(jù)，分別從物流成本、車輛平均裝載率和算法求解時(shí)間三個(gè)方面比較三種算法的優(yōu)化結(jié)果。三種算法的各項(xiàng)參數(shù)設(shè)置如下：GA-TS、HGA和GA-PSO算法中的種群規(guī)模popsize=100，最大迭代次數(shù)maxgen=200，選擇概率Ps=0.9，交叉概率Pc=0.9，變異概率Pm=0.1；GA-TS算法中禁忌搜索迭代次數(shù)tsin=40，禁忌表長(zhǎng)度TL=28；GA-PSO算法中的慣性權(quán)重w=0.9，學(xué)習(xí)因子c1=1.2，c2=1.4。將每種算法分別運(yùn)行30次，選取最優(yōu)的物流運(yùn)營(yíng)總成本和平均裝載率以及對(duì)應(yīng)的算法求解運(yùn)行時(shí)間，如表4所示。

表3 實(shí)驗(yàn)數(shù)據(jù)參數(shù)表

表4 不同算法優(yōu)化結(jié)果的比較

由表4可知，GA-TS算法、HGA算法與GA-PSO算法的最小物流運(yùn)營(yíng)成本的t檢驗(yàn)和p值的比較結(jié)果表明GA-TS算法的最小物流運(yùn)營(yíng)成本與其他兩種算法相比具有明顯差異。此外，在物流運(yùn)營(yíng)成本和裝載率方面，GA-TS在大多數(shù)情況下均優(yōu)于HGA和GA-PSO求解的結(jié)果。在計(jì)算時(shí)間方面，GA-TS算法比GA-PSO算法需要更多收斂時(shí)間，但在物流運(yùn)營(yíng)成本最小化方面優(yōu)于后者。

4 算例分析

4.1 算例相關(guān)數(shù)據(jù)

以重慶市某配送中心(DC)及其服務(wù)的110個(gè)客戶點(diǎn)(C1-C110)進(jìn)行研究。該配送中心服務(wù)的商品類型有4種，其相應(yīng)的長(zhǎng)、寬、高及重量如表5所示，且C1-C50是具有單一商品類型需求的客戶點(diǎn)，C51-C90是具有2種不同商品類型需求的客戶點(diǎn)，C91-C110是具有3種不同商品類型需求的客戶點(diǎn)。

表5 各種類型的貨物規(guī)格

假設(shè)每輛配送車輛的車廂可以近似看成箱體，且每一個(gè)車廂有4個(gè)大小不同的分區(qū)，每個(gè)區(qū)域只能裝載相應(yīng)類型的貨物。每個(gè)區(qū)域的大小及可裝載貨物的數(shù)量如表6所示。

表6 各個(gè)區(qū)域規(guī)格大小及可裝載貨物的數(shù)量

4.2 結(jié)果與分析

在現(xiàn)有文獻(xiàn)[3,9,10]和多次實(shí)驗(yàn)計(jì)算的基礎(chǔ)上，相應(yīng)參數(shù)設(shè)置如下：L=420cm，W=180cm，H=200cm，Qk=1300kg，Vk=15.12m2，K=25，g=0.2，T=52，ck=0.8，fk=200，mk=16000，φ1=15，φ2=20，popsize=100，maxgen=200，Ps=0.9，Pc=0.9，Pm= 0.1，tsin=40，TL=28。GA-TS混合算法求解帶時(shí)間窗的三維裝載物流配送優(yōu)化前后結(jié)果的對(duì)比如表7所示。

表7 三維裝載車輛路徑優(yōu)化前后結(jié)果對(duì)比

由表7可知，應(yīng)用GA-TS混合算法優(yōu)化后的配送方案相比優(yōu)化前的方案，配送時(shí)間減少了37.5%，早到和晚到時(shí)間共減少了71.88%，車輛數(shù)節(jié)省了50%，時(shí)間窗懲罰成本減少了80.28%，配送成本減少了32.33%，物流成本節(jié)約了44.71%，平均裝載率提高了42.92%。

此外，本文選取平均裝載率最高的配送車輛9和平均裝載率最低的配送車輛14的各區(qū)域裝載率和整車廂裝載率，如表8所示。

表8 車輛9和14的各區(qū)域裝載率和整車廂裝載率

由表8可知，在配送車輛9和14中，兩車區(qū)域1的裝載率均為88.1%，區(qū)域2的裝載率均為92.5%，而車輛9區(qū)域3，區(qū)域4和整車廂的裝載率分別比車輛14的相應(yīng)區(qū)域和整車廂的裝載率高15.5%，22.5%和15.3%。

4.3 分析與討論

為進(jìn)一步探討不同空間分區(qū)模式對(duì)優(yōu)化結(jié)果的影響，將車廂空間區(qū)域分別平均劃分為2個(gè)區(qū)域，3個(gè)區(qū)域，4個(gè)區(qū)域，5個(gè)區(qū)域，車廂空間不分區(qū)域以及按貨物類型劃分成4個(gè)區(qū)域六種情況。討論不同空間分區(qū)模式下物流運(yùn)營(yíng)成本、配送車輛使用數(shù)和車輛平均裝載率等的變化，計(jì)算結(jié)果如表9所示。

表9 不同車廂分區(qū)模式下優(yōu)化結(jié)果對(duì)比

由表9可知，按貨物類型把車廂空間劃分為4個(gè)區(qū)域時(shí)配送車輛的平均裝載率最高，車輛使用數(shù)最少，物流運(yùn)營(yíng)成本最低。相比車輛車廂空間不分區(qū)域、分成2個(gè)區(qū)域、3個(gè)區(qū)域、4個(gè)區(qū)域和5個(gè)區(qū)域五種情況，按貨物類型把車輛車廂空間劃分為4個(gè)區(qū)域空間的車輛數(shù)分別減少了15輛、13輛、7輛、13輛和14輛；車輛平均裝載率分別提高了42.92%、39.86%、27.32%、39.86%和41.44%；物流運(yùn)營(yíng)成本分別節(jié)約了44.71%、37.73%、21.64%、34.87%和39.50。因此，根據(jù)客戶不同規(guī)格型號(hào)的貨物需求，合理劃分配送車輛車廂的區(qū)域進(jìn)行貨物配送，可以有效提高車輛裝載率，減少車輛使用數(shù)和降低物流運(yùn)營(yíng)成本。

5 結(jié)論

本文研究了帶時(shí)間窗的三維裝載物流配送優(yōu)化問(wèn)題，結(jié)合客戶不同規(guī)格貨物和服務(wù)時(shí)間窗的需求進(jìn)行合理的配送路線調(diào)度和貨物裝載方式優(yōu)化，建立了包含配送中心的固定成本、配送車輛的運(yùn)輸成本、維修成本、租賃成本和違反時(shí)間窗懲罰成本的物流運(yùn)營(yíng)總成本最小化和配送車輛空間利用率最大化的雙目標(biāo)優(yōu)化模型。結(jié)合車廂分區(qū)模式、貨物裝載方式與配送路線調(diào)度，設(shè)計(jì)了一種GA-TS混合算法求解模型，該算法有效結(jié)合了GA算法的全局搜索性能和TS算法的局部搜索性能，拓展了優(yōu)化解空間的搜索能力。將GA-TS混合算法與HGA算法、GA-PSO混合算法進(jìn)行了物流運(yùn)營(yíng)成本，平均車輛裝載率和求解運(yùn)行時(shí)間的對(duì)比分析，進(jìn)一步驗(yàn)證了本研究提出的混合算法的有效性和合理性。

本文以重慶市某配送中心及其物流配送網(wǎng)絡(luò)為例，驗(yàn)證了模型和算法的有效性。計(jì)算結(jié)果表明，三維裝載物流配送優(yōu)化后相比于優(yōu)化前的方案，物流運(yùn)營(yíng)成本和車輛使用數(shù)分別減少了44.71%和50%，平均裝載率提高了42.92%。此外，不同空間分區(qū)模式下物流運(yùn)營(yíng)成本、車輛使用數(shù)和平均裝載率等的對(duì)比結(jié)果表明，當(dāng)客戶需求商品種類數(shù)與車輛的空間區(qū)域劃分?jǐn)?shù)相等且按貨物類型進(jìn)行空間區(qū)域劃分時(shí)，配送中心的物流運(yùn)營(yíng)成本最低，配送車輛使用數(shù)最少，車輛平均裝載率最高。本研究可為三維裝載的物流配送優(yōu)化問(wèn)題提供新的研究思路，并有較強(qiáng)的現(xiàn)實(shí)意義和應(yīng)用價(jià)值。