考慮變化調(diào)整時(shí)間及帶有時(shí)間窗的車輛調(diào)度問(wèn)題研究

楊貴紅 張蕾

摘 要：本文就車輛調(diào)度問(wèn)題進(jìn)行了深入分析，并提出了幾種常用的問(wèn)題研究算法，希望能夠?yàn)橥袠I(yè)工作者提供一些幫助。

關(guān)鍵詞：考慮變化調(diào)整時(shí)間;時(shí)間窗;車輛調(diào)度問(wèn)題;算法

科學(xué)技術(shù)的發(fā)展與裝備制造業(yè)的進(jìn)步，使得多數(shù)企業(yè)逐漸提高了對(duì)于物流配送環(huán)節(jié)的重視，這就使得當(dāng)下大型物流企業(yè)將革新的重點(diǎn)放在了車輛調(diào)度系統(tǒng)的升級(jí)上。相較傳統(tǒng)調(diào)度系統(tǒng)，考慮變化調(diào)整時(shí)間及帶有時(shí)間窗的車來(lái)給你調(diào)度系統(tǒng)有著諸多應(yīng)用優(yōu)勢(shì)，由于能夠更好的反映出車輛的實(shí)際運(yùn)行狀況，因此從根本上減少了運(yùn)營(yíng)成本，為企業(yè)的未來(lái)可持續(xù)發(fā)展奠定了堅(jiān)實(shí)的基礎(chǔ)，因此對(duì)車輛調(diào)度問(wèn)題進(jìn)行深入探究具有極為重要的現(xiàn)實(shí)意義。

調(diào)度優(yōu)化領(lǐng)域在近幾年表現(xiàn)的異?；钴S，以往僅僅停留在理論層面的優(yōu)化算法隨著技術(shù)的成熟已經(jīng)被逐漸應(yīng)用于實(shí)際的工業(yè)環(huán)境中，為從根本上解決生產(chǎn)運(yùn)營(yíng)問(wèn)題提供了基礎(chǔ)條件，是生產(chǎn)力進(jìn)步的關(guān)鍵因素。因此，需要對(duì)在工業(yè)快速發(fā)展的背景下進(jìn)行全面的學(xué)術(shù)研究，分析在工程問(wèn)題的背景下問(wèn)題的分析方式，以找尋解決問(wèn)題的最有效方式。近些年來(lái)各個(gè)領(lǐng)域的專家研究結(jié)構(gòu)如下：

1.TSP（旅行商問(wèn)題）

簡(jiǎn)單來(lái)說(shuō)TP就是倉(cāng)庫(kù)或中轉(zhuǎn)站開(kāi)始與結(jié)束車輛，以客戶對(duì)其具體需求為基礎(chǔ)選擇合適方式用以完成配送的相關(guān)任務(wù)。確保在充分考慮所關(guān)聯(lián)約束條件下車輛總行駛里程達(dá)到最小數(shù)值，從而實(shí)現(xiàn)運(yùn)輸成本的節(jié)約目標(biāo)。有專家率先提出分層分塊的優(yōu)化思想用以真正解決旅游線路的規(guī)劃問(wèn)題，并以此為基礎(chǔ)構(gòu)建完善的分塊網(wǎng)絡(luò)加權(quán)圖，并需要對(duì)可能出現(xiàn)的影響因素進(jìn)行深入分析以幫助改進(jìn)多旅行商優(yōu)化模型，而求解所應(yīng)用的基本算法為模擬退火法，最終以實(shí)例為依據(jù)制定出了在既有條件下的最優(yōu)游覽線路圖[1];若以應(yīng)急車輛的調(diào)度為基礎(chǔ)條件，在車輛容量有限與其不需要返回出發(fā)點(diǎn)的情況下，提出了配額環(huán)境下的在線漂泊旅行商問(wèn)題，此時(shí)所采用的算法為目標(biāo)算法;若針對(duì)自適應(yīng)大鄰域搜索，則主要用到的是廣義上的旅行商問(wèn)題算法，并以在算法運(yùn)行狀態(tài)下的不間斷巡回操作為基本特點(diǎn)，融入新式的插入機(jī)制以比較新的運(yùn)行機(jī)制用于求解其結(jié)果，具有較高的競(jìng)爭(zhēng)力。

