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

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

（中國民航大學(xué)，天津 300300）

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

0 引言

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

1 飛機(jī)加油車輛的分類及功能

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

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

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

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

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

將油庫編號為0，各個(gè)停機(jī)位編號為1，…，l。停機(jī)位及油庫均以點(diǎn)i（i=0，1，…，l）來表示。定義Ti為加油車在飛機(jī)處i的工作時(shí)間，則T0表示加油車在油庫的準(zhǔn)備時(shí)間。定義 k（k=1，2，…，K）為各個(gè)加油車的編號。

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

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

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

其中：

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

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

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

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

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

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

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

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

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

②每個(gè)螞蟻按概率移動(dòng)一步，確定待訪問點(diǎn)集allowedk。

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

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

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

⑥判斷allowedk表，若allowedk表為空則轉(zhuǎn)下一步，否則從表中獲取時(shí)間最早的點(diǎn)，并轉(zhuǎn)第③步。

表1 遠(yuǎn)機(jī)位待加油飛機(jī)信息表

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

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

⑧禁忌表清零，輸出結(jié)果。

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

設(shè)置油罐車加油車容量為 80，α=1，β=2，ρ=0.5，N=200；以加油成本為目標(biāo)函數(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車次油罐車去完成該仿真問題的加油任務(wù)。

4 結(jié)論

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

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

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

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