基于車(chē)輛共享的多配送中心車(chē)輛路徑問(wèn)題研究

□ 文 軍

(蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，甘肅 蘭州 730070)

1 引言

據(jù)中國(guó)物流與采購(gòu)聯(lián)合會(huì)統(tǒng)計(jì)顯示，2017年中國(guó)社會(huì)物流總費(fèi)用為12.1萬(wàn)億元，其中運(yùn)輸費(fèi)用為6.6萬(wàn)億元，占比高達(dá)54.5%。因此，在物流系統(tǒng)優(yōu)化過(guò)程中，怎樣經(jīng)濟(jì)高效地選擇車(chē)輛配送路徑依然是一個(gè)極其重要的問(wèn)題。

基于車(chē)輛共享的多配送中心車(chē)輛路徑問(wèn)題其實(shí)質(zhì)就是開(kāi)放式車(chē)輛路徑問(wèn)題，它是1981年由Schrage[1]首次提出的一類(lèi)經(jīng)典N(xiāo)P難問(wèn)題。為提高客戶滿意度，本文還添加了軟時(shí)間窗的限制，其相當(dāng)于帶軟時(shí)間窗的多配送中心開(kāi)放式車(chē)輛路徑問(wèn)題(Multi-Depot Open Vehicle Routing Problem with Soft Time Windows，MDOVRPSTW)，因此對(duì)其求解更加困難。

目前，國(guó)內(nèi)外學(xué)者對(duì)VRP研究充分，但在MDOVRPSTW問(wèn)題的研究上，還相對(duì)缺乏。對(duì)該問(wèn)題的研究主要集中在智能算法方面，如遺傳算法[2][3]、禁忌搜索算法[4]、蟻群算法[5-7]等。但多態(tài)蟻群算法在MDVRPSTW中的應(yīng)用中，仍存在著許多未解決的問(wèn)題。為此，本文設(shè)計(jì)了一種結(jié)合2-opt局部?jī)?yōu)化算法的自適應(yīng)多態(tài)蟻群算法進(jìn)行求解，采用實(shí)例驗(yàn)證該算法在求解MDOVRPSTW問(wèn)題中的可行性和有效性。

2 構(gòu)造模型

2.1 闡述問(wèn)題

假設(shè)在某市存在著若干個(gè)物流配送中心，每個(gè)配送中心擁有數(shù)量相等的運(yùn)輸車(chē)輛，需要為本市多個(gè)客戶承擔(dān)貨物配送任務(wù)。已知：①每個(gè)配送中心的貨物充足且配送車(chē)輛的載量相同；②客戶之間、客戶與各配送中心之間均可順利到達(dá)，且距離已知并具有對(duì)稱性；③為提高客戶的滿意度，為每個(gè)客戶提供服務(wù)軟時(shí)間窗；④配送車(chē)輛在完成配送任務(wù)之后無(wú)須返回原配送中心，可根據(jù)就近原則，?？吭诰徒渌椭行摹?/p>

問(wèn)題的目標(biāo)是：在配送車(chē)輛有限的情況下，如何合理地設(shè)計(jì)各配送車(chē)輛的運(yùn)輸路徑，以滿足客戶需求的前提下，達(dá)到運(yùn)輸總成本最小的目標(biāo)。

2.2 符號(hào)定義

P={p|1,2,3,…,p}表示配送中心個(gè)數(shù)；

G={g|1,2,3,…,g}表示客戶數(shù)量；

K={k|1,2,3,…,k}表示運(yùn)輸車(chē)輛數(shù)；

dij表示任意兩點(diǎn)之間的歐式距離，?i,j∈P∪G；

c表示車(chē)輛運(yùn)輸?shù)膯挝痪嚯x成本；

c1表示早到車(chē)輛的單位時(shí)間等待成本；

c2表示晚到車(chē)輛的單位時(shí)間罰金成本；

Z表示運(yùn)輸車(chē)輛配送時(shí)產(chǎn)生的總成本；

Q表示運(yùn)輸車(chē)輛最大裝載量；

qi表示客戶i的所需貨物量；

[Ei,Li]表示客戶i限制的提供配送服務(wù)時(shí)間窗；

ti表示對(duì)客戶i提供物流配送服務(wù)的時(shí)間；

Ti表示車(chē)輛到達(dá)客戶i的時(shí)間；