2.CVRP（帶有容量的車隊(duì)路徑問(wèn)題）

該種方式在確定車輛載重與行駛時(shí)間后，以實(shí)際情況為算法的應(yīng)用背景一般表現(xiàn)出對(duì)此載重與時(shí)間的約束狀態(tài)。其以切比雪夫方法為依據(jù)的多目標(biāo)模型的建立，其針對(duì)的是不同車型的VRP（車輛調(diào)度問(wèn)題），成本、排放因子以及容量是在融入于最小化總運(yùn)營(yíng)成本的三個(gè)目標(biāo)函數(shù)。為達(dá)到同時(shí)減少車輛尾氣排放的目的，在不對(duì)時(shí)間窗約束條件進(jìn)行深入探究的背景下提出了一種新式算法——節(jié)省啟發(fā)式算法，在對(duì)案例進(jìn)行分析與應(yīng)用前需要首先確定算法是否具有實(shí)用性并應(yīng)對(duì)模型進(jìn)行確認(rèn)[2];以VRP為基礎(chǔ)提出了在碳足跡條件下的庫(kù)存路徑問(wèn)題，問(wèn)題的重點(diǎn)在于當(dāng)碳排放精度水平足夠的基礎(chǔ)上一旦確定具有有效性的碳排放庫(kù)存路線后，需要選擇出合適的庫(kù)存編制供應(yīng)商，同時(shí)應(yīng)對(duì)庫(kù)存路線進(jìn)行深度優(yōu)化以實(shí)現(xiàn)效率的最大化，同時(shí)并不會(huì)影響到既有成本，反而會(huì)使得耗費(fèi)成本有縮小的特征表現(xiàn);在考慮到單產(chǎn)品條件后，有專家提出了貨物權(quán)重的車輛路徑問(wèn)題，而對(duì)問(wèn)題進(jìn)行設(shè)計(jì)的目標(biāo)在于實(shí)現(xiàn)路線的最小化，并需要計(jì)算出在確定運(yùn)載重量與距離數(shù)值的情況下產(chǎn)生的路徑總費(fèi)用。根據(jù)問(wèn)題表現(xiàn)出的特點(diǎn)，提出了符合解答車輛路徑問(wèn)題的SS算法。

3.VRPTW（時(shí)間窗車輛調(diào)度問(wèn)題）

該種車輛不僅需要符合VRP的限制條件，同時(shí)應(yīng)滿足時(shí)間窗的具體限制，并需要以時(shí)間窗的具體限制為依據(jù)在對(duì)其進(jìn)行優(yōu)化的過(guò)程中構(gòu)建符合時(shí)間窗特點(diǎn)的經(jīng)過(guò)優(yōu)化的目標(biāo)函數(shù)，從而幫助解決由于添加了時(shí)間窗條件限制而導(dǎo)致問(wèn)題求解復(fù)雜度的增加。若以電子商務(wù)為訂單配送問(wèn)題的產(chǎn)生環(huán)境，可以根據(jù)該問(wèn)題的特點(diǎn)構(gòu)建以訂單懲罰費(fèi)用與最小化車輛行駛費(fèi)用為目標(biāo)的數(shù)學(xué)模型，在這一數(shù)學(xué)模型的基礎(chǔ)上則能夠幫助設(shè)計(jì)具有兩階段結(jié)構(gòu)特點(diǎn)的啟發(fā)式求解算法;以實(shí)際問(wèn)題為依據(jù)則能構(gòu)建出有著多目標(biāo)特點(diǎn)的在時(shí)間約束下的車輛調(diào)度模型，并需要以例子群算法為基礎(chǔ)求解出與之相關(guān)聯(lián)的車輛調(diào)度問(wèn)題，幫助制定最優(yōu)的車輛調(diào)度方案[3];而通過(guò)對(duì)VRP進(jìn)行深入分析，則可幫助與實(shí)際運(yùn)輸特點(diǎn)相關(guān)聯(lián)的數(shù)學(xué)模型，此時(shí)想要求解則需要應(yīng)用混合智能算法，或是應(yīng)用SS算法以幫助解決數(shù)學(xué)問(wèn)題模型。

4.VRPSTW（軟時(shí)間窗車輛路徑問(wèn)題）

