考慮變化調整時間及帶有時間窗的車輛調度問題研究

楊貴紅 張蕾

摘 要：本文就車輛調度問題進行了深入分析，并提出了幾種常用的問題研究算法，希望能夠為同行業工作者提供一些幫助。

關鍵詞：考慮變化調整時間;時間窗;車輛調度問題;算法

科學技術的發展與裝備制造業的進步，使得多數企業逐漸提高了對于物流配送環節的重視，這就使得當下大型物流企業將革新的重點放在了車輛調度系統的升級上。相較傳統調度系統，考慮變化調整時間及帶有時間窗的車來給你調度系統有著諸多應用優勢，由于能夠更好的反映出車輛的實際運行狀況，因此從根本上減少了運營成本，為企業的未來可持續發展奠定了堅實的基礎，因此對車輛調度問題進行深入探究具有極為重要的現實意義。

調度優化領域在近幾年表現的異常活躍，以往僅僅停留在理論層面的優化算法隨著技術的成熟已經被逐漸應用于實際的工業環境中，為從根本上解決生產運營問題提供了基礎條件，是生產力進步的關鍵因素。因此，需要對在工業快速發展的背景下進行全面的學術研究，分析在工程問題的背景下問題的分析方式，以找尋解決問題的最有效方式。近些年來各個領域的專家研究結構如下：

1.TSP（旅行商問題）

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

2.CVRP（帶有容量的車隊路徑問題）

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

3.VRPTW（時間窗車輛調度問題）

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

4.VRPSTW（軟時間窗車輛路徑問題）

該問題實際上是時間窗問題的延伸，以客戶對車輛的實際到達時間為依據需要構建不同種類型的時間窗目標函數。在對整車物流配送問題進行分析時，需要以總成本最小為基礎目標，盡量提高客戶滿意度以構建對應的數學模型，并為其設計具有自適應特點的遺傳算法;經驗性分析法是替代傳統算法的一種新式分析手段，其在對算法算子不同組合方面的相對效率評價與遺傳算法方面的參數去那種均有著極佳的應用效果，解決了VRPSTW。

5.VRPSSTW（半軟時間窗路徑問題）

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

6.結束語

綜上所述，在對變化調整時間以及帶有時間窗車輛調度問題進行分析時，需要以實際生產所面對的問題為基礎，并需要在車輛的調度環節添加容量限制與時間窗的限制條件，并通過對時間進行調整能夠構建出新式的用于車輛調度的數學模型，也可以將其作為VRP模型的擴展，為后續解決類似問題提供了參考條件。

參考文獻：

[1]趙亮.客戶配送要求變動的車輛調度問題研究[D].大連海事大學，2018.

[2]谷俊輝.開放式車輛調度問題的參數控制蟻群算法的研究[D].合肥工業大學，2017.

[3]馮德健.多行程多時間窗需求可拆分的應急疏散車輛調度[D].哈爾濱工業大學，2018.

本文為云南省教育廳科學研究基金項目，項目名稱：線性規劃法在帶軟時間窗車輛調度優化問題中的應用——以內蒙古烏蘭察布市物流倉儲配送中心為例，項目編號：2019J1108。

（云南師范大學文理學院 ?云南 ?昆明 ?650222）