多中心半開放式同時(shí)送取貨的車輛路徑問題研究

陳榮虎,張建宏,徐 禎

(安徽工業(yè)大學(xué) 管理科學(xué)與工程學(xué)院,安徽 馬鞍山 243032)

近年來,物流行業(yè)發(fā)展迅速,很多物流企業(yè)擁有多個(gè)配送中心,并采用第三方租賃的車輛進(jìn)行配送服務(wù),因此多中心半開放式車輛路徑問題(Multi-depot Half Open Vehicle Routing Problem, 下文簡稱MDHOVRP)得到了更多的關(guān)注.半開放式配送模式是指車輛服務(wù)完路線中所有客戶點(diǎn)后,不一定返回原發(fā)出配送中心,而是根據(jù)車輛服務(wù)路線中最后一個(gè)客戶點(diǎn)離各個(gè)配送中心的歐式距離,就近返回某一配送中心.在許多實(shí)際問題中,客戶點(diǎn)同時(shí)具有送取兩種需求,且兩種需求分開服務(wù)在操作上具有一定的復(fù)雜性,為了減少這種復(fù)雜性,顧客要求只能被服務(wù)一次.如某個(gè)區(qū)域由多個(gè)快遞總站給各小區(qū)快遞站點(diǎn)提供送取快遞服務(wù),在考慮各個(gè)快遞站點(diǎn)的服務(wù)時(shí)間窗的情況下,租賃第三方物流公司的車輛,實(shí)現(xiàn)各快遞總站之間的車輛共享,可以減少車輛的配送距離,使得各種資源都能得到合理的配置.因此,為了更好地滿足現(xiàn)實(shí)復(fù)雜的物流配送情況,尋求一種在已有多個(gè)配送中心的條件下,考慮客戶點(diǎn)的時(shí)間窗進(jìn)行同時(shí)送取貨的一種半開放式配送模式十分必要.

針對帶時(shí)間窗的多中心車輛問題,Cordeau等[1]設(shè)計(jì)了禁忌搜索算法對其求解,引入了一種自適應(yīng)的懲罰系數(shù),可以把原來不可行的解變?yōu)榭尚薪?Liu等[2]設(shè)計(jì)了融合人工蜂群算法的一種混合遺傳算法對此類問題進(jìn)行求解,并通過仿真對比實(shí)驗(yàn),證明該算法求解效果較優(yōu).辜勇等[3]根據(jù)MDHOVRP問題的復(fù)雜性,提出一種三階段的算法處理方式,同時(shí)采用多蟻群算法解決MDHOVRP問題.范厚明等[4]將生鮮品的配送和MDHOVRPTW問題聯(lián)立了起來,建立了多目標(biāo)模型,并采用蟻群算法進(jìn)行求解.張穎鈺等[5]設(shè)計(jì)了一種與大變異鄰域相結(jié)合的遺傳算法,有效地解決了送取可以進(jìn)行拆解的MDHOVRP問題.馬冰山等[6]為改善生態(tài)環(huán)境,采用純電動(dòng)汽車進(jìn)行配送服務(wù),設(shè)計(jì)了一種改進(jìn)的蟻群算法求解純電動(dòng)車配送的MDHOVRPTW問題.針對帶時(shí)間窗同時(shí)送取車輛路徑問題(Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Windows, 下文簡稱VRPSDPTW)Wang等[7]設(shè)計(jì)一種共同進(jìn)化的遺傳算法進(jìn)行求解,同時(shí)還結(jié)合了Solomon算例,創(chuàng)造了VRPSDPTW基準(zhǔn)實(shí)例.袁曉建等[8]研究VRPSDPTW問題時(shí),設(shè)計(jì)了一種改進(jìn)的量子算法,并對Wang的基準(zhǔn)實(shí)例進(jìn)行了測試.王超等設(shè)計(jì)了離散布谷鳥搜索算法[9]、回溯搜索優(yōu)化算法[10]有效的求解了VRPSDPTW問題.張家善等[11]將差分進(jìn)化算子與蜂群算法相結(jié)合,有效的求解了VRPSDP問題.黃務(wù)蘭等[12]為研究VRPSDPTW問題,設(shè)計(jì)了一種經(jīng)過仿真實(shí)驗(yàn),來獲取算法里具體參數(shù)的改進(jìn)全局人工魚群算法去求解該問題.李珺等[13]為研究VRPSDPTW問題,設(shè)計(jì)了一種自適應(yīng)大規(guī)模鄰域搜索與模擬退火結(jié)合的混合算法,對56個(gè)大規(guī)模算例進(jìn)行驗(yàn)證.

