基于兩階段算法的帶時(shí)間窗車輛路徑研究

宿 愷， 趙 潔， 郭明順

(沈陽工業(yè)大學(xué) 管理學(xué)院， 沈陽 110870)

物流作為電商的重要要素之一，在時(shí)間上制約了電商行業(yè)的發(fā)展。如何優(yōu)化車輛路徑、提高運(yùn)輸效率，是電商行業(yè)在物流環(huán)節(jié)急需解決的問題[1]?，F(xiàn)階段，許多車輛路徑規(guī)劃缺乏高效的線路設(shè)計(jì)，也未將時(shí)間延遲等情況考慮在內(nèi)。能夠針對(duì)顧客的要求進(jìn)行特定時(shí)間段的配送，對(duì)于降低企業(yè)運(yùn)輸成本、改進(jìn)客戶服務(wù)質(zhì)量具有重要意義。對(duì)企業(yè)而言，如何進(jìn)行合理的路徑規(guī)劃是降低生產(chǎn)成本的合理方式之一[2]。

在實(shí)際配送過程中，顧客分布點(diǎn)不均勻，許多智能優(yōu)化算法[3-7]被提出用來解決配送實(shí)際問題。遺傳算法因極強(qiáng)的魯棒性及收斂速度快，能夠避免出現(xiàn)局部最優(yōu)解；聚類算法在前期對(duì)客戶點(diǎn)進(jìn)行聚類則可以大大提高配送效率。因此，本文對(duì)遺傳算法和聚類分析進(jìn)行改進(jìn)[8]，將二者結(jié)合起來建立數(shù)學(xué)模型，并運(yùn)用算例分析驗(yàn)證其合理性和可行性。

一、數(shù)學(xué)模型建立

由于在實(shí)際情況中需求點(diǎn)分布失衡，導(dǎo)致在制定車輛路徑方案時(shí)若僅根據(jù)以往工作人員經(jīng)驗(yàn)會(huì)出現(xiàn)浪費(fèi)時(shí)間和車輛的情況，尤其是在客戶對(duì)于配送時(shí)間段要求比較高的時(shí)候，如何將貨物準(zhǔn)時(shí)送達(dá)是降低運(yùn)輸時(shí)間成本、提高顧客滿意度所面臨的重要挑戰(zhàn)[9]。

本文建立的帶軟時(shí)間窗的車輛路徑優(yōu)化模型主要出于以下幾方面考慮[10-11]：一是在顧客的規(guī)定時(shí)間進(jìn)行貨物配送可以提高配送環(huán)節(jié)的服務(wù)質(zhì)量，提高顧客滿意度；二是合理安排配送可以降低配送成本、提高配送效率從而帶來更大的效益，在定量的時(shí)間內(nèi)合理分配時(shí)間；三是使得車輛得到合理利用，用最大的負(fù)載率完成特定的任務(wù)，減少車輛空間冗余情況，同時(shí)緩解城市交通擁堵狀況。

據(jù)此本文的VRPTW問題可以描述為：在軟時(shí)間窗的條件下，針對(duì)不同客戶定制不同的配送方案，使得滿足車輛負(fù)載限制、交通情況等約束條件時(shí)總運(yùn)輸成本最低。

1. 基本假設(shè)及符號(hào)定義

基本假設(shè)：

(1) 配送為單向，即在商品運(yùn)輸過程中只進(jìn)行配送，不提供其他服務(wù)。

(2) 每次配送要求從固定配送中心出發(fā)，開始和結(jié)束位置相同，所有車輛在完成若干客戶的服務(wù)后必須返回相應(yīng)的配送中心。

(3) 所有車輛的載重不超過負(fù)載能力。

(4) 所有車輛車種相同，且容量可知。

(5) 每個(gè)客戶僅被服務(wù)一次。

(6) 每個(gè)客戶都有一個(gè)指定服務(wù)時(shí)間[Ei，Li]，客戶可接受在規(guī)定時(shí)間外服務(wù)，企業(yè)接受在規(guī)定時(shí)間外服務(wù)產(chǎn)生的懲罰成本。

(7) 客戶需求量已知，該點(diǎn)貨運(yùn)只能由一輛車完成，且所有客戶都獲得該服務(wù)。

(8) 假定車輛配送成本即為車輛配送距離。

(9) 所有服務(wù)均不考慮服務(wù)時(shí)間。

