基于蟻群算法的飛機加油車輛調(diào)度問題研究

劉長有 LIU Chang-you；王一飛 WANG Yi-fei

（中國民航大學，天津 300300）

（Civil Aviation University of China，Tianjin 300300，China）

0 引言

飛機加油是機場運行的基本內(nèi)容，安全、有序、高效的完成飛機加油作業(yè)是機場運行追求的目標。對飛機加油作業(yè)影響最大的是加油車輛的管理與調(diào)度。安全有序的車輛管理加上最優(yōu)化的行駛路線調(diào)度是保證按時完成加油作業(yè)的關鍵，因此對飛機加油車輛調(diào)度的研究與仿真便成了十分重要的問題。車輛調(diào)度是一個VRP（Vehicle Routing Problem）問題，最早由Dantzig和Ramser于1959年提出，是旅行商問題（Traveling Saleman Problem,TSP）的特例，是一個NP難題。Bodin于1983年將車輛優(yōu)化調(diào)度問題分為VRP(Vehicle Routing Problem)問題和VSP(Vehicle Scheduling Problem)問題，后來兩者的混合問題帶有時間窗的車輛調(diào)度問題統(tǒng)稱為VRPTW(Vehicle Scheduling Problem with Time Windows)問題。Solomon和 Desrosiers首次對有時間窗約束的VRP問題進行求解。在國內(nèi)李軍，郭耀煌等學者對物流配送車輛優(yōu)化調(diào)度理論與方法進行了深入的研究，為本文的研究提供了一定的理論依據(jù)。國內(nèi)很多學者采用蟻群算法解決VRP問題，王海星等學者發(fā)表了“蟻群算法解決有時間窗的車輛優(yōu)化調(diào)度問題研究”，該文介紹了如何運用改進的蟻群算法去優(yōu)化帶時間窗的車輛調(diào)度問題，對本文的實例有很大的借鑒意義。

1 飛機加油車輛的分類及功能

運輸飛機加油作業(yè)都由加油車完成，加油車有兩種類型，即管線加油車和油罐車。管線加油車用于對近機位航空器提供航空用油，油罐車用于對遠機位的航空器提供航空用油。所謂進機位是指靠近航站樓的停機位，顧名思義遠機位就是遠離航站樓的停機位。進機位地底鋪有輸油管道，飛機加油時只需要管線加油車將管道中的航空用油抽出輸送到飛機油箱中，而遠機位地下沒有輸油管道，因此需要油罐車為該位置飛機提供航空用油。

管線加油車是以大流量將地井中的航空燃油安全、快速地輸入飛機油箱。在輸油的同時過濾燃油中的雜質(zhì)、灰塵和水分，并精確地計量輸油量。管線加油車還具有壓力控制裝置，可使輸油過程中壓力限制在安全范圍內(nèi)。它是飛機在進機位加油所使用的加油車輛。

油罐車又稱流動加油車，具有吸油、泵油，多種油分裝、分放等功能。運油車專用部分由罐體、取力器、傳動軸、齒輪油泵、管網(wǎng)系統(tǒng)等部件組成。管網(wǎng)系統(tǒng)由油泵、三通四位球閥、雙向球閥、濾網(wǎng)、管道組成。它是飛機在遠機位加油所使用的車輛。本文將建立油罐車的調(diào)度模型并對其進行仿真計算。

2 油罐加油車輛調(diào)度數(shù)學模型

2.1 油罐加油車輛調(diào)度模型變量的定義 加油車輛行駛的基本過程可理解為每輛加油車從油庫出發(fā)沿著一條行車路線對等待加油的飛機提供加油服務后返回油庫。每輛加油車可以對多架飛機提供加油服務但每架飛機只能由一輛加油車為其加油。對于油罐車，其載油能力有限，所以為飛機提供的油量不能超過這個限制，設定所有油罐車的容量為Q。對于其他各個變量定義如下：

將油庫編號為0，各個停機位編號為1，…，l。停機位及油庫均以點i（i=0，1，…，l）來表示。定義Ti為加油車在飛機處i的工作時間，則T0表示加油車在油庫的準備時間。定義 k（k=1，2，…，K）為各個加油車的編號。

定義cij為加油車輛由點i行駛到點j的成本。dij為加油車輛由點i行駛到點j的距離。tij為加油車輛由點i行駛到點j所需的時間。qi為點i飛機所需求的油量。Ti為加油車輛在點i完成加油任務所需要的時間。Si為加油車輛到達點i的時間，因此Si+1=Si+Ti+ti，i+1。飛機加油車輛的調(diào)度是一個帶有時間窗的模型，即加油任務的開始時間需要在一定的時間范圍內(nèi)，設這個時間范圍為[ETi，LTi]。其中ETi為加油任務i的允許最早開始時間，LTi為加油任務i的允許最晚開始時間。如果加油車輛在ET之前到達i，則會產(chǎn)生等待成本，如果加油車輛在LTi之后到達i，則會產(chǎn)生延誤會造成損失。設定一個罰函數(shù)Pi（Si），其具體定義為：

