張淼寒，安裕強(qiáng) ，潘 楠，孫雨軒，鮑 景，高 瀚，韓宇航

(1.昆明理工大學(xué) 民航與航空學(xué)院，云南 昆明 650500；2.紅云紅河煙草(集團(tuán))有限責(zé)任公司 ，云南 昆明 650000；3.昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院 ，云南 昆明 650500；4.昆明理工大學(xué) 管理與經(jīng)濟(jì)學(xué)院 ，云南 昆明 650500)

0 引言

近年來(lái)，隨著車輛的快速增長(zhǎng)以及城市物流貨運(yùn)量的急劇增加，城市交通日趨擁堵，同時(shí)受交通政策、節(jié)假日等條件的影響，當(dāng)前交通網(wǎng)具有一定的實(shí)時(shí)性和隨機(jī)性[1].如何高效實(shí)現(xiàn)城市物流配送的降本提效已成為國(guó)內(nèi)外學(xué)者廣泛關(guān)注的問(wèn)題[2].

城市物流配送不同于傳統(tǒng)的長(zhǎng)途運(yùn)輸配送，其具有流量大、流向多變、節(jié)點(diǎn)多、分布廣、配送半徑小、路徑實(shí)時(shí)性、可選擇車輛多等特點(diǎn)[3].因此,城市物流配送的核心問(wèn)題是涉及多維約束條件下的車輛路徑優(yōu)化問(wèn)題(Vehicle Routing Problem,VRP).隨著相關(guān)學(xué)者在時(shí)間窗、多車型配送、配送成本、多目標(biāo)優(yōu)化等多方面展開(kāi)研究，城市物流的配送調(diào)度模型也愈發(fā)復(fù)雜多變.同時(shí),考慮到傳統(tǒng)算法[4]難以高效獲得問(wèn)題解空間，當(dāng)前相關(guān)文獻(xiàn)大多傾向于利用元啟發(fā)式算法[5-7]來(lái)求解此類多維復(fù)雜環(huán)境約束條件下的VRP問(wèn)題.在時(shí)間窗約束的VRP問(wèn)題[8]中，文獻(xiàn)[9-11]在時(shí)間窗問(wèn)題的基礎(chǔ)上分別添加了多車型、作業(yè)時(shí)間及客戶需求作為優(yōu)化目標(biāo)，同時(shí)設(shè)計(jì)了非支配排序遺傳算法、多鄰域自適應(yīng)禁忌搜索算法和精英蟻群算法進(jìn)行模型求解.在多車型調(diào)度問(wèn)題中，文獻(xiàn)[12-13]設(shè)計(jì)了改進(jìn)的遺傳算法求解異構(gòu)車輛在動(dòng)態(tài)路徑規(guī)劃及集配貨的車輛調(diào)度分配方案.文獻(xiàn)[14]則考慮了異構(gòu)車輛對(duì)油耗的影響建立了一種多車型的低碳混合整數(shù)規(guī)劃模型.文獻(xiàn)[15]綜合考慮時(shí)間窗和多車型對(duì)危險(xiǎn)品運(yùn)輸?shù)挠绊?，設(shè)計(jì)了基于變鄰域的混合多目標(biāo)算法進(jìn)行求解.在配送成本問(wèn)題中，文獻(xiàn)[16-17]在以總成本最低為目標(biāo)的基礎(chǔ)上分別構(gòu)建了顧客滿意度最大和需求緊迫度有限的物流調(diào)度模型，并設(shè)計(jì)離散多元宇宙算法和改進(jìn)的遺傳算法進(jìn)行調(diào)度方案求解.在多目標(biāo)優(yōu)化方面，文獻(xiàn)[18]以配送成本、車輛數(shù)最少、客戶滿意適度最大構(gòu)建多目標(biāo)路徑規(guī)劃模型，文獻(xiàn)[19]則在時(shí)間窗約束下，以最小化車輛最大行駛距離和最大化車輛負(fù)載之差為多優(yōu)化目標(biāo).文獻(xiàn)[20]以總行駛距離、時(shí)間窗約束、車輛數(shù)量等為多維優(yōu)化目標(biāo)并設(shè)計(jì)局部搜索策略的人工蜂群算法進(jìn)行多目標(biāo)模型求解.

