考慮軟時間窗的多車型車輛配送路徑優(yōu)化

鮑 偉，賈江鳴，李湘生，周慶紅

（1.浙江理工大學(xué) 機械與自動控制學(xué)院，浙江 杭州310018；2.金華市華南汽配有限公司，浙江 金華321000）

0 引言

近年來，物流產(chǎn)業(yè)在國家相關(guān)政策的扶持下迅速發(fā)展，但物流成本仍居高不下。配送作為物流系統(tǒng)的核心環(huán)節(jié)，在物流成本中的占比超過50%，因此配送成本過高成為了物流成本居高不下的重要因素[1-3]。通過合理地安排車輛進(jìn)行配送才能有效地降低物流成本。

目前，國內(nèi)外學(xué)者將車輛配送路徑優(yōu)化問題稱為VRP（Vehicle Routing Problem）問題，并進(jìn)行了大量研究。Yin等[4]將解決車輛配送路徑優(yōu)化問題的方法歸為兩類：精確優(yōu)化算法和啟發(fā)式優(yōu)化算法。吳艷群等[5]根據(jù)先驗經(jīng)驗設(shè)置初始值，再采用模擬退火算法對車輛路徑問題進(jìn)行求解。同時部分學(xué)者為降低運輸成本對多車型車輛問題進(jìn)行研究，陳研等[6]以總成本最小為目標(biāo)，考慮提高車輛滿載率、減少出行次數(shù)，構(gòu)建多車型集配貨一體化車輛優(yōu)化模型。王旭坪等[7]加入車型調(diào)整策略所構(gòu)造的鄰域搜索算法，用于滿足客戶對不同車型服務(wù)的多樣化需求。葛顯龍等[8]以車輛運輸成本和固定成本最小化為目標(biāo)，建立出針對超市越庫作業(yè)的多車型車輛路徑優(yōu)化模型。部分學(xué)者們在VRP的基礎(chǔ)上考慮時間窗因素的車輛路徑問題（Vehicle Routing Problem Time Windows，VRPTM），Malek等[9]提出一種人工蜜蜂搜索算法來提高VRPTM的收斂速度。李珍萍等[10]提出一種求解模型的聯(lián)合優(yōu)化遺傳算法用于解決多需求混合整數(shù)規(guī)劃模型。李兵飛等[11]提出一種改進(jìn)的人工蜂群算法用于解決時變VRPTM問題。

綜上所述，目前針對VRPTM問題的研究存在模型復(fù)雜、算法收斂較慢、依賴先驗經(jīng)驗等問題。因此，本文以車輛固定成本、車輛運輸成本、等待時間懲罰成本組成的總配送成本最小化為目標(biāo)，引入軟時間窗懲罰函數(shù)，建立多車型車輛配送路徑優(yōu)化（Multi-type Vehicle Routing Problem Time Windows，MVRPTM）模型；采用自適應(yīng)競爭的遺傳算法對多車型車輛配送路徑優(yōu)化模型進(jìn)行求解，其中引入自適應(yīng)競爭策略來提高算法的收斂速度，采用多車型車輛選擇算法來對車型進(jìn)行選擇。最后通過某物流公司的配送算例對模型和算法性能進(jìn)行評估分析。

1 問題描述與模型建立

1.1 問題描述

某配送中心配備多種車型的車輛且車輛數(shù)目充足，某個區(qū)域中存在待服務(wù)的客戶點，配送中心在滿足每個客戶的需求量和可接受服務(wù)時間的條件下，合理安排各種類型的車輛對客戶進(jìn)行配送服務(wù)，最終車輛服務(wù)完所有客戶后返回配送中心。

考慮到實際問題的復(fù)雜性和不確定性，對MVRPTM做出基本假設(shè)：

（1）配送中心有且僅有一個，且能滿足所有客戶的貨物裝載；

（2）車輛從配送中心出發(fā)服務(wù)完所有客戶，最終返回配送中心；

（3）每位客戶的貨物不允許拆分放置于多輛車；

（4）客戶的需求量、服務(wù)時間、接受服務(wù)時間、客戶地圖位置信息都是已知的；

（5）車輛運輸貨物容量小于車輛的容量，且每位客戶的需求量小于車輛容量。

1.2 模型中符號和決策變量（如表1所示）

表1

1.3 模型建立

根據(jù)問題描述，將以總配送成本最小化為目標(biāo)，建立帶軟時間窗的多車型車輛路徑優(yōu)化模型。其中總配送成本包括：車輛固定成本、車輛運輸成本、等待時間懲罰成本，并根據(jù)問題描述，建立三維裝箱約束下的多車型車輛路徑組合優(yōu)化模型見式（1）至式（10）：

（a）目標(biāo)函數(shù)

（b）約束條件