綜上所述,目前已有很多學(xué)者對MDHOVRP問題和VRPSDPTW問題進(jìn)行了深入研究,但很少有學(xué)者將兩個(gè)問題結(jié)合一起研究.因此本文從實(shí)際出發(fā),研究了MDHOVRP問題和VRPSDPTW問題相結(jié)合的帶軟時(shí)間窗的多中心半開放式同時(shí)送取貨車輛路徑問題 (Multi-depot Half Open Vehicle Routing Problem with Simultaneous Delivery-Pickup and Soft Time Windows, 下文簡稱MDHOVRPSDPSTW),采用租賃第三方物流公司的車輛對客戶點(diǎn)同時(shí)進(jìn)行送取服務(wù),車輛配送完路線上的所有客戶點(diǎn)后,就近返回任意配送中心,縮短了配送路徑,節(jié)約了配送成本.針對MDHOVRPSDPSTW問題的特點(diǎn)及其復(fù)雜性,設(shè)計(jì)了一種自適應(yīng)精英算法求解,引入自適應(yīng)機(jī)制和精英保留策略,既可以保護(hù)優(yōu)秀個(gè)體,又增強(qiáng)了算法的全局搜索能力.通過具體的案例分析,驗(yàn)證了模型和算法的有效性.

1 數(shù)學(xué)模型

1.1 問題描述

本文所研究的MDHOVRPSDPSTW問題,定義如下:已知多個(gè)配送中心和若干個(gè)客戶點(diǎn)的具體數(shù)目及坐標(biāo)位置,采用租賃的外部車輛為客戶點(diǎn)提供送取服務(wù),每輛配送車輛相同,且為提高送取貨效率,車輛載貨空間可分為送貨取貨兩個(gè)獨(dú)立空間.車輛從任意配送中心出發(fā),裝載著配送路線所需配送的所有貨物,對其配送路線上的所有客戶點(diǎn)執(zhí)行同時(shí)送取任務(wù).車輛在配送過程中必須滿足自身載重約束,當(dāng)車輛服務(wù)完配送路線上所有客戶點(diǎn)后,根據(jù)車輛服務(wù)路線中最后一個(gè)客戶點(diǎn)離各個(gè)配送中心的歐式距離,就近返回某個(gè)配送中心.最后,車輛在其所返回的配送中心卸完所取的貨后,自行返回第三方車輛租賃公司,決策的目標(biāo)是求解得到既符合所有約束條件,又能使總配送成本最低的配送方案.

1.2 模型假設(shè)

為了求解MDHOVRPSDPSTW問題,建立了如下基本假設(shè):

1)配送中心、客戶點(diǎn)的坐標(biāo)和數(shù)量已知;

2)客戶點(diǎn)的送取需求和服務(wù)的具體時(shí)間窗均已知;

3)所有租賃車輛載重量和車型已知且完全一樣;

4) 每個(gè)客戶點(diǎn)由同一輛車同時(shí)提供送取服務(wù),且送取需求能在1次配送中得到滿足;

5)車輛勻速行駛;

6)采用原有配送中心進(jìn)行配送不考慮其建設(shè)成本.

1.3 符號(hào)說明

1.3.1 模型參數(shù)