xijk表示運(yùn)輸車(chē)輛順利從點(diǎn)i到達(dá)點(diǎn)J時(shí)為1，未順利到達(dá)則為0，?i,j∈G；

yijk表示車(chē)輛從配送中心i到客戶j或者從客戶i到配送中心j時(shí)為1，否則為0，?i,j∈P∪G；

V表示車(chē)輛行駛的平均時(shí)速。

2.3 模型建立

根據(jù)以上的問(wèn)題闡述和符號(hào)定義，構(gòu)造如下帶軟時(shí)間窗的多配送中心開(kāi)放式VRP的混合整數(shù)規(guī)劃模型如下：

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

?i∈G,?j∈P,?k∈Kor?i∈P,?j∈G,?k∈K

(10)

其中，表達(dá)式的含義為：

目標(biāo)函數(shù)(1)表示使運(yùn)輸成本與客戶等待時(shí)間成本之和最小化，即使物流配送總成本最小化；

約束條件(2)表示每個(gè)客戶只能被一輛運(yùn)輸車(chē)輛進(jìn)行配送服務(wù)一次；

約束條件(3)表示為客戶j提供配送服務(wù)的車(chē)輛數(shù)在到發(fā)方面保持一致；

約束條件(4)表示運(yùn)輸車(chē)輛服務(wù)客戶的需求量之和不大于其最大裝載量；

約束條件(5)表示運(yùn)輸車(chē)輛抵達(dá)客戶j的時(shí)刻點(diǎn)；

約束條件(6)表示運(yùn)輸車(chē)輛在完成相應(yīng)的物流配送服務(wù)后，可選擇任一配送中心?？浚?/p>

約束條件(7)和(8)表示運(yùn)輸車(chē)輛在完成相應(yīng)的物流配送服務(wù)后，一定得選擇一個(gè)配送中心?？浚?/p>

約束條件(9)和(10)表示決策變量的0-1約束。

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

3.1 算法設(shè)計(jì)的總體思路

本文基于傳統(tǒng)的TSP蟻群算法，結(jié)合具有軟時(shí)間窗的多配送中心開(kāi)放式車(chē)倆路徑問(wèn)題的具體約束條件，適當(dāng)改進(jìn)了選擇、更新以及協(xié)調(diào)等機(jī)制，同時(shí)添加了自適應(yīng)的轉(zhuǎn)移策略和信息素更新策略。由蟻群具有多樣社會(huì)分工的特性，使偵察螞蟻在偵測(cè)過(guò)程帶有特定的約束；讓搜索螞蟻來(lái)完成搜索滿足目標(biāo)函數(shù)可行解的任務(wù)。通過(guò)不同種類(lèi)螞蟻的分工協(xié)作，最后將信息素自適應(yīng)策略與多態(tài)蟻群算法相結(jié)合，改進(jìn)的算法有效地加快了基礎(chǔ)蟻群算法收斂速度，克服了早熟現(xiàn)象的發(fā)生。

3.2 自適應(yīng)多態(tài)蟻群算法步驟

根據(jù)陳美軍等提出的自適應(yīng)多態(tài)蟻群算法相關(guān)原理[8]，本文加入2-opt局部?jī)?yōu)化算法，將其應(yīng)用于解決本文構(gòu)建的帶軟時(shí)間窗的多配送中心開(kāi)放式車(chē)輛路徑模型上，其求解步驟如下：

①初始時(shí)刻，設(shè)置參數(shù)Q、C、α、β、ξ和ρ，并設(shè)置最大迭代數(shù)為MAXGEN等。

②在N個(gè)客戶點(diǎn)放置N只偵察蟻，把所在客戶點(diǎn)i看作相應(yīng)偵察蟻的中心，對(duì)其他N-1個(gè)客戶點(diǎn)進(jìn)行偵察，計(jì)算并記錄總偵察表，將結(jié)果賦予Sij。

③在初始時(shí)設(shè)置每條路徑上的信息量。

④設(shè)置進(jìn)化代數(shù)NC初值為0。

⑤將搜索蟻k的初始位置定為虛擬配送中心點(diǎn)，并將該位置放在與搜索蟻k相對(duì)應(yīng)的禁忌表tabuk中。

⑥搜索蟻k用輪盤(pán)賭方法挑選下一個(gè)訪問(wèn)的客戶點(diǎn)，相應(yīng)的禁忌表tabuk加入該客戶點(diǎn)。