(10) 假設(shè)路況均為順暢，對(duì)車輛行駛不造成影響。

上述參數(shù)的符號(hào)定義如表1所示。

表1 參數(shù)符號(hào)及含義

如果車輛在客戶要求時(shí)間Ei之前到達(dá)，則會(huì)產(chǎn)生等待成本；如果在Li之后到達(dá)，則需要支付一定罰金。懲罰函數(shù)Pi(Si)表示懲罰成本的高低，定義如下[12]：

(1)

式中，ai、bi表示懲罰系數(shù)。

2. 模型建立

本文模型目標(biāo)是在配送過程中使運(yùn)輸成本最低，根據(jù)以上假設(shè)建立模型：

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

ti+Si+tij-M(1-xijk)≤tj
?i，j∈(1，2，…，n)，k∈(1，2，…，K)

(10)

(11)

(12)

(13)

式(2)為配送成本最小的目標(biāo)函數(shù)；式(3)表示編號(hào)為k的車輛最大載重量不超過車輛的負(fù)荷；式(4)表示從配送中心一共出發(fā)了K輛車進(jìn)行服務(wù)；式(5)表示每個(gè)客戶只能由一輛車進(jìn)行服務(wù)；式(6)表示車輛完成相應(yīng)顧客服務(wù)后要返回配送中心；式(7)表示所有車輛配送的顧客之和等于有貨物需求的客戶總數(shù)；式(8)、(9)表示0～1決策變量x、y之間的關(guān)系；式(10)保證了車輛行駛路線的總耗時(shí)不超過預(yù)先設(shè)定范圍，以滿足客戶對(duì)供貨時(shí)間的要求；式(11)表示出發(fā)時(shí)間和返回時(shí)間均在設(shè)定時(shí)間范圍內(nèi)；式(12)表示VRPTW有向圖的權(quán)重值，當(dāng)編號(hào)為k的車輛途徑客戶i完成對(duì)客戶j的服務(wù)時(shí)xijk=1，否則xijk=0；式(13)表示當(dāng)客戶i的服務(wù)由編號(hào)為k的車輛負(fù)責(zé)時(shí)變量yijk=1，否則yijk=0。

上述模型充分考慮了實(shí)際約束情況，接近實(shí)際問題，得到的解為全局解，對(duì)于解決具體問題有很好的借鑒作用。

二、相關(guān)算法概述

1. K均值算法概述

K均值算法是一種迭代求解的聚類分析算法，其優(yōu)點(diǎn)是可以使數(shù)據(jù)形成類，從而快速對(duì)繁瑣復(fù)雜的事物進(jìn)行分類，使得相似度高的事物聚集到一起分為一類。本文使用的K均值算法是非系統(tǒng)聚類方法中常用的一種。

2. 遺傳算法概述

遺傳算法是啟發(fā)式算法之一，與傳統(tǒng)算法相比迭代速度更快，能避免時(shí)間上的浪費(fèi)。遺傳算法模擬自然環(huán)境中的物種進(jìn)化過程來選擇優(yōu)良個(gè)體和保留部分變異，可以用于復(fù)雜問題的優(yōu)化計(jì)算，具有實(shí)際應(yīng)用價(jià)值[13-14]。在產(chǎn)生初始種群之后，根據(jù)優(yōu)勝劣汰的原則使后代適應(yīng)度越來越高。在每一代中，根據(jù)個(gè)體適應(yīng)度的不同選擇一些較為優(yōu)良的個(gè)體，并在進(jìn)化過程中參與交叉、變異，同時(shí)設(shè)定相應(yīng)的交叉算子及變異算子來幫助產(chǎn)生下一代。待優(yōu)化過程結(jié)束之后，可以產(chǎn)生新種群的最佳個(gè)體，這時(shí)得到的解作為實(shí)際問題的近似最優(yōu)解。

三、算法實(shí)現(xiàn)操作

1. 聚類分析設(shè)計(jì)

聚類數(shù)目根據(jù)具體數(shù)據(jù)的車輛數(shù)確定。聚類完成以后，為了保證每個(gè)類中的需求總量不會(huì)超過每輛車的負(fù)載量，在每加入下一個(gè)客戶時(shí)要檢查貨物總重量是否超過車輛負(fù)荷，若超過則將不滿足條件的客戶從此群中去除。此時(shí)被犧牲的客戶為距離聚類中心最遠(yuǎn)的那個(gè)客戶，對(duì)該客戶繼續(xù)采用聚類算法將其加入其他類中，直到?jīng)]有客戶被犧牲為止。具體步驟為[15-16]：

