禁忌搜索算法在車輛調度決策中的應用

摘要：論文探討了交通線路可能被敵方毀壞情況下的車輛路徑優(yōu)化問題，建立了不確定的兩階段整數(shù)規(guī)劃數(shù)學模型，分析了路徑方案的最大和最小效用值。在線路方案評價值的計算中只計算最小值和最大值，簡化了方案的目標值計算。設計了求解模型的雙層禁忌搜索算法。最后通過應用示例驗證了模型和算法的有效性。

關鍵詞：車輛路徑問題；不確定決策；禁忌搜索算法

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

文章編號：1002-3100(2007)12-0026-04

Abstract: A vehicle routing problem in war is discussed， in which some routes may be destroyed uncertainly by competitor. A two-stage integer program model is constructed. The value of a route in a uncertain situation is analyzed. In the method， only the maximum value and the minimum value are countered into the object value， simpling the computation of the object value of the model. A two-stage tabu search algorithm is designed. In the end， an example is given.

Key words: vehicle routing problem; uncertain decision; tabu search algorithm

0引言

戰(zhàn)爭環(huán)境下，交通線路中的一些關鍵性的橋梁、隧道和線路樞紐隨時可能被敵方破壞。利用這些關鍵性的橋梁（隧道）運輸時間將會縮短，但如果這些橋梁被毀壞，運輸車可能要繞道運輸甚至原路返回，反而延誤了運輸時間。這一類問題同樣也存在于自然災害的救援活動中。在人類的發(fā)展歷史上，地震、洪水、臺風和雪崩等自然災害也是破壞交通線的重要因素。1995年日本的神戶地震、美國近期的颶風“麗塔”、我國1998年的特大洪水等都破壞了許多交通設施，同時這些自然災害還隨時威脅物資救援的運輸線路。由于這類運輸直接關系到整個軍事（救援）活動的成功與否和人員的生命安全，因此研究這一類不確定的運輸決策問題無論對于戰(zhàn)爭還是人類戰(zhàn)勝自然災害都具有重要的意義。目前關于車輛線路優(yōu)化的研究很多，但涉及戰(zhàn)爭環(huán)境下（或自然災害環(huán)境）的研究很少，正式的研究文獻幾乎沒有看到。本文探討了一個個別關鍵路段（橋梁、隧道等）可能被毀壞情況下的多車輛路徑決策問題，提出了相應的數(shù)學模型并給出了求解模型的禁忌啟發(fā)式算法。

1問題描述及復雜性分析

1.1問題的提出

2數(shù)學模型

調整上述模型的一些參數(shù)，即可建立不協(xié)作的兩階段規(guī)劃模型，這里不再詳述。

3線路方案的評價值

4禁忌搜索算法

禁忌搜索算法主要內容如下：

（1）隨機產生一個路徑序列為初始解。為n個需求點編序列號，倉庫為0。路徑解的首尾各為0，中間是n個需求點加上M-1個0的隨機排列。相鄰兩個0之間為一個車輛的服務路徑。以6個需求點，兩輛車為例，一個路徑解為0-1-2-3-0-4-5-6-0。

（2）鄰域的產生。分別采用任意兩個需求點交換位置、任意一個需求點插入到線路任意位置的方法產生新的解。

（3）車輛容量限制的處理。當一個車輛線路中的需求點的總需求量超過車輛最大載貨量時，該線路方案被淘汰。

（4）禁忌對象為兩個相鄰的需求點。禁忌表的長度隨進化代數(shù)的增加而加長。當前值優(yōu)于歷史最優(yōu)值時，禁忌解除。

（6）線路的方向。在樂觀準則下，毀壞后線路的調整變化沒有被計算到評價值中，為了彌補這一缺陷，可選出樂觀準則下的最優(yōu)方案和多個次優(yōu)方案，并計算出最壞情況下的結果，以供決策參考。即使是最優(yōu)化方案，相同的線路次序但不同的線路方向也被認為是不同的方案。如線路0-1-2-3-4-0和0-4-3-2-1-0是不同的方案。

5示例

表1是一個路網(wǎng)的距離數(shù)據(jù)。其中路段2-4經過一個難以修復的橋梁，被敵方破壞的可能性非常大。0表示倉庫，其它10個序號表示需求點，每個需求點需求為5，每輛車的最大載貨量為35，用兩輛車送貨，要求規(guī)劃不同期望值準則下的里程最短的線路。

由于車輛載貨量的限制，完成任務必須兩輛車。采用文中的禁忌搜索算法得到不同準則下的最優(yōu)方案。

6結束語

戰(zhàn)時或各種搶險救災時的物流運輸保障具有重大意義。但這類運輸線路優(yōu)化問題至今研究很少。本文把不確定決策技術和車輛路徑優(yōu)化技術結合起來，建立了不確定環(huán)境下的運輸線路優(yōu)化模型，研究結果可以為不確定環(huán)境下的物流配送決策提供參考。

參考文獻：

[1] 李軍，郭耀煌. 車輛優(yōu)化調度理論與方法[M]. 北京：中國物資出版社，2001:7-10.

[2] 甘應愛，田豐，等. 運籌學[M]. 北京：清華大學出版社，1990.

[3] 柳春光，焦雙健. 城市震后救災系統(tǒng)救災決策研究[J]. 自然災害學報，2000，9(3):21-24.

[4] 吳育華，杜綱. 管理科學基礎[M]. 天津：天津大學出版社，2001.

[5] 張鳳林，武小悅，郭波，等. 物流網(wǎng)絡可用性研究[J]. 系統(tǒng)工程理論方法應用，2002，12(1):16-19.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”