⑦對(duì)還沒(méi)有訪問(wèn)到的客戶點(diǎn)集合進(jìn)行刷新，并再次計(jì)算可選客戶點(diǎn)的集合。

⑧若還有客戶點(diǎn)沒(méi)有訪問(wèn)到而這些客戶點(diǎn)都是不可選的，則說(shuō)明雖然還有沒(méi)提供配送服務(wù)的客戶點(diǎn)，但是這些客戶點(diǎn)都不符合約束條件。此時(shí)搜索蟻k返回虛擬配送中心點(diǎn)，相應(yīng)的在禁忌表tabuk的末尾加入該點(diǎn)，構(gòu)成以虛擬配送中心為始末位置的一條閉環(huán)路線。返回步驟⑤，直到還沒(méi)用訪問(wèn)到的客戶點(diǎn)的集合為空，轉(zhuǎn)入下一步。

⑨計(jì)算每條路徑中第一個(gè)和最后一個(gè)客戶與實(shí)際配送中心之間的距離，用合適的實(shí)際配送中心代替虛擬配送中心，連接第一個(gè)客戶的首端和最后一個(gè)客戶末端，形成完整的路徑。

⑩計(jì)算每只搜索蟻的目標(biāo)函數(shù)值f(Z)，并記錄當(dāng)前最佳解。

結(jié)合2-opt局部?jī)?yōu)化算法的自適應(yīng)多態(tài)蟻群算法的流程圖見(jiàn)圖1。

4 實(shí)例仿真

本文采用Matlab R2015a仿真軟件來(lái)計(jì)算優(yōu)化結(jié)果。設(shè)計(jì)3個(gè)配送中心位置點(diǎn)，各配送中心擁有的車(chē)輛最大數(shù)是3，20個(gè)客戶位置點(diǎn)，每個(gè)位置點(diǎn)分散在一個(gè)100*100的正方形區(qū)域。其具體數(shù)據(jù)見(jiàn)表1。

圖1 算法流程圖

表1 位置點(diǎn)數(shù)據(jù)

其中，標(biāo)號(hào)為1-3的位置點(diǎn)為配送中心的相關(guān)數(shù)據(jù)，標(biāo)號(hào)為4-23的位置點(diǎn)為客戶的相關(guān)數(shù)據(jù)。

基于以上數(shù)據(jù)，并結(jié)合過(guò)去的經(jīng)驗(yàn)，將算法中的相關(guān)參數(shù)賦予相應(yīng)的初始值：α=1，β=2，ρ(t0)=1，ξ=0.95，N=23，Q=100，C=3，max(Pc)=10，最大迭代次數(shù)為50。模型中車(chē)輛的相關(guān)系數(shù)設(shè)定值為：?jiǎn)挝贿\(yùn)輸成本c=1，早到的消耗單位成本c1=0.2，遲到的懲罰單位成本c2=2，最大裝載量Q=6，平均時(shí)速V=40。模型求解得到的最小總成本為554.682，車(chē)輛的行駛路徑情況如下表2所示：

表2 最優(yōu)車(chē)輛配送路徑

通過(guò)實(shí)驗(yàn)所得的配送車(chē)輛路徑最佳圖和最優(yōu)解收斂曲線圖如圖2(a)和(b)所示：

圖2(a)配送車(chē)輛路徑圖

圖2(b)收斂曲線圖

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

根據(jù)城市物流實(shí)際配送中遇到的多配送中心、多任務(wù)車(chē)輛調(diào)度優(yōu)化問(wèn)題，為降低整個(gè)配送過(guò)程中配送所產(chǎn)生的物流成本，提高城市的社會(huì)物流效益，本文從運(yùn)輸、時(shí)間等方面出發(fā)構(gòu)建了一個(gè)基于物流配送車(chē)輛共享的開(kāi)放式車(chē)輛路徑問(wèn)題數(shù)學(xué)模型。對(duì)于該模型，使用自適應(yīng)多態(tài)蟻群算法來(lái)優(yōu)化求解，并且將2-opt算法用于局部?jī)?yōu)化以加速算法的收斂。最后，該算法由Matlab R2015a仿真軟件實(shí)現(xiàn)，并通過(guò)實(shí)例驗(yàn)證了自適應(yīng)多態(tài)蟻群算法在處理基于車(chē)輛共享的開(kāi)放式車(chē)輛路徑問(wèn)題是有效且可取的。