時間窗約束下的非滿載車輛優化調度算法研究

摘要：在車輛優化調度問題上，文章將配送車輛根據任務的性質分成滿載和非滿載兩類問題。針對時間窗約束下的非滿載車輛優化調度問題，同時考慮特定的時間窗和車輛容量、行駛距離等約束條件，運用數學規劃理論對其進行了研究。并在分析其數學模型的基礎上，給出了實例分析，對提高物流配送效率和降低成本具有重要意義。

關鍵詞：時間窗；算法；車輛優化調度

中圖分類號：F224文獻標識碼：A

文章編號：1002-3100(2008)11-0028-04

Abstract: On the problem of optimization of vehicle dispatching optimizing， this thesis studying on the distribution freight vehicle， analyses two problems named as full loaded vehicle scheduling problem and non-full loaded vehicle scheduling problem which are classed by the property of the task. For resolving the OVD problem under the time windows and vehicle capacity constraints， as the same time， taking special restrictions such as time window， the capability of vehicle and the run distance into account， the theory of mathematical programming is used. By analyzing the mathematical model of the OVD， its practical example is given， and it is very important to improve the efficiency of logistics distribution and reduce cost.

Key words: time windows; algorithm; optimization of vehicle dispatching

0引言

在汽車運輸部（分）隊擔負的繁重的運輸保障任務中，大量存在的時間窗約束下的非滿載車輛調度問題，由于沒有合理的優化算法支撐，往往得不到較好的解決，致使運輸部（分）隊保障效率低下、資源浪費現象嚴重，極大地限制了汽車運輸部（分）隊保障能力的發揮。因此，研究時間窗約束下非滿載車輛優化調度算法，就顯得愈發的重要和迫切。

1非滿載OVD問題的數學模型構建

1.1非滿載OVD問題的數學模型

將輸送中心S編號為0，任務編號為1，2，…，L，任務及保障點均以點ii=0，1，…，L來表示，定義變量如下：

于是，得到本OVD問題的調度線路為：0→8→5→7→0；0→3→1→2→0；0→6→4→0。

3結束語

本文提出了時間窗約束下非滿載OVD的算法，較好地解決了汽車運輸部（分）隊車輛調度優化問題。在算法設計過程中，對OVD問題模型結合車輛與貨物裝載屬性進行了全面地討論，具有較高的實際應用價值。

參考文獻：

[1] 呂永波，胡天軍，雷黎. 系統工程[M]. 北京：北方交通大學出版社，2003.

[2] 錢頌迪. 運籌學[M]. 北京：清華大學出版社，1999.

[3] 吳清一. 物流系統工程[M]. 北京：中國物資出版社，2004.

[4]Ngoin B.K.A， Tay M.L， Chua E.S. Applying Spatial Representation Techniques to the container Packing Problems[J]. International Journal of Production Research， 1994(32):111-123.