基于送貨時間窗的物流配送車輛路徑問題研究

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

ZHAO Xiao-ting (School of Traffic and Transportation, Lanzhou Jiaotong University, Lanzhou 730070, China)

0 引 言

物流配送管理的核心問題就是配送車輛路徑問題，而帶有時間窗的配送車輛路徑問題是由此演化而來的。此類問題要求車輛必須在用戶規(guī)定的時間窗內(nèi)對客戶進(jìn)行服務(wù)，每個顧客僅被服務(wù)一次，如果不能在用戶規(guī)定的時間窗內(nèi)完成服務(wù)則引入適當(dāng)?shù)难诱`懲罰。問題具有極強(qiáng)的現(xiàn)實(shí)意義，如銀行運(yùn)鈔車調(diào)度問題、接送學(xué)生校車問題、冷鮮蔬菜海鮮配送問題[1]等，已經(jīng)在配送問題的研究領(lǐng)域引起了很大的關(guān)注度。郭建紅[2]建立了帶時間窗的動態(tài)車輛路徑優(yōu)化模型，提出了采用兩階段法求解策略和改進(jìn)型遺傳算法。張炯，郎茂祥[3]建立了該問題的基于直觀描述的數(shù)學(xué)模型，通過設(shè)計新的解的表示方法構(gòu)造了求解該問題的禁忌搜索算法。對于帶有時間窗的配送車輛路徑問題采用節(jié)約算法[4-5]進(jìn)行求解，混合算法[8]進(jìn)行求解，論文[6-7]對此問題采用改進(jìn)的遺傳算法求解。

為了解決帶有送貨時間窗的配送車輛路徑問題，本文建立了該問題的整數(shù)規(guī)劃模型，并用遺傳算法對模型進(jìn)行求解，對實(shí)例進(jìn)行計算得到最優(yōu)路徑配送方案。

1 帶有送貨時間窗的物流配送車輛路徑模型

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表示車輛訪問?。╥,j）產(chǎn)生的配送成本，ai表示用戶i允許最早開始的服務(wù)時間，bi表示客戶i允許最晚開始的服務(wù)時間，[ai,bi]為用戶i的時間窗，si表示車輛到達(dá)用戶點(diǎn)i的時刻，fi表示車輛在用戶點(diǎn)i的服務(wù)時間，tij表示用戶點(diǎn)i到用戶點(diǎn)j的行駛時間，C1表示車輛早到的單位成本，C2表示單位車輛遲到的單位成本，Ci（ti）表示車輛在t時刻到達(dá)用戶i時所對應(yīng)的懲罰成本，引入決策變量xijk，當(dāng)xijk=1 時表示車輛k訪問?。╥,j），否則xijk=0。

1.2 模型假設(shè)。（1） 物品流向?yàn)閱蜗?，即純送貨；?） 配送中心只有一個，每條線路起始點(diǎn)都是配送中心，配送中心和客戶點(diǎn)的位置坐標(biāo)己知：（3） 車輛為同種車型，且容量已知，在配送過程中不得超過其額定載重量，車輛數(shù)量給定，且沒有行駛距離限制；（4） 每個客戶必須且只能被訪問一次，該點(diǎn)貨物只能由一輛汽本完成，每輛車從車場出發(fā)最后必須返回車場；（5） 每個客戶都有一個規(guī)定的時間窗[ai,bi]，送貨時刻最好在此時間范圍內(nèi)進(jìn)行，時間窗約束考慮軟時間窗，即配送車輛如無法在客戶指定的時間范圍內(nèi)完成配送任務(wù)，則要懲罰。

目標(biāo)函數(shù)為：

約束條件：

約束（2）、（3） 表示每個用戶只被一輛車服務(wù)一次，約束（4） 表示車輛駛?cè)胗脩鬷，必定會駛出用戶i，約束（5） 表示載重量約束，分配給k車輛的載重量不能超過車輛載重量Q，約束（6） 為用戶節(jié)點(diǎn)時間窗約束，約束（7） 為懲罰函數(shù)。

2 遺傳算法對模型求解

遺傳算法是模擬生物進(jìn)化規(guī)律基于適者生存的一種自適應(yīng)全局優(yōu)化概率搜索算法。遺傳算法構(gòu)造一個適應(yīng)度函數(shù)對種群進(jìn)行不斷的選擇、交叉、變異等操作，最終獲得最優(yōu)解。利用該算法可以較好地解決VRP 問題。

2.1 編碼。遺傳算法的編碼都是可理解為解的代碼表現(xiàn)形式，VRPTW 問題的編碼可以采用自然編碼的方法，直接產(chǎn)生一組不重復(fù)的自然數(shù)的排列，該排列構(gòu)成了問題的一個解，并且對應(yīng)一種配送方案。根據(jù)約束可按順序依次劃分各輛車的配送路徑。

2.2 適應(yīng)度函數(shù)。適應(yīng)度函數(shù)是評價每個染色體優(yōu)劣的函數(shù)，是獲得最優(yōu)染色體的基本依據(jù)，一般與目標(biāo)函數(shù)有密切的聯(lián)系，一般目標(biāo)函數(shù)為Z（x），設(shè)計的適應(yīng)度函數(shù)為：

其中Cmax為一個適當(dāng)相對較大的數(shù)。

2.3 遺傳操作。評價函數(shù)是遺傳過程中優(yōu)勝劣汰的基本依據(jù)，選擇優(yōu)良的染色體以較大的概率進(jìn)入種群，反之劣質(zhì)的染色體被選入種群的概率較小。采用輪盤賭選擇操作，評價函數(shù)越大，在輪盤中所占比例越大，該染色體選入種群的概率也越大。其具體選中概率為：

2.4 交叉規(guī)則。交叉是種群中的個體為父代，依照一定的規(guī)則互相交換特定位置的基因信息，從而產(chǎn)生繼承父代大部分信息又不同于父代的子代染色體，這里具體采用雙點(diǎn)交叉操作，在個體編碼串中隨機(jī)設(shè)置兩個交叉點(diǎn)，然后再進(jìn)行部分基因交換。

2.5 變異規(guī)則。采用倒位變異操作，是指隨機(jī)選定連續(xù)排列中的一部分客戶，將這部分客戶的排列進(jìn)行倒置。假設(shè)個體為123|4567|8，選中4567 部分，進(jìn)行倒位操作，則通過倒位變異操作后個體就變成了123|7654|8。

3 實(shí)例應(yīng)用

某物流中心分布在一個30km 的正方形區(qū)域內(nèi)，有一個配送點(diǎn)和15 個用戶，配送中心編號為0，配送中心的坐標(biāo)為（20,12），用戶編號依次為1,2,…,15，物流中心配有5 輛型號相同的貨運(yùn)車，時間窗采用24 小時制，每輛車的載重為8.5t 配送的單位距離成本為5 元/公里，貨車的平均行駛速度為35 公里/小時，貨車早到的懲罰成本C1為8 元/小時，遲到的懲罰成本C2為20 元/小時，計算機(jī)隨機(jī)產(chǎn)生15 個用戶坐標(biāo)如表1 所示。

利用遺傳算法對實(shí)例求解得到的初始優(yōu)化配送方案如表2 所示。

初始優(yōu)化配送方案路徑如圖1 所示。

各路徑到達(dá)和離開用戶的時間情況如表3 所示。間、出發(fā)時間以及早晚點(diǎn)情況。

4 結(jié) 論

針對帶有送貨時間窗的物流配送問題，采用遺傳算法求解，建立了帶有軟時間窗的懲罰函數(shù)的配送整數(shù)規(guī)劃模型。該模型更加貼合用戶對于時間窗約束的要求，制定了結(jié)合不同實(shí)際的配送車輛路徑問題的配送策略。方法原理適用性強(qiáng)，有一定的操作性，具有實(shí)際應(yīng)用的價值，計算效率較高，可為實(shí)際的物流配送問題的解決提供參考。

表1 客戶初始信息表

表2 初始最優(yōu)配送方案

圖1 初始配送方案配送路徑圖

表3 子路徑車輛達(dá)到和出發(fā)時間情況

[1] 潘立軍. 帶時間窗車輛路徑問題及其算法研究[D]. 長沙：中南大學(xué)（博士學(xué)位論文），2012.

[2] 郭建紅. 帶時間窗的卷煙物流配送動態(tài)車輛路徑優(yōu)化方法研究[D]. 北京：北京交通大學(xué)（碩士學(xué)位論文），2013.

[3] 張炯，郎茂祥. 有時間窗配送車輛調(diào)度問題的禁忌搜索算法[J]. 北方交通大學(xué)學(xué)報，2004,28(2):103-106.

[4] 王海麗，王勇，曾永長. 帶時間窗的易腐食品冷藏車輛配送問題[J]. 工業(yè)工程，2008,11(3):127-130.

[5] 董立娟. 帶時間窗約束的冷鮮肉制品配送路徑優(yōu)化[D]. 長沙：中南大學(xué)（碩士學(xué)位論文），2011.

[6] 楊文超. 顧客時間窗變化的物流配送干擾管理模型及其算法[D]. 大連：大連理工大學(xué)（博士學(xué)位論文），2012.

[7] 吳紅麗. 基于時間窗的家電行業(yè)物流配送路徑優(yōu)化問題研究[D]. 武漢：武漢科技大學(xué)（碩士學(xué)位論文），2013.

[8] 張瑞鋒. 基于混合算法的帶時間窗的車輛路徑問題求解[J]. 計算機(jī)工程，2007(14):47-53.