高亞偉

【摘? 要】在物流配送的過(guò)程中，經(jīng)常會(huì)發(fā)生一些對(duì)初始配送方案造成擾動(dòng)的干擾事件，這會(huì)對(duì)物流運(yùn)營(yíng)商及客戶造成不良的影響。為解決這一難題，論文對(duì)多車場(chǎng)車輛調(diào)度干擾管理問(wèn)題進(jìn)行分析，通過(guò)對(duì)相關(guān)文獻(xiàn)的研究，歸納出多車場(chǎng)車輛調(diào)度問(wèn)題及干擾管理問(wèn)題的研究現(xiàn)狀，并對(duì)相關(guān)的啟發(fā)式算法進(jìn)行總結(jié)，指出現(xiàn)有研究的不足，展望下一步的研究方向。

【Abstract】In the process of logistics distribution， there are often some disturbance events that disturb the initial distribution scheme， which will have a bad impact on the logistics operators and customers. In order to solve this problem， this paper analyzes the disruption management problem of multi-depot vehicle scheduling. Through the research of the relevant literature， the paper summarizes the current research status of the multi-depot vehicle scheduling problem and the disruption management problem， and summarizes the related heuristic algorithms， points out the deficiencies of the existing research， and looks forward to the next research direction.

【關(guān)鍵詞】多車場(chǎng);車輛調(diào)度;干擾管理;啟發(fā)式算法

【Keywords】multi-depot; vehicle scheduling; disruption management; heuristic algorithms

【中圖分類號(hào)】F259.2? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文獻(xiàn)標(biāo)志碼】A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文章編號(hào)】1673-1069（2020）12-0148-02

1 引言

作為我國(guó)國(guó)民經(jīng)濟(jì)的基礎(chǔ)產(chǎn)業(yè)，現(xiàn)代物流行業(yè)涉及領(lǐng)域廣、從業(yè)人數(shù)多，包含了運(yùn)輸、倉(cāng)儲(chǔ)以及物聯(lián)網(wǎng)等多個(gè)產(chǎn)業(yè)，已成為我國(guó)的重點(diǎn)發(fā)展行業(yè)。同時(shí)，現(xiàn)代物流業(yè)也是供給側(cè)改革的重要內(nèi)容，其發(fā)展程度已成為衡量一個(gè)國(guó)家綜合國(guó)力的重要標(biāo)志之一。近年來(lái)，得益于我國(guó)國(guó)內(nèi)經(jīng)濟(jì)的增長(zhǎng)、互聯(lián)網(wǎng)的普及以及電子商務(wù)的快速發(fā)展，我國(guó)物流行業(yè)發(fā)展迅速。一方面，現(xiàn)代物流企業(yè)資產(chǎn)重組、資源整合的進(jìn)程進(jìn)一步加快，物流市場(chǎng)結(jié)構(gòu)不斷優(yōu)化，與“互聯(lián)網(wǎng)+”相結(jié)合的物流新興產(chǎn)業(yè)接踵而來(lái)，逐漸形成了一批管理現(xiàn)代化、服務(wù)網(wǎng)絡(luò)化、所有制多元化的現(xiàn)代物流企業(yè);另一方面，我國(guó)的社會(huì)物流總費(fèi)用與GDP的比值逐年下降，物流運(yùn)行效率和質(zhì)量有所提升，物流行業(yè)升級(jí)轉(zhuǎn)型趨勢(shì)明顯。據(jù)中國(guó)產(chǎn)業(yè)經(jīng)濟(jì)信息網(wǎng)統(tǒng)計(jì)，2019年全年我國(guó)社會(huì)物流總額高達(dá)298萬(wàn)億元，累計(jì)增長(zhǎng)5.9%。社會(huì)物流總費(fèi)用已達(dá)14.6萬(wàn)億元，其中社會(huì)物流總費(fèi)用與GDP的比值約為14.7%。然而歐美、日本等發(fā)達(dá)國(guó)家的社會(huì)物流總費(fèi)用與GDP的比值均不到10%，這說(shuō)明我國(guó)的物流行業(yè)還處于由發(fā)展期向成熟期過(guò)渡的階段，依然存在著較大的發(fā)展空間。其中，車輛運(yùn)輸過(guò)程中所產(chǎn)生的費(fèi)用在物流總費(fèi)用中占有很大的比重，物流運(yùn)營(yíng)商若能對(duì)配送的車輛進(jìn)行合理的調(diào)度將減少5%～20%的運(yùn)輸成本，所以對(duì)車輛調(diào)度問(wèn)題的研究具有一定的現(xiàn)實(shí)意義。