式（1）表示最小化總配送成本的目標(biāo)函數(shù)；式（2）表示車輛運輸貨物的容量小于車輛的容量；式（3）表示每位客戶的需求貨物不能拆封放置于多輛車上；式（4）表示每輛車都從配送中心出發(fā)，最終返回配送中心；式（5）表示車輛駛向某客戶點，則必須從該客戶點離開；式（6）表示車輛要在最大時間窗內(nèi)對客戶進(jìn)行配送服務(wù)；式（7）表示調(diào)度車輛數(shù)不超過配送中心車輛總數(shù)；式（8）至式（10）表示決策變量。

2 自適應(yīng)競爭的遺傳算法求解MVRPTM

MVRPTM的實際應(yīng)用問題屬于NP-hard難題，通常采用啟發(fā)式算法求解。遺傳算法本身從問題解的串集開始搜索，采用概率變遷規(guī)則來指導(dǎo)搜索方向，優(yōu)化過程中同時處理多個個體，并對搜索空間中的多個解進(jìn)行評估有利于全局擇優(yōu)，適用于對組合優(yōu)化問題的求解，但存在收斂速度慢或過早收斂等問題。局部搜索算法從一個初始解開始通過鄰域搜索，選擇最優(yōu)鄰域解做為下一迭代的初始解，經(jīng)過多次局部搜索，有利于提高解集的質(zhì)量[12]。本文利用局部搜索算法的優(yōu)勢，在遺傳算法中引入自適應(yīng)競爭策略來提高算法獲取優(yōu)秀解的能力。

自適應(yīng)競爭的遺傳算法流程圖如圖1所示。首先遺傳算法生成初始種群，經(jīng)過自適應(yīng)競爭策略對種群進(jìn)行優(yōu)化，給出客戶反向配送順序，再通過多車型車輛選擇算法和構(gòu)造式啟發(fā)式算法給出多車型車輛的裝箱方案和多車型車輛的配送方案。最后對自適應(yīng)競爭的遺傳算法進(jìn)行迭代循環(huán)，直到滿足終止條件。

圖1 自適應(yīng)競爭的遺傳算法流程圖

2.1 染色體的編碼與解碼

本文采用自然數(shù)編碼，用0表示配送中心，1,2,…,n表示客戶點，染色體編碼如圖2（a）所示，每條染色體表示客戶裝載的順序。圖2（b）表示染色體解碼后的個體，每個個體表示車輛對客戶進(jìn)行配送服務(wù)的順序，第一輛車從配送中心0出發(fā)，依次服務(wù)客戶3,1,2,10然后返回配送中心0，第二輛車從配送中心0出發(fā)，依次服務(wù)客戶4,6,5，然后返回配送中心0，第三輛車從配送中心0出發(fā)，依次服務(wù)客戶8,9,7，然后返回配送中心0。

圖2 染色體編碼與解碼示意圖

2.2 適應(yīng)度函數(shù)

本文將多目標(biāo)函數(shù)轉(zhuǎn)化為以總配送成本最小化的單目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)，適應(yīng)度函數(shù)越高遺傳到下一代的概率越高。

2.3 選擇算子

本文采用Holland提出的輪盤賭策略，根據(jù)每個染色體適應(yīng)度的比例來確定該染色體被選擇的概率，依照選擇概率選擇個體直到種群數(shù)達(dá)到M。每次生成的新種群結(jié)合精英保留策略，用上一代最優(yōu)個體替換新種群中適應(yīng)度函數(shù)最差的個體。

2.4 改進(jìn)的交叉算子

本文的交叉算子是對傳統(tǒng)的部分映射交叉算子進(jìn)行改進(jìn)。當(dāng)兩個被選擇的染色體相同時，仍能產(chǎn)生新個體，避免丟失種群多樣性，陷入局部最優(yōu)。改進(jìn)交叉算子示意圖如圖3所示，基本思路為：

Step1：以概率Pc選擇兩個父代parent1、parent2，隨機產(chǎn)生兩個交叉點a、b，同時產(chǎn)生交叉基因片段Fab;

Step2：對染色體parent1、parent2進(jìn)行基因前移，直到交叉點a為首個染色體基因；將parent1中發(fā)生交叉的染色體基因片段Fab逆序插入到前移后的染色體parent2末尾；將parent2中發(fā)生交叉的染色體基因片段逆序插入到前移后的染色體parent1頭部；

Step3：刪除與交叉片段基因相同的部分，得到子代offspring1、offspring2。

圖3 改進(jìn)交叉算子示意圖

2.5 變異算子

本文采用兩點互異的變異算子，以一定的概率Pm隨機選擇一條染色體，隨機生成兩個變異點，將變異點基因互換得到新個體。

2.6 自適應(yīng)競爭策略