雖然上述研究對(duì)VRP問(wèn)題展開(kāi)了有益探索，但隨著智慧城市物流供應(yīng)鏈的數(shù)字化構(gòu)建，城市物流調(diào)度模型在約束條件及優(yōu)化目標(biāo)上也將更加符合實(shí)際情況.為此，本文重點(diǎn)研究面向?qū)崟r(shí)交通條件下城市超市配送的異構(gòu)車輛調(diào)度問(wèn)題，充分考慮包括配送成本、時(shí)間窗、道路車型限制、車輛泡貨的體積與重量比、車型分配、路徑實(shí)時(shí)性等多維角度下的VRP問(wèn)題，并提出將配送車輛的泡重比作為約束條件考慮進(jìn)物流車輛路徑規(guī)劃中，構(gòu)建符合實(shí)際情況下的多目標(biāo)優(yōu)化數(shù)學(xué)模型，最后設(shè)計(jì)改進(jìn)的鯨魚優(yōu)化算法進(jìn)行模型仿真求解及數(shù)據(jù)分析對(duì)比.

1 問(wèn)題描述

隨著城市經(jīng)濟(jì)化水平的提高以及車輛限制的相關(guān)政策不斷出臺(tái)，傳統(tǒng)的城市車輛配送模式往往會(huì)產(chǎn)生大量的資源浪費(fèi)，因此考慮如何構(gòu)建面向交通擁堵實(shí)時(shí)性、客戶時(shí)間窗、車型限制、車輛泡重比、調(diào)度運(yùn)輸成本等多維約束條件下實(shí)現(xiàn)以成本最低、裝載量最高為目標(biāo)的車輛路徑調(diào)度規(guī)劃已成為當(dāng)前要解決的重點(diǎn)問(wèn)題.

1.1 模型假設(shè)

(1)確定配送中心和客戶點(diǎn)位置，且可以滿足客戶需求；

(2)車輛由配送中心出發(fā)，完成任務(wù)后返回配送中心；

(3)配送中心車輛數(shù)目有限，各型號(hào)車輛各有Ca輛；

(4)各客戶點(diǎn)僅以其所在轄區(qū)的主要所在位置來(lái)判斷所能通行的車輛；

(5)某市內(nèi)不同客戶點(diǎn)所在轄區(qū)ψ對(duì)車輛型號(hào)a的要求約束不相同.

1.2 考慮交通擁堵下的車速實(shí)時(shí)性

1.3 數(shù)學(xué)模型的建立

為提高車輛配送效率的同時(shí)盡可能的降低配送成本，因此構(gòu)建以總成本最小，裝載率最高為優(yōu)化目標(biāo)的城市異構(gòu)車輛調(diào)度模型，目標(biāo)函數(shù)如式(1)所示：

(1)

式中：F1為車輛總固定成本,元；F2為車輛總運(yùn)費(fèi)，元；F3為所有司機(jī)的工資成本，元；τ為車輛配載利用率；Rak為0-1變量，表示車輛ak是否進(jìn)行運(yùn)貨，若是取1，否則取0.

車輛的總固定成本包括其起步費(fèi)及點(diǎn)位費(fèi)，計(jì)算公式如式(2)所示：

(2)

式中：Pak表示車輛ak的固定成本;PSak表示車輛ak的起步價(jià);Pfa表示車輛型號(hào)a的點(diǎn)位費(fèi);Kak,j為0-1變量，若車輛ak到達(dá)客戶點(diǎn)j,則Kak,j取1， 否則取0；I={1,2,…}為車輛型號(hào)集合,Ca={1a,2a,…}為車輛集合；

車輛的配送成本分為泡貨與重貨2種方式計(jì)算.式(3)為車輛總配送成本計(jì)算公式，式(4)為泡貨及重貨計(jì)算方式，式(5)為車輛ak泡重比的計(jì)算方式：

(3)

(4)

(5)

式中：Sak為車輛ak的運(yùn)輸成本，元；經(jīng)查相關(guān)陸運(yùn)資料，選泡重比參數(shù)μak為5作為分界線進(jìn)行計(jì)算，若泡重比小于等于5則運(yùn)用重貨單價(jià)計(jì)算，否則按泡貨單價(jià)進(jìn)行計(jì)算；q1為重貨的運(yùn)輸單價(jià)，元/(kg·km)；q2為泡貨運(yùn)輸單價(jià)，元/(m3·km)；Wj為客戶點(diǎn)j所需的貨物重量，kg；Vj為客戶點(diǎn)j所需要的貨物體積，m3；loj為發(fā)貨點(diǎn)o到j(luò)個(gè)客戶點(diǎn)的距離，m；ljj′為距離矩陣中j客戶點(diǎn)到j(luò)′客戶點(diǎn)的距離，m.

