基于柵格遺傳算法的采購供應(yīng)物流配送車輛路線規(guī)劃方法

張大威，張明廣，劉文浩，彭 振 （重慶中車四方所科技有限公司，重慶 400000）

0 引 言

采購供應(yīng)物流配送車輛路線規(guī)劃問題屬于典型車輛路徑問題，同時(shí)也屬于非線性規(guī)劃問題，在規(guī)劃過程中需要考慮多種因素，包括配送路徑長度、物流成本、配送時(shí)間、車輛裝載能力等，綜合多方面因素規(guī)劃出最合理的配送線路，同時(shí)還要考慮采購供應(yīng)物流配送的時(shí)效性。目前，采購供應(yīng)行業(yè)不斷發(fā)展，線下客戶節(jié)點(diǎn)數(shù)量比較多、配送量比較大，因此采購供應(yīng)物流配送車輛路線規(guī)劃難度比較高，這也使采購供應(yīng)行業(yè)面臨巨大挑戰(zhàn)。車輛路線規(guī)劃關(guān)系到采購供應(yīng)企業(yè)的經(jīng)濟(jì)效益，同時(shí)也直接關(guān)系到企業(yè)配送的服務(wù)質(zhì)量，因此對(duì)配送車輛路線規(guī)劃研究具有重要的現(xiàn)實(shí)意義和價(jià)值。由于國內(nèi)關(guān)于物流配送車輛路徑規(guī)劃研究起步比較晚，相關(guān)理論與技術(shù)還不夠成熟與完善，尤其是在當(dāng)前時(shí)代背景下，用戶對(duì)物流配送線路規(guī)劃要求不斷提高，不僅要保證規(guī)劃的線路最短，同時(shí)還要保證規(guī)劃線路時(shí)間成本最小，線性方法無法達(dá)到預(yù)期的規(guī)劃效果，按照規(guī)劃線路配送耗時(shí)比較長，傳統(tǒng)方法已經(jīng)無法滿足實(shí)際需求，為此提出基于柵格遺傳算法的采購供應(yīng)物流配送車輛路線規(guī)劃方法研究。

1 建立配送車輛線路規(guī)劃目標(biāo)函數(shù)

此次將采購供應(yīng)物流配送車輛線路規(guī)劃問題轉(zhuǎn)換為線路優(yōu)化問題，采用有向圖建立采購供應(yīng)物流配送網(wǎng)絡(luò)，其用公式表示為

式（1）中，G表示采購供應(yīng)物流配送網(wǎng)絡(luò)；V表示所有配送節(jié)點(diǎn)集合，即客戶節(jié)點(diǎn)集合，客戶主要分為靜態(tài)客戶與動(dòng)態(tài)客戶；A表示連接各節(jié)點(diǎn)的邊集；Z表示采購供應(yīng)物流配送中心[1]。針對(duì)配送車輛線路規(guī)劃問題提出以下假設(shè)。

假設(shè)1：每輛配送車的配送總量不能超出車輛的最大載重量；

假設(shè)2：每個(gè)客戶有且僅有一輛配送車輛服務(wù)，服務(wù)次數(shù)只能每天一次；

假設(shè)3：采購供應(yīng)物流配送中心能夠滿足所有配送點(diǎn)需求，不存在缺貨現(xiàn)象；

假設(shè)4：所有車輛完成物流配送后直接返回到采購供應(yīng)物流配送中心；

假設(shè)5：所有配送車輛型號(hào)相同，最大載重量相同；

假設(shè)6：在物流配送過程中不考慮交通堵塞對(duì)配送的影響。

根據(jù)以上假設(shè)，以物流配送成本最小為目標(biāo)建立目標(biāo)函數(shù)，其用公式表示為

式（2）中， minH表示采購供應(yīng)物流配送最小成本；d1表示碳排放成本；d2表示配送車輛啟動(dòng)成本；d3表示油耗成本；d4表示未在規(guī)定時(shí)間內(nèi)完成配送任務(wù)的懲罰成本；d5表示貨損成本[2]。將其轉(zhuǎn)換為另外一種形式