面對(duì)社會(huì)物流需求的不斷增長(zhǎng)，客戶網(wǎng)點(diǎn)分布不斷分散，物流運(yùn)營(yíng)商若只考慮用一個(gè)車場(chǎng)對(duì)客戶進(jìn)行物流配送服務(wù)已遠(yuǎn)遠(yuǎn)不能滿足現(xiàn)實(shí)生活的需要，配備多個(gè)車場(chǎng)必然是未來(lái)的趨勢(shì)。物流運(yùn)營(yíng)商需要在多個(gè)車場(chǎng)間合理地安排車輛的行駛路線，在考慮物流配送成本的同時(shí)，還需考慮到時(shí)間窗、客戶滿意度、碳排放等因素，由此延伸出了多車場(chǎng)車輛調(diào)度問(wèn)題。

在實(shí)際的物流配送過(guò)程中，經(jīng)常會(huì)發(fā)生一些干擾事件，如客戶地址變動(dòng)、車輛故障、客戶需求量變動(dòng)等，這些事件的發(fā)生必然會(huì)對(duì)物流運(yùn)營(yíng)商的配送計(jì)劃造成一定的擾動(dòng)，從而影響物流運(yùn)營(yíng)商、客戶以及配送人員之間的利益。因此，如何合理地對(duì)車輛的行駛路線進(jìn)行調(diào)整以達(dá)到擾動(dòng)最小是物流運(yùn)營(yíng)商亟待解決的問(wèn)題。

2 多車場(chǎng)車輛調(diào)度問(wèn)題研究

多車場(chǎng)車輛調(diào)度問(wèn)題指的是物流運(yùn)營(yíng)商可以從多個(gè)車場(chǎng)調(diào)度車輛，為多個(gè)客戶提供物流配送服務(wù)，在滿足服務(wù)時(shí)間窗、客戶需求量、車輛容量等約束條件下，達(dá)到客戶滿意度最高、配送成本最低等目標(biāo)。該問(wèn)題是基本車輛調(diào)度問(wèn)題的擴(kuò)展，是更為復(fù)雜的NP難題，目前學(xué)者已從多方面對(duì)該問(wèn)題進(jìn)行了全面的研究。例如，研究了帶有時(shí)間窗約束的多車場(chǎng)車輛調(diào)度問(wèn)題，即每個(gè)客戶都有自己期望收到貨物的時(shí)間窗，物流運(yùn)營(yíng)商需要在規(guī)定的時(shí)間窗內(nèi)將貨物送給客戶，否則將會(huì)受到相應(yīng)的懲罰，其中時(shí)間窗主要分為硬時(shí)間窗、軟時(shí)間窗及模糊時(shí)間窗三類?？紤]了多種車型的多車場(chǎng)車輛調(diào)度問(wèn)題，即物流運(yùn)營(yíng)商配有多種車型對(duì)客戶提供物流服務(wù)，每種車型的裝載量、使用成本、行駛速度等均不相同?？紤]了多起訖點(diǎn)的多車場(chǎng)車輛調(diào)度問(wèn)題，即貨物的轉(zhuǎn)運(yùn)點(diǎn)隨著貨物信息的動(dòng)態(tài)變化而變化，更符合現(xiàn)實(shí)的需求?？紤]了多維裝箱問(wèn)題的多車場(chǎng)車輛調(diào)度問(wèn)題，即在物流配送過(guò)程中由于某些特殊貨物具有易損、易碎等特征，這種情況下貨物不可隨意疊放。這時(shí)貨物能否裝車就取決于貨物底面能否拼裝入車廂底面中，需要靈活確定待裝貨物和裝貨空間之間的匹配關(guān)系，以減少重復(fù)確定裝箱方案所消耗的時(shí)間。根據(jù)運(yùn)輸貨物種類的不同，可以分為冷鏈物流、農(nóng)產(chǎn)品物流、危險(xiǎn)品物流等多種類型。根據(jù)配送車輛服務(wù)完客戶后是否返回原車場(chǎng)，還可將多車場(chǎng)車輛調(diào)度問(wèn)題分為封閉式和開(kāi)放式兩種類型。

