趙曉婷 (蘭州交通大學(xué) 交通運(yùn)輸學(xué)院,甘肅 蘭州730070)
ZHAO Xiao-ting (School of Traffic and Transportation, Lanzhou Jiaotong University, Lanzhou 730070, China)
物流配送管理的核心問題就是配送車輛路徑問題,而帶有時(shí)間窗的配送車輛路徑問題是由此演化而來的。此類問題要求車輛必須在用戶規(guī)定的時(shí)間窗內(nèi)對客戶進(jìn)行服務(wù),每個(gè)顧客僅被服務(wù)一次,如果不能在用戶規(guī)定的時(shí)間窗內(nèi)完成服務(wù)則引入適當(dāng)?shù)难诱`懲罰。問題具有極強(qiáng)的現(xiàn)實(shí)意義,如銀行運(yùn)鈔車調(diào)度問題、接送學(xué)生校車問題、冷鮮蔬菜海鮮配送問題[1]等,已經(jīng)在配送問題的研究領(lǐng)域引起了很大的關(guān)注度。郭建紅[2]建立了帶時(shí)間窗的動(dòng)態(tài)車輛路徑優(yōu)化模型,提出了采用兩階段法求解策略和改進(jìn)型遺傳算法。張炯,郎茂祥[3]建立了該問題的基于直觀描述的數(shù)學(xué)模型,通過設(shè)計(jì)新的解的表示方法構(gòu)造了求解該問題的禁忌搜索算法。對于帶有時(shí)間窗的配送車輛路徑問題采用節(jié)約算法[4-5]進(jìn)行求解,混合算法[8]進(jìn)行求解,論文[6-7]對此問題采用改進(jìn)的遺傳算法求解。
為了解決帶有送貨時(shí)間窗的配送車輛路徑問題,本文建立了該問題的整數(shù)規(guī)劃模型,并用遺傳算法對模型進(jìn)行求解,對實(shí)例進(jìn)行計(jì)算得到最優(yōu)路徑配送方案。
1.1 問題的描述。在配送網(wǎng)絡(luò)中,N代表配送中心所有的用戶節(jié)點(diǎn)N={1,2,…,N},節(jié)點(diǎn)0 表示配送中心車場,V表示全部的節(jié)點(diǎn)集V=N∪{0 },(i,j)表示弧集i,j∈V,i≠j,K={1,2,…,M}表示配送車輛的集合,M表示車輛數(shù),Q表示每輛車的最大載重量,di表示用戶i的需求量,Cij表示車輛訪問弧(i,j)產(chǎn)生的配送成本,ai表示用戶i允許最早開始的服務(wù)時(shí)間,bi表示客戶i允許最晚開始的服務(wù)時(shí)間,[ai,bi]為用戶i的時(shí)間窗,si表示車輛到達(dá)用戶點(diǎn)i的時(shí)刻,fi表示車輛在用戶點(diǎn)i的服務(wù)時(shí)間,tij表示用戶點(diǎn)i到用戶點(diǎn)j的行駛時(shí)間,C1表示車輛早到的單位成本,C2表示單位車輛遲到的單位成本,Ci(ti)表示車輛在t時(shí)刻到達(dá)用戶i時(shí)所對應(yīng)的懲罰成本,引入決策變量xijk,當(dāng)xijk=1 時(shí)表示車輛k訪問?。╥,j),否則xijk=0。
1.2 模型假設(shè)。(1) 物品流向?yàn)閱蜗颍醇兯拓?;?) 配送中心只有一個(gè),每條線路起始點(diǎn)都是配送中心,配送中心和客戶點(diǎn)的位置坐標(biāo)己知:(3) 車輛為同種車型,且容量已知,在配送過程中不得超過其額定載重量,車輛數(shù)量給定,且沒有行駛距離限制;(4) 每個(gè)客戶必須且只能被訪問一次,該點(diǎn)貨物只能由一輛汽本完成,每輛車從車場出發(fā)最后必須返回車場;(5) 每個(gè)客戶都有一個(gè)規(guī)定的時(shí)間窗[ai,bi],送貨時(shí)刻最好在此時(shí)間范圍內(nèi)進(jìn)行,時(shí)間窗約束考慮軟時(shí)間窗,即配送車輛如無法在客戶指定的時(shí)間范圍內(nèi)完成配送任務(wù),則要懲罰。
目標(biāo)函數(shù)為:
約束條件:
約束(2)、(3) 表示每個(gè)用戶只被一輛車服務(wù)一次,約束(4) 表示車輛駛?cè)胗脩鬷,必定會(huì)駛出用戶i,約束(5) 表示載重量約束,分配給k車輛的載重量不能超過車輛載重量Q,約束(6) 為用戶節(jié)點(diǎn)時(shí)間窗約束,約束(7) 為懲罰函數(shù)。
遺傳算法是模擬生物進(jìn)化規(guī)律基于適者生存的一種自適應(yīng)全局優(yōu)化概率搜索算法。遺傳算法構(gòu)造一個(gè)適應(yīng)度函數(shù)對種群進(jìn)行不斷的選擇、交叉、變異等操作,最終獲得最優(yōu)解。利用該算法可以較好地解決VRP 問題。
2.1 編碼。遺傳算法的編碼都是可理解為解的代碼表現(xiàn)形式,VRPTW 問題的編碼可以采用自然編碼的方法,直接產(chǎn)生一組不重復(fù)的自然數(shù)的排列,該排列構(gòu)成了問題的一個(gè)解,并且對應(yīng)一種配送方案。根據(jù)約束可按順序依次劃分各輛車的配送路徑。
2.2 適應(yīng)度函數(shù)。適應(yīng)度函數(shù)是評價(jià)每個(gè)染色體優(yōu)劣的函數(shù),是獲得最優(yōu)染色體的基本依據(jù),一般與目標(biāo)函數(shù)有密切的聯(lián)系,一般目標(biāo)函數(shù)為Z(x),設(shè)計(jì)的適應(yīng)度函數(shù)為:
其中Cmax為一個(gè)適當(dāng)相對較大的數(shù)。
2.3 遺傳操作。評價(jià)函數(shù)是遺傳過程中優(yōu)勝劣汰的基本依據(jù),選擇優(yōu)良的染色體以較大的概率進(jìn)入種群,反之劣質(zhì)的染色體被選入種群的概率較小。采用輪盤賭選擇操作,評價(jià)函數(shù)越大,在輪盤中所占比例越大,該染色體選入種群的概率也越大。其具體選中概率為:
2.4 交叉規(guī)則。交叉是種群中的個(gè)體為父代,依照一定的規(guī)則互相交換特定位置的基因信息,從而產(chǎn)生繼承父代大部分信息又不同于父代的子代染色體,這里具體采用雙點(diǎn)交叉操作,在個(gè)體編碼串中隨機(jī)設(shè)置兩個(gè)交叉點(diǎn),然后再進(jìn)行部分基因交換。
2.5 變異規(guī)則。采用倒位變異操作,是指隨機(jī)選定連續(xù)排列中的一部分客戶,將這部分客戶的排列進(jìn)行倒置。假設(shè)個(gè)體為123|4567|8,選中4567 部分,進(jìn)行倒位操作,則通過倒位變異操作后個(gè)體就變成了123|7654|8。
某物流中心分布在一個(gè)30km 的正方形區(qū)域內(nèi),有一個(gè)配送點(diǎn)和15 個(gè)用戶,配送中心編號為0,配送中心的坐標(biāo)為(20,12),用戶編號依次為1,2,…,15,物流中心配有5 輛型號相同的貨運(yùn)車,時(shí)間窗采用24 小時(shí)制,每輛車的載重為8.5t 配送的單位距離成本為5 元/公里,貨車的平均行駛速度為35 公里/小時(shí),貨車早到的懲罰成本C1為8 元/小時(shí),遲到的懲罰成本C2為20 元/小時(shí),計(jì)算機(jī)隨機(jī)產(chǎn)生15 個(gè)用戶坐標(biāo)如表1 所示。
利用遺傳算法對實(shí)例求解得到的初始優(yōu)化配送方案如表2 所示。
初始優(yōu)化配送方案路徑如圖1 所示。
各路徑到達(dá)和離開用戶的時(shí)間情況如表3 所示。間、出發(fā)時(shí)間以及早晚點(diǎn)情況。
針對帶有送貨時(shí)間窗的物流配送問題,采用遺傳算法求解,建立了帶有軟時(shí)間窗的懲罰函數(shù)的配送整數(shù)規(guī)劃模型。該模型更加貼合用戶對于時(shí)間窗約束的要求,制定了結(jié)合不同實(shí)際的配送車輛路徑問題的配送策略。方法原理適用性強(qiáng),有一定的操作性,具有實(shí)際應(yīng)用的價(jià)值,計(jì)算效率較高,可為實(shí)際的物流配送問題的解決提供參考。
表1 客戶初始信息表
表2 初始最優(yōu)配送方案
圖1 初始配送方案配送路徑圖
表3 子路徑車輛達(dá)到和出發(fā)時(shí)間情況
[1] 潘立軍. 帶時(shí)間窗車輛路徑問題及其算法研究[D]. 長沙:中南大學(xué)(博士學(xué)位論文),2012.
[2] 郭建紅. 帶時(shí)間窗的卷煙物流配送動(dòng)態(tài)車輛路徑優(yōu)化方法研究[D]. 北京:北京交通大學(xué)(碩士學(xué)位論文),2013.
[3] 張炯,郎茂祥. 有時(shí)間窗配送車輛調(diào)度問題的禁忌搜索算法[J]. 北方交通大學(xué)學(xué)報(bào),2004,28(2):103-106.
[4] 王海麗,王勇,曾永長. 帶時(shí)間窗的易腐食品冷藏車輛配送問題[J]. 工業(yè)工程,2008,11(3):127-130.
[5] 董立娟. 帶時(shí)間窗約束的冷鮮肉制品配送路徑優(yōu)化[D]. 長沙:中南大學(xué)(碩士學(xué)位論文),2011.
[6] 楊文超. 顧客時(shí)間窗變化的物流配送干擾管理模型及其算法[D]. 大連:大連理工大學(xué)(博士學(xué)位論文),2012.
[7] 吳紅麗. 基于時(shí)間窗的家電行業(yè)物流配送路徑優(yōu)化問題研究[D]. 武漢:武漢科技大學(xué)(碩士學(xué)位論文),2013.
[8] 張瑞鋒. 基于混合算法的帶時(shí)間窗的車輛路徑問題求解[J]. 計(jì)算機(jī)工程,2007(14):47-53.