自適應(yīng)策略根據(jù)當(dāng)前種群變化的狀態(tài)來自適應(yīng)調(diào)整競爭狀態(tài)的開啟與停止，以此來平衡搜索效率與種群多樣性之間的關(guān)系。競爭策略開啟階段將交叉階段產(chǎn)生的子代與父代進(jìn)行比較，僅對優(yōu)于父代的子代進(jìn)行保留，加強優(yōu)秀染色體片段的遺傳性，提高算法的收斂速度；競爭策略關(guān)閉階段，每次迭代引入新種群，以提高種群的多樣性。

（a）競爭策略停止準(zhǔn)則。如果當(dāng)前種群最優(yōu)解優(yōu)于上一代種群最優(yōu)解，重置自適應(yīng)競爭狀態(tài)s；否則自適應(yīng)競爭狀態(tài)s次數(shù)加1，直到自適應(yīng)競爭狀態(tài)s達(dá)到閾值時停止競爭策略。

（b）競爭策略再開啟準(zhǔn)則。競爭策略停止?fàn)顟B(tài)下，每次迭代向種群中引入M新種群數(shù)，當(dāng)競爭策略關(guān)閉狀態(tài)下，種群生成次數(shù)占當(dāng)前總種群生成次數(shù)的比例系數(shù)達(dá)到ζ時，開啟競爭策略，并重置自適應(yīng)競爭狀態(tài)s。

（c）交叉階段進(jìn)行競爭策略。在競爭策略開啟階段，對交叉算子生成的子代進(jìn)行判斷，如果存在某個子代優(yōu)于父代，則保留本次子代并重置競爭次數(shù)；否則，自適應(yīng)競爭狀態(tài)o加1，直到自適應(yīng)競爭狀態(tài)o達(dá)到閾值時輸出最優(yōu)解并自適應(yīng)競爭狀態(tài)o。

2.7 多車型車輛選擇

多車型車輛選擇算法應(yīng)用了深度優(yōu)先搜索的思想，如圖4所示。各種類型車輛按照類型號從大到小排序，且車輛容積由大到小順序調(diào)用，即后面調(diào)用車輛的容積不大于前面調(diào)用車輛的容積，假設(shè)排序為V1,V2,V3,…,Vk。其中第一輛車調(diào)用的可能為V1,V2,V3,…,Vk，當(dāng)?shù)谝惠v車的車型為V1時，第二輛車的車型可能為V1,V2,V3,…,Vk，若第一輛車的車型為V2時，第二輛車的車型可能為V2,V3,…,Vk，依此類推進(jìn)行車輛選擇。基本流程如下：

Step1：按照深度優(yōu)先搜索方式，對配送貨物進(jìn)行裝載；

Step2：若車輛無法再裝載剩余客戶的貨物，則調(diào)用下一輛車；若所有客戶的貨物都裝載，則生成可行裝載方案；

Step3：進(jìn)行下一次深度優(yōu)先搜索裝載，直到深度優(yōu)先搜索完成；

Step4：比較所有深度優(yōu)先搜索生成的裝載方案，選擇最優(yōu)的裝載方案。

圖4 多車型車輛選擇算法示意圖

3 算例分析

3.1 數(shù)值實例

針對某物流公司2018年10月的實際業(yè)務(wù)數(shù)據(jù)。物流配送中心分別對19位客戶進(jìn)行配送服務(wù)。其中配送中心共有3種類型的車輛（每種車型5輛，共15輛）給予租賃。車輛規(guī)格信息、客戶信息分別如表2、表3所示。若車輛在服務(wù)時間窗前到達(dá)客戶點的等待時間懲罰成本0.3元/分鐘。

根據(jù)上述案例對模型進(jìn)行仿真，以迭代次數(shù)為算法終止標(biāo)準(zhǔn)，設(shè)置模型參數(shù)如下：種群規(guī)模M=50，迭代次數(shù)T=5 000，交叉概率Pc=0.85，變異概率Pm=0.1，設(shè)置自適應(yīng)狀態(tài)o的閾值α=20，自適應(yīng)狀態(tài)s的閾值β=13，競爭策略停止階段種群生成次數(shù)占當(dāng)前總種群生成次數(shù)的比例系數(shù)ζ=0.3。

表2 物流公司待調(diào)度車輛規(guī)格

表3 2018年10月部分客戶貨物信息

試驗平臺為3.6GHz的AMD 3600處理器、16GB內(nèi)存的計算機平臺實現(xiàn)，最終模型優(yōu)化結(jié)果如表4所示，物流中心安排1輛容積為8t和2輛容積為6t的車輛對19個客戶點進(jìn)行配送服務(wù)，總配送成本510.35元；最終的多車型車輛配送路徑如圖5所示。

表4 采用自適應(yīng)競爭的遺傳算法優(yōu)化后的結(jié)果