3 車輛調(diào)度干擾管理問(wèn)題研究

干擾管理理論是指在計(jì)劃執(zhí)行的過(guò)程中發(fā)生了不可預(yù)測(cè)的干擾事件，使得正在執(zhí)行的方案變得不可行，此時(shí)要對(duì)正在執(zhí)行的方案進(jìn)行調(diào)整，調(diào)整后的方案不僅要滿足最初的優(yōu)化目標(biāo)，還要使干擾事件帶來(lái)的負(fù)面作用最小。干擾管理需要根據(jù)研究的問(wèn)題及具體的干擾事件構(gòu)建對(duì)應(yīng)的數(shù)學(xué)模型，快速地給出最優(yōu)調(diào)整方案。調(diào)整后的方案并不是對(duì)原方案進(jìn)行徹底的改動(dòng)，而是在原方案的基礎(chǔ)上進(jìn)行小規(guī)模的調(diào)整，目的是得出對(duì)整體系統(tǒng)擾動(dòng)最小的調(diào)整方案，所以干擾管理方案得出的結(jié)果往往并不是成本最優(yōu)的。干擾管理理論自被提出以來(lái)就受到學(xué)者的廣泛關(guān)注，目前已在項(xiàng)目管理、航空調(diào)度、企業(yè)管理以及車輛調(diào)度等領(lǐng)域取得了很好的應(yīng)用成果。

學(xué)者對(duì)于車輛調(diào)度中的干擾事件研究主要?jiǎng)澐譃榭蛻魰r(shí)間窗變動(dòng)、客戶地址變動(dòng)、車輛故障、客戶需求變動(dòng)、客戶數(shù)量變動(dòng)等幾類。學(xué)者針對(duì)不同的干擾事件，以干擾事件對(duì)系統(tǒng)造成的擾動(dòng)進(jìn)行度量，構(gòu)建出具體的干擾管理數(shù)學(xué)模型。楊華龍等[1]研究了客戶時(shí)間窗變動(dòng)的干擾管理問(wèn)題，考慮了路線、服務(wù)時(shí)間、運(yùn)輸費(fèi)用三個(gè)方面的因素，以費(fèi)用偏離最小為目標(biāo)構(gòu)建數(shù)學(xué)模型。卜心怡等[2]針對(duì)客戶地址變動(dòng)這一擾動(dòng)因素，以客戶和物流運(yùn)營(yíng)商的利益最大化為目標(biāo)構(gòu)建擾動(dòng)恢復(fù)模型。曹慶奎等[3]以車輛故障為干擾因素，結(jié)合了行為運(yùn)籌理論對(duì)客戶、物流運(yùn)營(yíng)商及配送人員的滿意度進(jìn)行度量，建立救援車輛調(diào)度數(shù)學(xué)模型。

4 相關(guān)求解算法研究