該問(wèn)題實(shí)際上是時(shí)間窗問(wèn)題的延伸，以客戶對(duì)車輛的實(shí)際到達(dá)時(shí)間為依據(jù)需要構(gòu)建不同種類型的時(shí)間窗目標(biāo)函數(shù)。在對(duì)整車物流配送問(wèn)題進(jìn)行分析時(shí)，需要以總成本最小為基礎(chǔ)目標(biāo)，盡量提高客戶滿意度以構(gòu)建對(duì)應(yīng)的數(shù)學(xué)模型，并為其設(shè)計(jì)具有自適應(yīng)特點(diǎn)的遺傳算法;經(jīng)驗(yàn)性分析法是替代傳統(tǒng)算法的一種新式分析手段，其在對(duì)算法算子不同組合方面的相對(duì)效率評(píng)價(jià)與遺傳算法方面的參數(shù)去那種均有著極佳的應(yīng)用效果，解決了VRPSTW。

5.VRPSSTW（半軟時(shí)間窗路徑問(wèn)題）

該問(wèn)題的限制條件為車輛僅僅允許到達(dá)時(shí)間提前或滯后，在聯(lián)系硬軟時(shí)間窗后所表現(xiàn)出的狀態(tài)特點(diǎn)更加與現(xiàn)實(shí)情況相貼近。以鋼包調(diào)度問(wèn)題為例，在研究此類問(wèn)題是需要將其抽象畫(huà)為半軟時(shí)間窗與對(duì)車輛路徑進(jìn)行調(diào)整的相關(guān)問(wèn)題，并需要構(gòu)建與之對(duì)應(yīng)的具有非線性特征的數(shù)學(xué)規(guī)劃模型，并為其設(shè)計(jì)一個(gè)新式算法用以幫助將這一問(wèn)題解決;而在只考慮延遲到達(dá)的懲罰而提前到達(dá)無(wú)懲罰的條件下，提出了以列為基礎(chǔ)所對(duì)應(yīng)形成的具有精確性的優(yōu)化方法，從而獲得關(guān)于這一類型問(wèn)題的最優(yōu)解答;精確優(yōu)化算法的主要特點(diǎn)是資源約束條件的突顯，在應(yīng)用至延遲到達(dá)懲罰最短路徑方面的問(wèn)題后可以將其轉(zhuǎn)化為子問(wèn)題從而被快速解決。該種解決方案通過(guò)在道路網(wǎng)絡(luò)上的應(yīng)用實(shí)例中可以看到，路線數(shù)量相較以往有了明年減少，而所導(dǎo)致形成的延遲罰金僅僅占有總成本的極小比例。

6.結(jié)束語(yǔ)

綜上所述，在對(duì)變化調(diào)整時(shí)間以及帶有時(shí)間窗車輛調(diào)度問(wèn)題進(jìn)行分析時(shí)，需要以實(shí)際生產(chǎn)所面對(duì)的問(wèn)題為基礎(chǔ)，并需要在車輛的調(diào)度環(huán)節(jié)添加容量限制與時(shí)間窗的限制條件，并通過(guò)對(duì)時(shí)間進(jìn)行調(diào)整能夠構(gòu)建出新式的用于車輛調(diào)度的數(shù)學(xué)模型，也可以將其作為VRP模型的擴(kuò)展，為后續(xù)解決類似問(wèn)題提供了參考條件。

參考文獻(xiàn)：

[1]趙亮.客戶配送要求變動(dòng)的車輛調(diào)度問(wèn)題研究[D].大連海事大學(xué)，2018.

[2]谷俊輝.開(kāi)放式車輛調(diào)度問(wèn)題的參數(shù)控制蟻群算法的研究[D].合肥工業(yè)大學(xué)，2017.

[3]馮德健.多行程多時(shí)間窗需求可拆分的應(yīng)急疏散車輛調(diào)度[D].哈爾濱工業(yè)大學(xué)，2018.

本文為云南省教育廳科學(xué)研究基金項(xiàng)目，項(xiàng)目名稱：線性規(guī)劃法在帶軟時(shí)間窗車輛調(diào)度優(yōu)化問(wèn)題中的應(yīng)用——以內(nèi)蒙古烏蘭察布市物流倉(cāng)儲(chǔ)配送中心為例，項(xiàng)目編號(hào)：2019J1108。

（云南師范大學(xué)文理學(xué)院 ?云南 ?昆明 ?650222）