以作業(yè)時(shí)間為標(biāo)準(zhǔn)來(lái)計(jì)算司機(jī)的工資成本，如式(6)所示：

(6)

式中，G表示工人單位時(shí)間工資，元/小時(shí).

車輛ak的裝載率及總車輛裝載率τ由式(7)、(8)得到：

(7)

(8)

式中：Wakmax和Vakmax分別為車輛ak的最大裝載重量和最大裝載體積;Ψ表示轄區(qū)的集合,ψ∈Ψ,Ψ={1,2,…}；Jψ表示轄區(qū)ψ的客戶點(diǎn)j的集合Jψ={1ψ,2ψ,…}.

在配送過(guò)程中，每個(gè)收貨點(diǎn)只能訪問(wèn)一次，約束如式(9)所示：

(9)

在調(diào)度配送過(guò)程中需滿足各型號(hào)車輛的最大數(shù)量限制.各型號(hào)的車輛數(shù)量由配送公司自身?xiàng)l件決定.約束如式(10)所示：

(10)

配送車輛ak在配送過(guò)程中需滿足最大裝載重量和最大裝載體積限制：

(11)

(12)

在轄區(qū)ψ內(nèi)的車型為a的車輛一次出車能去的客戶點(diǎn)數(shù)為ζ，該限制由公司擬定，約束如式(13)所示：

∑Kψak,j≤ζ，?a∈I,?k∈Ca

(13)

在車輛配送過(guò)程中需滿足各收貨點(diǎn)配送時(shí)間窗的限制，約束如式(14)所示：

(14)

式中，Tak,0為車輛ak駛出配送中心的時(shí)間.

車輛ak在配送過(guò)程中需滿足最大行駛距離約束，如式(15)所示：

∑(ljj′·Kak,j)+loj≤Lakmax，?a∈I,?k∈Ca

(15)

式中，Lakmax為車輛ak的最大行駛距離.

2 算法描述

2.1 傳統(tǒng)鯨魚群算法更新策略

在傳統(tǒng)鯨魚群算法中，算法的更新通過(guò)鯨魚群的跟隨搜索、圍捕獵物、搜索獵物來(lái)實(shí)現(xiàn)，每個(gè)個(gè)體都有可能執(zhí)行這3種行為之中的其中一種.在對(duì)每個(gè)個(gè)體的變量進(jìn)行更新時(shí)，將生成一個(gè)隨機(jī)數(shù)rand判斷該個(gè)體的該變量執(zhí)行哪一種行為，如公式(16)所示：

(16)

(17)

式中，g為當(dāng)前迭代次數(shù)；G為總迭代次數(shù).鯨魚群優(yōu)化算法采用跟隨搜索的尋優(yōu)方式，使得鯨魚群優(yōu)化算法在解決大規(guī)模優(yōu)化問(wèn)題時(shí)極易陷入局部最優(yōu)，并且鯨魚群優(yōu)化算法涉及到的參數(shù)較多，導(dǎo)致參數(shù)尋優(yōu)能力受參數(shù)變化影響較大.

2.2 改進(jìn)策略

2.2.1 指數(shù)型溫度下降

隨著迭代次數(shù)的增加，傳統(tǒng)模擬退火的降溫策略在后期易使算法陷入局部最優(yōu)，后期的全局尋優(yōu)能力較弱，因此為提高算法的全局搜索能力.本文所提溫度下降公式如下所示：

T=T0exp(-Cg)

(18)

在迭代初期，溫度值較高，粒子對(duì)能量值較高的狀態(tài)接受率較高;隨著迭代次數(shù)的增加，溫度值會(huì)急速下降并逐漸趨于穩(wěn)定;在后期,溫度值較低，粒子對(duì)能量值較高的狀態(tài)接受率較低，符合現(xiàn)實(shí)情況.

2.2.2 變量交叉擾動(dòng)

