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

陳榮虎,張建宏,徐 禎

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

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

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

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

1 數(shù)學模型

1.1 問題描述

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

1.2 模型假設

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

1)配送中心、客戶點的坐標和數(shù)量已知;

2)客戶點的送取需求和服務的具體時間窗均已知;

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

4) 每個客戶點由同一輛車同時提供送取服務,且送取需求能在1次配送中得到滿足;

5)車輛勻速行駛;

6)采用原有配送中心進行配送不考慮其建設成本.

1.3 符號說明

1.3.1 模型參數(shù)

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

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)

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

2 改進遺傳算法設計

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

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

圖1 自適應精英遺傳算法流程圖

2.1 編碼與解碼

2.1.1 編碼

為更好的求解MDHOVRPSDPSTW問題,本文設計了一種雙層編碼的方式.假設有m個配送中心和n個客戶點,第一層n個編碼表示客戶點的服務次序,第二層n個編碼表示客戶點為相應的配送中心的車輛進行配送.以下表示一個配送中心為2個,受災點為10個的解的編碼方式.

第一層編碼19756321084

2.1.2 解碼

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

156011080

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

就近返回配送中心11561

2.2 初始種群的生成

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

2.3 適應度函數(shù)

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

2.4 遺傳操作

2.4.1 選擇操作

本文采用輪盤賭選擇法來進行選擇操作.

2.4.2 交叉操作

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

2.4.3 變異操作

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

2.5 自適應機制

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

(12)

(13)

2.6 精英保留策略

3 實例分析

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

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

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

3.2 結(jié)果分析

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

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

表3 配送路徑方案

圖2 算法迭代圖

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

4 結(jié) 語

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