式（3）中，i表示物流配送中心；j表示客戶節(jié)點(diǎn)；k表示配送車輛；sijk表示物流配送車輛由配送中心i到客戶節(jié)點(diǎn)j的距離；cij表示物流配送中心到客戶節(jié)點(diǎn)的距離；za表示單位配送距離成本（碳排放、車輛啟動(dòng)、油耗、貨損等成本總和）；n表示配送車輛數(shù)量；zb表示每輛配送車輛的成本。

2 設(shè)定約束條件

在實(shí)際情況中，采購供應(yīng)物流配送需要滿足一定條件，根據(jù)以上建立的目標(biāo)函數(shù)對(duì)配送車輛的載重進(jìn)行約束，其約束條件為

式（4）中，G表示配送車輛最大載重量；uik表示客戶節(jié)點(diǎn)由第k輛配送車輛配送的貨物量；qi表示客戶節(jié)點(diǎn)所需的貨物總量；xi表示客戶節(jié)點(diǎn)單位貨位體積[3]。其次還需要滿足配送時(shí)間條件，其約束條件用公式表示為

式（5）中，t表示配送車輛達(dá)到客戶節(jié)點(diǎn)處的時(shí)刻；rijk表示一個(gè)0、1的變量，如果存在配送車輛從配送中心到客戶節(jié)點(diǎn)的采購供應(yīng)配送任務(wù)，則rijk為1，如果不存在則rijk為0；t1表示配送車輛從配送中心出發(fā)的時(shí)間；ai表示配送服務(wù)時(shí)長；t2表示配送車輛到達(dá)客戶節(jié)點(diǎn)的時(shí)間[4]。利用以上約束條件規(guī)定配送車輛到達(dá)客戶的時(shí)間點(diǎn)。

3 基于柵格遺傳算法的最優(yōu)線路規(guī)劃決策

根據(jù)約束條件，利用柵格遺傳算法對(duì)以上建立的目標(biāo)函數(shù)進(jìn)行求解，得出最優(yōu)線路規(guī)劃決策；該算法是將采購供應(yīng)物流配送網(wǎng)絡(luò)柵格化，將其劃分為長度相同的柵格，并形成柵格地圖，再用遺傳算法確定采購供應(yīng)物流配送車輛最優(yōu)線路，其具體規(guī)劃流程如圖1所示。

圖1 基于柵格遺傳算法的線路規(guī)劃流程圖

如圖1所示，采用格雷碼編碼方式對(duì)配送網(wǎng)絡(luò)進(jìn)行柵格化處理，單個(gè)柵格的規(guī)格為2×2，生成柵格地圖。對(duì)遺傳種群進(jìn)行初始化，每個(gè)遺傳子代個(gè)體使用二進(jìn)制進(jìn)行編碼，并根據(jù)實(shí)際情況設(shè)定迭代次數(shù)、遺傳因子數(shù)量等參數(shù)[5]。利用適應(yīng)度函數(shù)確定遺傳因子個(gè)體適應(yīng)度與種群適應(yīng)度之間的關(guān)系，其用公式表示為

式（6）中，ε表示遺傳因子個(gè)體與種群之間的適應(yīng)度；k1表示遺傳因子個(gè)體適應(yīng)度；k2表示種群適應(yīng)度；?表示隨機(jī)數(shù)；ρ表示蒙特卡洛算子。利用上述公式確定個(gè)體與種群的適應(yīng)度，每迭代計(jì)算一次都檢驗(yàn)是否滿足迭代終止條件，如果滿足條件則適應(yīng)度最大的個(gè)體為最優(yōu)線路，如果不滿足則對(duì)個(gè)體進(jìn)行遺傳交叉與變異，交叉示意圖如圖2所示。

圖2 個(gè)體交叉操作示意圖

如圖2所示，在上一代遺傳因子個(gè)體中隨機(jī)選擇一段交叉區(qū)段，將其與子代進(jìn)行基因交叉，消除相同區(qū)段，形成新遺傳基因，并將其遺傳給子代，再對(duì)其進(jìn)行變異操作，生成新個(gè)體，迭代步數(shù)加1，再按照上述流程，直到滿足迭代條件為止[6]。輸出個(gè)體為最佳配送車輛線路，以此完成基于柵格遺傳算法的采購供應(yīng)物流配送車輛路線規(guī)劃。