為使個(gè)體的搜索更具有方向性，引入變量交叉擾動(dòng)方式，包括單變量交叉擾動(dòng)與多變量交叉擾動(dòng).在原種群維度D中，首先隨機(jī)選中多個(gè)變量r，進(jìn)行交叉產(chǎn)生新個(gè)體，若新個(gè)體的目標(biāo)函數(shù)值為正無(wú)窮，即不滿足約束條件，將新個(gè)體刪去，改為采用單變量擾動(dòng)產(chǎn)生新個(gè)體;如果新個(gè)體不滿足約束條件則退出擾動(dòng)，不再產(chǎn)生新個(gè)體.多變量交叉擾動(dòng)與單變量交叉擾動(dòng)公式如式(19)、(20)所示：

(19)

(20)

2.2.3 種群分級(jí)

為平衡算法的全局尋優(yōu)能力與局部尋優(yōu)能力，采用種群分級(jí)的思想對(duì)種群個(gè)體進(jìn)行劃分.首先對(duì)目標(biāo)函數(shù)值進(jìn)行排序，選定一個(gè)閾值，目標(biāo)函數(shù)值大于等于該閾值，說(shuō)明其位置較差，需要跟隨最優(yōu)個(gè)體搜索，所以這一類個(gè)體將采用公式(16)進(jìn)行跟隨搜索；目標(biāo)函數(shù)值小于該閾值，說(shuō)明該個(gè)體位置較優(yōu)，如果繼續(xù)進(jìn)行跟隨搜索可能會(huì)陷入局部尋優(yōu)，因此這一類個(gè)體將通過(guò)公式(19)、(20)進(jìn)行交叉搜索.

2.3 基于改進(jìn)混合鯨魚群算法步驟

基于改進(jìn)混合鯨魚群算法步驟如下：

Step 1：初始化算法參數(shù)，隨機(jī)初始化種群；

Step 2：計(jì)算當(dāng)前溫度T；

Step 3：通過(guò)個(gè)體變量計(jì)算車輛訂單信息與車輛路徑信息；

Step 4：計(jì)算種群目標(biāo)函數(shù)值，保存全局最優(yōu)個(gè)體與全局最優(yōu)個(gè)體的目標(biāo)函數(shù)值；

Step 5：執(zhí)行種群分級(jí)操作；

Step 6：目標(biāo)函數(shù)值較大的個(gè)體根據(jù)公式(16)執(zhí)行跟隨搜索操作；

Step 7：目標(biāo)函數(shù)值較小的個(gè)體根據(jù)公式(19)、(20)進(jìn)行交叉搜索操作；

Step 8：是否達(dá)到最大迭代次數(shù)，是則退出；否則返回Step 2.

其算法流程圖如圖1所示.

圖1 算法流程圖Fig.1 Algorithm flow chart

3 算例分析

3.1 仿真結(jié)果

為驗(yàn)證問(wèn)題模型及所提改進(jìn)算法的有效性，首先選取北京市內(nèi)多個(gè)商超類型客戶點(diǎn)的運(yùn)輸配送業(yè)務(wù)為背景，并采用中國(guó)外運(yùn)股份有限公司2021年提供的公開(kāi)數(shù)據(jù)集生成仿真算例；然后用文中設(shè)計(jì)的混合鯨魚群算法進(jìn)行求解，制定合理的配送方案；最后選取粒子群算法、模擬退火算法及鯨魚算法進(jìn)行算例對(duì)比，以驗(yàn)證本文所提出的面向城市超市配送的異構(gòu)車輛智慧調(diào)度模型及算法的普適性.其中，文中所用各型號(hào)的車輛信息如表1所示，訂單信息如表2所示，城區(qū)交通擁堵延遲系數(shù)情況如表3所示.

表1 各型號(hào)的車輛信息表Tab.1 Vehicle information of each model

表2 訂單信息表Tab.2 Order information

表3 北京市配送城區(qū)交通情況Tab.3 Traffic conditions in various urban areas of Beijing

為保證橫向?qū)Ρ人惴ǖ墓叫?，PSO、WOA、SA、WOA-ISA 4種算法的種群數(shù)量NP=200,迭代次數(shù)G=200；PSO算法中的學(xué)習(xí)因子c1、c2等于1.5，粒子速度vmax=5，vmin=-5;WOA算法中l(wèi)=1,初始溫度設(shè)置為100°.將4種算法各運(yùn)行30次取得其中的結(jié)果.其中，WOA-ISA算法的規(guī)劃結(jié)果如表4所示，任意一次算法求解的收斂曲線如圖2所示，4個(gè)算法運(yùn)行30次的平均目標(biāo)函數(shù)值如圖3所示，目標(biāo)函數(shù)最值對(duì)比如圖4所示.進(jìn)一步將圖5的5個(gè)指標(biāo)歸一化處理進(jìn)行對(duì)比分析，4個(gè)算法的指標(biāo)對(duì)比如表5所示.