多車場(chǎng)車輛調(diào)度干擾管理問(wèn)題已被證明為NP難題，難以找出問(wèn)題的最優(yōu)解，因此，普通的精確算法已不適用于求解此類問(wèn)題，目前，學(xué)者更熱衷于采用啟發(fā)式算法來(lái)提高此類問(wèn)題的求解效率和準(zhǔn)確性。①遺傳算法。依據(jù)達(dá)爾文生物進(jìn)化論中“優(yōu)勝劣汰”的法則，John Holland于20世紀(jì)70年代提出遺傳算法。該算法通過(guò)交叉、變異等操作對(duì)種群不斷優(yōu)化，通過(guò)判斷染色體的適應(yīng)度值大小，將種群中適應(yīng)度高的個(gè)體遺傳到下一代，經(jīng)過(guò)多次迭代找出最優(yōu)解。該算法具有很強(qiáng)的魯棒性，但容易出現(xiàn)早熟的問(wèn)題。②蟻群算法。該算法通過(guò)模仿蟻群覓食活動(dòng)演變而來(lái)，在尋找食物的過(guò)程中螞蟻會(huì)慢慢地聚集在最短路徑上，該路徑就是問(wèn)題的最優(yōu)解。蟻群算法對(duì)初始路徑的要求不高、參數(shù)較少，但容易陷入局部最優(yōu)。③禁忌搜索算法。禁忌搜索是在搜索過(guò)程中構(gòu)造一個(gè)短期記憶表，即為禁忌表，表中存放剛剛搜索過(guò)的結(jié)果。在一定次數(shù)范圍r內(nèi)，禁忌表中所存放的結(jié)果不能重復(fù)，r次之后，禁忌解除。禁忌表始終保持r個(gè)移動(dòng)。當(dāng)滿足停止規(guī)則或迭代內(nèi)所搜索到最好結(jié)果無(wú)法改進(jìn)時(shí)，搜索活動(dòng)停止。該算法容易理解，容易實(shí)現(xiàn)，具有較強(qiáng)的通用性，且局部開(kāi)發(fā)能力強(qiáng)，收斂速度很快。但全局開(kāi)發(fā)能力弱，只能搜索到局部最優(yōu)解，并且搜索的結(jié)果完全依賴于初始解和鄰域的映射關(guān)系。

除了上述算法之外，還有人工蜂群算法、細(xì)菌覓食算法、模擬植物生長(zhǎng)算法等啟發(fā)式算法。每種算法具有各自的特點(diǎn)，研究者需根據(jù)不同的研究問(wèn)題結(jié)合不同的算法進(jìn)行求解。

5 結(jié)語(yǔ)與展望

目前，學(xué)者對(duì)多車場(chǎng)車輛調(diào)度問(wèn)題、干擾管理問(wèn)題及相關(guān)求解算法進(jìn)行了全面的研究，但對(duì)于多車場(chǎng)車輛調(diào)度干擾管理問(wèn)題的研究還存在以下幾點(diǎn)問(wèn)題：①現(xiàn)有的研究大多以時(shí)間來(lái)度量客戶的滿意度，然而現(xiàn)實(shí)生活中影響客戶滿意度的不只有時(shí)間因素，在后續(xù)的研究中應(yīng)考慮加入其他因素;②目前，學(xué)者的研究?jī)H僅考慮了一種干擾因素，事實(shí)上考慮多種干擾因素相結(jié)合更符合現(xiàn)實(shí)的需求;③目前，很多啟發(fā)式算法在求解大規(guī)模復(fù)雜問(wèn)題上依然存在著許多的問(wèn)題，今后的研究應(yīng)繼續(xù)對(duì)算法進(jìn)行改進(jìn)，提高算法的性能。

【參考文獻(xiàn)】

【1】楊華龍，葉迪，張倩，等.時(shí)間窗變動(dòng)的車輛調(diào)度干擾管理模型與算法[J].運(yùn)籌與管理，2017，26（10）：56-64.

【2】卜心怡，劉超，錢(qián)軍.基于配送地點(diǎn)變化的物流干擾管理研究[J].生產(chǎn)力研究，2016（11）：19-22.

【3】曹慶奎，邵松娟，任向陽(yáng).考慮配送主體感知的救援車輛調(diào)度研究[J].物流科技，2016，39（2）：1-3.