步驟1 在系統(tǒng)中導(dǎo)入原始數(shù)據(jù)文件，包含客戶坐標(biāo)、時(shí)間要求、車輛負(fù)荷等。

步驟2 計(jì)算需要的車輛數(shù)目，對(duì)客戶進(jìn)行分群，直到所有客戶點(diǎn)都被分配。

步驟3 檢查各群內(nèi)的顧客總需求量是否超出車輛最大載重量。若超過則執(zhí)行步驟4，否則執(zhí)行步驟8。

步驟4 去除距離聚類中心最遠(yuǎn)且超過車輛負(fù)荷的客戶，直到符合車輛負(fù)荷要求。

步驟5 檢查其他客戶群的車輛是否有剩余容量。如果有則執(zhí)行步驟6，否則執(zhí)行步驟7。

步驟6 將剔除的客戶加入到距離最近且加入后不超過車輛最大容量的客戶群，并執(zhí)行步驟8。

步驟7 分配一輛車服務(wù)，回到步驟2。

步驟8 聚類完成，得到的編碼即為遺傳算法的配送中心點(diǎn)。

2. 遺傳算法設(shè)計(jì)

(1) 編碼設(shè)計(jì)。遺傳算法通常使用二進(jìn)制編碼，但這種編碼方式可能會(huì)在計(jì)算過程中出現(xiàn)無效解。因此本文采用自然數(shù)編碼形式，這種編碼方式對(duì)于路徑優(yōu)化來說能在很大程度上提高運(yùn)算效率[17]。

當(dāng)被服務(wù)客戶數(shù)量為n，服務(wù)車輛數(shù)量為m時(shí)，整個(gè)染色體的長度為m+n+1，所有染色體表示為{0，…，S1，S2，0，S3，…，Sn，0}，其中Si表示第i個(gè)客戶點(diǎn)，出現(xiàn)0的個(gè)數(shù)與配送貨物所需車輛的數(shù)量有關(guān)。用0代表配送中心對(duì)各個(gè)路段進(jìn)行劃分，便于觀察車輛的具體路徑。

(2) 適應(yīng)度函數(shù)設(shè)計(jì)。在遺傳算法中，適應(yīng)度函數(shù)值大小與染色體能否遺傳到下一代具有重要關(guān)聯(lián)[18]。本文所建立的模型以運(yùn)輸費(fèi)用最低為目標(biāo)，因此適應(yīng)度函數(shù)為運(yùn)輸費(fèi)用的倒數(shù)，運(yùn)輸費(fèi)用越小，適應(yīng)度函數(shù)值越大，可行性越高，其關(guān)系表達(dá)式為

ai=1/bi(i=1，2，…，g)

(14)

式中：ai表示個(gè)體適應(yīng)度；bi表示第i個(gè)個(gè)體對(duì)應(yīng)的運(yùn)輸費(fèi)用；g表示種群規(guī)模。

(3) 選擇設(shè)計(jì)。采用最佳個(gè)體保留策略和比例選擇策略相結(jié)合的方法對(duì)選擇算子進(jìn)行設(shè)計(jì)[19]。選擇方式如下：①根據(jù)適應(yīng)度函數(shù)計(jì)算每個(gè)個(gè)體的適應(yīng)度，然后根據(jù)數(shù)值降序排列，將排序后的個(gè)體平均分成3份[20]。②將處于排序前1/3的個(gè)體倍數(shù)增加。③處于中間1/3的個(gè)體直接復(fù)制。④處于排序后1/3的個(gè)體直接淘汰。當(dāng)種群進(jìn)化到后期階段，直接采用最佳個(gè)體保留法，不再參加其余進(jìn)化過程，提高種群優(yōu)良性。

(4) 交叉。交叉操作的作用是在進(jìn)化過程中通過染色體片段的交換來形成新的個(gè)體，降低對(duì)優(yōu)良模式的破壞概率。本文采用順序交叉法，確保前一代的優(yōu)良個(gè)體能夠順利得到遺傳，同時(shí)增加了個(gè)體多樣性。例如：

