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

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

0 引言

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

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

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

1 問(wèn)題描述與模型建立

1.1 問(wèn)題描述

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

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

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

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

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

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

（5）車(chē)輛運(yùn)輸貨物容量小于車(chē)輛的容量，且每位客戶的需求量小于車(chē)輛容量。

1.2 模型中符號(hào)和決策變量（如表1所示）

表1

1.3 模型建立

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

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

（b）約束條件

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

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

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

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

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

2.1 染色體的編碼與解碼

本文采用自然數(shù)編碼，用0表示配送中心，1,2,…,n表示客戶點(diǎn)，染色體編碼如圖2（a）所示，每條染色體表示客戶裝載的順序。圖2（b）表示染色體解碼后的個(gè)體，每個(gè)個(gè)體表示車(chē)輛對(duì)客戶進(jìn)行配送服務(wù)的順序，第一輛車(chē)從配送中心0出發(fā)，依次服務(wù)客戶3,1,2,10然后返回配送中心0，第二輛車(chē)從配送中心0出發(fā)，依次服務(wù)客戶4,6,5，然后返回配送中心0，第三輛車(chē)從配送中心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提出的輪盤(pán)賭策略，根據(jù)每個(gè)染色體適應(yīng)度的比例來(lái)確定該染色體被選擇的概率，依照選擇概率選擇個(gè)體直到種群數(shù)達(dá)到M。每次生成的新種群結(jié)合精英保留策略，用上一代最優(yōu)個(gè)體替換新種群中適應(yīng)度函數(shù)最差的個(gè)體。

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

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

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

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

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

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

2.5 變異算子

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

2.6 自適應(yīng)競(jìng)爭(zhēng)策略

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

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

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

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

2.7 多車(chē)型車(chē)輛選擇

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

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

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

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

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

圖4 多車(chē)型車(chē)輛選擇算法示意圖

3 算例分析

3.1 數(shù)值實(shí)例

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

根據(jù)上述案例對(duì)模型進(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，競(jìng)爭(zhēng)策略停止階段種群生成次數(shù)占當(dāng)前總種群生成次數(shù)的比例系數(shù)ζ=0.3。

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

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

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

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

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

3.2 算法實(shí)驗(yàn)性能分析

為驗(yàn)證自適應(yīng)競(jìng)爭(zhēng)遺傳算法對(duì)MVRPTM問(wèn)題的求解性能，將該算法和遺傳算法進(jìn)行對(duì)比分析。利用上述案例的數(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，競(jìng)爭(zhēng)策略停止階段種群生成次數(shù)占當(dāng)前總種群生成次數(shù)的比例系數(shù)ζ=0.3。自適應(yīng)競(jìng)爭(zhēng)遺傳算法和遺傳算法迭代圖，如圖6所示。

圖5 2018年10月多車(chē)型車(chē)輛配送路徑圖

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

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

3.3 敏感度分析

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

表5 單采用6t車(chē)型配送路徑方案

表6 單采用7t車(chē)型配送路徑方案

表7 單采用8t車(chē)型配送路徑方案

表8 采用各種車(chē)型方案的總路徑和總成本對(duì)比

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

4 結(jié)論

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

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