其中m，n為懲罰系數(shù)。定義hi為判斷該點飛機是否產(chǎn)生延誤，當改點飛機發(fā)生延誤時其值為1，當該點飛機沒有延誤則其值為0。

2.2 油罐加油車輛調(diào)度最優(yōu)化數(shù)學模型 根據(jù)一般的車輛調(diào)度模型首先建立基本目標函數(shù)：

其中：

考慮油罐加油車輛調(diào)度是帶有時間窗的模型，只有在時間窗內(nèi)進行加油作業(yè)時才不會產(chǎn)生懲罰，否則會造成成本損失，故建立時間窗目標函數(shù)：

由以上分析得出最終目標函數(shù)：

約束條件設定：定義一個參數(shù)y，用以判斷該點的飛機是由哪輛油罐加油車提供航空用油。

油罐車的容量Q為固定值，因此根據(jù)一般車輛調(diào)度約束條件定義飛機油罐加油車輛調(diào)度的模型約束為：

3 油罐加油車輛優(yōu)化調(diào)度的蟻群算法

3.1 蟻群算法構造 車輛調(diào)度模型的解決方法可以分為兩類，一類是優(yōu)化算法，一類是啟發(fā)式算法。而啟發(fā)式算法中的群體智能仿生算法在解決這類問題時有其獨到之處。本文將用蟻群算法解決該車輛調(diào)度問題，并用matlab進行仿真計算。蟻群算法是通過對螞蟻群在巢穴與食物間的路徑選擇的模擬，來解決現(xiàn)實的NP難題。其重要的參數(shù)為（第k只螞蟻的狀態(tài)轉移概率）；τij（信息素濃度）；ηij（啟發(fā)因子）；ρ（信息素揮發(fā)系數(shù)）；α，β（重要度因子）。根據(jù)本文的模型對其進行如下定義：

其中：dij為停機位i點到j點之間的距離；μij稱為節(jié)約值，其表示兩點直接相連比兩點分別與加油中心相連距離的節(jié)約量；δij是反應滿足時間窗程度的變量，w1+w2=1；信息素更新策略則按公式（15），（16）進行。

3.2 具體實現(xiàn)步驟

①信息初始化，將螞蟻置于加油中心位置，即禁忌表tabuk第一列位于初始位置。

②每個螞蟻按概率移動一步，確定待訪問點集allowedk。

③按公式計算狀態(tài)轉移概率p，按狀態(tài)轉移概率確定轉移節(jié)點j，并將j添加到tabuk末尾。

④判斷線路上加油量是否小于車輛負載Q，是則接下一步，否則跳轉第⑥步。

⑤判斷時間窗是否滿足要求，是則將點j加入到tabuk中，并計算路徑長度及其成本，統(tǒng)計車輛數(shù)并跳轉第②步。否則跳轉第⑥步驟。

⑥判斷allowedk表，若allowedk表為空則轉下一步，否則從表中獲取時間最早的點，并轉第③步。

表1 遠機位待加油飛機信息表

圖1 油罐加油車優(yōu)化路徑圖

⑦更新全局信息素，更新最好最差螞蟻。

⑧禁忌表清零，輸出結果。

3.3 算例分析 以某機場油罐加油車優(yōu)化調(diào)度為例，設置加油中心為原點坐標，x表示停機位的橫坐標，y表示停機位的縱坐標ETi，LTi分別表示飛機加油作業(yè)時間窗的上限和下限，q表示該飛機需要的油量，Ti表示該飛機加油所需要的時間，具體數(shù)據(jù)見表1。

設置油罐車加油車容量為 80，α=1，β=2，ρ=0.5，N=200；以加油成本為目標函數(shù)，用matlab編程工具使用蟻群算法最終得到油罐車最優(yōu)路徑圖如圖1所示，其優(yōu)化路徑為 0-1-2-3-4-0，0-5-6-7-8-9-0，0-10-11-12-13-0，0-14-15-16-17-19-0,0-18-22-23-0,0-20-21-24-25-0，共需要5車次油罐車去完成該仿真問題的加油任務。

4 結論

飛機加油作業(yè)是停機坪地面保障作業(yè)的重要環(huán)節(jié)，文中所引用的車輛調(diào)度的模型概括的模擬了飛機加油車輛的優(yōu)化調(diào)度，并用蟻群優(yōu)化算法對該模型進行仿真計算，得到了比較理想的結果，這對實際中飛機加油作業(yè)的操作具有一定的借鑒意義。

[1]郭耀煌，李軍.車輛調(diào)度問題的研究現(xiàn)狀評述[J].西南交通大學學報，1995，30（4）：376-382.

[2]王海星，王德占，申金升.蟻群算法解決有時間窗的車輛優(yōu)化調(diào)度問題研究[J].物流技術，2006,11：37-40.

[3]段海濱等.蟻群算法原理及其應用[M].科學出版社，2005（12）.