A(136458792)→A′(1364|5879|2)→

A1(243158796)

B(279431865)→B′(2794|3186|5)→

B1(457931862)

(5) 變異。在遺傳過程中會(huì)出現(xiàn)一定概率的基因突變。變異算子用來表示這種現(xiàn)象可能發(fā)生的概率，改變?nèi)旧w中的基因片段，呈現(xiàn)出基因多樣性[21]。本文采用逆轉(zhuǎn)變異對(duì)染色體中的基因片段進(jìn)行調(diào)整。該方法能夠?qū)ΨN群中的變異進(jìn)行適當(dāng)調(diào)整，在一定程度上防止過早收斂的現(xiàn)象。例如：

A(136458792)→A′(13|645|8792)→

A1(135468792)

(6) 終止規(guī)則。作為一種隨機(jī)搜索算法，遺傳算法需要提前設(shè)定終止條件來保證在一定時(shí)間內(nèi)結(jié)束迭代循環(huán)。本文設(shè)定為進(jìn)化次數(shù)達(dá)到100則停止運(yùn)算[22]。

四、仿真實(shí)驗(yàn)與性能分析

采用MATLAB2018a軟件實(shí)現(xiàn)該算法對(duì)帶時(shí)間窗的車輛路徑優(yōu)化問題的求解過程。為進(jìn)一步驗(yàn)證兩階段算法的性能，與經(jīng)典遺傳算法的算法性能進(jìn)行對(duì)比分析，使用Solomon數(shù)據(jù)集進(jìn)行仿真測試。選取數(shù)據(jù)集r106，如表2所示。

表2 客戶需求點(diǎn)

仿真過程中相關(guān)運(yùn)算參數(shù)設(shè)定如表3所示。

表3 實(shí)驗(yàn)參數(shù)設(shè)置

實(shí)驗(yàn)結(jié)果及相關(guān)對(duì)比如圖1～3所示。圖1表示實(shí)驗(yàn)數(shù)據(jù)在第一階段聚類分析之后得到的初始聚類中心以及各分布點(diǎn)位置。

圖1 客戶位置分布

圖2表示運(yùn)用經(jīng)典遺傳算法運(yùn)算得到的仿真路徑。圖3表示加入聚類分析并對(duì)遺傳算法進(jìn)行改進(jìn)之后得到的仿真路徑，從中可以看出改進(jìn)的算法能夠明顯對(duì)需求點(diǎn)進(jìn)行分類配送。

圖2 經(jīng)典遺傳算法配送路線

圖3 改進(jìn)遺傳算法配送路線

為驗(yàn)證兩階段算法在求解問題時(shí)的最優(yōu)性，對(duì)兩階段算法求解結(jié)果與經(jīng)典遺傳算法進(jìn)行對(duì)比，如表4、5所示。

表4 兩階段算法求得的最優(yōu)解

表4(續(xù))

表5 經(jīng)典遺傳算法求得的最優(yōu)解

對(duì)比表4、5可以看出，本文采用兩階段算法求得的最優(yōu)解相對(duì)于經(jīng)典遺傳算法在等待時(shí)間和延誤時(shí)間上有明顯優(yōu)勢，更符合帶時(shí)間窗的車輛路徑優(yōu)化問題對(duì)時(shí)間窗的要求，提高了服務(wù)效率。

從Solomon數(shù)據(jù)集中另外選出4組數(shù)據(jù)進(jìn)行仿真，得出實(shí)驗(yàn)數(shù)據(jù)如表6、7所示。對(duì)比可見改進(jìn)算法可以明顯優(yōu)化計(jì)算結(jié)果。

表6 實(shí)驗(yàn)最優(yōu)運(yùn)行時(shí)間對(duì)比

表7 實(shí)驗(yàn)最優(yōu)運(yùn)輸成本對(duì)比

五、結(jié) 語

為更好地解決物流配送中存在的顧客時(shí)間限制問題，本文提出將聚類分析和遺傳算法相結(jié)合的兩階段算法并對(duì)其進(jìn)行改進(jìn)。使用Solomon數(shù)據(jù)集進(jìn)行算例分析并進(jìn)行對(duì)比，結(jié)果表明該算法在求解帶軟時(shí)間窗的車輛路徑優(yōu)化問題時(shí)具有良好的可行性，能夠提供最優(yōu)方案。