M{i|i=n+1,n+2,…,n+m}為配送中心集合,N{j|j=1,2,…,n}為客戶點(diǎn)集合,V{k|k=1,2,…,K}為車輛集合,G為配送網(wǎng)絡(luò)所有節(jié)點(diǎn)集合,即G={M}∪{N}.Zi為配送中心i(i∈M)的最大容量;cj為客戶j(j∈N)的送貨需求;wj為客戶點(diǎn)j(j∈N)的取貨需求;dab為節(jié)點(diǎn)a(a∈G)與節(jié)點(diǎn)b(b∈G)之間的距離;Ok為車輛k(k∈V)的派遣成本;F為單位距離車輛行駛成本;Q1為車輛k(k∈V)的送貨裝載容量;Q2為車輛的取貨裝載容量,tab為車輛k(k∈V)從節(jié)點(diǎn)a(a∈G)到節(jié)點(diǎn)b(b∈N)的行駛時(shí)間;[Ej,Lj]為客戶點(diǎn)j的時(shí)間窗.Tbk為車輛k(k∈V)到達(dá)節(jié)點(diǎn)b(b∈N)的時(shí)間,ta為車輛在節(jié)點(diǎn)a(a∈N)處等待時(shí)間,t′a為車輛在節(jié)點(diǎn)a(a∈N)處的服務(wù)時(shí)間,Tbk=Tak+tab+ta+t′a,若b∈M時(shí),Tbk=0.α為單位時(shí)間提前到達(dá)的懲罰成本,β為單位時(shí)間遲到懲罰成本.

1.3.2 決策變量

其中:a,b∈G,a≠b.

其中:k∈V,i∈M.

1.4 模型構(gòu)建

(1)

(2)

(3)

(4)

(5)

(6)

xabk(Tbk-Tak)≥0, ?a,b∈G,k∈V

(7)

Tbk=Tak+tab+ta+t′a,

?a∈G, ?b∈N, ?k∈V

(8)

ta=max{Ea-Tak, 0}, ?a∈G, ?k∈V

(9)

yik={0,1}, ?i∈M, ?k∈V

(10)

xabk={0, 1}, ?a,b∈G,k∈V

(11)

目標(biāo)函數(shù)式(1)表示使總成本最小,其中包括運(yùn)輸成本、車輛租賃成本以及早到和遲到的懲罰成本;約束式(2)、(3)分別使得每輛車送貨量、取貨量小于其送貨裝載容量和取貨裝載容量;式(4)表示車輛只從其派遣的配送中心出發(fā)一次,服務(wù)完路線上所有客戶點(diǎn)后,可以返回任意配送中心;式(5)表示配送車從哪個(gè)客戶點(diǎn)進(jìn),也要從哪個(gè)客戶點(diǎn)出;式(6)表示所有的客戶點(diǎn)都只有1輛車服務(wù);式(7)表示車輛提供送取服務(wù)有一定順序;式(8)～(9)為客戶點(diǎn)時(shí)間窗約束;式(10)～(11)表示0-1決策變量.

2 改進(jìn)遺傳算法設(shè)計(jì)

遺傳算法(Genetic Algorithm)是美國John Holland教授在1975年率先提出的,是一種模擬自然環(huán)境中生物的遺傳和進(jìn)化過程搜索得到最優(yōu)解的方法.該算法的特點(diǎn)是運(yùn)算速度較快,相較于一般的精確算法更為簡單,針對一般的復(fù)雜組合問題能得到較優(yōu)的結(jié)果.

根據(jù)MDHOVRPSDPSTW問題的復(fù)雜性,本文設(shè)計(jì)了一種自適應(yīng)精英遺傳算法對其求解,引入了自適應(yīng)交叉、變異算子與精英保留策略,不僅增強(qiáng)了算法的全局優(yōu)化能力,還均衡了算法的局部搜索能力.自適應(yīng)精英遺傳算法的流程圖如圖1所示.

圖1 自適應(yīng)精英遺傳算法流程圖