4 實(shí)驗(yàn)論證

4.1 實(shí)驗(yàn)準(zhǔn)備與設(shè)計(jì)

為了驗(yàn)證本文設(shè)計(jì)的基于柵格遺傳算法的采購供應(yīng)物流配送車輛路線規(guī)劃方法的可靠性與可行性，選擇某采購供應(yīng)企業(yè)為實(shí)驗(yàn)對(duì)象，該企業(yè)有7臺(tái)配送車、車輛最大裝貨量為750kg[7]，有1個(gè)配送中心，該配送中心對(duì)應(yīng)10個(gè)配送點(diǎn)（客戶節(jié)點(diǎn)），分布如圖3所示。

圖3 采購供應(yīng)物流配送平面圖

利用本文的設(shè)計(jì)方法對(duì)采購供應(yīng)物流配送車輛路線進(jìn)行規(guī)劃，并選擇兩種傳統(tǒng)方法作對(duì)比，兩種傳統(tǒng)方法分別為遺傳算法和改進(jìn)蟻群算法，以下用傳統(tǒng)方法1與傳統(tǒng)方法2表示[8]。配送中出現(xiàn)的客戶需求如表1所示。

表1 配送需求信息

按照上述流程對(duì)物流配送車輛路線進(jìn)行規(guī)劃，規(guī)劃結(jié)果如表2所示。

表2 采購供應(yīng)物流配送車輛路線規(guī)劃

在可接受時(shí)間范圍內(nèi)完成所有貨物配送，本設(shè)計(jì)方法可以完成采購供應(yīng)物流配送車輛路線規(guī)劃任務(wù)，以下對(duì)具體規(guī)劃效果進(jìn)行檢驗(yàn)。

4.2 實(shí)驗(yàn)結(jié)果討論

實(shí)驗(yàn)以物流配送耗時(shí)作為三種方法的性能評(píng)價(jià)指標(biāo)，配送耗時(shí)最短表示規(guī)劃的線路最合理，隨機(jī)選取4次配送車輛路線，對(duì)4次配送耗時(shí)進(jìn)行統(tǒng)計(jì)，根據(jù)統(tǒng)計(jì)數(shù)據(jù)繪制3種方法配送耗時(shí)對(duì)比圖如圖4所示。

圖4 3種方法規(guī)劃路線耗時(shí)對(duì)比圖

從圖4可以看出，按照本文的設(shè)計(jì)方法規(guī)劃的路線配送，配送用時(shí)比較短，與傳統(tǒng)方法1相比，4次物流配送節(jié)約將近80分鐘，與傳統(tǒng)方法2相比，4次物流配送節(jié)約將近110分鐘[9]。因此本次實(shí)驗(yàn)證明了本文的設(shè)計(jì)方法規(guī)劃的物流配送路線的時(shí)間成本最小，規(guī)劃路線的合理性優(yōu)于傳統(tǒng)方法，相比兩種傳統(tǒng)方法更適用于采購供應(yīng)物流車輛路線規(guī)劃。

5 結(jié) 語

本次研究針對(duì)當(dāng)前物流配送車輛路線規(guī)劃理論存在的不足，參考相關(guān)文獻(xiàn)資料，將柵格遺傳算法應(yīng)用到線路規(guī)劃中，提出了全新的規(guī)劃思路，并通過實(shí)驗(yàn)論證了該思路的可行性與可靠性，對(duì)現(xiàn)有理論進(jìn)行了完善，是對(duì)傳統(tǒng)方法的優(yōu)化與創(chuàng)新。本次研究為采購供應(yīng)物流配送車輛線路規(guī)劃提供了參考依據(jù)，同時(shí)對(duì)柵格遺傳算法在物流配送路徑規(guī)劃方面的廣泛應(yīng)用起到一定的推廣作用。