圖2 單次函數(shù)值對(duì)比Fig.2 Comparison of single function value

圖3 平均函數(shù)值對(duì)比Fig.3 Comparison of average function values

圖4 目標(biāo)函數(shù)最值對(duì)比Fig.4 Comparison of objective function maxima

圖5 歸一化指標(biāo)對(duì)比圖Fig.5 Comparison chart of normalized indicators

表4 隨機(jī)選取WOA-ISA算法30次運(yùn)行過(guò)程中某次的規(guī)劃結(jié)果Tab.4 Random selection of the planning results of a certain time of the 30 runs of the WOA-ISA algorithm

3.2 仿真實(shí)驗(yàn)結(jié)果分析

由圖2和圖3可以看出，相較于SA算法、PSO算法和WOA算法，本文所提出的WOA-ISA算法的全局搜索能力較強(qiáng)，在100代左右，其他算法趨于收斂的同時(shí)本文所提算法仍保持著高效的搜索模式.從圖4的最值比較中也可以得出WOA-ISA算法在求解過(guò)程中的優(yōu)異性.這主要得益于算法中的種群分級(jí)以及變異交叉擾動(dòng)操作，使得算法具備跳出局部最優(yōu)解的能力，提高了算法的全局搜索性能，這也說(shuō)明了本文所提改進(jìn)策略的優(yōu)越性.由圖3可知，本文所提算法相較于SA、PSO、WOA算法,其目標(biāo)函數(shù)值分別降低了42%、35%及26%.

進(jìn)一步根據(jù)圖5、表5可知：相較于SA、PSO、WOA算法，無(wú)論是配送成本、泡重成本、配送車輛數(shù)量、最長(zhǎng)配時(shí)及裝載率，本文所提算法均有著較強(qiáng)的競(jìng)爭(zhēng)力,在運(yùn)輸固定成本上分別降低了6%、15%、12%,泡重成本減少了42%、36%、35%,配送時(shí)間降低了20%、24%、14%,裝載率提高了17%、9.2%、5.8%，經(jīng)過(guò)擁堵路段的次數(shù)降低了37%、25%及29%,發(fā)車數(shù)量減少了近2輛.達(dá)到了配送成本最小、車輛裝載利用率最大、發(fā)車數(shù)輛最少的多目標(biāo)優(yōu)化.本文所提的WOA-ISA算法相較于其他算法具有更好的收斂性以及收斂速度，同時(shí)具備跳出局部最優(yōu)解的能力，具有更好的全局搜索性.因此相較于其他的智能優(yōu)化算法，WOA-ISA算法在解決面向城市超市配送的異構(gòu)車輛智慧調(diào)度模型問(wèn)題上，可以高效地提供更為有效的調(diào)度方案，在降低成本的同時(shí)極大提高了車輛的配送效率.

表5 算法指標(biāo)對(duì)比Tab.5 Comparison of algorithm indexes

4 結(jié)論

本文在城市物流配送快速發(fā)展的背景下，充分考慮到當(dāng)前物流調(diào)度模型的不足，建立以車輛泡重比、司機(jī)工資成本、運(yùn)費(fèi)成本、車輛物理約束、時(shí)間窗約束、車輛配送的實(shí)時(shí)性、擁堵系數(shù)為約束條件，以配送成本最小，車輛裝載利用率為多維優(yōu)化目標(biāo)的異構(gòu)車輛智慧調(diào)度數(shù)學(xué)模型.同時(shí)針對(duì)鯨魚算法在求解大規(guī)模目標(biāo)問(wèn)題時(shí)存在的缺陷，設(shè)計(jì)了一種包括變量交叉擾動(dòng)、種群分級(jí)等策略的混合鯨魚群算法.最后通過(guò)仿真實(shí)驗(yàn)表明，本文所提算法能夠有效應(yīng)用于該類復(fù)雜大規(guī)模問(wèn)題，提高車輛裝載率、降低配送費(fèi)用、減少配送公司發(fā)車次數(shù)，為數(shù)字化物流系統(tǒng)的構(gòu)建提供理論參考.