2.1 編碼與解碼

2.1.1 編碼

為更好的求解MDHOVRPSDPSTW問題,本文設(shè)計(jì)了一種雙層編碼的方式.假設(shè)有m個(gè)配送中心和n個(gè)客戶點(diǎn),第一層n個(gè)編碼表示客戶點(diǎn)的服務(wù)次序,第二層n個(gè)編碼表示客戶點(diǎn)為相應(yīng)的配送中心的車輛進(jìn)行配送.以下表示一個(gè)配送中心為2個(gè),受災(zāi)點(diǎn)為10個(gè)的解的編碼方式.

第一層編碼19756321084

2.1.2 解碼

如上述編碼所示,由配送中心1發(fā)出的車輛服務(wù)的客戶點(diǎn)有5、6、10、8,由配送中心2發(fā)出的車輛服務(wù)的 客戶點(diǎn)1、9、7、3、2、4.本文所研究的路徑是半開放式的,因此可先引進(jìn)配送中心0,作為每條路徑所服務(wù)的最后一個(gè)點(diǎn)距離最近的配送中心.以配送中心1發(fā)出的車輛路徑為例,根據(jù)客戶點(diǎn)的送取貨量以及各種約束,假設(shè)分成兩條路徑并將配送中心0插入到上述路徑中,則其對應(yīng)的配送次序可為

156011080

若在第一條路徑中,客戶點(diǎn)6是路線里最后一個(gè)客戶點(diǎn),又與配送中心1的歐式距離最短,則配送車根據(jù)就近原則返回配送中心1,反之返回配送中心2.假設(shè)客戶點(diǎn)6離配送中心1近,客戶點(diǎn)8離配送中心2近則解碼為

就近返回配送中心11561

2.2 初始種群的生成

由于使用隨機(jī)的方法生成的初始種群,容易形成多個(gè)劣質(zhì)方案,影響整體解的質(zhì)量,故本文采用掃描法[14]生成初始種群,能使種群一開始就表現(xiàn)較優(yōu).具體步驟如下:1)建立一個(gè)極坐標(biāo)系,并以配送中心為原點(diǎn),過原點(diǎn)連接任一客戶點(diǎn)形成射線并逆時(shí)針轉(zhuǎn)動(dòng);2)疊加射線掃過扇面所包含客戶點(diǎn)的送取量,當(dāng)已掃過的客戶點(diǎn)的送取量之和滿足車輛送取量約束后停止轉(zhuǎn)動(dòng),得到一個(gè)客戶點(diǎn)分群;3)重復(fù)操作,建立新的客戶點(diǎn)分群,直到所有客戶點(diǎn)全部被覆蓋.

2.3 適應(yīng)度函數(shù)

本文針對MDHOVRPSDPSTW問題,建立了以總配送成本最小為目標(biāo)的優(yōu)化模型.令U=minZ,為使適應(yīng)度函數(shù)最大化,則適應(yīng)度函數(shù)可表示為f(x)=1/U.

2.4 遺傳操作

2.4.1 選擇操作

本文采用輪盤賭選擇法來進(jìn)行選擇操作.

2.4.2 交叉操作

本文采用的是雙層編碼的方式,兩層編碼均可進(jìn)行獨(dú)立的交叉變異.在交叉操作中,第一層采用順序交叉法,隨機(jī)選擇兩條染色體,后對兩條之中的任意一條染色體隨機(jī)切片,并任意復(fù)制一個(gè)片段到子代的同樣的位置,后在另一條染色體上將子代片段中沒有的基因根據(jù)順序填進(jìn)去,另一個(gè)子代也采用同樣的方法獲得.第二層編碼采用的是單點(diǎn)交叉法,隨機(jī)選取兩條染色體作為父代染色體,后在兩條父代染色體上任意選擇位置點(diǎn)進(jìn)行切割,然后相互交換切割的右側(cè)部分,以此獲得兩條不相同的子染色體.