圖5為多車型車輛配送路徑圖，數(shù)字“0”表示物流配送中心，數(shù)字“1,2,…,19”表示客戶點。其中不同樣式的線條表示不同的車輛，圖例中顯示所調(diào)用車輛的類型。直線表示的配送線路“0-4-2-7-5-6-13-0”由容積為8t的車輛進(jìn)行配送；虛線表示的配送路線“0-18-3-9-16-11-1-0”由容積為6t的車輛進(jìn)行配送；點畫線表示的配送路線“0-17-12-8-15-10-19-14-0”由容積為6t的車輛進(jìn)行配送。

3.2 算法實驗性能分析

為驗證自適應(yīng)競爭遺傳算法對MVRPTM問題的求解性能，將該算法和遺傳算法進(jìn)行對比分析。利用上述案例的數(shù)據(jù)，設(shè)置初始化參數(shù)：種群規(guī)模M=50，迭代次數(shù)T=5 000，交叉概率Pc=0.85，變異概率Pm=0.1，設(shè)置自適應(yīng)狀態(tài)o的閾值α=20，自適應(yīng)狀態(tài)s的閾值β=13，競爭策略停止階段種群生成次數(shù)占當(dāng)前總種群生成次數(shù)的比例系數(shù)ζ=0.3。自適應(yīng)競爭遺傳算法和遺傳算法迭代圖，如圖6所示。

圖5 2018年10月多車型車輛配送路徑圖

圖6 自適應(yīng)競爭的遺傳算法和遺傳算法迭代圖

將上述算法各仿真10次取平均值，自適應(yīng)競爭遺傳算法求解波動相對平穩(wěn)，算法在622代收斂，總配送成本為510.35元；遺傳算法在3 105代收斂，總配送成本為528.74元。自適應(yīng)競爭的遺傳算法收斂代數(shù)與遺傳算法比較提升5倍左右，最終自適應(yīng)競爭的遺傳算法的總配送成本比遺傳算法減少18.39元。

3.3 敏感度分析

在實際貨物配送過程，調(diào)度不同車型的車輛對總配送成本有影響。本文根據(jù)實際物流車輛配送情況，采用多車型車輛配送模式，在一定程度上降低物流成本，提高運作效率。因此車型的使用是影響配送成本的關(guān)鍵，繼續(xù)采用上述的實例和參數(shù)對車輛路徑問題進(jìn)行敏感度分析。求解結(jié)果如表5至表8所示。

表5 單采用6t車型配送路徑方案

表6 單采用7t車型配送路徑方案

表7 單采用8t車型配送路徑方案

表8 采用各種車型方案的總路徑和總成本對比

由表8可知，采用單車型6t的總配送成本為590.44元，采用單車型7t的總配送成本為528.08元，采用單車型8t的總配送成本為583.11元。隨著車型的容積從小到大，總行駛路徑逐漸變短，考慮到配送成本，僅采用車型3不一定是配送成本最少的方案。采用多車型配送與采用單6t車型配送相比，裝載率提升16.33%，總路徑長度減少3.33km，減少成本80.08元；與單7t車型配送相比，雖然總路徑長度增加2.99km，但裝載率提升4.67%，總配送成本減少17.72元；與單8t車型配送相比，雖然總路徑長度增加3.81km，但裝載率提升16.33%，總配送成本減少72.75元。因此，通過采用單車型車輛與多車型車輛進(jìn)行總配送成本對比，可以看出在配送中采用多車型進(jìn)行配送能更好地降低配送路徑，并減少物流的配送成本。

4 結(jié)論

本文針對帶軟時間窗的多車型車輛配送路徑優(yōu)化問題，以車輛固定成本、車輛運輸成本、等待時間懲罰成本最小化為目標(biāo)，建立帶軟時間窗的多車型車輛路徑優(yōu)化模型。考慮到模型的復(fù)雜性，本文引入自適應(yīng)競爭策略、多車型車輛選擇算法設(shè)計出自適應(yīng)遺傳算法求解本文的模型。最后以某物流企業(yè)的配送為仿真對象進(jìn)行優(yōu)化實驗，實驗結(jié)果表明物流企業(yè)在對客戶進(jìn)行配送時，采用多車型配送與采用單6t車型配送相比，總路徑長度減少2.22%，減少成本13.6%；與單7t車型配送相比，雖然總路徑長度增加2.04%，但是總配送成本減少3.36%；與單8t車型配送相比，雖然總路徑長度增加2.6%，但總配送成本減少12.48%。且自適應(yīng)遺傳算法與遺傳算法相比具有更高的優(yōu)化精度與優(yōu)化效率。

模型中考慮多車場、可變油耗、時變車速、交通擁擠等更多實際因素，進(jìn)一步降低物流成本是下一步研究方向。