2.4.3 變異操作

在變異操作中,本文兩層編碼均采用動(dòng)態(tài)變異策略.即在父代染色體上,任意選擇兩個(gè)或以上的基因位,進(jìn)行動(dòng)態(tài)置換,經(jīng)過置換的基因即為變異基因可遺傳給子代,再繼續(xù)進(jìn)行后續(xù)進(jìn)化.

2.5 自適應(yīng)機(jī)制

本文引入自適應(yīng)機(jī)制[15],該機(jī)制可以自適應(yīng)地調(diào)動(dòng)交叉概率pc與變異概率pm,能夠防止算法局部收斂和早熟,提高了算法的全局搜索能力,縮短了算法的尋優(yōu)時(shí)間.

(12)

(13)

2.6 精英保留策略

3 實(shí)例分析

3.1 基礎(chǔ)數(shù)據(jù)

某企業(yè)有3個(gè)配送中心,租賃外部車輛,對20個(gè)客戶點(diǎn)進(jìn)行同時(shí)送取貨服務(wù).每輛車的租賃成本為480元,車輛的載貨空間分為送貨、取貨兩種空間,且送貨、取貨的空間容量均為100,配送車平均速度為60 km/h,單位行駛成本為3元.本文采用軟時(shí)間窗約束,提前到達(dá)和遲到均懲罰100元/h,假定所有客戶點(diǎn)的送取貨的服務(wù)時(shí)間均為0.3 h.3個(gè)配送中心分別用A、B、C表示,其他數(shù)據(jù)見表1.

表1 配送中心和客戶點(diǎn)數(shù)據(jù)

3.2 結(jié)果分析

本文利用Matlab R2021a軟件進(jìn)行案例仿真,算法參數(shù)設(shè)置如下:種群規(guī)模為100;最大迭代次數(shù)為500;基礎(chǔ)交叉概率k1=0.8,基礎(chǔ)變異概率k2=0.2.經(jīng)過多次實(shí)驗(yàn)求解,求解得到最優(yōu)總成本為4 534.99元,路線總長為704.12 km,共使用5輛車進(jìn)行配送,時(shí)間窗懲罰成本為22.63元,見表2.圖2、3分別為本方案的算法迭代圖和配送路徑圖.從圖2可以看出本文所設(shè)計(jì)自適應(yīng)精英遺傳算法,全局搜索性能較強(qiáng),易跳出局部最優(yōu),收斂速度快.從圖3可以看出半開放式配送路徑的特點(diǎn),車輛在服務(wù)完路線所有客戶點(diǎn)后,不一定返回起始配送中心.每輛車具體服務(wù)的客戶點(diǎn)及配送路徑方案見表3.

表2 輸出數(shù)據(jù)

表3 配送路徑方案

圖2 算法迭代圖

該結(jié)果符合總成本最低的原則,減少了車輛的配送距離,使得資源得到合理的配置,證明了模型和算法的有效性.

4 結(jié) 語

本文將MDHOVRP問題和VRPSDPTW問題相結(jié)合,研究了MDHOVRPSDPSTW問題.構(gòu)建了以配送總成本最小為目標(biāo)的優(yōu)化模型,更好地滿足了物流企業(yè)運(yùn)營的實(shí)際需求.該模型從全局的角度出發(fā),有利于物流系統(tǒng)的整體優(yōu)化,采取半開放式的配送方式,減少了車輛的配送距離,使資源得到合理的配置.在求解模型時(shí),采用掃描法的方式生成初始種群,并引入精英保留策略和自適應(yīng)機(jī)制,設(shè)計(jì)了自適應(yīng)精英遺傳算法.通過案例仿真實(shí)驗(yàn)驗(yàn)證了模型和算法的有效性.此外,在今后的研究中,可通過考慮時(shí)間窗的模糊性、交通運(yùn)輸?shù)膭?dòng)態(tài)性和客戶滿意度使模型更好地滿足不同情景的客戶需求.